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