summaryrefslogtreecommitdiff
path: root/src/hash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/hash.h')
-rw-r--r--src/hash.h137
1 files changed, 137 insertions, 0 deletions
diff --git a/src/hash.h b/src/hash.h
index 1bb25c9..6c4a443 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -71,6 +71,10 @@ namespace Bu
71 bool bFilled; 71 bool bFilled;
72 72
73 public: 73 public:
74 /**
75 * Cast operator for HashProxy.
76 *@returns (value_type &) The value the HashProxy is pointing to.
77 */
74 operator _value &() 78 operator _value &()
75 { 79 {
76 if( bFilled == false ) 80 if( bFilled == false )
@@ -81,6 +85,10 @@ namespace Bu
81 return *pValue; 85 return *pValue;
82 } 86 }
83 87
88 /**
89 * Direct function for retrieving a value out of the HashProxy.
90 *@returns (value_type &) The value pointed to by this HashProxy.
91 */
84 _value &value() 92 _value &value()
85 { 93 {
86 if( bFilled == false ) 94 if( bFilled == false )
@@ -91,11 +99,17 @@ namespace Bu
91 return *pValue; 99 return *pValue;
92 } 100 }
93 101
102 /**
103 * Whether this HashProxy points to something real or not.
104 */
94 bool isFilled() 105 bool isFilled()
95 { 106 {
96 return bFilled; 107 return bFilled;
97 } 108 }
98 109
110 /**
111 * Erase the data pointed to by this HashProxy.
112 */
99 void erase() 113 void erase()
100 { 114 {
101 if( bFilled ) 115 if( bFilled )
@@ -105,6 +119,10 @@ namespace Bu
105 } 119 }
106 } 120 }
107 121
122 /**
123 * Assign data to this point in the hash table.
124 *@param nval (value_type) the data to assign.
125 */
108 _value operator=( _value nval ) 126 _value operator=( _value nval )
109 { 127 {
110 if( bFilled ) 128 if( bFilled )
@@ -122,6 +140,11 @@ namespace Bu
122 return nval; 140 return nval;
123 } 141 }
124 142
143 /**
144 * Pointer extraction operator. Access to members of data pointed to
145 * by HashProxy.
146 *@returns (value_type *)
147 */
125 _value *operator->() 148 _value *operator->()
126 { 149 {
127 if( bFilled == false ) 150 if( bFilled == false )
@@ -133,6 +156,15 @@ namespace Bu
133 } 156 }
134 }; 157 };
135 158
159 /**
160 * Libbu Template Hash Table
161 *@param key (typename) The datatype of the hashtable keys
162 *@param value (typename) The datatype of the hashtable data
163 *@param sizecalc (typename) Functor to compute new table size on rehash
164 *@param keyalloc (typename) Memory allocator for hashtable keys
165 *@param valuealloc (typename) Memory allocator for hashtable values
166 *@param challoc (typename) Byte allocator for bitflags
167 */
136 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 168 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc >
137 class Hash 169 class Hash
138 { 170 {
@@ -186,6 +218,10 @@ namespace Bu
186 } 218 }
187 } 219 }
188 220
221 /**
222 * Hashtable assignment operator. Clears this hashtable and
223 * copies RH into it.
224 */
189 Hash &operator=( const Hash &src ) 225 Hash &operator=( const Hash &src )
190 { 226 {
191 for( uint32_t j = 0; j < nCapacity; j++ ) 227 for( uint32_t j = 0; j < nCapacity; j++ )
@@ -244,26 +280,49 @@ namespace Bu
244 ca.deallocate( aHashCodes, nCapacity ); 280 ca.deallocate( aHashCodes, nCapacity );
245 } 281 }
246 282
283 /**
284 * Get the current hash table capacity. (Changes at re-hash)
285 *@returns (uint32_t) The current capacity.
286 */
247 uint32_t getCapacity() 287 uint32_t getCapacity()
248 { 288 {
249 return nCapacity; 289 return nCapacity;
250 } 290 }
251 291
292 /**
293 * Get the number of hash locations spoken for. (Including
294 * not-yet-cleaned-up deleted items.)
295 *@returns (uint32_t) The current fill state.
296 */
252 uint32_t getFill() 297 uint32_t getFill()
253 { 298 {
254 return nFilled; 299 return nFilled;
255 } 300 }
256 301
302 /**
303 * Get the number of items stored in the hash table.
304 *@returns (uint32_t) The number of items stored in the hash table.
305 */
257 uint32_t size() 306 uint32_t size()
258 { 307 {
259 return nFilled-nDeleted; 308 return nFilled-nDeleted;
260 } 309 }
261 310
311 /**
312 * Get the number of items which have been deleted, but not yet
313 * cleaned up.
314 *@returns (uint32_t) The number of deleted items.
315 */
262 uint32_t getDeleted() 316 uint32_t getDeleted()
263 { 317 {
264 return nDeleted; 318 return nDeleted;
265 } 319 }
266 320
321 /**
322 * Hash table index operator
323 *@param k (key_type) Key of data to be retrieved.
324 *@returns (HashProxy) Proxy pointing to the data.
325 */
267 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k ) 326 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k )
268 { 327 {
269 uint32_t hash = __calcHashCode( k ); 328 uint32_t hash = __calcHashCode( k );
@@ -280,6 +339,11 @@ namespace Bu
280 } 339 }
281 } 340 }
282 341
342 /**
343 * Insert a value (v) under key (k) into the hash table
344 *@param k (key_type) Key to list the value under.
345 *@param v (value_type) Value to store in the hash table.
346 */
283 virtual void insert( key k, value v ) 347 virtual void insert( key k, value v )
284 { 348 {
285 uint32_t hash = __calcHashCode( k ); 349 uint32_t hash = __calcHashCode( k );
@@ -299,6 +363,10 @@ namespace Bu
299 } 363 }
300 } 364 }
301 365
366 /**
367 * Remove a value from the hash table.
368 *@param k (key_type) The data under this key will be erased.
369 */
302 virtual void erase( key k ) 370 virtual void erase( key k )
303 { 371 {
304 uint32_t hash = __calcHashCode( k ); 372 uint32_t hash = __calcHashCode( k );
@@ -313,6 +381,11 @@ namespace Bu
313 } 381 }
314 382
315 struct iterator; 383 struct iterator;
384
385 /**
386 * Remove a value from the hash pointed to from an iterator.
387 *@param i (iterator &) The data to be erased.
388 */
316 virtual void erase( struct iterator &i ) 389 virtual void erase( struct iterator &i )
317 { 390 {
318 if( this != &i.hsh ) 391 if( this != &i.hsh )
@@ -324,6 +397,9 @@ namespace Bu
324 } 397 }
325 } 398 }
326 399
400 /**
401 * Remove all data from the hash table.
402 */
327 virtual void clear() 403 virtual void clear()
328 { 404 {
329 for( uint32_t j = 0; j < nCapacity; j++ ) 405 for( uint32_t j = 0; j < nCapacity; j++ )
@@ -340,6 +416,11 @@ namespace Bu
340 clearBits(); 416 clearBits();
341 } 417 }
342 418
419 /**
420 * Get an item of data from the hash table.
421 *@param k (key_type) Key pointing to the data to be retrieved.
422 *@returns (value_type &) The data pointed to by (k).
423 */
343 virtual value &get( key k ) 424 virtual value &get( key k )
344 { 425 {
345 uint32_t hash = __calcHashCode( k ); 426 uint32_t hash = __calcHashCode( k );
@@ -359,6 +440,12 @@ namespace Bu
359 } 440 }
360 } 441 }
361 442
443 /**
444 * Get a const item of data from the hash table.
445 *@param k (key_type) Key pointing to the data to be retrieved.
446 *@returns (const value_type &) A const version of the data pointed
447 * to by (k).
448 */
362 virtual const value &get( key k ) const 449 virtual const value &get( key k ) const
363 { 450 {
364 uint32_t hash = __calcHashCode( k ); 451 uint32_t hash = __calcHashCode( k );
@@ -378,6 +465,11 @@ namespace Bu
378 } 465 }
379 } 466 }
380 467
468 /**
469 * Does the hash table contain an item under key (k).
470 *@param k (key_type) The key to check.
471 *@returns (bool) Whether there was an item in the hash under key (k).
472 */
381 virtual bool has( key k ) 473 virtual bool has( key k )
382 { 474 {
383 bool bFill; 475 bool bFill;
@@ -386,6 +478,9 @@ namespace Bu
386 return bFill; 478 return bFill;
387 } 479 }
388 480
481 /**
482 * Iteration structure for iterating through the hash.
483 */
389 typedef struct iterator 484 typedef struct iterator
390 { 485 {
391 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>; 486 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
@@ -410,6 +505,9 @@ namespace Bu
410 bool bFinished; 505 bool bFinished;
411 506
412 public: 507 public:
508 /**
509 * Iterator incrementation operator. Move the iterator forward.
510 */
413 iterator operator++( int ) 511 iterator operator++( int )
414 { 512 {
415 if( bFinished == false ) 513 if( bFinished == false )
@@ -418,6 +516,9 @@ namespace Bu
418 return *this; 516 return *this;
419 } 517 }
420 518
519 /**
520 * Iterator incrementation operator. Move the iterator forward.
521 */
421 iterator operator++() 522 iterator operator++()
422 { 523 {
423 if( bFinished == false ) 524 if( bFinished == false )
@@ -426,6 +527,9 @@ namespace Bu
426 return *this; 527 return *this;
427 } 528 }
428 529
530 /**
531 * Iterator equality comparison operator. Iterators the same?
532 */
429 bool operator==( const iterator &oth ) 533 bool operator==( const iterator &oth )
430 { 534 {
431 if( bFinished != oth.bFinished ) 535 if( bFinished != oth.bFinished )
@@ -442,11 +546,17 @@ namespace Bu
442 } 546 }
443 } 547 }
444 548
549 /**
550 * Iterator not equality comparison operator. Not the same?
551 */
445 bool operator!=( const iterator &oth ) 552 bool operator!=( const iterator &oth )
446 { 553 {
447 return !(*this == oth ); 554 return !(*this == oth );
448 } 555 }
449 556
557 /**
558 * Iterator assignment operator.
559 */
450 iterator operator=( const iterator &oth ) 560 iterator operator=( const iterator &oth )
451 { 561 {
452 if( &hsh != &oth.hsh ) 562 if( &hsh != &oth.hsh )
@@ -456,32 +566,59 @@ namespace Bu
456 bFinished = oth.bFinished; 566 bFinished = oth.bFinished;
457 } 567 }
458 568
569 /**
570 * Iterator dereference operator... err.. get the value
571 *@returns (value_type &) The value behind this iterator.
572 */
459 value &operator *() 573 value &operator *()
460 { 574 {
461 return hsh.getValueAtPos( nPos ); 575 return hsh.getValueAtPos( nPos );
462 } 576 }
463 577
578 /**
579 * Get the key behind this iterator.
580 *@returns (key_type &) The key behind this iterator.
581 */
464 key &getKey() 582 key &getKey()
465 { 583 {
466 return hsh.getKeyAtPos( nPos ); 584 return hsh.getKeyAtPos( nPos );
467 } 585 }
468 586
587 /**
588 * Get the value behind this iterator.
589 *@returs (value_type &) The value behind this iterator.
590 */
469 value &getValue() 591 value &getValue()
470 { 592 {
471 return hsh.getValueAtPos( nPos ); 593 return hsh.getValueAtPos( nPos );
472 } 594 }
473 }; 595 };
474 596
597 /**
598 * Get an iterator pointing to the first item in the hash table.
599 *@returns (iterator) An iterator pointing to the first item in the
600 * hash table.
601 */
475 iterator begin() 602 iterator begin()
476 { 603 {
477 return iterator( *this ); 604 return iterator( *this );
478 } 605 }
479 606
607 /**
608 * Get an iterator pointing to a point just past the last item in the
609 * hash table.
610 *@returns (iterator) An iterator pointing to a point just past the
611 * last item in the hash table.
612 */
480 iterator end() 613 iterator end()
481 { 614 {
482 return iterator( *this, true ); 615 return iterator( *this, true );
483 } 616 }
484 617
618 /**
619 * Get a list of all the keys in the hash table.
620 *@returns (std::list<key_type>) The list of keys in the hash table.
621 */
485 std::list<key> getKeys() 622 std::list<key> getKeys()
486 { 623 {
487 std::list<key> lKeys; 624 std::list<key> lKeys;
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-27 13:15:45 +0000