aboutsummaryrefslogtreecommitdiff
path: root/src/set.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-08-05 04:57:04 +0000
committerMike Buland <eichlan@xagasoft.com>2007-08-05 04:57:04 +0000
commit9cf4949ff56464ce4737fd3a0e6b757032354b0e (patch)
tree748d74a84c73f929d3c9874cf1b5bbccdf78dd1e /src/set.h
parent383ad5a674e192830287dfdd53d48507b9aea46e (diff)
downloadlibbu++-9cf4949ff56464ce4737fd3a0e6b757032354b0e.tar.gz
libbu++-9cf4949ff56464ce4737fd3a0e6b757032354b0e.tar.bz2
libbu++-9cf4949ff56464ce4737fd3a0e6b757032354b0e.tar.xz
libbu++-9cf4949ff56464ce4737fd3a0e6b757032354b0e.zip
Set is just a copy of hash for now. It'd be cool if they could be linked, not
really sure how that could happen easily.
Diffstat (limited to '')
-rw-r--r--src/set.h1072
1 files changed, 1072 insertions, 0 deletions
diff --git a/src/set.h b/src/set.h
new file mode 100644
index 0000000..36665a6
--- /dev/null
+++ b/src/set.h
@@ -0,0 +1,1072 @@
1#ifndef BU_HASH_H
2#define BU_HASH_H
3
4#include <stddef.h>
5#include <string.h>
6#include <memory>
7#include <iostream>
8#include <list>
9#include <utility>
10#include "bu/exceptionbase.h"
11#include "bu/list.h"
12///#include "archival.h"
13///#include "archive.h"
14
15#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
16
17namespace Bu
18{
19 subExceptionDecl( HashException )
20
21 enum eHashException
22 {
23 excodeNotFilled
24 };
25
26 template<typename T>
27 uint32_t __calcHashCode( const T &k );
28
29 template<typename T>
30 bool __cmpHashKeys( const T &a, const T &b );
31
32 struct __calcNextTSize_fast
33 {
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
160 /**
161 * Libbu Template Hash Table
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 }
193
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 )
203 {
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++ )
214 {
215 if( src.isFilled( j ) )
216 {
217 insert( src.aKeys[j], src.aValues[j] );
218 }
219 }
220 }
221
222 /**
223 * Hashtable assignment operator. Clears this hashtable and
224 * copies RH into it.
225 */
226 Hash &operator=( const Hash &src )
227 {
228 for( uint32_t j = 0; j < nCapacity; 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 ) )
258 {
259 insert( src.aKeys[j], src.aValues[j] );
260 }
261 }
262
263 return *this;
264 }
265
266 virtual ~Hash()
267 {
268 for( uint32_t j = 0; j < nCapacity; j++ )
269 {
270 if( isFilled( j ) )
271 if( !isDeleted( j ) )
272 {
273 va.destroy( &aValues[j] );
274 ka.destroy( &aKeys[j] );
275 }
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 );
282 }
283
284 /**
285 * Get the current hash table capacity. (Changes at re-hash)
286 *@returns (uint32_t) The current capacity.
287 */
288 uint32_t getCapacity()
289 {
290 return nCapacity;
291 }
292
293 /**
294 * Get the number of hash locations spoken for. (Including
295 * not-yet-cleaned-up deleted items.)
296 *@returns (uint32_t) The current fill state.
297 */
298 uint32_t getFill()
299 {
300 return nFilled;
301 }
302
303 /**
304 * Get the number of items stored in the hash table.
305 *@returns (uint32_t) The number of items stored in the hash table.
306 */
307 uint32_t size()
308 {
309 return nFilled-nDeleted;
310 }
311
312 /**
313 * Get the number of items which have been deleted, but not yet
314 * cleaned up.
315 *@returns (uint32_t) The number of deleted items.
316 */
317 uint32_t getDeleted()
318 {
319 return nDeleted;
320 }
321
322 /**
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
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 )
349 {
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 }
365 }
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 )
372 {
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 }
382 }
383
384 struct iterator;
385
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 )
391 {
392 if( this != &i.hsh )
393 throw HashException("This iterator didn't come from this Hash.");
394 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
395 {
396 _erase( i.nPos );
397 onDelete();
398 }
399 }
400
401 /**
402 * Remove all data from the hash table.
403 */
404 virtual void clear()
405 {
406 for( uint32_t j = 0; j < nCapacity; j++ )
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();
418 }
419
420 /**
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).
471 *@param k (key_type) The key to check.
472 *@returns (bool) Whether there was an item in the hash under key (k).
473 */
474 virtual bool has( key k )
475 {
476 bool bFill;
477 probe( __calcHashCode( k ), k, bFill, false );
478
479 return bFill;
480 }
481
482 /**
483 * Iteration structure for iterating through the hash.
484 */
485 typedef struct iterator
486 {
487 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
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 )
539 {
540 return true;
541 }
542 else
543 {
544 if( oth.nPos == nPos )
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 }
557
558 /**
559 * Iterator assignment operator.
560 */
561 iterator operator=( const iterator &oth )
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 }
569
570 /**
571 * Iterator dereference operator... err.. get the value
572 *@returns (value_type &) The value behind this iterator.
573 */
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
602 {
603 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
604 private:
605 const_iterator( const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) :
606 hsh( hsh ),
607 nPos( 0 ),
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 }
619
620 const Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
621 uint32_t nPos;
622 bool bFinished;
623
624 public:
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 );
632
633 return *this;
634 }
635
636 /**
637 * Iterator incrementation operator. Move the iterator forward.
638 */
639 const_iterator operator++()
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()
720 {
721 return iterator( *this );
722 }
723
724 const_iterator begin() const
725 {
726 return const_iterator( *this );
727 }
728
729 /**
730 * Get an iterator pointing to a point just past the last item in the
731 * hash table.
732 *@returns (iterator) An iterator pointing to a point just past the
733 * last item in the hash table.
734 */
735 iterator end()
736 {
737 return iterator( *this, true );
738 }
739
740 const_iterator end() const
741 {
742 return const_iterator( *this, true );
743 }
744
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
750 {
751 Bu::List<key> lKeys;
752
753 for( uint32_t j = 0; j < nCapacity; j++ )
754 {
755 if( isFilled( j ) )
756 {
757 if( !isDeleted( j ) )
758 {
759 lKeys.append( aKeys[j] );
760 }
761 }
762 }
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++ )
776 {
777 bFilled[j] = bDeleted[j] = 0;
778 }
779 }
780
781 virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash )
782 {
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 );
790 }
791
792 virtual void _erase( uint32_t loc )
793 {
794 bDeleted[loc/32] |= (1<<(loc%32));
795 va.destroy( &aValues[loc] );
796 ka.destroy( &aKeys[loc] );
797 nDeleted++;
798 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
799 // nFilled, nDeleted, nCapacity );
800 }
801
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 )
808 {
809 return aKeys[nPos];
810 }
811
812 virtual const key &getKeyAtPos( uint32_t nPos ) const
813 {
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];
825 }
826
827 virtual uint32_t getFirstPos( bool &bFinished ) const
828 {
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;
838 }
839
840 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
841 {
842 for( uint32_t j = nPos+1; j < nCapacity; j++ )
843 {
844 if( isFilled( j ) )
845 if( !isDeleted( j ) )
846 return j;
847 }
848
849 bFinished = true;
850 return 0;
851 }
852
853 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true )
854 {
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 int8_t j;
860 for( j = 0;
861 isFilled( nCur ) && j < 32;
862 nCur = (nCur + (1<<j))%nCapacity, j++
863 )
864 {
865 // Is this the same hash code we were looking for?
866 if( hash == aHashCodes[nCur] )
867 {
868 // Skip over deleted entries. Deleted entries are also filled,
869 // so we only have to do this check here.
870 if( isDeleted( nCur ) )
871 continue;
872
873 // Is it really the same key? (for safety)
874 if( __cmpHashKeys( aKeys[nCur], k ) == true )
875 {
876 bFill = true;
877 return nCur;
878 }
879 }
880 }
881
882 // This is our insurance, if the table is full, then go ahead and
883 // rehash, then try again.
884 if( (isFilled( nCur ) || j == 32) && rehash == true )
885 {
886 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
887
888 // This is potentially dangerous, and could cause an infinite loop.
889 // Be careful writing probe, eh?
890 return probe( hash, k, bFill );
891 }
892
893 bFill = false;
894 return nCur;
895 }
896
897 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) const
898 {
899 uint32_t nCur = hash%nCapacity;
900
901 // First we scan to see if the key is already there, abort if we
902 // run out of probing room, or we find a non-filled entry
903 for( int8_t j = 0;
904 isFilled( nCur ) && j < 32;
905 nCur = (nCur + (1<<j))%nCapacity, j++
906 )
907 {
908 // Is this the same hash code we were looking for?
909 if( hash == aHashCodes[nCur] )
910 {
911 // Skip over deleted entries. Deleted entries are also filled,
912 // so we only have to do this check here.
913 if( isDeleted( nCur ) )
914 continue;
915
916 // Is it really the same key? (for safety)
917 if( __cmpHashKeys( aKeys[nCur], k ) == true )
918 {
919 bFill = true;
920 return nCur;
921 }
922 }
923 }
924
925 bFill = false;
926 return nCur;
927 }
928
929 void reHash( uint32_t nNewSize )
930 {
931 //printf("---REHASH---");
932 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
933 // nFilled, nDeleted, nCapacity );
934
935 // Save all the old data
936 uint32_t nOldCapacity = nCapacity;
937 uint32_t *bOldFilled = bFilled;
938 uint32_t *aOldHashCodes = aHashCodes;
939 uint32_t nOldKeysSize = nKeysSize;
940 uint32_t *bOldDeleted = bDeleted;
941 value *aOldValues = aValues;
942 key *aOldKeys = aKeys;
943
944 // Calculate new sizes
945 nCapacity = nNewSize;
946 nKeysSize = bitsToBytes( nCapacity );
947
948 // Allocate new memory + prep
949 bFilled = ca.allocate( nKeysSize );
950 bDeleted = ca.allocate( nKeysSize );
951 clearBits();
952
953 aHashCodes = ca.allocate( nCapacity );
954 aKeys = ka.allocate( nCapacity );
955 aValues = va.allocate( nCapacity );
956
957 nDeleted = nFilled = 0;
958
959 // Re-insert all of the old data (except deleted items)
960 for( uint32_t j = 0; j < nOldCapacity; j++ )
961 {
962 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
963 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
964 {
965 insert( aOldKeys[j], aOldValues[j] );
966 }
967 }
968
969 // Delete all of the old data
970 for( uint32_t j = 0; j < nOldCapacity; j++ )
971 {
972 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
973 {
974 va.destroy( &aOldValues[j] );
975 ka.destroy( &aOldKeys[j] );
976 }
977 }
978 va.deallocate( aOldValues, nOldCapacity );
979 ka.deallocate( aOldKeys, nOldCapacity );
980 ca.deallocate( bOldFilled, nOldKeysSize );
981 ca.deallocate( bOldDeleted, nOldKeysSize );
982 ca.deallocate( aOldHashCodes, nOldCapacity );
983 }
984
985 virtual bool isFilled( uint32_t loc ) const
986 {
987 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
988 }
989
990 virtual bool isDeleted( uint32_t loc ) const
991 {
992 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
993 }
994
995 protected:
996 uint32_t nCapacity;
997 uint32_t nFilled;
998 uint32_t nDeleted;
999 uint32_t *bFilled;
1000 uint32_t *bDeleted;
1001 uint32_t nKeysSize;
1002 key *aKeys;
1003 value *aValues;
1004 uint32_t *aHashCodes;
1005 valuealloc va;
1006 keyalloc ka;
1007 challoc ca;
1008 sizecalc szCalc;
1009 };
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}
1071
1072#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 08:26:05 +0000