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