aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/set.cpp101
-rw-r--r--src/set.h399
2 files changed, 34 insertions, 466 deletions
diff --git a/src/set.cpp b/src/set.cpp
index a207c29..69f4996 100644
--- a/src/set.cpp
+++ b/src/set.cpp
@@ -1,101 +1,4 @@
1#include "hash.h" 1#include "set.h"
2 2
3namespace Bu { subExceptionDef( HashException ) } 3namespace Bu { subExceptionDef( SetException ) }
4
5template<> uint32_t Bu::__calcHashCode<int>( const int &k )
6{
7 return k;
8}
9
10template<> bool Bu::__cmpHashKeys<int>( const int &a, const int &b )
11{
12 return a == b;
13}
14
15template<> uint32_t Bu::__calcHashCode<unsigned int>( const unsigned int &k )
16{
17 return k;
18}
19
20template<> bool Bu::__cmpHashKeys<unsigned int>( const unsigned int &a, const unsigned int &b )
21{
22 return a == b;
23}
24
25template<>
26uint32_t Bu::__calcHashCode<const char *>( const char * const &k )
27{
28 if (k == NULL)
29 {
30 return 0;
31 }
32
33 unsigned long int nPos = 0;
34 for( const char *s = k; *s; s++ )
35 {
36 nPos = *s + (nPos << 6) + (nPos << 16) - nPos;
37 }
38
39 return nPos;
40}
41
42template<> bool Bu::__cmpHashKeys<const char *>( const char * const &a, const char * const &b )
43{
44 if( a == b )
45 return true;
46
47 for(int j=0; a[j] == b[j]; j++ )
48 if( a[j] == '\0' )
49 return true;
50
51 return false;
52}
53
54template<>
55uint32_t Bu::__calcHashCode<char *>( char * const &k )
56{
57 if (k == NULL)
58 {
59 return 0;
60 }
61
62 unsigned long int nPos = 0;
63 for( const char *s = k; *s; s++ )
64 {
65 nPos = *s + (nPos << 6) + (nPos << 16) - nPos;
66 }
67
68 return nPos;
69}
70
71template<> bool Bu::__cmpHashKeys<char *>( char * const &a, char * const &b )
72{
73 if( a == b )
74 return true;
75
76 for(int j=0; a[j] == b[j]; j++ )
77 if( a[j] == '\0' )
78 return true;
79
80 return false;
81}
82
83template<> uint32_t Bu::__calcHashCode<std::string>( const std::string &k )
84{
85 std::string::size_type j, sz = k.size();
86 const char *s = k.c_str();
87
88 unsigned long int nPos = 0;
89 for( j = 0; j < sz; j++, s++ )
90 {
91 nPos = *s + (nPos << 6) + (nPos << 16) - nPos;
92 }
93
94 return nPos;
95}
96
97template<> bool Bu::__cmpHashKeys<std::string>( const std::string &a, const std::string &b )
98{
99 return a == b;
100}
101 4
diff --git a/src/set.h b/src/set.h
index 36665a6..4788804 100644
--- a/src/set.h
+++ b/src/set.h
@@ -1,5 +1,5 @@
1#ifndef BU_HASH_H 1#ifndef BU_SET_H
2#define BU_HASH_H 2#define BU_SET_H
3 3
4#include <stddef.h> 4#include <stddef.h>
5#include <string.h> 5#include <string.h>
@@ -16,12 +16,7 @@
16 16
17namespace Bu 17namespace Bu
18{ 18{
19 subExceptionDecl( HashException ) 19 subExceptionDecl( SetException )
20
21 enum eHashException
22 {
23 excodeNotFilled
24 };
25 20
26 template<typename T> 21 template<typename T>
27 uint32_t __calcHashCode( const T &k ); 22 uint32_t __calcHashCode( const T &k );
@@ -29,156 +24,27 @@ namespace Bu
29 template<typename T> 24 template<typename T>
30 bool __cmpHashKeys( const T &a, const T &b ); 25 bool __cmpHashKeys( const T &a, const T &b );
31 26
32 struct __calcNextTSize_fast 27 template<typename key, typename sizecalc = struct __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename challoc = std::allocator<uint32_t> >
33 { 28 class Set;
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 };
41
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> >
43 class Hash;
44
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> >
46 struct HashProxy
47 {
48 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>;
49 private:
50 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, key *k, uint32_t nPos, uint32_t hash ) :
51 hsh( h ),
52 pKey( k ),
53 nPos( nPos ),
54 hash( hash ),
55 bFilled( false )
56 {
57 }
58
59 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) :
60 hsh( h ),
61 nPos( nPos ),
62 pValue( pValue ),
63 bFilled( true )
64 {
65 }
66
67 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
68 key *pKey;
69 uint32_t nPos;
70 _value *pValue;
71 uint32_t hash;
72 bool bFilled;
73
74 public:
75 /**
76 * Cast operator for HashProxy.
77 *@returns (value_type &) The value the HashProxy is pointing to.
78 */
79 operator _value &()
80 {
81 if( bFilled == false )
82 throw HashException(
83 excodeNotFilled,
84 "No data assosiated with that key."
85 );
86 return *pValue;
87 }
88
89 /**
90 * Direct function for retrieving a value out of the HashProxy.
91 *@returns (value_type &) The value pointed to by this HashProxy.
92 */
93 _value &value()
94 {
95 if( bFilled == false )
96 throw HashException(
97 excodeNotFilled,
98 "No data assosiated with that key."
99 );
100 return *pValue;
101 }
102
103 /**
104 * Whether this HashProxy points to something real or not.
105 */
106 bool isFilled()
107 {
108 return bFilled;
109 }
110
111 /**
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
123 /**
124 * Assign data to this point in the hash table.
125 *@param nval (value_type) the data to assign.
126 */
127 _value operator=( _value nval )
128 {
129 if( bFilled )
130 {
131 hsh.va.destroy( pValue );
132 hsh.va.construct( pValue, nval );
133 hsh.onUpdate();
134 }
135 else
136 {
137 hsh.fill( nPos, *pKey, nval, hash );
138 hsh.onInsert();
139 }
140
141 return nval;
142 }
143
144 /**
145 * Pointer extraction operator. Access to members of data pointed to
146 * by HashProxy.
147 *@returns (value_type *)
148 */
149 _value *operator->()
150 {
151 if( bFilled == false )
152 throw HashException(
153 excodeNotFilled,
154 "No data assosiated with that key."
155 );
156 return pValue;
157 }
158 };
159 29
160 /** 30 /**
161 * Libbu Template Hash Table 31 * Libbu Template Set
162 *@param key (typename) The datatype of the hashtable keys 32 *@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 33 *@param sizecalc (typename) Functor to compute new table size on rehash
165 *@param keyalloc (typename) Memory allocator for hashtable keys 34 *@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 35 *@param challoc (typename) Byte allocator for bitflags
168 */ 36 */
169 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 37 template<typename key, typename sizecalc, typename keyalloc, typename challoc >
170 class Hash 38 class Set
171 { 39 {
172 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>;
173 public: 40 public:
174 Hash() : 41 Set() :
175 nCapacity( 11 ), 42 nCapacity( 11 ),
176 nFilled( 0 ), 43 nFilled( 0 ),
177 nDeleted( 0 ), 44 nDeleted( 0 ),
178 bFilled( NULL ), 45 bFilled( NULL ),
179 bDeleted( NULL ), 46 bDeleted( NULL ),
180 aKeys( NULL ), 47 aKeys( NULL ),
181 aValues( NULL ),
182 aHashCodes( NULL ) 48 aHashCodes( NULL )
183 { 49 {
184 nKeysSize = bitsToBytes( nCapacity ); 50 nKeysSize = bitsToBytes( nCapacity );
@@ -188,17 +54,15 @@ namespace Bu
188 54
189 aHashCodes = ca.allocate( nCapacity ); 55 aHashCodes = ca.allocate( nCapacity );
190 aKeys = ka.allocate( nCapacity ); 56 aKeys = ka.allocate( nCapacity );
191 aValues = va.allocate( nCapacity );
192 } 57 }
193 58
194 Hash( const Hash &src ) : 59 Set( const Set &src ) :
195 nCapacity( src.nCapacity ), 60 nCapacity( src.nCapacity ),
196 nFilled( 0 ), 61 nFilled( 0 ),
197 nDeleted( 0 ), 62 nDeleted( 0 ),
198 bFilled( NULL ), 63 bFilled( NULL ),
199 bDeleted( NULL ), 64 bDeleted( NULL ),
200 aKeys( NULL ), 65 aKeys( NULL ),
201 aValues( NULL ),
202 aHashCodes( NULL ) 66 aHashCodes( NULL )
203 { 67 {
204 nKeysSize = bitsToBytes( nCapacity ); 68 nKeysSize = bitsToBytes( nCapacity );
@@ -208,33 +72,30 @@ namespace Bu
208 72
209 aHashCodes = ca.allocate( nCapacity ); 73 aHashCodes = ca.allocate( nCapacity );
210 aKeys = ka.allocate( nCapacity ); 74 aKeys = ka.allocate( nCapacity );
211 aValues = va.allocate( nCapacity );
212 75
213 for( uint32_t j = 0; j < src.nCapacity; j++ ) 76 for( uint32_t j = 0; j < src.nCapacity; j++ )
214 { 77 {
215 if( src.isFilled( j ) ) 78 if( src.isFilled( j ) )
216 { 79 {
217 insert( src.aKeys[j], src.aValues[j] ); 80 insert( src.aKeys[j] );
218 } 81 }
219 } 82 }
220 } 83 }
221 84
222 /** 85 /**
223 * Hashtable assignment operator. Clears this hashtable and 86 * Set assignment operator. Clears this hashtable and
224 * copies RH into it. 87 * copies RH into it.
225 */ 88 */
226 Hash &operator=( const Hash &src ) 89 Set &operator=( const Set &src )
227 { 90 {
228 for( uint32_t j = 0; j < nCapacity; j++ ) 91 for( uint32_t j = 0; j < nCapacity; j++ )
229 { 92 {
230 if( isFilled( j ) ) 93 if( isFilled( j ) )
231 if( !isDeleted( j ) ) 94 if( !isDeleted( j ) )
232 { 95 {
233 va.destroy( &aValues[j] );
234 ka.destroy( &aKeys[j] ); 96 ka.destroy( &aKeys[j] );
235 } 97 }
236 } 98 }
237 va.deallocate( aValues, nCapacity );
238 ka.deallocate( aKeys, nCapacity ); 99 ka.deallocate( aKeys, nCapacity );
239 ca.deallocate( bFilled, nKeysSize ); 100 ca.deallocate( bFilled, nKeysSize );
240 ca.deallocate( bDeleted, nKeysSize ); 101 ca.deallocate( bDeleted, nKeysSize );
@@ -250,31 +111,28 @@ namespace Bu
250 111
251 aHashCodes = ca.allocate( nCapacity ); 112 aHashCodes = ca.allocate( nCapacity );
252 aKeys = ka.allocate( nCapacity ); 113 aKeys = ka.allocate( nCapacity );
253 aValues = va.allocate( nCapacity );
254 114
255 for( uint32_t j = 0; j < src.nCapacity; j++ ) 115 for( uint32_t j = 0; j < src.nCapacity; j++ )
256 { 116 {
257 if( src.isFilled( j ) ) 117 if( src.isFilled( j ) )
258 { 118 {
259 insert( src.aKeys[j], src.aValues[j] ); 119 insert( src.aKeys[j] );
260 } 120 }
261 } 121 }
262 122
263 return *this; 123 return *this;
264 } 124 }
265 125
266 virtual ~Hash() 126 virtual ~Set()
267 { 127 {
268 for( uint32_t j = 0; j < nCapacity; j++ ) 128 for( uint32_t j = 0; j < nCapacity; j++ )
269 { 129 {
270 if( isFilled( j ) ) 130 if( isFilled( j ) )
271 if( !isDeleted( j ) ) 131 if( !isDeleted( j ) )
272 { 132 {
273 va.destroy( &aValues[j] );
274 ka.destroy( &aKeys[j] ); 133 ka.destroy( &aKeys[j] );
275 } 134 }
276 } 135 }
277 va.deallocate( aValues, nCapacity );
278 ka.deallocate( aKeys, nCapacity ); 136 ka.deallocate( aKeys, nCapacity );
279 ca.deallocate( bFilled, nKeysSize ); 137 ca.deallocate( bFilled, nKeysSize );
280 ca.deallocate( bDeleted, nKeysSize ); 138 ca.deallocate( bDeleted, nKeysSize );
@@ -320,32 +178,11 @@ namespace Bu
320 } 178 }
321 179
322 /** 180 /**
323 * Hash table index operator
324 *@param k (key_type) Key of data to be retrieved.
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 );
332
333 if( bFill )
334 {
335 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] );
336 }
337 else
338 {
339 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash );
340 }
341 }
342
343 /**
344 * Insert a value (v) under key (k) into the hash table 181 * Insert a value (v) under key (k) into the hash table
345 *@param k (key_type) Key to list the value under. 182 *@param k (key_type) Key to list the value under.
346 *@param v (value_type) Value to store in the hash table. 183 *@param v (value_type) Value to store in the hash table.
347 */ 184 */
348 virtual void insert( key k, value v ) 185 virtual void insert( key k )
349 { 186 {
350 uint32_t hash = __calcHashCode( k ); 187 uint32_t hash = __calcHashCode( k );
351 bool bFill; 188 bool bFill;
@@ -353,13 +190,11 @@ namespace Bu
353 190
354 if( bFill ) 191 if( bFill )
355 { 192 {
356 va.destroy( &aValues[nPos] );
357 va.construct( &aValues[nPos], v );
358 onUpdate(); 193 onUpdate();
359 } 194 }
360 else 195 else
361 { 196 {
362 fill( nPos, k, v, hash ); 197 fill( nPos, k, hash );
363 onInsert(); 198 onInsert();
364 } 199 }
365 } 200 }
@@ -390,7 +225,7 @@ namespace Bu
390 virtual void erase( struct iterator &i ) 225 virtual void erase( struct iterator &i )
391 { 226 {
392 if( this != &i.hsh ) 227 if( this != &i.hsh )
393 throw HashException("This iterator didn't come from this Hash."); 228 throw SetException("This iterator didn't come from this Hash.");
394 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) 229 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
395 { 230 {
396 _erase( i.nPos ); 231 _erase( i.nPos );
@@ -408,8 +243,6 @@ namespace Bu
408 if( isFilled( j ) ) 243 if( isFilled( j ) )
409 if( !isDeleted( j ) ) 244 if( !isDeleted( j ) )
410 { 245 {
411 va.destroy( &aValues[j] );
412 ka.destroy( &aKeys[j] );
413 onDelete(); 246 onDelete();
414 } 247 }
415 } 248 }
@@ -418,55 +251,6 @@ namespace Bu
418 } 251 }
419 252
420 /** 253 /**
421 * Get an item of data from the hash table.
422 *@param k (key_type) Key pointing to the data to be retrieved.
423 *@returns (value_type &) The data pointed to by (k).
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 );
430
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
451 {
452 uint32_t hash = __calcHashCode( k );
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 }
467 }
468
469 /**
470 * Does the hash table contain an item under key (k). 254 * Does the hash table contain an item under key (k).
471 *@param k (key_type) The key to check. 255 *@param k (key_type) The key to check.
472 *@returns (bool) Whether there was an item in the hash under key (k). 256 *@returns (bool) Whether there was an item in the hash under key (k).
@@ -484,9 +268,9 @@ namespace Bu
484 */ 268 */
485 typedef struct iterator 269 typedef struct iterator
486 { 270 {
487 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 271 friend class Set<key, sizecalc, keyalloc, challoc>;
488 private: 272 private:
489 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) : 273 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh ) :
490 hsh( hsh ), 274 hsh( hsh ),
491 nPos( 0 ), 275 nPos( 0 ),
492 bFinished( false ) 276 bFinished( false )
@@ -494,14 +278,14 @@ namespace Bu
494 nPos = hsh.getFirstPos( bFinished ); 278 nPos = hsh.getFirstPos( bFinished );
495 } 279 }
496 280
497 iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) : 281 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
498 hsh( hsh ), 282 hsh( hsh ),
499 nPos( 0 ), 283 nPos( 0 ),
500 bFinished( bDone ) 284 bFinished( bDone )
501 { 285 {
502 } 286 }
503 287
504 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 288 Set<key, sizecalc, keyalloc, challoc> &hsh;
505 uint32_t nPos; 289 uint32_t nPos;
506 bool bFinished; 290 bool bFinished;
507 291
@@ -561,7 +345,7 @@ namespace Bu
561 iterator operator=( const iterator &oth ) 345 iterator operator=( const iterator &oth )
562 { 346 {
563 if( &hsh != &oth.hsh ) 347 if( &hsh != &oth.hsh )
564 throw HashException( 348 throw SetException(
565 "Cannot mix iterators from different hash objects."); 349 "Cannot mix iterators from different hash objects.");
566 nPos = oth.nPos; 350 nPos = oth.nPos;
567 bFinished = oth.bFinished; 351 bFinished = oth.bFinished;
@@ -571,28 +355,10 @@ namespace Bu
571 * Iterator dereference operator... err.. get the value 355 * Iterator dereference operator... err.. get the value
572 *@returns (value_type &) The value behind this iterator. 356 *@returns (value_type &) The value behind this iterator.
573 */ 357 */
574 value &operator *() 358 key &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 { 359 {
585 return hsh.getKeyAtPos( nPos ); 360 return hsh.getKeyAtPos( nPos );
586 } 361 }
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 }; 362 };
597 363
598 /** 364 /**
@@ -600,9 +366,9 @@ namespace Bu
600 */ 366 */
601 typedef struct const_iterator 367 typedef struct const_iterator
602 { 368 {
603 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 369 friend class Set<key, sizecalc, keyalloc, challoc>;
604 private: 370 private:
605 const_iterator( const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) : 371 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh ) :
606 hsh( hsh ), 372 hsh( hsh ),
607 nPos( 0 ), 373 nPos( 0 ),
608 bFinished( false ) 374 bFinished( false )
@@ -610,14 +376,14 @@ namespace Bu
610 nPos = hsh.getFirstPos( bFinished ); 376 nPos = hsh.getFirstPos( bFinished );
611 } 377 }
612 378
613 const_iterator( const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) : 379 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
614 hsh( hsh ), 380 hsh( hsh ),
615 nPos( 0 ), 381 nPos( 0 ),
616 bFinished( bDone ) 382 bFinished( bDone )
617 { 383 {
618 } 384 }
619 385
620 const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 386 const Set<key, sizecalc, keyalloc, challoc> &hsh;
621 uint32_t nPos; 387 uint32_t nPos;
622 bool bFinished; 388 bool bFinished;
623 389
@@ -677,7 +443,7 @@ namespace Bu
677 const_iterator operator=( const const_iterator &oth ) 443 const_iterator operator=( const const_iterator &oth )
678 { 444 {
679 if( &hsh != &oth.hsh ) 445 if( &hsh != &oth.hsh )
680 throw HashException( 446 throw SetException(
681 "Cannot mix iterators from different hash objects."); 447 "Cannot mix iterators from different hash objects.");
682 nPos = oth.nPos; 448 nPos = oth.nPos;
683 bFinished = oth.bFinished; 449 bFinished = oth.bFinished;
@@ -687,28 +453,10 @@ namespace Bu
687 * Iterator dereference operator... err.. get the value 453 * Iterator dereference operator... err.. get the value
688 *@returns (value_type &) The value behind this iterator. 454 *@returns (value_type &) The value behind this iterator.
689 */ 455 */
690 const value &operator *() const 456 const key &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 { 457 {
701 return hsh.getKeyAtPos( nPos ); 458 return hsh.getKeyAtPos( nPos );
702 } 459 }
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 }; 460 };
713 461
714 /** 462 /**
@@ -778,10 +526,9 @@ namespace Bu
778 } 526 }
779 } 527 }
780 528
781 virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash ) 529 virtual void fill( uint32_t loc, key &k, uint32_t hash )
782 { 530 {
783 bFilled[loc/32] |= (1<<(loc%32)); 531 bFilled[loc/32] |= (1<<(loc%32));
784 va.construct( &aValues[loc], v );
785 ka.construct( &aKeys[loc], k ); 532 ka.construct( &aKeys[loc], k );
786 aHashCodes[loc] = hash; 533 aHashCodes[loc] = hash;
787 nFilled++; 534 nFilled++;
@@ -792,18 +539,12 @@ namespace Bu
792 virtual void _erase( uint32_t loc ) 539 virtual void _erase( uint32_t loc )
793 { 540 {
794 bDeleted[loc/32] |= (1<<(loc%32)); 541 bDeleted[loc/32] |= (1<<(loc%32));
795 va.destroy( &aValues[loc] );
796 ka.destroy( &aKeys[loc] ); 542 ka.destroy( &aKeys[loc] );
797 nDeleted++; 543 nDeleted++;
798 //printf("Filled: %d, Deleted: %d, Capacity: %d\n", 544 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
799 // nFilled, nDeleted, nCapacity ); 545 // nFilled, nDeleted, nCapacity );
800 } 546 }
801 547
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 ) 548 virtual key &getKeyAtPos( uint32_t nPos )
808 { 549 {
809 return aKeys[nPos]; 550 return aKeys[nPos];
@@ -814,16 +555,6 @@ namespace Bu
814 return aKeys[nPos]; 555 return aKeys[nPos];
815 } 556 }
816 557
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];
825 }
826
827 virtual uint32_t getFirstPos( bool &bFinished ) const 558 virtual uint32_t getFirstPos( bool &bFinished ) const
828 { 559 {
829 for( uint32_t j = 0; j < nCapacity; j++ ) 560 for( uint32_t j = 0; j < nCapacity; j++ )
@@ -938,7 +669,6 @@ namespace Bu
938 uint32_t *aOldHashCodes = aHashCodes; 669 uint32_t *aOldHashCodes = aHashCodes;
939 uint32_t nOldKeysSize = nKeysSize; 670 uint32_t nOldKeysSize = nKeysSize;
940 uint32_t *bOldDeleted = bDeleted; 671 uint32_t *bOldDeleted = bDeleted;
941 value *aOldValues = aValues;
942 key *aOldKeys = aKeys; 672 key *aOldKeys = aKeys;
943 673
944 // Calculate new sizes 674 // Calculate new sizes
@@ -952,7 +682,6 @@ namespace Bu
952 682
953 aHashCodes = ca.allocate( nCapacity ); 683 aHashCodes = ca.allocate( nCapacity );
954 aKeys = ka.allocate( nCapacity ); 684 aKeys = ka.allocate( nCapacity );
955 aValues = va.allocate( nCapacity );
956 685
957 nDeleted = nFilled = 0; 686 nDeleted = nFilled = 0;
958 687
@@ -962,7 +691,7 @@ namespace Bu
962 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 691 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
963 (bOldDeleted[j/32]&(1<<(j%32)))==0 ) 692 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
964 { 693 {
965 insert( aOldKeys[j], aOldValues[j] ); 694 insert( aOldKeys[j] );
966 } 695 }
967 } 696 }
968 697
@@ -971,11 +700,9 @@ namespace Bu
971 { 700 {
972 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 ) 701 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
973 { 702 {
974 va.destroy( &aOldValues[j] );
975 ka.destroy( &aOldKeys[j] ); 703 ka.destroy( &aOldKeys[j] );
976 } 704 }
977 } 705 }
978 va.deallocate( aOldValues, nOldCapacity );
979 ka.deallocate( aOldKeys, nOldCapacity ); 706 ka.deallocate( aOldKeys, nOldCapacity );
980 ca.deallocate( bOldFilled, nOldKeysSize ); 707 ca.deallocate( bOldFilled, nOldKeysSize );
981 ca.deallocate( bOldDeleted, nOldKeysSize ); 708 ca.deallocate( bOldDeleted, nOldKeysSize );
@@ -1000,73 +727,11 @@ namespace Bu
1000 uint32_t *bDeleted; 727 uint32_t *bDeleted;
1001 uint32_t nKeysSize; 728 uint32_t nKeysSize;
1002 key *aKeys; 729 key *aKeys;
1003 value *aValues;
1004 uint32_t *aHashCodes; 730 uint32_t *aHashCodes;
1005 valuealloc va;
1006 keyalloc ka; 731 keyalloc ka;
1007 challoc ca; 732 challoc ca;
1008 sizecalc szCalc; 733 sizecalc szCalc;
1009 }; 734 };
1010
1011 template<> uint32_t __calcHashCode<int>( const int &k );
1012 template<> bool __cmpHashKeys<int>( const int &a, const int &b );
1013
1014 template<> uint32_t __calcHashCode<unsigned int>( const unsigned int &k );
1015 template<> bool __cmpHashKeys<unsigned int>( const unsigned int &a, const unsigned int &b );
1016
1017 template<> uint32_t __calcHashCode<const char *>( const char * const &k );
1018 template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
1019
1020 template<> uint32_t __calcHashCode<char *>( char * const &k );
1021 template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
1022
1023 template<> uint32_t __calcHashCode<std::string>( const std::string &k );
1024 template<> bool __cmpHashKeys<std::string>( const std::string &a, const std::string &b );
1025
1026 /*
1027 template<typename key, typename value>
1028 Archive &operator<<( Archive &ar, Hash<key,value> &h )
1029 {
1030 ar << h.size();
1031 for( typename Hash<key,value>::iterator i = h.begin(); i != h.end(); i++ )
1032 {
1033 std::pair<key,value> p = *i;
1034 ar << p.first << p.second;
1035 }
1036
1037 return ar;
1038 }
1039
1040 template<typename key, typename value>
1041 Archive &operator>>( Archive &ar, Hash<key,value> &h )
1042 {
1043 h.clear();
1044 uint32_t nSize;
1045 ar >> nSize;
1046
1047 for( uint32_t j = 0; j < nSize; j++ )
1048 {
1049 key k; value v;
1050 ar >> k >> v;
1051 h.insert( k, v );
1052 }
1053
1054 return ar;
1055 }*/
1056
1057 /*
1058 template<typename key, typename value>
1059 Serializer &operator&&( Serializer &ar, Hash<key,value> &h )
1060 {
1061 if( ar.isLoading() )
1062 {
1063 return ar >> h;
1064 }
1065 else
1066 {
1067 return ar << h;
1068 }
1069 }*/
1070} 735}
1071 736
1072#endif 737#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 10:44:53 +0000