aboutsummaryrefslogtreecommitdiff
path: root/src/hash.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-07-03 00:28:59 +0000
committerMike Buland <eichlan@xagasoft.com>2007-07-03 00:28:59 +0000
commitac517a2b7625e0aa0862679e961c6349f859ea3b (patch)
treee3e27a6b9bd5e2be6150088495c91fc91786ad9d /src/hash.h
parentf8d4301e9fa4f3709258505941e37fab2eadadc6 (diff)
parentbd865cee5f89116c1f054cd0e5c275e97c2d0a9b (diff)
downloadlibbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.gz
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.bz2
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.tar.xz
libbu++-ac517a2b7625e0aa0862679e961c6349f859ea3b.zip
The reorg is being put in trunk, I think it's ready. Now we just get to find
out how many applications won't work anymore :)
Diffstat (limited to 'src/hash.h')
-rw-r--r--src/hash.h1488
1 files changed, 907 insertions, 581 deletions
diff --git a/src/hash.h b/src/hash.h
index a21d651..f183823 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -1,745 +1,1071 @@
1#ifndef HASH_H 1#ifndef BU_HASH_H
2#define HASH_H 2#define BU_HASH_H
3 3
4#include <stddef.h> 4#include <stddef.h>
5#include <string.h> 5#include <string.h>
6#include <memory> 6#include <memory>
7#include <iostream> 7#include <iostream>
8#include <list> 8#include <list>
9#include "exceptionbase.h" 9#include <utility>
10#include "hashable.h" 10#include "bu/exceptionbase.h"
11#include "serializable.h" 11#include "bu/list.h"
12#include "serializer.h" 12///#include "archival.h"
13///#include "archive.h"
13 14
14#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) 15#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
15 16
16subExceptionDecl( HashException ) 17namespace Bu
17
18enum eHashException
19{ 18{
20 excodeNotFilled 19 subExceptionDecl( HashException )
21};
22
23template<typename T>
24uint32_t __calcHashCode( const T &k );
25
26template<typename T>
27bool __cmpHashKeys( const T &a, const T &b );
28 20
29struct __calcNextTSize_fast 21 enum eHashException
30{
31 uint32_t operator()( uint32_t nCapacity, uint32_t nFill, uint32_t nDeleted ) const
32 { 22 {
33 if( nDeleted >= nCapacity/2 ) 23 excodeNotFilled
34 return nCapacity; 24 };
35 return nCapacity*2+1;
36 }
37};
38 25
39template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> > 26 template<typename T>
40class Hash; 27 uint32_t __calcHashCode( const T &k );
41 28
42template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> > 29 template<typename T>
43struct HashProxy 30 bool __cmpHashKeys( const T &a, const T &b );
44{
45 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>;
46private:
47 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, key *k, uint32_t nPos, uint32_t hash ) :
48 hsh( h ),
49 pKey( k ),
50 nPos( nPos ),
51 hash( hash ),
52 bFilled( false )
53 {
54 }
55 31
56 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) : 32 struct __calcNextTSize_fast
57 hsh( h ),
58 nPos( nPos ),
59 pValue( pValue ),
60 bFilled( true )
61 { 33 {
62 } 34 uint32_t operator()( uint32_t nCapacity, uint32_t nFill, uint32_t nDeleted ) const
35 {
36 if( nDeleted >= nCapacity/2 )
37 return nCapacity;
38 return nCapacity*2+1;
39 }
40 };
63 41
64 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 42 template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> >
65 key *pKey; 43 class Hash;
66 uint32_t nPos;
67 _value *pValue;
68 uint32_t hash;
69 bool bFilled;
70 44
71public: 45 template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> >
72 operator _value &() 46 struct HashProxy
73 { 47 {
74 if( bFilled == false ) 48 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>;
75 throw HashException( 49 private:
76 excodeNotFilled, 50 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, key *k, uint32_t nPos, uint32_t hash ) :
77 "No data assosiated with that key." 51 hsh( h ),
78 ); 52 pKey( k ),
79 return *pValue; 53 nPos( nPos ),
80 } 54 hash( hash ),
55 bFilled( false )
56 {
57 }
81 58
82 _value &value() 59 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) :
83 { 60 hsh( h ),
84 if( bFilled == false ) 61 nPos( nPos ),
85 throw HashException( 62 pValue( pValue ),
86 excodeNotFilled, 63 bFilled( true )
87 "No data assosiated with that key." 64 {
88 ); 65 }
89 return *pValue;
90 }
91 66
92 bool isFilled() 67 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
93 { 68 key *pKey;
94 return bFilled; 69 uint32_t nPos;
95 } 70 _value *pValue;
71 uint32_t hash;
72 bool bFilled;
96 73
97 void erase() 74 public:
98 { 75 /**
99 if( bFilled ) 76 * Cast operator for HashProxy.
77 *@returns (value_type &) The value the HashProxy is pointing to.
78 */
79 operator _value &()
100 { 80 {
101 hsh._erase( nPos ); 81 if( bFilled == false )
102 hsh.onDelete(); 82 throw HashException(
83 excodeNotFilled,
84 "No data assosiated with that key."
85 );
86 return *pValue;
103 } 87 }
104 }
105 88
106 _value operator=( _value nval ) 89 /**
107 { 90 * Direct function for retrieving a value out of the HashProxy.
108 if( bFilled ) 91 *@returns (value_type &) The value pointed to by this HashProxy.
92 */
93 _value &value()
109 { 94 {
110 hsh.va.destroy( pValue ); 95 if( bFilled == false )
111 hsh.va.construct( pValue, nval ); 96 throw HashException(
112 hsh.onUpdate(); 97 excodeNotFilled,
98 "No data assosiated with that key."
99 );
100 return *pValue;
113 } 101 }
114 else 102
103 /**
104 * Whether this HashProxy points to something real or not.
105 */
106 bool isFilled()
115 { 107 {
116 hsh.fill( nPos, *pKey, nval, hash ); 108 return bFilled;
117 hsh.onInsert();
118 } 109 }
119 110
120 return nval; 111 /**
121 } 112 * Erase the data pointed to by this HashProxy.
113 */
114 void erase()
115 {
116 if( bFilled )
117 {
118 hsh._erase( nPos );
119 hsh.onDelete();
120 }
121 }
122 122
123 _value *operator->() 123 /**
124 { 124 * Assign data to this point in the hash table.
125 if( bFilled == false ) 125 *@param nval (value_type) the data to assign.
126 throw HashException( 126 */
127 excodeNotFilled, 127 _value operator=( _value nval )
128 "No data assosiated with that key." 128 {
129 ); 129 if( bFilled )
130 return pValue; 130 {
131 } 131 hsh.va.destroy( pValue );
132}; 132 hsh.va.construct( pValue, nval );
133 hsh.onUpdate();
134 }
135 else
136 {
137 hsh.fill( nPos, *pKey, nval, hash );
138 hsh.onInsert();
139 }
133 140
134template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 141 return nval;
135class Hash 142 }
136{
137 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>;
138public:
139 Hash() :
140 nCapacity( 11 ),
141 nFilled( 0 ),
142 nDeleted( 0 ),
143 bFilled( NULL ),
144 bDeleted( NULL ),
145 aKeys( NULL ),
146 aValues( NULL ),
147 aHashCodes( NULL )
148 {
149 nKeysSize = bitsToBytes( nCapacity );
150 bFilled = ca.allocate( nKeysSize );
151 bDeleted = ca.allocate( nKeysSize );
152 clearBits();
153
154 aHashCodes = ca.allocate( nCapacity );
155 aKeys = ka.allocate( nCapacity );
156 aValues = va.allocate( nCapacity );
157 }
158 143
159 Hash( const Hash &src ) : 144 /**
160 nCapacity( src.nCapacity ), 145 * Pointer extraction operator. Access to members of data pointed to
161 nFilled( 0 ), 146 * by HashProxy.
162 nDeleted( 0 ), 147 *@returns (value_type *)
163 bFilled( NULL ), 148 */
164 bDeleted( NULL ), 149 _value *operator->()
165 aKeys( NULL ), 150 {
166 aValues( NULL ), 151 if( bFilled == false )
167 aHashCodes( NULL ) 152 throw HashException(
168 { 153 excodeNotFilled,
169 nKeysSize = bitsToBytes( nCapacity ); 154 "No data assosiated with that key."
170 bFilled = ca.allocate( nKeysSize ); 155 );
171 bDeleted = ca.allocate( nKeysSize ); 156 return pValue;
172 clearBits(); 157 }
158 };
173 159
174 aHashCodes = ca.allocate( nCapacity ); 160 /**
175 aKeys = ka.allocate( nCapacity ); 161 * Libbu Template Hash Table
176 aValues = va.allocate( nCapacity ); 162 *@param key (typename) The datatype of the hashtable keys
163 *@param value (typename) The datatype of the hashtable data
164 *@param sizecalc (typename) Functor to compute new table size on rehash
165 *@param keyalloc (typename) Memory allocator for hashtable keys
166 *@param valuealloc (typename) Memory allocator for hashtable values
167 *@param challoc (typename) Byte allocator for bitflags
168 */
169 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc >
170 class Hash
171 {
172 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>;
173 public:
174 Hash() :
175 nCapacity( 11 ),
176 nFilled( 0 ),
177 nDeleted( 0 ),
178 bFilled( NULL ),
179 bDeleted( NULL ),
180 aKeys( NULL ),
181 aValues( NULL ),
182 aHashCodes( NULL )
183 {
184 nKeysSize = bitsToBytes( nCapacity );
185 bFilled = ca.allocate( nKeysSize );
186 bDeleted = ca.allocate( nKeysSize );
187 clearBits();
188
189 aHashCodes = ca.allocate( nCapacity );
190 aKeys = ka.allocate( nCapacity );
191 aValues = va.allocate( nCapacity );
192 }
177 193
178 for( uint32_t j = 0; j < src.nCapacity; j++ ) 194 Hash( const Hash &src ) :
195 nCapacity( src.nCapacity ),
196 nFilled( 0 ),
197 nDeleted( 0 ),
198 bFilled( NULL ),
199 bDeleted( NULL ),
200 aKeys( NULL ),
201 aValues( NULL ),
202 aHashCodes( NULL )
179 { 203 {
180 if( src.isFilled( j ) ) 204 nKeysSize = bitsToBytes( nCapacity );
205 bFilled = ca.allocate( nKeysSize );
206 bDeleted = ca.allocate( nKeysSize );
207 clearBits();
208
209 aHashCodes = ca.allocate( nCapacity );
210 aKeys = ka.allocate( nCapacity );
211 aValues = va.allocate( nCapacity );
212
213 for( uint32_t j = 0; j < src.nCapacity; j++ )
181 { 214 {
182 insert( src.aKeys[j], src.aValues[j] ); 215 if( src.isFilled( j ) )
216 {
217 insert( src.aKeys[j], src.aValues[j] );
218 }
183 } 219 }
184 } 220 }
185 }
186 221
187 Hash &operator=( const Hash &src ) 222 /**
188 { 223 * Hashtable assignment operator. Clears this hashtable and
189 for( uint32_t j = 0; j < nCapacity; j++ ) 224 * copies RH into it.
225 */
226 Hash &operator=( const Hash &src )
190 { 227 {
191 if( isFilled( j ) ) 228 for( uint32_t j = 0; j < nCapacity; j++ )
192 if( !isDeleted( j ) ) 229 {
230 if( isFilled( j ) )
231 if( !isDeleted( j ) )
232 {
233 va.destroy( &aValues[j] );
234 ka.destroy( &aKeys[j] );
235 }
236 }
237 va.deallocate( aValues, nCapacity );
238 ka.deallocate( aKeys, nCapacity );
239 ca.deallocate( bFilled, nKeysSize );
240 ca.deallocate( bDeleted, nKeysSize );
241 ca.deallocate( aHashCodes, nCapacity );
242
243 nFilled = 0;
244 nDeleted = 0;
245 nCapacity = src.nCapacity;
246 nKeysSize = bitsToBytes( nCapacity );
247 bFilled = ca.allocate( nKeysSize );
248 bDeleted = ca.allocate( nKeysSize );
249 clearBits();
250
251 aHashCodes = ca.allocate( nCapacity );
252 aKeys = ka.allocate( nCapacity );
253 aValues = va.allocate( nCapacity );
254
255 for( uint32_t j = 0; j < src.nCapacity; j++ )
256 {
257 if( src.isFilled( j ) )
193 { 258 {
194 va.destroy( &aValues[j] ); 259 insert( src.aKeys[j], src.aValues[j] );
195 ka.destroy( &aKeys[j] );
196 } 260 }
197 } 261 }
198 va.deallocate( aValues, nCapacity );
199 ka.deallocate( aKeys, nCapacity );
200 ca.deallocate( bFilled, nKeysSize );
201 ca.deallocate( bDeleted, nKeysSize );
202 ca.deallocate( aHashCodes, nCapacity );
203
204 nFilled = 0;
205 nDeleted = 0;
206 nCapacity = src.nCapacity;
207 nKeysSize = bitsToBytes( nCapacity );
208 bFilled = ca.allocate( nKeysSize );
209 bDeleted = ca.allocate( nKeysSize );
210 clearBits();
211 262
212 aHashCodes = ca.allocate( nCapacity ); 263 return *this;
213 aKeys = ka.allocate( nCapacity ); 264 }
214 aValues = va.allocate( nCapacity );
215 265
216 for( uint32_t j = 0; j < src.nCapacity; j++ ) 266 virtual ~Hash()
217 { 267 {
218 if( src.isFilled( j ) ) 268 for( uint32_t j = 0; j < nCapacity; j++ )
219 { 269 {
220 insert( src.aKeys[j], src.aValues[j] ); 270 if( isFilled( j ) )
271 if( !isDeleted( j ) )
272 {
273 va.destroy( &aValues[j] );
274 ka.destroy( &aKeys[j] );
275 }
221 } 276 }
277 va.deallocate( aValues, nCapacity );
278 ka.deallocate( aKeys, nCapacity );
279 ca.deallocate( bFilled, nKeysSize );
280 ca.deallocate( bDeleted, nKeysSize );
281 ca.deallocate( aHashCodes, nCapacity );
222 } 282 }
223 283
224 return *this; 284 /**
225 } 285 * Get the current hash table capacity. (Changes at re-hash)
226 286 *@returns (uint32_t) The current capacity.
227 virtual ~Hash() 287 */
228 { 288 uint32_t getCapacity()
229 for( uint32_t j = 0; j < nCapacity; j++ )
230 { 289 {
231 if( isFilled( j ) ) 290 return nCapacity;
232 if( !isDeleted( j ) )
233 {
234 va.destroy( &aValues[j] );
235 ka.destroy( &aKeys[j] );
236 }
237 } 291 }
238 va.deallocate( aValues, nCapacity );
239 ka.deallocate( aKeys, nCapacity );
240 ca.deallocate( bFilled, nKeysSize );
241 ca.deallocate( bDeleted, nKeysSize );
242 ca.deallocate( aHashCodes, nCapacity );
243 }
244 292
245 uint32_t getCapacity() 293 /**
246 { 294 * Get the number of hash locations spoken for. (Including
247 return nCapacity; 295 * not-yet-cleaned-up deleted items.)
248 } 296 *@returns (uint32_t) The current fill state.
297 */
298 uint32_t getFill()
299 {
300 return nFilled;
301 }
249 302
250 uint32_t getFill() 303 /**
251 { 304 * Get the number of items stored in the hash table.
252 return nFilled; 305 *@returns (uint32_t) The number of items stored in the hash table.
253 } 306 */
307 uint32_t size()
308 {
309 return nFilled-nDeleted;
310 }
254 311
255 uint32_t size() 312 /**
256 { 313 * Get the number of items which have been deleted, but not yet
257 return nFilled-nDeleted; 314 * cleaned up.
258 } 315 *@returns (uint32_t) The number of deleted items.
316 */
317 uint32_t getDeleted()
318 {
319 return nDeleted;
320 }
259 321
260 uint32_t getDeleted() 322 /**
261 { 323 * Hash table index operator
262 return nDeleted; 324 *@param k (key_type) Key of data to be retrieved.
263 } 325 *@returns (HashProxy) Proxy pointing to the data.
326 */
327 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k )
328 {
329 uint32_t hash = __calcHashCode( k );
330 bool bFill;
331 uint32_t nPos = probe( hash, k, bFill );
264 332
265 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k ) 333 if( bFill )
266 { 334 {
267 uint32_t hash = __calcHashCode( k ); 335 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] );
268 bool bFill; 336 }
269 uint32_t nPos = probe( hash, k, bFill ); 337 else
338 {
339 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash );
340 }
341 }
270 342
271 if( bFill ) 343 /**
344 * Insert a value (v) under key (k) into the hash table
345 *@param k (key_type) Key to list the value under.
346 *@param v (value_type) Value to store in the hash table.
347 */
348 virtual void insert( key k, value v )
272 { 349 {
273 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] ); 350 uint32_t hash = __calcHashCode( k );
351 bool bFill;
352 uint32_t nPos = probe( hash, k, bFill );
353
354 if( bFill )
355 {
356 va.destroy( &aValues[nPos] );
357 va.construct( &aValues[nPos], v );
358 onUpdate();
359 }
360 else
361 {
362 fill( nPos, k, v, hash );
363 onInsert();
364 }
274 } 365 }
275 else 366
367 /**
368 * Remove a value from the hash table.
369 *@param k (key_type) The data under this key will be erased.
370 */
371 virtual void erase( key k )
276 { 372 {
277 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash ); 373 uint32_t hash = __calcHashCode( k );
374 bool bFill;
375 uint32_t nPos = probe( hash, k, bFill );
376
377 if( bFill )
378 {
379 _erase( nPos );
380 onDelete();
381 }
278 } 382 }
279 }
280 383
281 virtual void insert( key k, value v ) 384 struct iterator;
282 {
283 uint32_t hash = __calcHashCode( k );
284 bool bFill;
285 uint32_t nPos = probe( hash, k, bFill );
286 385
287 if( bFill ) 386 /**
387 * Remove a value from the hash pointed to from an iterator.
388 *@param i (iterator &) The data to be erased.
389 */
390 virtual void erase( struct iterator &i )
288 { 391 {
289 va.destroy( &aValues[nPos] ); 392 if( this != &i.hsh )
290 va.construct( &aValues[nPos], v ); 393 throw HashException("This iterator didn't come from this Hash.");
291 onUpdate(); 394 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
395 {
396 _erase( i.nPos );
397 onDelete();
398 }
292 } 399 }
293 else 400
401 /**
402 * Remove all data from the hash table.
403 */
404 virtual void clear()
294 { 405 {
295 fill( nPos, k, v, hash ); 406 for( uint32_t j = 0; j < nCapacity; j++ )
296 onInsert(); 407 {
408 if( isFilled( j ) )
409 if( !isDeleted( j ) )
410 {
411 va.destroy( &aValues[j] );
412 ka.destroy( &aKeys[j] );
413 onDelete();
414 }
415 }
416
417 clearBits();
297 } 418 }
298 }
299 419
300 virtual void erase( key k ) 420 /**
301 { 421 * Get an item of data from the hash table.
302 uint32_t hash = __calcHashCode( k ); 422 *@param k (key_type) Key pointing to the data to be retrieved.
303 bool bFill; 423 *@returns (value_type &) The data pointed to by (k).
304 uint32_t nPos = probe( hash, k, bFill ); 424 */
425 virtual value &get( key k )
426 {
427 uint32_t hash = __calcHashCode( k );
428 bool bFill;
429 uint32_t nPos = probe( hash, k, bFill );
305 430
306 if( bFill ) 431 if( bFill )
432 {
433 return aValues[nPos];
434 }
435 else
436 {
437 throw HashException(
438 excodeNotFilled,
439 "No data assosiated with that key."
440 );
441 }
442 }
443
444 /**
445 * Get a const item of data from the hash table.
446 *@param k (key_type) Key pointing to the data to be retrieved.
447 *@returns (const value_type &) A const version of the data pointed
448 * to by (k).
449 */
450 virtual const value &get( key k ) const
307 { 451 {
308 _erase( nPos ); 452 uint32_t hash = __calcHashCode( k );
309 onDelete(); 453 bool bFill;
454 uint32_t nPos = probe( hash, k, bFill );
455
456 if( bFill )
457 {
458 return aValues[nPos];
459 }
460 else
461 {
462 throw HashException(
463 excodeNotFilled,
464 "No data assosiated with that key."
465 );
466 }
310 } 467 }
311 }
312 468
313 struct iterator; 469 /**
314 virtual void erase( struct iterator &i ) 470 * Does the hash table contain an item under key (k).
315 { 471 *@param k (key_type) The key to check.
316 if( this != &i.hsh ) 472 *@returns (bool) Whether there was an item in the hash under key (k).
317 throw HashException("This iterator didn't come from this Hash."); 473 */
318 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) 474 virtual bool has( key k )
319 { 475 {
320 _erase( i.nPos ); 476 bool bFill;
321 onDelete(); 477 probe( __calcHashCode( k ), k, bFill, false );
478
479 return bFill;
322 } 480 }
323 }
324 481
325 virtual void clear() 482 /**
326 { 483 * Iteration structure for iterating through the hash.
327 for( uint32_t j = 0; j < nCapacity; j++ ) 484 */
485 typedef struct iterator
328 { 486 {
329 if( isFilled( j ) ) 487 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
330 if( !isDeleted( j ) ) 488 private:
489 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) :
490 hsh( hsh ),
491 nPos( 0 ),
492 bFinished( false )
493 {
494 nPos = hsh.getFirstPos( bFinished );
495 }
496
497 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) :
498 hsh( hsh ),
499 nPos( 0 ),
500 bFinished( bDone )
501 {
502 }
503
504 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
505 uint32_t nPos;
506 bool bFinished;
507
508 public:
509 /**
510 * Iterator incrementation operator. Move the iterator forward.
511 */
512 iterator operator++( int )
513 {
514 if( bFinished == false )
515 nPos = hsh.getNextPos( nPos, bFinished );
516
517 return *this;
518 }
519
520 /**
521 * Iterator incrementation operator. Move the iterator forward.
522 */
523 iterator operator++()
524 {
525 if( bFinished == false )
526 nPos = hsh.getNextPos( nPos, bFinished );
527
528 return *this;
529 }
530
531 /**
532 * Iterator equality comparison operator. Iterators the same?
533 */
534 bool operator==( const iterator &oth )
535 {
536 if( bFinished != oth.bFinished )
537 return false;
538 if( bFinished == true )
331 { 539 {
332 va.destroy( &aValues[j] ); 540 return true;
333 ka.destroy( &aKeys[j] );
334 onDelete();
335 } 541 }
336 } 542 else
337 543 {
338 clearBits(); 544 if( oth.nPos == nPos )
339 } 545 return true;
546 return false;
547 }
548 }
549
550 /**
551 * Iterator not equality comparison operator. Not the same?
552 */
553 bool operator!=( const iterator &oth )
554 {
555 return !(*this == oth );
556 }
340 557
341 virtual value &get( key k ) 558 /**
342 { 559 * Iterator assignment operator.
343 uint32_t hash = __calcHashCode( k ); 560 */
344 bool bFill; 561 iterator operator=( const iterator &oth )
345 uint32_t nPos = probe( hash, k, bFill ); 562 {
563 if( &hsh != &oth.hsh )
564 throw HashException(
565 "Cannot mix iterators from different hash objects.");
566 nPos = oth.nPos;
567 bFinished = oth.bFinished;
568 }
346 569
347 if( bFill ) 570 /**
348 { 571 * Iterator dereference operator... err.. get the value
349 return aValues[nPos]; 572 *@returns (value_type &) The value behind this iterator.
350 } 573 */
351 else 574 value &operator *()
575 {
576 return hsh.getValueAtPos( nPos );
577 }
578
579 /**
580 * Get the key behind this iterator.
581 *@returns (key_type &) The key behind this iterator.
582 */
583 key &getKey()
584 {
585 return hsh.getKeyAtPos( nPos );
586 }
587
588 /**
589 * Get the value behind this iterator.
590 *@returs (value_type &) The value behind this iterator.
591 */
592 value &getValue()
593 {
594 return hsh.getValueAtPos( nPos );
595 }
596 };
597
598 /**
599 * Iteration structure for iterating through the hash (const).
600 */
601 typedef struct const_iterator
352 { 602 {
353 throw HashException( 603 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
354 excodeNotFilled, 604 private:
355 "No data assosiated with that key." 605 const_iterator( const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) :
356 ); 606 hsh( hsh ),
357 } 607 nPos( 0 ),
358 } 608 bFinished( false )
609 {
610 nPos = hsh.getFirstPos( bFinished );
611 }
612
613 const_iterator( const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) :
614 hsh( hsh ),
615 nPos( 0 ),
616 bFinished( bDone )
617 {
618 }
359 619
360 virtual bool has( key k ) 620 const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
361 { 621 uint32_t nPos;
362 bool bFill; 622 bool bFinished;
363 probe( __calcHashCode( k ), k, bFill, false );
364 623
365 return bFill; 624 public:
366 } 625 /**
626 * Iterator incrementation operator. Move the iterator forward.
627 */
628 const_iterator operator++( int )
629 {
630 if( bFinished == false )
631 nPos = hsh.getNextPos( nPos, bFinished );
367 632
368 typedef struct iterator 633 return *this;
369 { 634 }
370 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 635
371 private: 636 /**
372 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) : 637 * Iterator incrementation operator. Move the iterator forward.
373 hsh( hsh ), 638 */
374 nPos( 0 ), 639 const_iterator operator++()
375 bFinished( false ) 640 {
641 if( bFinished == false )
642 nPos = hsh.getNextPos( nPos, bFinished );
643
644 return *this;
645 }
646
647 /**
648 * Iterator equality comparison operator. Iterators the same?
649 */
650 bool operator==( const const_iterator &oth )
651 {
652 if( bFinished != oth.bFinished )
653 return false;
654 if( bFinished == true )
655 {
656 return true;
657 }
658 else
659 {
660 if( oth.nPos == nPos )
661 return true;
662 return false;
663 }
664 }
665
666 /**
667 * Iterator not equality comparison operator. Not the same?
668 */
669 bool operator!=( const const_iterator &oth )
670 {
671 return !(*this == oth );
672 }
673
674 /**
675 * Iterator assignment operator.
676 */
677 const_iterator operator=( const const_iterator &oth )
678 {
679 if( &hsh != &oth.hsh )
680 throw HashException(
681 "Cannot mix iterators from different hash objects.");
682 nPos = oth.nPos;
683 bFinished = oth.bFinished;
684 }
685
686 /**
687 * Iterator dereference operator... err.. get the value
688 *@returns (value_type &) The value behind this iterator.
689 */
690 const value &operator *() const
691 {
692 return hsh.getValueAtPos( nPos );
693 }
694
695 /**
696 * Get the key behind this iterator.
697 *@returns (key_type &) The key behind this iterator.
698 */
699 const key &getKey() const
700 {
701 return hsh.getKeyAtPos( nPos );
702 }
703
704 /**
705 * Get the value behind this iterator.
706 *@returs (value_type &) The value behind this iterator.
707 */
708 const value &getValue() const
709 {
710 return hsh.getValueAtPos( nPos );
711 }
712 };
713
714 /**
715 * Get an iterator pointing to the first item in the hash table.
716 *@returns (iterator) An iterator pointing to the first item in the
717 * hash table.
718 */
719 iterator begin()
376 { 720 {
377 nPos = hsh.getFirstPos( bFinished ); 721 return iterator( *this );
378 } 722 }
379 723
380 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) : 724 const_iterator begin() const
381 hsh( hsh ),
382 nPos( 0 ),
383 bFinished( bDone )
384 { 725 {
726 return const_iterator( *this );
385 } 727 }
386 728
387 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 729 /**
388 uint32_t nPos; 730 * Get an iterator pointing to a point just past the last item in the
389 bool bFinished; 731 * hash table.
390 732 *@returns (iterator) An iterator pointing to a point just past the
391 public: 733 * last item in the hash table.
392 iterator operator++( int ) 734 */
735 iterator end()
393 { 736 {
394 if( bFinished == false ) 737 return iterator( *this, true );
395 nPos = hsh.getNextPos( nPos, bFinished );
396
397 return *this;
398 } 738 }
399 739
400 iterator operator++() 740 const_iterator end() const
401 { 741 {
402 if( bFinished == false ) 742 return const_iterator( *this, true );
403 nPos = hsh.getNextPos( nPos, bFinished );
404
405 return *this;
406 } 743 }
407 744
408 bool operator==( const iterator &oth ) 745 /**
746 * Get a list of all the keys in the hash table.
747 *@returns (std::list<key_type>) The list of keys in the hash table.
748 */
749 Bu::List<key> getKeys() const
409 { 750 {
410 if( bFinished != oth.bFinished ) 751 Bu::List<key> lKeys;
411 return false; 752
412 if( bFinished == true ) 753 for( uint32_t j = 0; j < nCapacity; j++ )
413 { 754 {
414 return true; 755 if( isFilled( j ) )
756 {
757 if( !isDeleted( j ) )
758 {
759 lKeys.append( aKeys[j] );
760 }
761 }
415 } 762 }
416 else 763
764 return lKeys;
765 }
766
767 protected:
768 virtual void onInsert() {}
769 virtual void onUpdate() {}
770 virtual void onDelete() {}
771 virtual void onReHash() {}
772
773 virtual void clearBits()
774 {
775 for( uint32_t j = 0; j < nKeysSize; j++ )
417 { 776 {
418 if( oth.nPos == nPos ) 777 bFilled[j] = bDeleted[j] = 0;
419 return true;
420 return false;
421 } 778 }
422 } 779 }
423 780
424 bool operator!=( const iterator &oth ) 781 virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash )
425 { 782 {
426 return !(*this == oth ); 783 bFilled[loc/32] |= (1<<(loc%32));
784 va.construct( &aValues[loc], v );
785 ka.construct( &aKeys[loc], k );
786 aHashCodes[loc] = hash;
787 nFilled++;
788 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
789 // nFilled, nDeleted, nCapacity );
427 } 790 }
428 791
429 iterator operator=( const iterator &oth ) 792 virtual void _erase( uint32_t loc )
430 { 793 {
431 if( &hsh != &oth.hsh ) 794 bDeleted[loc/32] |= (1<<(loc%32));
432 throw HashException( 795 va.destroy( &aValues[loc] );
433 "Cannot mix iterators from different hash objects."); 796 ka.destroy( &aKeys[loc] );
434 nPos = oth.nPos; 797 nDeleted++;
435 bFinished = oth.bFinished; 798 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
799 // nFilled, nDeleted, nCapacity );
436 } 800 }
437 801
438 std::pair<key,value> operator *() 802 virtual std::pair<key,value> getAtPos( uint32_t nPos )
803 {
804 return std::pair<key,value>(aKeys[nPos],aValues[nPos]);
805 }
806
807 virtual key &getKeyAtPos( uint32_t nPos )
439 { 808 {
440 return hsh.getAtPos( nPos ); 809 return aKeys[nPos];
441 } 810 }
442 811
443 key &getKey() 812 virtual const key &getKeyAtPos( uint32_t nPos ) const
444 { 813 {
445 return hsh.getKeyAtPos( nPos ); 814 return aKeys[nPos];
815 }
816
817 virtual value &getValueAtPos( uint32_t nPos )
818 {
819 return aValues[nPos];
820 }
821
822 virtual const value &getValueAtPos( uint32_t nPos ) const
823 {
824 return aValues[nPos];
446 } 825 }
447 826
448 value &getValue() 827 virtual uint32_t getFirstPos( bool &bFinished ) const
449 { 828 {
450 return hsh.getValueAtPos( nPos ); 829 for( uint32_t j = 0; j < nCapacity; j++ )
830 {
831 if( isFilled( j ) )
832 if( !isDeleted( j ) )
833 return j;
834 }
835
836 bFinished = true;
837 return 0;
451 } 838 }
452 };
453 839
454 iterator begin() 840 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
455 { 841 {
456 return iterator( *this ); 842 for( uint32_t j = nPos+1; j < nCapacity; j++ )
457 } 843 {
458 844 if( isFilled( j ) )
459 iterator end() 845 if( !isDeleted( j ) )
460 { 846 return j;
461 return iterator( *this, true ); 847 }
462 }
463 848
464 std::list<key> getKeys() 849 bFinished = true;
465 { 850 return 0;
466 std::list<key> lKeys; 851 }
467 852
468 for( uint32_t j = 0; j < nCapacity; j++ ) 853 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true )
469 { 854 {
470 if( isFilled( j ) ) 855 uint32_t nCur = hash%nCapacity;
856
857 // First we scan to see if the key is already there, abort if we
858 // run out of probing room, or we find a non-filled entry
859 for( int8_t j = 0;
860 isFilled( nCur ) && j < 32;
861 nCur = (nCur + (1<<j))%nCapacity, j++
862 )
471 { 863 {
472 if( !isDeleted( j ) ) 864 // Is this the same hash code we were looking for?
865 if( hash == aHashCodes[nCur] )
473 { 866 {
474 lKeys.push_back( aKeys[j] ); 867 // Skip over deleted entries. Deleted entries are also filled,
868 // so we only have to do this check here.
869 if( isDeleted( nCur ) )
870 continue;
871
872 // Is it really the same key? (for safety)
873 if( __cmpHashKeys( aKeys[nCur], k ) == true )
874 {
875 bFill = true;
876 return nCur;
877 }
475 } 878 }
476 } 879 }
477 }
478 880
479 return lKeys; 881 // This is our insurance, if the table is full, then go ahead and
480 } 882 // rehash, then try again.
883 if( isFilled( nCur ) && rehash == true )
884 {
885 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
481 886
482protected: 887 // This is potentially dangerous, and could cause an infinite loop.
483 virtual void onInsert() {} 888 // Be careful writing probe, eh?
484 virtual void onUpdate() {} 889 return probe( hash, k, bFill );
485 virtual void onDelete() {} 890 }
486 virtual void onReHash() {}
487 891
488 virtual void clearBits() 892 bFill = false;
489 { 893 return nCur;
490 for( uint32_t j = 0; j < nKeysSize; j++ )
491 {
492 bFilled[j] = bDeleted[j] = 0;
493 } 894 }
494 } 895
495 896 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) const
496 virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash )
497 {
498 bFilled[loc/32] |= (1<<(loc%32));
499 va.construct( &aValues[loc], v );
500 ka.construct( &aKeys[loc], k );
501 aHashCodes[loc] = hash;
502 nFilled++;
503 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
504 // nFilled, nDeleted, nCapacity );
505 }
506
507 virtual void _erase( uint32_t loc )
508 {
509 bDeleted[loc/32] |= (1<<(loc%32));
510 va.destroy( &aValues[loc] );
511 ka.destroy( &aKeys[loc] );
512 nDeleted++;
513 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
514 // nFilled, nDeleted, nCapacity );
515 }
516
517 virtual std::pair<key,value> getAtPos( uint32_t nPos )
518 {
519 return std::pair<key,value>(aKeys[nPos],aValues[nPos]);
520 }
521
522 virtual key &getKeyAtPos( uint32_t nPos )
523 {
524 return aKeys[nPos];
525 }
526
527 virtual value &getValueAtPos( uint32_t nPos )
528 {
529 return aValues[nPos];
530 }
531
532 virtual uint32_t getFirstPos( bool &bFinished )
533 {
534 for( uint32_t j = 0; j < nCapacity; j++ )
535 { 897 {
536 if( isFilled( j ) ) 898 uint32_t nCur = hash%nCapacity;
537 if( !isDeleted( j ) ) 899
538 return j; 900 // First we scan to see if the key is already there, abort if we
539 } 901 // run out of probing room, or we find a non-filled entry
902 for( int8_t j = 0;
903 isFilled( nCur ) && j < 32;
904 nCur = (nCur + (1<<j))%nCapacity, j++
905 )
906 {
907 // Is this the same hash code we were looking for?
908 if( hash == aHashCodes[nCur] )
909 {
910 // Skip over deleted entries. Deleted entries are also filled,
911 // so we only have to do this check here.
912 if( isDeleted( nCur ) )
913 continue;
914
915 // Is it really the same key? (for safety)
916 if( __cmpHashKeys( aKeys[nCur], k ) == true )
917 {
918 bFill = true;
919 return nCur;
920 }
921 }
922 }
540 923
541 bFinished = true; 924 bFill = false;
542 return 0; 925 return nCur;
543 } 926 }
544 927
545 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) 928 void reHash( uint32_t nNewSize )
546 {
547 for( uint32_t j = nPos+1; j < nCapacity; j++ )
548 { 929 {
549 if( isFilled( j ) ) 930 //printf("---REHASH---");
550 if( !isDeleted( j ) ) 931 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
551 return j; 932 // nFilled, nDeleted, nCapacity );
552 } 933
934 // Save all the old data
935 uint32_t nOldCapacity = nCapacity;
936 uint32_t *bOldFilled = bFilled;
937 uint32_t *aOldHashCodes = aHashCodes;
938 uint32_t nOldKeysSize = nKeysSize;
939 uint32_t *bOldDeleted = bDeleted;
940 value *aOldValues = aValues;
941 key *aOldKeys = aKeys;
942
943 // Calculate new sizes
944 nCapacity = nNewSize;
945 nKeysSize = bitsToBytes( nCapacity );
946
947 // Allocate new memory + prep
948 bFilled = ca.allocate( nKeysSize );
949 bDeleted = ca.allocate( nKeysSize );
950 clearBits();
553 951
554 bFinished = true; 952 aHashCodes = ca.allocate( nCapacity );
555 return 0; 953 aKeys = ka.allocate( nCapacity );
556 } 954 aValues = va.allocate( nCapacity );
557 955
558 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) 956 nDeleted = nFilled = 0;
559 {
560 uint32_t nCur = hash%nCapacity;
561 957
562 // First we scan to see if the key is already there, abort if we 958 // Re-insert all of the old data (except deleted items)
563 // run out of probing room, or we find a non-filled entry 959 for( uint32_t j = 0; j < nOldCapacity; j++ )
564 for( int8_t j = 0;
565 isFilled( nCur ) && j < 32;
566 nCur = (nCur + (1<<j))%nCapacity, j++
567 )
568 {
569 // Is this the same hash code we were looking for?
570 if( hash == aHashCodes[nCur] )
571 { 960 {
572 // Skip over deleted entries. Deleted entries are also filled, 961 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
573 // so we only have to do this check here. 962 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
574 if( isDeleted( nCur ) ) 963 {
575 continue; 964 insert( aOldKeys[j], aOldValues[j] );
965 }
966 }
576 967
577 // Is it really the same key? (for safety) 968 // Delete all of the old data
578 if( __cmpHashKeys( aKeys[nCur], k ) == true ) 969 for( uint32_t j = 0; j < nOldCapacity; j++ )
970 {
971 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
579 { 972 {
580 bFill = true; 973 va.destroy( &aOldValues[j] );
581 return nCur; 974 ka.destroy( &aOldKeys[j] );
582 } 975 }
583 } 976 }
977 va.deallocate( aOldValues, nOldCapacity );
978 ka.deallocate( aOldKeys, nOldCapacity );
979 ca.deallocate( bOldFilled, nOldKeysSize );
980 ca.deallocate( bOldDeleted, nOldKeysSize );
981 ca.deallocate( aOldHashCodes, nOldCapacity );
584 } 982 }
585 983
586 // This is our insurance, if the table is full, then go ahead and 984 virtual bool isFilled( uint32_t loc ) const
587 // rehash, then try again.
588 if( isFilled( nCur ) && rehash == true )
589 { 985 {
590 reHash( szCalc(getCapacity(), getFill(), getDeleted()) ); 986 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
987 }
591 988
592 // This is potentially dangerous, and could cause an infinite loop. 989 virtual bool isDeleted( uint32_t loc ) const
593 // Be careful writing probe, eh? 990 {
594 return probe( hash, k, bFill ); 991 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
595 } 992 }
596 993
597 bFill = false; 994 protected:
598 return nCur; 995 uint32_t nCapacity;
599 } 996 uint32_t nFilled;
997 uint32_t nDeleted;
998 uint32_t *bFilled;
999 uint32_t *bDeleted;
1000 uint32_t nKeysSize;
1001 key *aKeys;
1002 value *aValues;
1003 uint32_t *aHashCodes;
1004 valuealloc va;
1005 keyalloc ka;
1006 challoc ca;
1007 sizecalc szCalc;
1008 };
600 1009
601 void reHash( uint32_t nNewSize ) 1010 template<> uint32_t __calcHashCode<int>( const int &k );
602 { 1011 template<> bool __cmpHashKeys<int>( const int &a, const int &b );
603 //printf("---REHASH---");
604 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
605 // nFilled, nDeleted, nCapacity );
606
607 // Save all the old data
608 uint32_t nOldCapacity = nCapacity;
609 uint32_t *bOldFilled = bFilled;
610 uint32_t *aOldHashCodes = aHashCodes;
611 uint32_t nOldKeysSize = nKeysSize;
612 uint32_t *bOldDeleted = bDeleted;
613 value *aOldValues = aValues;
614 key *aOldKeys = aKeys;
615
616 // Calculate new sizes
617 nCapacity = nNewSize;
618 nKeysSize = bitsToBytes( nCapacity );
619
620 // Allocate new memory + prep
621 bFilled = ca.allocate( nKeysSize );
622 bDeleted = ca.allocate( nKeysSize );
623 clearBits();
624 1012
625 aHashCodes = ca.allocate( nCapacity ); 1013 template<> uint32_t __calcHashCode<unsigned int>( const unsigned int &k );
626 aKeys = ka.allocate( nCapacity ); 1014 template<> bool __cmpHashKeys<unsigned int>( const unsigned int &a, const unsigned int &b );
627 aValues = va.allocate( nCapacity );
628 1015
629 nDeleted = nFilled = 0; 1016 template<> uint32_t __calcHashCode<const char *>( const char * const &k );
1017 template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
630 1018
631 // Re-insert all of the old data (except deleted items) 1019 template<> uint32_t __calcHashCode<char *>( char * const &k );
632 for( uint32_t j = 0; j < nOldCapacity; j++ ) 1020 template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
633 {
634 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
635 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
636 {
637 insert( aOldKeys[j], aOldValues[j] );
638 }
639 }
640 1021
641 // Delete all of the old data 1022 template<> uint32_t __calcHashCode<std::string>( const std::string &k );
642 for( uint32_t j = 0; j < nOldCapacity; j++ ) 1023 template<> bool __cmpHashKeys<std::string>( const std::string &a, const std::string &b );
1024
1025 /*
1026 template<typename key, typename value>
1027 Archive &operator<<( Archive &ar, Hash<key,value> &h )
1028 {
1029 ar << h.size();
1030 for( typename Hash<key,value>::iterator i = h.begin(); i != h.end(); i++ )
643 { 1031 {
644 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 1032 std::pair<key,value> p = *i;
645 (bOldDeleted[j/32]&(1<<(j%32)))==0 ) 1033 ar << p.first << p.second;
646 {
647 va.destroy( &aOldValues[j] );
648 ka.destroy( &aOldKeys[j] );
649 }
650 } 1034 }
651 va.deallocate( aOldValues, nOldCapacity );
652 ka.deallocate( aOldKeys, nOldCapacity );
653 ca.deallocate( bOldFilled, nOldKeysSize );
654 ca.deallocate( bOldDeleted, nOldKeysSize );
655 ca.deallocate( aOldHashCodes, nOldCapacity );
656 }
657 1035
658 virtual bool isFilled( uint32_t loc ) const 1036 return ar;
659 {
660 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
661 } 1037 }
662 1038
663 virtual bool isDeleted( uint32_t loc ) 1039 template<typename key, typename value>
1040 Archive &operator>>( Archive &ar, Hash<key,value> &h )
664 { 1041 {
665 return (bDeleted[loc/32]&(1<<(loc%32)))!=0; 1042 h.clear();
666 } 1043 uint32_t nSize;
1044 ar >> nSize;
667 1045
668protected: 1046 for( uint32_t j = 0; j < nSize; j++ )
669 uint32_t nCapacity; 1047 {
670 uint32_t nFilled; 1048 key k; value v;
671 uint32_t nDeleted; 1049 ar >> k >> v;
672 uint32_t *bFilled; 1050 h.insert( k, v );
673 uint32_t *bDeleted; 1051 }
674 uint32_t nKeysSize;
675 key *aKeys;
676 value *aValues;
677 uint32_t *aHashCodes;
678 valuealloc va;
679 keyalloc ka;
680 challoc ca;
681 sizecalc szCalc;
682};
683
684template<> uint32_t __calcHashCode<int>( const int &k );
685template<> bool __cmpHashKeys<int>( const int &a, const int &b );
686
687template<> uint32_t __calcHashCode<unsigned int>( const unsigned int &k );
688template<> bool __cmpHashKeys<unsigned int>( const unsigned int &a, const unsigned int &b );
689
690template<> uint32_t __calcHashCode<const char *>( const char * const &k );
691template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
692
693template<> uint32_t __calcHashCode<char *>( char * const &k );
694template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
695
696template<> uint32_t __calcHashCode<std::string>( const std::string &k );
697template<> bool __cmpHashKeys<std::string>( const std::string &a, const std::string &b );
698
699template<> uint32_t __calcHashCode<Hashable>( const Hashable &k );
700template<> bool __cmpHashKeys<Hashable>( const Hashable &a, const Hashable &b );
701
702template<typename key, typename value>
703Serializer &operator<<( Serializer &ar, Hash<key,value> &h )
704{
705 ar << h.size();
706 for( typename Hash<key,value>::iterator i = h.begin(); i != h.end(); i++ )
707 {
708 std::pair<key,value> p = *i;
709 ar << p.first << p.second;
710 }
711 1052
712 return ar; 1053 return ar;
713} 1054 }*/
714 1055
715template<typename key, typename value> 1056 /*
716Serializer &operator>>( Serializer &ar, Hash<key,value> &h ) 1057 template<typename key, typename value>
717{ 1058 Serializer &operator&&( Serializer &ar, Hash<key,value> &h )
718 h.clear();
719 uint32_t nSize;
720 ar >> nSize;
721
722 for( uint32_t j = 0; j < nSize; j++ )
723 { 1059 {
724 key k; value v; 1060 if( ar.isLoading() )
725 ar >> k >> v; 1061 {
726 h.insert( k, v ); 1062 return ar >> h;
727 } 1063 }
728 1064 else
729 return ar; 1065 {
730} 1066 return ar << h;
731 1067 }
732template<typename key, typename value> 1068 }*/
733Serializer &operator&&( Serializer &ar, Hash<key,value> &h )
734{
735 if( ar.isLoading() )
736 {
737 return ar >> h;
738 }
739 else
740 {
741 return ar << h;
742 }
743} 1069}
744 1070
745#endif 1071#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 20:59:27 +0000