src/squirrel/squirrel/sqtable.cpp

   1 /*
   2 see copyright notice in squirrel.h
   3 */
   4 #include "sqpcheader.h"
   5 #include "sqvm.h"
   6 #include "sqtable.h"
   7 #include "sqfuncproto.h"
   8 #include "sqclosure.h"
   9
  10 SQTable::SQTable(SQSharedState *ss,SQInteger nInitialSize)
  11 {
  12         SQInteger pow2size=MINPOWER2;
  13         while(nInitialSize>pow2size)pow2size=pow2size<<1;
  14         AllocNodes(pow2size);
  15         _usednodes = 0;
  16         _delegate = NULL;
  17         INIT_CHAIN();
  18         ADD_TO_CHAIN(&_sharedstate->_gc_chain,this);
  19 }
  20
  21 void SQTable::Remove(const SQObjectPtr &key)
  22 {
  23
  24         _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
  25         if (n) {
  26                 n->val = n->key = _null_;
  27                 _usednodes--;
  28                 Rehash(false);
  29         }
  30 }
  31
  32 void SQTable::AllocNodes(SQInteger nSize)
  33 {
  34         _HashNode *nodes=(_HashNode *)SQ_MALLOC(sizeof(_HashNode)*nSize);
  35         for(SQInteger i=0;i<nSize;i++){
  36                 new (&nodes[i]) _HashNode;
  37                 nodes[i].next=NULL;
  38         }
  39         _numofnodes=nSize;
  40         _nodes=nodes;
  41         _firstfree=&_nodes[_numofnodes-1];
  42 }
  43
  44 void SQTable::Rehash(bool force)
  45 {
  46         SQInteger oldsize=_numofnodes;
  47         //prevent problems with the integer division
  48         if(oldsize<4)oldsize=4;
  49         _HashNode *nold=_nodes;
  50         SQInteger nelems=CountUsed();
  51         if (nelems >= oldsize-oldsize/4)  /* using more than 3/4? */
  52                 AllocNodes(oldsize*2);
  53         else if (nelems <= oldsize/4 &&  /* less than 1/4? */
  54                 oldsize > MINPOWER2)
  55                 AllocNodes(oldsize/2);
  56         else if(force)
  57                 AllocNodes(oldsize);
  58         else
  59                 return;
  60         _usednodes = 0;
  61         for (SQInteger i=0; i<oldsize; i++) {
  62                 _HashNode *old = nold+i;
  63                 if (type(old->key) != OT_NULL)
  64                         NewSlot(old->key,old->val);
  65         }
  66         for(SQInteger k=0;k<oldsize;k++)
  67                 nold[k].~_HashNode();
  68         SQ_FREE(nold,oldsize*sizeof(_HashNode));
  69 }
  70
  71 SQTable *SQTable::Clone()
  72 {
  73         SQTable *nt=Create(_opt_ss(this),_numofnodes);
  74         SQInteger ridx=0;
  75         SQObjectPtr key,val;
  76         while((ridx=Next(true,ridx,key,val))!=-1){
  77                 nt->NewSlot(key,val);
  78         }
  79         nt->SetDelegate(_delegate);
  80         return nt;
  81 }
  82
  83 bool SQTable::Get(const SQObjectPtr &key,SQObjectPtr &val)
  84 {
  85         if(type(key) == OT_NULL)
  86                 return false;
  87         _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
  88         if (n) {
  89                 val = _realval(n->val);
  90                 return true;
  91         }
  92         return false;
  93 }
  94 bool SQTable::NewSlot(const SQObjectPtr &key,const SQObjectPtr &val)
  95 {
  96         assert(type(key) != OT_NULL);
  97         SQHash h = HashObj(key) & (_numofnodes - 1);
  98         _HashNode *n = _Get(key, h);
  99         if (n) {
 100                 n->val = val;
 101                 return false;
 102         }
 103         _HashNode *mp = &_nodes[h];
 104         n = mp;
 105
 106
 107         //key not found I'll insert it
 108         //main pos is not free
 109
 110         if(type(mp->key) != OT_NULL) {
 111                 n = _firstfree;  /* get a free place */
 112                 SQHash mph = HashObj(mp->key) & (_numofnodes - 1);
 113                 _HashNode *othern;  /* main position of colliding node */
 114
 115                 if (mp > n && (othern = &_nodes[mph]) != mp){
 116                         /* yes; move colliding node into free position */
 117                         while (othern->next != mp){
 118                                 assert(othern->next != NULL);
 119                                 othern = othern->next;  /* find previous */
 120                         }
 121                         othern->next = n;  /* redo the chain with `n' in place of `mp' */
 122                         n->key = mp->key;
 123                         n->val = mp->val;/* copy colliding node into free pos. (mp->next also goes) */
 124                         n->next = mp->next;
 125                         mp->key = _null_;
 126                         mp->val = _null_;
 127                         mp->next = NULL;  /* now `mp' is free */
 128                 }
 129                 else{
 130                         /* new node will go into free position */
 131                         n->next = mp->next;  /* chain new position */
 132                         mp->next = n;
 133                         mp = n;
 134                 }
 135         }
 136         mp->key = key;
 137
 138         for (;;) {  /* correct `firstfree' */
 139                 if (type(_firstfree->key) == OT_NULL && _firstfree->next == NULL) {
 140                         mp->val = val;
 141                         _usednodes++;
 142                         return true;  /* OK; table still has a free place */
 143                 }
 144                 else if (_firstfree == _nodes) break;  /* cannot decrement from here */
 145                 else (_firstfree)--;
 146         }
 147         Rehash(true);
 148         return NewSlot(key, val);
 149 }
 150
 151 SQInteger SQTable::Next(bool getweakrefs,const SQObjectPtr &refpos, SQObjectPtr &outkey, SQObjectPtr &outval)
 152 {
 153         SQInteger idx = (SQInteger)TranslateIndex(refpos);
 154         while (idx < _numofnodes) {
 155                 if(type(_nodes[idx].key) != OT_NULL) {
 156                         //first found
 157                         _HashNode &n = _nodes[idx];
 158                         outkey = n.key;
 159                         outval = getweakrefs?(SQObject)n.val:_realval(n.val);
 160                         //return idx for the next iteration
 161                         return ++idx;
 162                 }
 163                 ++idx;
 164         }
 165         //nothing to iterate anymore
 166         return -1;
 167 }
 168
 169
 170 bool SQTable::Set(const SQObjectPtr &key, const SQObjectPtr &val)
 171 {
 172         _HashNode *n = _Get(key, HashObj(key) & (_numofnodes - 1));
 173         if (n) {
 174                 n->val = val;
 175                 return true;
 176         }
 177         return false;
 178 }
 179
 180 void SQTable::_ClearNodes()
 181 {
 182         for(SQInteger i = 0;i < _numofnodes; i++) { _nodes[i].key = _null_; _nodes[i].val = _null_; }
 183 }
 184
 185 void SQTable::Finalize()
 186 {
 187         _ClearNodes();
 188         SetDelegate(NULL);
 189 }
 190
 191 void SQTable::Clear()
 192 {
 193         _ClearNodes();
 194         _usednodes = 0;
 195         Rehash(true);
 196 }