source/libps/pstable.cpp

0001 /*

0002 see copyright notice in pscript.h

0003 */
0004 #include "pspcheader.h"
0005 #include "psvm.h"
0006 #include "pstable.h"
0007 #include "psfuncproto.h"
0008 #include "psclosure.h"
0009
0010 PSTable::PSTable(PSSharedState *ss,PSInteger nInitialSize)
0011 {
0012     PSInteger pow2size=MINPOWER2;
0013     while(nInitialSize>pow2size)pow2size=pow2size<<1;
0014     AllocNodes(pow2size);
0015     _usednodes = 0;
0016     _delegate = NULL;
0017     INIT_CHAIN();
0018     ADD_TO_CHAIN(&_sharedstate->_gc_chain,this);
0019 }
0020
0021 void PSTable::Remove(const PSObjectPtr &key)
0022 {
0023
0024     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
0025     if (n) {
0026         n->val.Null();
0027         n->key.Null();
0028         _usednodes--;
0029         Rehash(false);
0030     }
0031 }
0032
0033 void PSTable::AllocNodes(PSInteger nSize)
0034 {
0035     _HashNode *nodes=(_HashNode *)PS_MALLOC(sizeof(_HashNode)*nSize);
0036     for(PSInteger i=0;i<nSize;i++){
0037         _HashNode &n = nodes[i];
0038         new (&n) _HashNode;
0039         n.next=NULL;
0040     }
0041     _numofnodes=nSize;
0042     _nodes=nodes;
0043     _firstfree=&_nodes[_numofnodes-1];
0044 }
0045
0046 void PSTable::Rehash(bool force)
0047 {
0048     PSInteger oldsize=_numofnodes;
0049     //prevent problems with the integer division

0050     if(oldsize<4)oldsize=4;
0051     _HashNode *nold=_nodes;
0052     PSInteger nelems=CountUsed();
0053     if (nelems >= oldsize-oldsize/4)  /* using more than 3/4? */
0054         AllocNodes(oldsize*2);
0055     else if (nelems <= oldsize/4 &&  /* less than 1/4? */
0056         oldsize > MINPOWER2)
0057         AllocNodes(oldsize/2);
0058     else if(force)
0059         AllocNodes(oldsize);
0060     else
0061         return;
0062     _usednodes = 0;
0063     for (PSInteger i=0; i<oldsize; i++) {
0064         _HashNode *old = nold+i;
0065         if (type(old->key) != OT_NULL)
0066             NewSlot(old->key,old->val);
0067     }
0068     for(PSInteger k=0;k<oldsize;k++)
0069         nold[k].~_HashNode();
0070     PS_FREE(nold,oldsize*sizeof(_HashNode));
0071 }
0072
0073 PSTable *PSTable::Clone()
0074 {
0075     PSTable *nt=Create(_opt_ss(this),_numofnodes);
0076 #ifdef _FAST_CLONE
0077     _HashNode *basesrc = _nodes;
0078     _HashNode *basedst = nt->_nodes;
0079     _HashNode *src = _nodes;
0080     _HashNode *dst = nt->_nodes;
0081     PSInteger n = 0;
0082     for(n = 0; n < _numofnodes; n++) {
0083         dst->key = src->key;
0084         dst->val = src->val;
0085         if(src->next) {
0086             assert(src->next > basesrc);
0087             dst->next = basedst + (src->next - basesrc);
0088             assert(dst != dst->next);
0089         }
0090         dst++;
0091         src++;
0092     }
0093     assert(_firstfree > basesrc);
0094     assert(_firstfree != NULL);
0095     nt->_firstfree = basedst + (_firstfree - basesrc);
0096     nt->_usednodes = _usednodes;
0097 #else
0098     PSInteger ridx=0;
0099     PSObjectPtr key,val;
0100     while((ridx=Next(true,ridx,key,val))!=-1){
0101         nt->NewSlot(key,val);
0102     }
0103 #endif
0104     nt->SetDelegate(_delegate);
0105     return nt;
0106 }
0107
0108 bool PSTable::Get(const PSObjectPtr &key,PSObjectPtr &val)
0109 {
0110     if(type(key) == OT_NULL)
0111         return false;
0112     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
0113     if (n) {
0114         val = _realval(n->val);
0115         return true;
0116     }
0117     return false;
0118 }
0119 bool PSTable::NewSlot(const PSObjectPtr &key,const PSObjectPtr &val)
0120 {
0121     assert(type(key) != OT_NULL);
0122     PSHash h = HashObj(key) & (_numofnodes - 1);
0123     _HashNode *n = _Get(key, h);
0124     if (n) {
0125         n->val = val;
0126         return false;
0127     }
0128     _HashNode *mp = &_nodes[h];
0129     n = mp;
0130
0131
0132     //key not found I'll insert it

0133     //main pos is not free

0134
0135     if(type(mp->key) != OT_NULL) {
0136         n = _firstfree;  /* get a free place */
0137         PSHash mph = HashObj(mp->key) & (_numofnodes - 1);
0138         _HashNode *othern;  /* main position of colliding node */
0139
0140         if (mp > n && (othern = &_nodes[mph]) != mp){
0141             /* yes; move colliding node into free position */
0142             while (othern->next != mp){
0143                 assert(othern->next != NULL);
0144                 othern = othern->next;  /* find previous */
0145             }
0146             othern->next = n;  /* redo the chain with `n' in place of `mp' */
0147             n->key = mp->key;
0148             n->val = mp->val;/* copy colliding node into free pos. (mp->next also goes) */
0149             n->next = mp->next;
0150             mp->key.Null();
0151             mp->val.Null();
0152             mp->next = NULL;  /* now `mp' is free */
0153         }
0154         else{
0155             /* new node will go into free position */
0156             n->next = mp->next;  /* chain new position */
0157             mp->next = n;
0158             mp = n;
0159         }
0160     }
0161     mp->key = key;
0162
0163     for (;;) {  /* correct `firstfree' */
0164         if (type(_firstfree->key) == OT_NULL && _firstfree->next == NULL) {
0165             mp->val = val;
0166             _usednodes++;
0167             return true;  /* OK; table still has a free place */
0168         }
0169         else if (_firstfree == _nodes) break;  /* cannot decrement from here */
0170         else (_firstfree)--;
0171     }
0172     Rehash(true);
0173     return NewSlot(key, val);
0174 }
0175
0176 PSInteger PSTable::Next(bool getweakrefs,const PSObjectPtr &refpos, PSObjectPtr &outkey, PSObjectPtr &outval)
0177 {
0178     PSInteger idx = (PSInteger)TranslateIndex(refpos);
0179     while (idx < _numofnodes) {
0180         if(type(_nodes[idx].key) != OT_NULL) {
0181             //first found

0182             _HashNode &n = _nodes[idx];
0183             outkey = n.key;
0184             outval = getweakrefs?(PSObject)n.val:_realval(n.val);
0185             //return idx for the next iteration

0186             return ++idx;
0187         }
0188         ++idx;
0189     }
0190     //nothing to iterate anymore

0191     return -1;
0192 }
0193
0194
0195 bool PSTable::Set(const PSObjectPtr &key, const PSObjectPtr &val)
0196 {
0197     _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
0198     if (n) {
0199         n->val = val;
0200         return true;
0201     }
0202     return false;
0203 }
0204
0205 void PSTable::_ClearNodes()
0206 {
0207     for(PSInteger i = 0;i < _numofnodes; i++) { _HashNode &n = _nodes[i]; n.key.Null(); n.val.Null(); }
0208 }
0209
0210 void PSTable::Finalize()
0211 {
0212     _ClearNodes();
0213     SetDelegate(NULL);
0214 }
0215
0216 void PSTable::Clear()
0217 {
0218     _ClearNodes();
0219     _usednodes = 0;
0220     Rehash(true);
0221 }