src/squirrel/squirrel/sqtable.cpp

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