sqtable.cpp

00001 /*
00002 see copyright notice in squirrel.h
00003 */
00004 #include "sqpcheader.h"
00005 #include "sqvm.h"
00006 #include "sqtable.h"
00007 #include "sqfuncproto.h"
00008 #include "sqclosure.h"
00009 
00010 SQTable::SQTable(SQSharedState *ss,SQInteger nInitialSize)
00011 {
00012     SQInteger pow2size=MINPOWER2;
00013     while(nInitialSize>pow2size)pow2size=pow2size<<1;
00014     AllocNodes(pow2size);
00015     _usednodes = 0;
00016     _delegate = NULL;
00017     INIT_CHAIN();
00018     ADD_TO_CHAIN(&_sharedstate->_gc_chain,this);
00019 }
00020 
00021 void SQTable::Remove(const SQObjectPtr &key)
00022 {
00023     
00024     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
00025     if (n) {
00026         n->val.Null();
00027         n->key.Null();
00028         _usednodes--;
00029         Rehash(false);
00030     }
00031 }
00032 
00033 void SQTable::AllocNodes(SQInteger nSize)
00034 {
00035     _HashNode *nodes=(_HashNode *)SQ_MALLOC(sizeof(_HashNode)*nSize);
00036     for(SQInteger i=0;i<nSize;i++){
00037         _HashNode &n = nodes[i];
00038         new (&n) _HashNode;
00039         n.next=NULL;
00040     }
00041     _numofnodes=nSize;
00042     _nodes=nodes;
00043     _firstfree=&_nodes[_numofnodes-1];
00044 }
00045 
00046 void SQTable::Rehash(bool force)
00047 {
00048     SQInteger oldsize=_numofnodes;
00049     //prevent problems with the integer division
00050     if(oldsize<4)oldsize=4;
00051     _HashNode *nold=_nodes;
00052     SQInteger nelems=CountUsed();
00053     if (nelems >= oldsize-oldsize/4)  /* using more than 3/4? */
00054         AllocNodes(oldsize*2);
00055     else if (nelems <= oldsize/4 &&  /* less than 1/4? */
00056         oldsize > MINPOWER2)
00057         AllocNodes(oldsize/2);
00058     else if(force)
00059         AllocNodes(oldsize);
00060     else
00061         return;
00062     _usednodes = 0;
00063     for (SQInteger i=0; i<oldsize; i++) {
00064         _HashNode *old = nold+i;
00065         if (type(old->key) != OT_NULL)
00066             NewSlot(old->key,old->val);
00067     }
00068     for(SQInteger k=0;k<oldsize;k++) 
00069         nold[k].~_HashNode();
00070     SQ_FREE(nold,oldsize*sizeof(_HashNode));
00071 }
00072 
00073 SQTable *SQTable::Clone()
00074 {
00075     SQTable *nt=Create(_opt_ss(this),_numofnodes);
00076 #ifdef _FAST_CLONE
00077     _HashNode *basesrc = _nodes;
00078     _HashNode *basedst = nt->_nodes;
00079     _HashNode *src = _nodes;
00080     _HashNode *dst = nt->_nodes;
00081     SQInteger n = 0;
00082     for(n = 0; n < _numofnodes; n++) {
00083         dst->key = src->key;
00084         dst->val = src->val;
00085         if(src->next) {
00086             assert(src->next > basesrc);
00087             dst->next = basedst + (src->next - basesrc);
00088             assert(dst != dst->next);
00089         }
00090         dst++;
00091         src++;
00092     }
00093     assert(_firstfree > basesrc);
00094     assert(_firstfree != NULL);
00095     nt->_firstfree = basedst + (_firstfree - basesrc);
00096     nt->_usednodes = _usednodes;
00097 #else
00098     SQInteger ridx=0;
00099     SQObjectPtr key,val;
00100     while((ridx=Next(true,ridx,key,val))!=-1){
00101         nt->NewSlot(key,val);
00102     }
00103 #endif
00104     nt->SetDelegate(_delegate);
00105     return nt;
00106 }
00107 
00108 bool SQTable::Get(const SQObjectPtr &key,SQObjectPtr &val)
00109 {
00110     if(type(key) == OT_NULL)
00111         return false;
00112     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
00113     if (n) {
00114         val = _realval(n->val);
00115         return true;
00116     }
00117     return false;
00118 }
00119 bool SQTable::NewSlot(const SQObjectPtr &key,const SQObjectPtr &val)
00120 {
00121     assert(type(key) != OT_NULL);
00122     SQHash h = HashObj(key) & (_numofnodes - 1);
00123     _HashNode *n = _Get(key, h);
00124     if (n) {
00125         n->val = val;
00126         return false;
00127     }
00128     _HashNode *mp = &_nodes[h];
00129     n = mp;
00130 
00131 
00132     //key not found I'll insert it
00133     //main pos is not free
00134 
00135     if(type(mp->key) != OT_NULL) {
00136         n = _firstfree;  /* get a free place */
00137         SQHash mph = HashObj(mp->key) & (_numofnodes - 1);
00138         _HashNode *othern;  /* main position of colliding node */
00139         
00140         if (mp > n && (othern = &_nodes[mph]) != mp){
00141             /* yes; move colliding node into free position */
00142             while (othern->next != mp){
00143                 assert(othern->next != NULL);
00144                 othern = othern->next;  /* find previous */
00145             }
00146             othern->next = n;  /* redo the chain with `n' in place of `mp' */
00147             n->key = mp->key;
00148             n->val = mp->val;/* copy colliding node into free pos. (mp->next also goes) */
00149             n->next = mp->next;
00150             mp->key.Null();
00151             mp->val.Null();
00152             mp->next = NULL;  /* now `mp' is free */
00153         }
00154         else{
00155             /* new node will go into free position */
00156             n->next = mp->next;  /* chain new position */
00157             mp->next = n;
00158             mp = n;
00159         }
00160     }
00161     mp->key = key;
00162 
00163     for (;;) {  /* correct `firstfree' */
00164         if (type(_firstfree->key) == OT_NULL && _firstfree->next == NULL) {
00165             mp->val = val;
00166             _usednodes++;
00167             return true;  /* OK; table still has a free place */
00168         }
00169         else if (_firstfree == _nodes) break;  /* cannot decrement from here */
00170         else (_firstfree)--;
00171     }
00172     Rehash(true);
00173     return NewSlot(key, val);
00174 }
00175 
00176 SQInteger SQTable::Next(bool getweakrefs,const SQObjectPtr &refpos, SQObjectPtr &outkey, SQObjectPtr &outval)
00177 {
00178     SQInteger idx = (SQInteger)TranslateIndex(refpos);
00179     while (idx < _numofnodes) {
00180         if(type(_nodes[idx].key) != OT_NULL) {
00181             //first found
00182             _HashNode &n = _nodes[idx];
00183             outkey = n.key;
00184             outval = getweakrefs?(SQObject)n.val:_realval(n.val);
00185             //return idx for the next iteration
00186             return ++idx;
00187         }
00188         ++idx;
00189     }
00190     //nothing to iterate anymore
00191     return -1;
00192 }
00193 
00194 
00195 bool SQTable::Set(const SQObjectPtr &key, const SQObjectPtr &val)
00196 {
00197     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
00198     if (n) {
00199         n->val = val;
00200         return true;
00201     }
00202     return false;
00203 }
00204 
00205 void SQTable::_ClearNodes()
00206 {
00207     for(SQInteger i = 0;i < _numofnodes; i++) { _HashNode &n = _nodes[i]; n.key.Null(); n.val.Null(); }
00208 }
00209 
00210 void SQTable::Finalize()
00211 {
00212     _ClearNodes();
00213     SetDelegate(NULL);
00214 }
00215 
00216 void SQTable::Clear()
00217 {
00218     _ClearNodes();
00219     _usednodes = 0;
00220     Rehash(true);
00221 }