← Back to branch summary

~ubuntu-branches/debian/squeeze/openttd/squeeze

« back to all changes in this revision

Viewing changes to src/3rdparty/squirrel/squirrel/sqtable.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jordi Mallach, Matthijs Kooijman, Jordi Mallach
  • Date: 2009-04-15 18:22:10 UTC
  • mfrom: (1.1.6 upstream) (2.1.3 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090415182210-22ktb8kdbp2tf3bm
[ Matthijs Kooijman ]
* New upstream release.
* Remove Debian specific desktop file, upstream provides one now. 
* Add debian/watch file.

[ Jordi Mallach ]
* Bump Standards-Version to 3.8.1, with no changes required.
* Move to debhelper compat 7. Bump Build-Depends accordingly.
* Use dh_prep.
* Add "set -e" to config script.
* Remove a few extra doc files that get installed by upstream Makefile.
* Add more complete copyright information.

Show diffs side-by-side

added added

removed removed

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