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