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