aboutsummaryrefslogtreecommitdiff
path: root/src/stable/hash.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2012-03-25 20:00:08 +0000
committerMike Buland <eichlan@xagasoft.com>2012-03-25 20:00:08 +0000
commit469bbcf0701e1eb8a6670c23145b0da87357e178 (patch)
treeb5b062a16e46a6c5d3410b4e574cd0cc09057211 /src/stable/hash.h
parentee1b79396076edc4e30aefb285fada03bb45e80d (diff)
downloadlibbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.gz
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.bz2
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.xz
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.zip
Code is all reorganized. We're about ready to release. I should write up a
little explenation of the arrangement.
Diffstat (limited to 'src/stable/hash.h')
-rw-r--r--src/stable/hash.h1306
1 files changed, 1306 insertions, 0 deletions
diff --git a/src/stable/hash.h b/src/stable/hash.h
new file mode 100644
index 0000000..71aec73
--- /dev/null
+++ b/src/stable/hash.h
@@ -0,0 +1,1306 @@
1/*
2 * Copyright (C) 2007-2011 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_HASH_H
9#define BU_HASH_H
10
11#include <memory>
12#include "bu/exceptionbase.h"
13#include "bu/list.h"
14#include "bu/util.h"
15#include "bu/archivebase.h"
16#include "bu/sharedcore.h"
17
18namespace Bu
19{
20 subExceptionDecl( HashException )
21
22 enum eHashException
23 {
24 excodeNotFilled
25 };
26
27 template<typename T>
28 uint32_t __calcHashCode( const T &k );
29
30 template<typename T>
31 bool __cmpHashKeys( const T &a, const T &b );
32
33 /**
34 * Default functor used to compute the size of hash tables. This version
35 * effectively doubles the size of the table when space is low, ensuring
36 * that you always wind up with an odd number for the table size. A
37 * better but slower option is to always find the next prime number that's
38 * above double your current table size, but that has the potential to be
39 * slower.
40 */
41 struct __calcNextTSize_fast
42 {
43 uint32_t operator()( uint32_t nCapacity, uint32_t nFilled,
44 uint32_t nDeleted ) const
45 {
46 // This frist case will allow hashtables that are mostly deleted
47 // items to reset to small allocations
48 if( nFilled-nDeleted <= nCapacity/4 )
49 {
50 nCapacity = 11;
51 while( nCapacity < nFilled*5/4 )
52 nCapacity = nCapacity*2+1;
53 return nCapacity;
54 }
55 // This will hopefully prevent hash tables from growing needlessly
56 if( nFilled-nDeleted <= nCapacity/2 )
57 return nCapacity;
58 // Otherwise, just increase the capacity
59 return nCapacity*2+1;
60 }
61 };
62
63 template<typename totype>
64 int bitsTo( int iCount )
65 {
66 return ( (iCount/(sizeof(totype)*8))
67 + (iCount%(sizeof(totype)*8)>0 ? 1 : 0));
68 }
69
70 template<typename key, typename value, typename sizecalc, typename keyalloc,
71 typename valuealloc, typename challoc>
72 class Hash;
73
74 /** @cond DEVEL */
75 template<typename key, typename value, typename sizecalc, typename keyalloc,
76 typename valuealloc, typename challoc >
77 class HashCore
78 {
79 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
80 friend class SharedCore<
81 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
82 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
83 >;
84 private:
85 HashCore() :
86 nCapacity( 0 ),
87 nFilled( 0 ),
88 nDeleted( 0 ),
89 bFilled( NULL ),
90 bDeleted( NULL ),
91 aKeys( NULL ),
92 aValues( NULL ),
93 aHashCodes( NULL )
94 {
95 }
96
97 virtual ~HashCore()
98 {
99 clear();
100 }
101
102 void init()
103 {
104 if( nCapacity > 0 )
105 return;
106
107 nCapacity = 11;
108 nKeysSize = bitsTo<uint32_t>( nCapacity );
109 bFilled = ca.allocate( nKeysSize );
110 bDeleted = ca.allocate( nKeysSize );
111 clearBits();
112
113 aHashCodes = ca.allocate( nCapacity );
114 aKeys = ka.allocate( nCapacity );
115 aValues = va.allocate( nCapacity );
116 }
117
118 void clearBits()
119 {
120 if( nCapacity == 0 )
121 return;
122
123 for( uint32_t j = 0; j < nKeysSize; j++ )
124 {
125 bFilled[j] = bDeleted[j] = 0;
126 }
127 }
128
129 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
130 {
131 init();
132
133 bFilled[loc/32] |= (1<<(loc%32));
134 va.construct( &aValues[loc], v );
135 ka.construct( &aKeys[loc], k );
136 aHashCodes[loc] = hash;
137 nFilled++;
138 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
139 // nFilled, nDeleted, nCapacity );
140 }
141
142 void _erase( uint32_t loc )
143 {
144 if( nCapacity == 0 )
145 return;
146
147 bDeleted[loc/32] |= (1<<(loc%32));
148 va.destroy( &aValues[loc] );
149 ka.destroy( &aKeys[loc] );
150 nDeleted++;
151 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
152 // nFilled, nDeleted, nCapacity );
153 }
154
155 key &getKeyAtPos( uint32_t nPos )
156 {
157 if( nPos >= nCapacity )
158 throw HashException("Referenced position invalid.");
159 return aKeys[nPos];
160 }
161
162 const key &getKeyAtPos( uint32_t nPos ) const
163 {
164 if( nPos >= nCapacity )
165 throw HashException("Referenced position invalid.");
166 return aKeys[nPos];
167 }
168
169 value &getValueAtPos( uint32_t nPos )
170 {
171 if( nPos >= nCapacity )
172 throw HashException("Referenced position invalid.");
173 return aValues[nPos];
174 }
175
176 const value &getValueAtPos( uint32_t nPos ) const
177 {
178 if( nPos >= nCapacity )
179 throw HashException("Referenced position invalid.");
180 return aValues[nPos];
181 }
182
183 uint32_t getFirstPos( bool &bFinished ) const
184 {
185 for( uint32_t j = 0; j < nCapacity; j++ )
186 {
187 if( isFilled( j ) )
188 if( !isDeleted( j ) )
189 return j;
190 }
191
192 bFinished = true;
193 return 0;
194 }
195
196 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
197 {
198 for( uint32_t j = nPos+1; j < nCapacity; j++ )
199 {
200 if( isFilled( j ) )
201 if( !isDeleted( j ) )
202 return j;
203 }
204
205 bFinished = true;
206 return 0;
207 }
208
209 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
210 {
211 init();
212
213 uint32_t nCur = hash%nCapacity;
214
215 // First we scan to see if the key is already there, abort if we
216 // run out of probing room, or we find a non-filled entry
217 int8_t j;
218 for( j = 0;
219 isFilled( nCur ) && j < 32;
220 nCur = (nCur + (1<<j))%nCapacity, j++
221 )
222 {
223 // Is this the same hash code we were looking for?
224 if( hash == aHashCodes[nCur] )
225 {
226 // Skip over deleted entries. Deleted entries are also filled,
227 // so we only have to do this check here.
228 if( isDeleted( nCur ) )
229 continue;
230
231 // Is it really the same key? (for safety)
232 if( __cmpHashKeys( aKeys[nCur], k ) == true )
233 {
234 bFill = true;
235 return nCur;
236 }
237 }
238 }
239
240 // This is our insurance, if the table is full, then go ahead and
241 // rehash, then try again.
242 if( (isFilled( nCur ) || j == 32) && rehash == true )
243 {
244 reHash( szCalc( nCapacity, nFilled, nDeleted ) );
245
246 // This is potentially dangerous, and could cause an infinite loop.
247 // Be careful writing probe, eh?
248 return probe( hash, k, bFill );
249 }
250
251 bFill = false;
252 return nCur;
253 }
254
255 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
256 {
257 if( nCapacity == 0 )
258 throw Bu::ExceptionBase("Probe in empty hash table.");
259
260 uint32_t nCur = hash%nCapacity;
261
262 // First we scan to see if the key is already there, abort if we
263 // run out of probing room, or we find a non-filled entry
264 for( int8_t j = 0;
265 isFilled( nCur ) && j < 32;
266 nCur = (nCur + (1<<j))%nCapacity, j++
267 )
268 {
269 // Is this the same hash code we were looking for?
270 if( hash == aHashCodes[nCur] )
271 {
272 // Skip over deleted entries. Deleted entries are also filled,
273 // so we only have to do this check here.
274 if( isDeleted( nCur ) )
275 continue;
276
277 // Is it really the same key? (for safety)
278 if( __cmpHashKeys( aKeys[nCur], k ) == true )
279 {
280 bFill = true;
281 return nCur;
282 }
283 }
284 }
285
286 bFill = false;
287 return nCur;
288 }
289
290 void insert( const key &k, const value &v )
291 {
292 uint32_t hash = __calcHashCode( k );
293 bool bFill;
294 uint32_t nPos = probe( hash, k, bFill );
295
296 if( bFill )
297 {
298 va.destroy( &aValues[nPos] );
299 va.construct( &aValues[nPos], v );
300 }
301 else
302 {
303 fill( nPos, k, v, hash );
304 }
305 }
306
307 void reHash( uint32_t nNewSize )
308 {
309 //printf("---REHASH---");
310 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
311 // nFilled, nDeleted, nCapacity );
312
313 // Save all the old data
314 uint32_t nOldCapacity = nCapacity;
315 uint32_t *bOldFilled = bFilled;
316 uint32_t *aOldHashCodes = aHashCodes;
317 uint32_t nOldKeysSize = nKeysSize;
318 uint32_t *bOldDeleted = bDeleted;
319 value *aOldValues = aValues;
320 key *aOldKeys = aKeys;
321
322 // Calculate new sizes
323 nCapacity = nNewSize;
324 nKeysSize = bitsTo<uint32_t>( nCapacity );
325
326 // Allocate new memory + prep
327 bFilled = ca.allocate( nKeysSize );
328 bDeleted = ca.allocate( nKeysSize );
329 clearBits();
330
331 aHashCodes = ca.allocate( nCapacity );
332 aKeys = ka.allocate( nCapacity );
333 aValues = va.allocate( nCapacity );
334
335 nDeleted = nFilled = 0;
336
337 // Re-insert all of the old data (except deleted items)
338 for( uint32_t j = 0; j < nOldCapacity; j++ )
339 {
340 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
341 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
342 {
343 insert( aOldKeys[j], aOldValues[j] );
344 }
345 }
346
347 // Delete all of the old data
348 for( uint32_t j = 0; j < nOldCapacity; j++ )
349 {
350 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
351 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
352 {
353 va.destroy( &aOldValues[j] );
354 ka.destroy( &aOldKeys[j] );
355 }
356 }
357 va.deallocate( aOldValues, nOldCapacity );
358 ka.deallocate( aOldKeys, nOldCapacity );
359 ca.deallocate( bOldFilled, nOldKeysSize );
360 ca.deallocate( bOldDeleted, nOldKeysSize );
361 ca.deallocate( aOldHashCodes, nOldCapacity );
362 }
363
364 bool isFilled( uint32_t loc ) const
365 {
366 if( loc >= nCapacity )
367 throw HashException("Referenced position invalid.");
368 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
369 }
370
371 bool isDeleted( uint32_t loc ) const
372 {
373 if( loc >= nCapacity )
374 throw HashException("Referenced position invalid.");
375 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
376 }
377
378 void clear()
379 {
380 for( uint32_t j = 0; j < nCapacity; j++ )
381 {
382 if( isFilled( j ) )
383 if( !isDeleted( j ) )
384 {
385 va.destroy( &aValues[j] );
386 ka.destroy( &aKeys[j] );
387 }
388 }
389 va.deallocate( aValues, nCapacity );
390 ka.deallocate( aKeys, nCapacity );
391 ca.deallocate( bFilled, nKeysSize );
392 ca.deallocate( bDeleted, nKeysSize );
393 ca.deallocate( aHashCodes, nCapacity );
394
395 bFilled = NULL;
396 bDeleted = NULL;
397 aKeys = NULL;
398 aValues = NULL;
399 aHashCodes = NULL;
400
401 nCapacity = 0;
402 nFilled = 0;
403 nDeleted = 0;
404 }
405
406 uint32_t nCapacity;
407 uint32_t nFilled;
408 uint32_t nDeleted;
409 uint32_t *bFilled;
410 uint32_t *bDeleted;
411 uint32_t nKeysSize;
412 key *aKeys;
413 value *aValues;
414 uint32_t *aHashCodes;
415 valuealloc va;
416 keyalloc ka;
417 challoc ca;
418 sizecalc szCalc;
419 };
420 /** @endcond */
421
422 /**
423 * Libbu++ Template Hash Table. This is your average hash table, that uses
424 * template functions in order to do fast, efficient, generalized hashing.
425 * It's pretty easy to use, and works well with all other libbu++ types so
426 * far.
427 *
428 * In order to use it, I recommend the following for all basic usage:
429 *@code
430 // Define a Hash typedef with strings as keys and ints as values.
431 typedef Bu::Hash<Bu::String, int> StrIntHash;
432
433 // Create one
434 StrIntHash hInts;
435
436 // Insert some integers
437 hInts["one"] = 1;
438 hInts["forty-two"] = 42;
439 hInts.insert("forty two", 42 );
440
441 // Get values out of the hash, the last two options are the most explicit,
442 // and must be used if the hash's value type does not match what you're
443 // comparing to exactly.
444 if( hInts["one"] == 1 ) doSomething();
445 if( hInts["forty-two"].value() == 42 ) doSomething();
446 if( hInts.get("forty two") == 42 ) doSomething();
447
448 // Iterate through the Hash
449 for( StrIntHash::iterator i = hInts.begin(); i != hInts.end(); i++ )
450 {
451 // i.getValue() works too
452 print("'%s' = %d\n", i.getKey().getStr(), (*i) );
453 }
454
455 @endcode
456 *@param key (typename) The datatype of the hashtable keys
457 *@param value (typename) The datatype of the hashtable data
458 *@param sizecalc (typename) Functor to compute new table size on rehash
459 *@param keyalloc (typename) Memory allocator for hashtable keys
460 *@param valuealloc (typename) Memory allocator for hashtable values
461 *@param challoc (typename) Byte allocator for bitflags
462 *@ingroup Containers
463 */
464 template<typename key, typename value,
465 typename sizecalc = __calcNextTSize_fast,
466 typename keyalloc = std::allocator<key>,
467 typename valuealloc = std::allocator<value>,
468 typename challoc = std::allocator<uint32_t>
469 >
470 class Hash : public SharedCore<
471 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
472 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
473 >
474 {
475 private:
476 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core;
477 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType;
478 protected:
479 using SharedCore<MyType, Core>::core;
480 using SharedCore<MyType, Core>::_hardCopy;
481 using SharedCore<MyType, Core>::_resetCore;
482 using SharedCore<MyType, Core>::_allocateCore;
483
484 public:
485 Hash()
486 {
487 }
488
489 Hash( const MyType &src ) :
490 SharedCore<MyType, Core >( src )
491 {
492 }
493
494 virtual ~Hash()
495 {
496 }
497
498 /**
499 * Get the current hash table capacity. (Changes at re-hash)
500 *@returns (uint32_t) The current capacity.
501 */
502 uint32_t getCapacity() const
503 {
504 return core->nCapacity;
505 }
506
507 /**
508 * Get the number of hash locations spoken for. (Including
509 * not-yet-cleaned-up deleted items.)
510 *@returns (uint32_t) The current fill state.
511 */
512 uint32_t getFill() const
513 {
514 return core->nFilled;
515 }
516
517 /**
518 * Get the number of items stored in the hash table.
519 *@returns (uint32_t) The number of items stored in the hash table.
520 */
521 uint32_t getSize() const
522 {
523 return core->nFilled-core->nDeleted;
524 }
525
526 bool isEmpty() const
527 {
528 return (core->nFilled-core->nDeleted) == 0;
529 }
530
531 /**
532 * Get the number of items which have been deleted, but not yet
533 * cleaned up.
534 *@returns (uint32_t) The number of deleted items.
535 */
536 uint32_t getDeleted() const
537 {
538 return core->nDeleted;
539 }
540
541 struct HashProxy
542 {
543 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
544 private:
545 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) :
546 hsh( h ),
547 pKey( k ),
548 nPos( nPos ),
549 hash( hash ),
550 bFilled( false )
551 {
552 }
553
554 HashProxy( MyType &h, uint32_t nPos, value *pValue ) :
555 hsh( h ),
556 nPos( nPos ),
557 pValue( pValue ),
558 bFilled( true )
559 {
560 }
561
562 MyType &hsh;
563 const key *pKey;
564 uint32_t nPos;
565 value *pValue;
566 uint32_t hash;
567 bool bFilled;
568
569 public:
570 /**
571 * Cast operator for HashProxy.
572 *@returns (value_type &) The value the HashProxy is pointing to.
573 */
574 operator value &()
575 {
576 if( bFilled == false )
577 throw HashException(
578 excodeNotFilled,
579 "No data assosiated with that key."
580 );
581 return *pValue;
582 }
583
584 /**
585 * Direct function for retrieving a value out of the HashProxy.
586 *@returns (value_type &) The value pointed to by this HashProxy.
587 */
588 value &getValue()
589 {
590 if( bFilled == false )
591 throw HashException(
592 excodeNotFilled,
593 "No data assosiated with that key."
594 );
595 return *pValue;
596 }
597
598 /**
599 * Whether this HashProxy points to something real or not.
600 */
601 bool isFilled()
602 {
603 return bFilled;
604 }
605
606 /**
607 * Erase the data pointed to by this HashProxy.
608 */
609 void erase()
610 {
611 if( bFilled )
612 {
613 hsh.core->_erase( nPos );
614 }
615 }
616
617 /**
618 * Assign data to this point in the hash table.
619 *@param nval (value_type) the data to assign.
620 */
621 value operator=( value nval )
622 {
623 if( bFilled )
624 {
625 hsh.core->va.destroy( &hsh.core->aValues[nPos] );
626 hsh.core->va.construct( &hsh.core->aValues[nPos], nval );
627 }
628 else
629 {
630 hsh.core->fill( nPos, *pKey, nval, hash );
631 }
632
633 return nval;
634 }
635
636 /**
637 * Pointer extraction operator. Access to members of data pointed to
638 * by HashProxy.
639 *@returns (value_type *)
640 */
641 value *operator->()
642 {
643 if( bFilled == false )
644 throw HashException(
645 excodeNotFilled,
646 "No data assosiated with that key."
647 );
648 return pValue;
649 }
650 };
651
652 /**
653 * Hash table index operator
654 *@param k (key_type) Key of data to be retrieved.
655 *@returns (HashProxy) Proxy pointing to the data.
656 */
657 HashProxy operator[]( const key &k )
658 {
659 _hardCopy();
660
661 uint32_t hash = __calcHashCode( k );
662 bool bFill;
663 uint32_t nPos = core->probe( hash, k, bFill );
664
665 if( bFill )
666 {
667 return HashProxy( *this, nPos, &core->aValues[nPos] );
668 }
669 else
670 {
671 return HashProxy( *this, &k, nPos, hash );
672 }
673 }
674
675 /**
676 * Insert a value (v) under key (k) into the hash table
677 *@param k (key_type) Key to list the value under.
678 *@param v (value_type) Value to store in the hash table.
679 */
680 void insert( const key &k, const value &v )
681 {
682 _hardCopy();
683
684 core->insert( k, v );
685 }
686
687 /**
688 * Remove a value from the hash table.
689 *@param k (key_type) The data under this key will be erased.
690 */
691 void erase( const key &k )
692 {
693 _hardCopy();
694
695 uint32_t hash = __calcHashCode( k );
696 bool bFill;
697 uint32_t nPos = core->probe( hash, k, bFill );
698
699 if( bFill )
700 {
701 core->_erase( nPos );
702 }
703 }
704
705 struct iterator;
706
707 /**
708 * Remove a value from the hash pointed to from an iterator.
709 *@param i (iterator &) The data to be erased.
710 */
711 void erase( struct iterator &i )
712 {
713 if( this != i.hsh )
714 throw HashException("This iterator didn't come from this Hash.");
715
716 _hardCopy();
717
718 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) )
719 {
720 core->_erase( i.nPos );
721 }
722 }
723
724 /**
725 * Remove all data from the hash table.
726 */
727 virtual void clear()
728 {
729 _resetCore();
730 }
731
732 /**
733 * Get an item of data from the hash table.
734 *@param k (key_type) Key pointing to the data to be retrieved.
735 *@returns (value_type &) The data pointed to by (k).
736 */
737 value &get( const key &k )
738 {
739 _hardCopy();
740
741 uint32_t hash = __calcHashCode( k );
742 bool bFill;
743 uint32_t nPos = core->probe( hash, k, bFill, false );
744
745 if( bFill )
746 {
747 return core->aValues[nPos];
748 }
749 else
750 {
751 throw HashException(
752 excodeNotFilled,
753 "No data assosiated with that key."
754 );
755 }
756 }
757
758 /**
759 * Get a const item of data from the hash table.
760 *@param k (key_type) Key pointing to the data to be retrieved.
761 *@returns (const value_type &) A const version of the data pointed
762 * to by (k).
763 */
764 const value &get( const key &k ) const
765 {
766 uint32_t hash = __calcHashCode( k );
767 bool bFill;
768 uint32_t nPos = core->probe( hash, k, bFill );
769
770 if( bFill )
771 {
772 return core->aValues[nPos];
773 }
774 else
775 {
776 throw HashException(
777 excodeNotFilled,
778 "No data assosiated with that key."
779 );
780 }
781 }
782
783 /**
784 * Does the hash table contain an item under key (k).
785 *@param k (key_type) The key to check.
786 *@returns (bool) Whether there was an item in the hash under key (k).
787 */
788 bool has( const key &k ) const
789 {
790 bool bFill;
791 core->probe( __calcHashCode( k ), k, bFill );
792
793 return bFill;
794 }
795
796 /**
797 * Iteration structure for iterating through the hash.
798 */
799 typedef struct iterator
800 {
801 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
802 private:
803 iterator( MyType *hsh ) :
804 hsh( hsh ),
805 nPos( 0 ),
806 bFinished( false )
807 {
808 nPos = hsh->core->getFirstPos( bFinished );
809 }
810
811 iterator( MyType *hsh, bool bDone ) :
812 hsh( hsh ),
813 nPos( 0 ),
814 bFinished( bDone )
815 {
816 }
817
818 MyType *hsh;
819 uint32_t nPos;
820 bool bFinished;
821
822 public:
823 iterator( const iterator &i ) :
824 hsh( i.hsh ),
825 nPos( i.nPos ),
826 bFinished( i.bFinished )
827 {
828 }
829
830 iterator() :
831 hsh( NULL ),
832 nPos( NULL ),
833 bFinished( true )
834 {
835 }
836
837 bool isValid() const
838 {
839 return !bFinished;
840 }
841
842 operator bool() const
843 {
844 return !bFinished;
845 }
846
847 /**
848 * Iterator incrementation operator. Move the iterator forward.
849 */
850 iterator operator++( int )
851 {
852 if( bFinished == false )
853 nPos = hsh->core->getNextPos( nPos, bFinished );
854
855 return *this;
856 }
857
858 /**
859 * Iterator incrementation operator. Move the iterator forward.
860 */
861 iterator operator++()
862 {
863 if( bFinished == false )
864 nPos = hsh->core->getNextPos( nPos, bFinished );
865
866 return *this;
867 }
868
869 /**
870 * Iterator equality comparison operator. Iterators the same?
871 */
872 bool operator==( const iterator &oth ) const
873 {
874 if( bFinished != oth.bFinished )
875 return false;
876 if( bFinished == true )
877 {
878 return true;
879 }
880 else
881 {
882 if( oth.nPos == nPos )
883 return true;
884 return false;
885 }
886 }
887
888 /**
889 * Iterator not equality comparison operator. Not the same?
890 */
891 bool operator!=( const iterator &oth ) const
892 {
893 return !(*this == oth );
894 }
895
896 /**
897 * Iterator assignment operator.
898 */
899 iterator operator=( const iterator &oth )
900 {
901 hsh = oth.hsh;
902 nPos = oth.nPos;
903 bFinished = oth.bFinished;
904 return *this;
905 }
906
907 /**
908 * Iterator dereference operator... err.. get the value
909 *@returns (value_type &) The value behind this iterator.
910 */
911 value &operator *()
912 {
913 hsh->_hardCopy();
914 return hsh->core->getValueAtPos( nPos );
915 }
916
917 const value &operator *() const
918 {
919 return hsh->core->getValueAtPos( nPos );
920 }
921
922 /**
923 * Get the key behind this iterator.
924 *@returns (key_type &) The key behind this iterator.
925 */
926 const key &getKey() const
927 {
928 return hsh->core->getKeyAtPos( nPos );
929 }
930
931 /**
932 * Get the value behind this iterator.
933 *@returns (value_type &) The value behind this iterator.
934 */
935 value &getValue()
936 {
937 hsh->_hardCopy();
938 return hsh->core->getValueAtPos( nPos );
939 }
940
941 /**
942 * Get the value behind this iterator.
943 *@returns (value_type &) The value behind this iterator.
944 */
945 const value &getValue() const
946 {
947 return hsh->core->getValueAtPos( nPos );
948 }
949 } iterator;
950
951 /**
952 * Iteration structure for iterating through the hash (const).
953 */
954 typedef struct const_iterator
955 {
956 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
957 private:
958 const_iterator( const MyType *hsh ) :
959 hsh( hsh ),
960 nPos( 0 ),
961 bFinished( false )
962 {
963 nPos = hsh->core->getFirstPos( bFinished );
964 }
965
966 const_iterator( const MyType *hsh, bool bDone ) :
967 hsh( hsh ),
968 nPos( 0 ),
969 bFinished( bDone )
970 {
971 }
972
973 const MyType *hsh;
974 uint32_t nPos;
975 bool bFinished;
976
977 public:
978 const_iterator() :
979 hsh( NULL ),
980 nPos( 0 ),
981 bFinished( true )
982 {
983 }
984
985 const_iterator( const const_iterator &src ) :
986 hsh( src.hsh ),
987 nPos( src.nPos ),
988 bFinished( src.bFinished )
989 {
990 }
991
992 const_iterator( const iterator &src ) :
993 hsh( src.hsh ),
994 nPos( src.nPos ),
995 bFinished( src.bFinished )
996 {
997 }
998
999 bool isValid() const
1000 {
1001 return !bFinished;
1002 }
1003
1004 operator bool() const
1005 {
1006 return !bFinished;
1007 }
1008
1009 /**
1010 * Iterator incrementation operator. Move the iterator forward.
1011 */
1012 const_iterator operator++( int )
1013 {
1014 if( bFinished == false )
1015 nPos = hsh->core->getNextPos( nPos, bFinished );
1016
1017 return *this;
1018 }
1019
1020 /**
1021 * Iterator incrementation operator. Move the iterator forward.
1022 */
1023 const_iterator operator++()
1024 {
1025 if( bFinished == false )
1026 nPos = hsh->core->getNextPos( nPos, bFinished );
1027
1028 return *this;
1029 }
1030
1031 /**
1032 * Iterator equality comparison operator. Iterators the same?
1033 */
1034 bool operator==( const const_iterator &oth ) const
1035 {
1036 if( bFinished != oth.bFinished )
1037 return false;
1038 if( bFinished == true )
1039 {
1040 return true;
1041 }
1042 else
1043 {
1044 if( oth.nPos == nPos )
1045 return true;
1046 return false;
1047 }
1048 }
1049
1050 /**
1051 * Iterator not equality comparison operator. Not the same?
1052 */
1053 bool operator!=( const const_iterator &oth ) const
1054 {
1055 return !(*this == oth );
1056 }
1057
1058 /**
1059 * Iterator assignment operator.
1060 */
1061 const_iterator operator=( const const_iterator &oth )
1062 {
1063 hsh = oth.hsh;
1064 nPos = oth.nPos;
1065 bFinished = oth.bFinished;
1066 return *this;
1067 }
1068
1069 /**
1070 * Iterator dereference operator... err.. get the value
1071 *@returns (value_type &) The value behind this iterator.
1072 */
1073 const value &operator *() const
1074 {
1075 return hsh->core->getValueAtPos( nPos );
1076 }
1077
1078 /**
1079 * Get the key behind this iterator.
1080 *@returns (key_type &) The key behind this iterator.
1081 */
1082 const key &getKey() const
1083 {
1084 return hsh->core->getKeyAtPos( nPos );
1085 }
1086
1087 /**
1088 * Get the value behind this iterator.
1089 *@returns (value_type &) The value behind this iterator.
1090 */
1091 const value &getValue() const
1092 {
1093 return hsh->core->getValueAtPos( nPos );
1094 }
1095 } const_iterator;
1096
1097 /**
1098 * Get an iterator pointing to the first item in the hash table.
1099 *@returns (iterator) An iterator pointing to the first item in the
1100 * hash table.
1101 */
1102 iterator begin()
1103 {
1104 return iterator( this );
1105 }
1106
1107 const_iterator begin() const
1108 {
1109 return const_iterator( this );
1110 }
1111
1112 /**
1113 * Get an iterator pointing to a point just past the last item in the
1114 * hash table.
1115 *@returns (iterator) An iterator pointing to a point just past the
1116 * last item in the hash table.
1117 */
1118 iterator end()
1119 {
1120 return iterator( this, true );
1121 }
1122
1123 const_iterator end() const
1124 {
1125 return const_iterator( this, true );
1126 }
1127
1128 /**
1129 * Get a list of all the keys in the hash table.
1130 *@returns (std::list<key_type>) The list of keys in the hash table.
1131 */
1132 Bu::List<key> getKeys() const
1133 {
1134 Bu::List<key> lKeys;
1135
1136 for( uint32_t j = 0; j < core->nCapacity; j++ )
1137 {
1138 if( core->isFilled( j ) )
1139 {
1140 if( !core->isDeleted( j ) )
1141 {
1142 lKeys.append( core->aKeys[j] );
1143 }
1144 }
1145 }
1146
1147 return lKeys;
1148 }
1149
1150 Bu::List<value> getValues() const
1151 {
1152 Bu::List<value> lValues;
1153
1154 for( uint32_t j = 0; j < core->nCapacity; j++ )
1155 {
1156 if( core->isFilled( j ) )
1157 {
1158 if( !core->isDeleted( j ) )
1159 {
1160 lValues.append( core->aValues[j] );
1161 }
1162 }
1163 }
1164
1165 return lValues;
1166 }
1167
1168 bool operator==( const MyType &rhs ) const
1169 {
1170 if( this == &rhs )
1171 return true;
1172 if( core == rhs.core )
1173 return true;
1174 if( core == NULL || rhs.core == NULL )
1175 return false;
1176 if( getSize() != rhs.getSize() )
1177 return false;
1178
1179 for( uint32_t j = 0; j < core->nCapacity; j++ )
1180 {
1181 if( core->isFilled( j ) )
1182 {
1183 if( !core->isDeleted( j ) )
1184 {
1185 // Check to see if this key is in the other hash
1186 if( rhs.has( core->aKeys[j] ) )
1187 {
1188 if( !(core->aValues[j] == rhs.get( core->aKeys[j]) ) )
1189 {
1190 return false;
1191 }
1192 }
1193 else
1194 {
1195 return false;
1196 }
1197 }
1198 }
1199 }
1200
1201 return true;
1202 }
1203
1204 bool operator!=( const MyType &rhs ) const
1205 {
1206 return !(*this == rhs);
1207 }
1208
1209 protected:
1210 virtual Core *_copyCore( Core *src )
1211 {
1212 Core *pRet = _allocateCore();
1213
1214 pRet->nFilled = 0;
1215 pRet->nDeleted = 0;
1216 pRet->nCapacity = src->nCapacity;
1217 pRet->nKeysSize = bitsTo<uint32_t>( pRet->nCapacity );
1218 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize );
1219 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize );
1220 pRet->clearBits();
1221
1222 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity );
1223 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity );
1224 pRet->aValues = pRet->va.allocate( pRet->nCapacity );
1225
1226 for( uint32_t j = 0; j < src->nCapacity; j++ )
1227 {
1228 if( src->isFilled( j ) && !src->isDeleted( j ) )
1229 {
1230 pRet->insert( src->aKeys[j], src->aValues[j] );
1231 }
1232 }
1233
1234 return pRet;
1235 }
1236 };
1237
1238 template<typename T> uint32_t __calcHashCode( const T &k )
1239 {
1240 return static_cast<uint32_t>( k );
1241 }
1242
1243 template<typename T> bool __cmpHashKeys( const T &a, const T &b )
1244 {
1245 return (a == b);
1246 }
1247
1248 template<> uint32_t __calcHashCode<const char *>( const char * const &k );
1249 template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
1250
1251 template<> uint32_t __calcHashCode<char *>( char * const &k );
1252 template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
1253
1254 class Formatter;
1255 Formatter &operator<<( Formatter &rOut, char *sStr );
1256 Formatter &operator<<( Formatter &rOut, signed char c );
1257 template<typename key, typename value>
1258 Formatter &operator<<( Formatter &f, const Bu::Hash<key, value> &l )
1259 {
1260 f << '{';
1261 for( typename Bu::Hash<key,value>::const_iterator i = l.begin(); i; i++ )
1262 {
1263 if( i != l.begin() )
1264 f << ", ";
1265 f << i.getKey() << ": " << i.getValue();
1266 }
1267 f << '}';
1268
1269 return f;
1270 }
1271
1272 template<typename key, typename value, typename a, typename b,
1273 typename c, typename d>
1274 ArchiveBase &operator<<( ArchiveBase &ar, const Hash<key,value,a,b,c,d> &h )
1275 {
1276 long iSize = h.getSize();
1277 ar << iSize;
1278 for( typename Hash<key,value,a,b,c,d>::const_iterator i = h.begin(); i != h.end(); i++ )
1279 {
1280 ar << (i.getKey());
1281 ar << (i.getValue());
1282 }
1283
1284 return ar;
1285 }
1286
1287 template<typename key, typename value, typename a, typename b,
1288 typename c, typename d>
1289 ArchiveBase &operator>>( ArchiveBase &ar, Hash<key,value,a,b,c,d> &h )
1290 {
1291 h.clear();
1292 long nSize;
1293 ar >> nSize;
1294
1295 for( long j = 0; j < nSize; j++ )
1296 {
1297 key k; value v;
1298 ar >> k >> v;
1299 h.insert( k, v );
1300 }
1301
1302 return ar;
1303 }
1304}
1305
1306#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-21 08:34:50 +0000