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