123
124 //------------------------------Clear----------------------------------------
125 // Zap to empty; ready for re-use
126 void Dict::Clear() {
127 _cnt = 0; // Empty contents
128 for( uint i=0; i<_size; i++ )
129 _bin[i]._cnt = 0; // Empty buckets, but leave allocated
130 // Leave _size & _bin alone, under the assumption that dictionary will
131 // grow to this size again.
132 }
133
134 //------------------------------doubhash---------------------------------------
135 // Double hash table size. If can't do so, just suffer. If can, then run
136 // thru old hash table, moving things to new table. Note that since hash
137 // table doubled, exactly 1 new bit is exposed in the mask - so everything
138 // in the old table ends up on 1 of two lists in the new table; a hi and a
139 // lo list depending on the value of the bit.
140 void Dict::doubhash(void) {
141 uint oldsize = _size;
142 _size <<= 1; // Double in size
143 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*oldsize, sizeof(bucket)*_size );
144 memset( &_bin[oldsize], 0, oldsize*sizeof(bucket) );
145 // Rehash things to spread into new table
146 for( uint i=0; i < oldsize; i++) { // For complete OLD table do
147 bucket *b = &_bin[i]; // Handy shortcut for _bin[i]
148 if( !b->_keyvals ) continue; // Skip empties fast
149
150 bucket *nb = &_bin[i+oldsize]; // New bucket shortcut
151 uint j = b->_max; // Trim new bucket to nearest power of 2
152 while( j > b->_cnt ) j >>= 1; // above old bucket _cnt
153 if( !j ) j = 1; // Handle zero-sized buckets
154 nb->_max = j<<1;
155 // Allocate worst case space for key-value pairs
156 nb->_keyvals = (void**)_arena->Amalloc_4( sizeof(void *)*nb->_max*2 );
157 uint nbcnt = 0;
158
159 for( j=0; j<b->_cnt; j++ ) { // Rehash all keys in this bucket
160 void *key = b->_keyvals[j+j];
161 if( (_hash( key ) & (_size-1)) != i ) { // Moving to hi bucket?
162 nb->_keyvals[nbcnt+nbcnt] = key;
163 nb->_keyvals[nbcnt+nbcnt+1] = b->_keyvals[j+j+1];
164 nb->_cnt = nbcnt = nbcnt+1;
165 b->_cnt--; // Remove key/value from lo bucket
166 b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ];
167 b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1];
168 j--; // Hash compacted element also
169 }
170 } // End of for all key-value pairs in bucket
171 } // End of for all buckets
172
173
174 }
175
176 //------------------------------Dict-----------------------------------------
177 // Deep copy a dictionary.
178 Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) {
179 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size);
180 memcpy( _bin, d._bin, sizeof(bucket)*_size );
181 for( uint i=0; i<_size; i++ ) {
182 if( !_bin[i]._keyvals ) continue;
183 _bin[i]._keyvals=(void**)_arena->Amalloc_4( sizeof(void *)*_bin[i]._max*2);
184 memcpy( _bin[i]._keyvals, d._bin[i]._keyvals,_bin[i]._cnt*2*sizeof(void*));
185 }
186 }
187
188 //------------------------------Dict-----------------------------------------
189 // Deep copy a dictionary.
190 Dict &Dict::operator =( const Dict &d ) {
191 if( _size < d._size ) { // If must have more buckets
192 _arena = d._arena;
193 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*_size, sizeof(bucket)*d._size );
|
123
124 //------------------------------Clear----------------------------------------
125 // Zap to empty; ready for re-use
126 void Dict::Clear() {
127 _cnt = 0; // Empty contents
128 for( uint i=0; i<_size; i++ )
129 _bin[i]._cnt = 0; // Empty buckets, but leave allocated
130 // Leave _size & _bin alone, under the assumption that dictionary will
131 // grow to this size again.
132 }
133
134 //------------------------------doubhash---------------------------------------
135 // Double hash table size. If can't do so, just suffer. If can, then run
136 // thru old hash table, moving things to new table. Note that since hash
137 // table doubled, exactly 1 new bit is exposed in the mask - so everything
138 // in the old table ends up on 1 of two lists in the new table; a hi and a
139 // lo list depending on the value of the bit.
140 void Dict::doubhash(void) {
141 uint oldsize = _size;
142 _size <<= 1; // Double in size
143 _bin = (bucket*)_arena->Arealloc(_bin, sizeof(bucket) * oldsize, sizeof(bucket) * _size);
144 memset(&_bin[oldsize], 0, oldsize * sizeof(bucket));
145 // Rehash things to spread into new table
146 for (uint i = 0; i < oldsize; i++) { // For complete OLD table do
147 bucket *b = &_bin[i]; // Handy shortcut for _bin[i]
148 if (!b->_keyvals) continue; // Skip empties fast
149
150 bucket *nb = &_bin[i+oldsize]; // New bucket shortcut
151 uint j = b->_max; // Trim new bucket to nearest power of 2
152 while (j > b->_cnt) { j >>= 1; } // above old bucket _cnt
153 if (!j) { j = 1; } // Handle zero-sized buckets
154 nb->_max = j << 1;
155 // Allocate worst case space for key-value pairs
156 nb->_keyvals = (void**)_arena->Amalloc_4(sizeof(void *) * nb->_max * 2);
157 uint nbcnt = 0;
158
159 for (j = 0; j < b->_cnt; ) { // Rehash all keys in this bucket
160 void *key = b->_keyvals[j + j];
161 if ((_hash(key) & (_size-1)) != i) { // Moving to hi bucket?
162 nb->_keyvals[nbcnt + nbcnt] = key;
163 nb->_keyvals[nbcnt + nbcnt + 1] = b->_keyvals[j + j + 1];
164 nb->_cnt = nbcnt = nbcnt + 1;
165 b->_cnt--; // Remove key/value from lo bucket
166 b->_keyvals[j + j] = b->_keyvals[b->_cnt + b->_cnt];
167 b->_keyvals[j + j + 1] = b->_keyvals[b->_cnt + b->_cnt + 1];
168 // Don't increment j, hash compacted element also.
169 } else {
170 j++; // Iterate.
171 }
172 } // End of for all key-value pairs in bucket
173 } // End of for all buckets
174 }
175
176 //------------------------------Dict-----------------------------------------
177 // Deep copy a dictionary.
178 Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) {
179 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size);
180 memcpy( _bin, d._bin, sizeof(bucket)*_size );
181 for( uint i=0; i<_size; i++ ) {
182 if( !_bin[i]._keyvals ) continue;
183 _bin[i]._keyvals=(void**)_arena->Amalloc_4( sizeof(void *)*_bin[i]._max*2);
184 memcpy( _bin[i]._keyvals, d._bin[i]._keyvals,_bin[i]._cnt*2*sizeof(void*));
185 }
186 }
187
188 //------------------------------Dict-----------------------------------------
189 // Deep copy a dictionary.
190 Dict &Dict::operator =( const Dict &d ) {
191 if( _size < d._size ) { // If must have more buckets
192 _arena = d._arena;
193 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*_size, sizeof(bucket)*d._size );
|