|
AGX Dynamics 2.42.3.1
|
A simple hash table using quadratic probing. More...
#include <QuadraticProbingHashTable.h>
Inheritance diagram for agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >:Classes | |
| class | Bucket |
| class | insert_iterator |
| class | template_iterator |
Public Types | |
| typedef template_iterator< const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > > | const_iterator |
| typedef HashT | hash_fn_type |
| typedef template_iterator< QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > > | iterator |
| Iterators. | |
| typedef KeyT | key_type |
| typedef DataT | value_type |
Public Types inherited from agx::Container | |
| enum | ClearPolicy { SHRINK_BUFFER , SHRINK_BUFFER_AVERAGED , MAINTAIN_BUFFER } |
| agxData::Values from this enumeration is passed to the subclasses' 'clear' method in order to control what should become of the container's memory. More... | |
Public Member Functions | |
| QuadraticProbingHashTableImplementation (const AllocatorT &allocator=AllocatorT()) | |
| Constructor. | |
| QuadraticProbingHashTableImplementation (const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > &other) | |
| Copy constructor. | |
| ~QuadraticProbingHashTableImplementation () | |
| Destructor. | |
| AllocatorT & | allocator () |
| const AllocatorT & | allocator () const |
| iterator | begin () |
| Iterator to first element in hash table. | |
| const_iterator | begin () const |
| void | clear (ClearPolicy policy=SHRINK_BUFFER_AVERAGED) |
| Remove all elements. | |
| bool | contains (const KeyT &key) const |
| Boolean query to test existence of an element. | |
| iterator | end () |
| Iterator marking end of hash table. | |
| const_iterator | end () const |
| iterator | erase (const iterator &it) |
| Erase an element using an iterator. | |
| bool | erase (const KeyT &key) |
| Erase an element from the hash table. | |
| iterator | find (const KeyT &key) |
| Find an element. | |
| const_iterator | find (const KeyT &key) const |
| const Bucket * | getBucketBuffer () const |
| size_t | getMaxProbeLength () const |
| size_t | getNumBuckets () const |
| DataT & | getOrCreate (const KeyT &key) |
| Returns value given key. | |
| insert_iterator | insert (const KeyT &key, const DataT &data) |
| Insert an element, overwriting if key already exists. | |
| QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > & | operator= (const QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT > &other) |
| Assignment operator. | |
| DataT & | operator[] (const KeyT &key) |
| Index operator for accessing elements in the hash, inserting it if not found. | |
| const DataT & | operator[] (const KeyT &key) const |
| template<typename T > | |
| void | purge (T purger) |
| Purge the hash table. | |
| void | reserve (size_t size) |
| Reserve capacity in the hash table. | |
Public Member Functions inherited from agx::Container | |
| size_t | capacity () const |
| Returns the size of the memory are used by the container to store its elements. | |
| bool | empty () const |
| void * | ptr () |
| const void * | ptr () const |
| size_t | size () const |
Protected Member Functions | |
| Bucket * | buckets () const |
| bool | eraseBucket (size_t index) |
| template<typename T2 > | |
| size_t | findBucket (const T2 &key) const |
| size_t & | numBuckets () |
| size_t | numBuckets () const |
| size_t & | numFilled () |
| size_t | numFilled () const |
| void | rebuild (size_t size) |
| Rebuild, and optionally resize hash table. | |
Protected Member Functions inherited from agx::Container | |
| Container () | |
| Container (const Container &other) | |
| Container (Container &&other) | |
| ~Container () | |
Additional Inherited Members | |
Protected Attributes inherited from agx::Container | |
| void * | m_buffer |
| size_t | m_capacity |
| size_t | m_size |
A simple hash table using quadratic probing.
Built-in support for keys of type int, agx::String, and pointers. To use other types of keys, a custom hash functor must be supplied.
\todo implement [] operator
Definition at line 47 of file QuadraticProbingHashTable.h.
| typedef template_iterator< const QuadraticProbingHashTableImplementation<KeyT, DataT, HashT, AllocatorT> > agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::const_iterator |
Definition at line 228 of file QuadraticProbingHashTable.h.
| typedef HashT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::hash_fn_type |
Definition at line 52 of file QuadraticProbingHashTable.h.
| typedef template_iterator< QuadraticProbingHashTableImplementation<KeyT, DataT, HashT, AllocatorT> > agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::iterator |
Iterators.
Definition at line 227 of file QuadraticProbingHashTable.h.
| typedef KeyT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::key_type |
Definition at line 51 of file QuadraticProbingHashTable.h.
| typedef DataT agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::value_type |
Definition at line 50 of file QuadraticProbingHashTable.h.
|
inline |
Constructor.
Definition at line 259 of file QuadraticProbingHashTable.h.
|
inline |
Copy constructor.
Definition at line 263 of file QuadraticProbingHashTable.h.
|
inline |
Destructor.
Definition at line 285 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::Container::m_buffer, agx::Container::m_capacity, and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
|
inline |
Definition at line 565 of file QuadraticProbingHashTable.h.
|
inline |
Definition at line 566 of file QuadraticProbingHashTable.h.
|
inline |
Iterator to first element in hash table.
Definition at line 419 of file QuadraticProbingHashTable.h.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=().
|
inline |
Definition at line 422 of file QuadraticProbingHashTable.h.
|
inlineprotected |
Definition at line 586 of file QuadraticProbingHashTable.h.
References agx::Container::m_buffer.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::~QuadraticProbingHashTableImplementation(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::clear(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getBucketBuffer(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::purge(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild().
|
inline |
Remove all elements.
Definition at line 458 of file QuadraticProbingHashTable.h.
References AGX_HASH_TABLE_MIN_SIZE, AGX_HASH_TABLE_SHRINK_THRESHOLD, AGX_HASH_TABLE_SMOOTHING_FACTOR, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::Container::m_buffer, agx::Container::m_capacity, agx::Container::MAINTAIN_BUFFER, agx::nextPrime(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second, and agx::Container::SHRINK_BUFFER.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=().
|
inline |
Boolean query to test existence of an element.
Definition at line 397 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
|
inline |
Iterator marking end of hash table.
Definition at line 429 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[]().
|
inline |
Definition at line 432 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
|
inline |
Erase an element using an iterator.
Definition at line 449 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket().
|
inline |
Erase an element from the hash table.
Definition at line 440 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket().
|
inlineprotected |
Definition at line 659 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::ACTIVE, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::erase(), and agx::QuadraticProbingHashTable< agx::ref_ptr< KeyT >, DataT, HashT, AllocatorT >::erase().
|
inline |
Find an element.
Definition at line 405 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket().
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[]().
|
inline |
Definition at line 410 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket().
|
inlineprotected |
Definition at line 632 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::hashKeyEqual(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isActive(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::contains(), agx::QuadraticProbingHashTable< agx::ref_ptr< KeyT >, DataT, HashT, AllocatorT >::contains(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::erase(), agx::QuadraticProbingHashTable< agx::ref_ptr< KeyT >, DataT, HashT, AllocatorT >::erase(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::find(), and agx::QuadraticProbingHashTable< agx::ref_ptr< KeyT >, DataT, HashT, AllocatorT >::find().
|
inline |
Definition at line 573 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets().
|
inline |
Definition at line 574 of file QuadraticProbingHashTable.h.
|
inline |
Definition at line 575 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets().
|
inline |
Returns value given key.
If the key doesn't exist, the key is inserted and the default value is returned.
| key | - key |
Definition at line 321 of file QuadraticProbingHashTable.h.
|
inline |
Insert an element, overwriting if key already exists.
Definition at line 330 of file QuadraticProbingHashTable.h.
References AGX_HASH_TABLE_GROW_FACTOR, AGX_HASH_TABLE_GROW_THRESHOLD, AGX_HASH_TABLE_MAX_PROBE_LENGTH, agxAssert, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::hashKeyEqual(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isActive(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second, and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::VALID.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator[](), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild().
|
inlineprotected |
Definition at line 583 of file QuadraticProbingHashTable.h.
References agx::Container::m_capacity.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::~QuadraticProbingHashTableImplementation(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::clear(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::contains(), agx::QuadraticProbingHashTable< agx::ref_ptr< KeyT >, DataT, HashT, AllocatorT >::contains(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::findBucket(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::getNumBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::purge(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::reserve().
|
inlineprotected |
Definition at line 587 of file QuadraticProbingHashTable.h.
References agx::Container::m_capacity.
|
inlineprotected |
Definition at line 584 of file QuadraticProbingHashTable.h.
References agx::Container::m_size.
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::clear(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::eraseBucket(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::purge(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild().
|
inlineprotected |
Definition at line 588 of file QuadraticProbingHashTable.h.
References agx::Container::m_size.
|
inline |
Assignment operator.
Definition at line 269 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::begin(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::clear(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::Container::MAINTAIN_BUFFER, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::reserve(), and agx::Container::size().
|
inline |
Index operator for accessing elements in the hash, inserting it if not found.
| key | - The key to look for |
Definition at line 299 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::find(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second.
|
inline |
Definition at line 308 of file QuadraticProbingHashTable.h.
References agxAssert, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::end(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::find(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second.
|
inline |
Purge the hash table.
Good to use when removing multiple items, since iterators are invalidated after any modification. The purger should be a functor class which takes the key and value as parameters and return true if the pair should be removed from the hash table.
Definition at line 543 of file QuadraticProbingHashTable.h.
References agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::ACTIVE, AGX_HASH_TABLE_GROW_FACTOR, AGX_HASH_TABLE_MIN_SIZE, AGX_HASH_TABLE_SHRINK_FACTOR, AGX_HASH_TABLE_SHRINK_THRESHOLD, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second.
|
inlineprotected |
Rebuild, and optionally resize hash table.
Definition at line 594 of file QuadraticProbingHashTable.h.
References AGX_HASH_TABLE_MIN_SIZE, agxAssert, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::buckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::first, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::isValid(), agx::Container::m_buffer, agx::nextPrime(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numFilled(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::Bucket::second, and agx::Container::size().
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::insert(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::purge(), and agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::reserve().
|
inline |
Reserve capacity in the hash table.
Definition at line 528 of file QuadraticProbingHashTable.h.
References AGX_HASH_TABLE_GROW_THRESHOLD, agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::numBuckets(), agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::rebuild(), and agx::Container::size().
Referenced by agx::QuadraticProbingHashTableImplementation< KeyT, DataT, HashT, AllocatorT >::operator=().