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