Johan Wikman / SQUIRREL3

The Squirrel interpreter. See http://www.squirrel-lang.org/

Dependents:   Squirrel

squirrel/sqtable.cpp@0:97a4f8cc534c, 2014-12-16 (annotated)

Committer:
jhnwkmn
Date:
Tue Dec 16 10:20:34 2014 +0000
Revision:
0:97a4f8cc534c
Initial import of Squirrel.

Who changed what in which revision?

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