pwxlib
0.8.9
Tools Library for C++ Development
|
Virtual base class for hash containers. More...
#include <pwxVTHashBase.h>
Public Types | |
typedef VContainer | base_t |
Base type of the hash. | |
typedef VTHashBase< key_t, data_t, elem_t > | hash_t |
Type of this hash. | |
typedef VContainer | list_t |
typedef std::mutex | lock_t |
Use standard mutex if no spinlocks are used. | |
Public Member Functions | |
VTHashBase (uint32_t initSize, uint32_t keyLen_, double maxLoad_, double dynGrow_) | |
default constructor More... | |
VTHashBase (uint32_t initSize, void(*destroy_)(data_t *data), uint32_t(*hash_)(const key_t *key, uint32_t keyLen), uint32_t keyLen_, double maxLoad_, double dynGrow_) noexcept | |
full constructor with key length More... | |
VTHashBase (uint32_t initSize, void(*destroy_)(data_t *data), uint32_t(*hash_)(const key_t *key), double maxLoad_, double dynGrow_) | |
full constructor without key length More... | |
VTHashBase (void(*destroy_)(data_t *data), uint32_t(*hash_)(const key_t *key, uint32_t keyLen), uint32_t keyLen_, double maxLoad_, double dynGrow_) noexcept | |
limiting user method constructor More... | |
VTHashBase (void(*destroy_)(data_t *data), uint32_t(*hash_)(const key_t *key), double maxLoad_, double dynGrow_) noexcept | |
user method constructor More... | |
VTHashBase (void(*destroy_)(data_t *data), double maxLoad_, double dynGrow_) noexcept | |
destroy method constructor More... | |
VTHashBase (uint32_t keyLen_, double maxLoad_, double dynGrow_) noexcept | |
key length constructor More... | |
VTHashBase (double maxLoad_, double dynGrow_) noexcept | |
pseudo empty constructor More... | |
VTHashBase () PWX_DELETE | |
Empty ctor is not available. | |
VTHashBase (const hash_t &src) | |
copy constructor More... | |
virtual | ~VTHashBase () noexcept |
default destructor More... | |
virtual uint32_t | add (const elem_t &src) |
add an element to the hash More... | |
virtual uint32_t | add (const key_t &key, data_t *data) |
add a key-data-pair to the hash More... | |
virtual void | clear () noexcept |
delete all elements More... | |
virtual uint32_t | delElem (elem_t &elem) |
delete the element elem More... | |
virtual uint32_t | delKey (const key_t &key) |
delete the element with the key key More... | |
virtual void | disable_thread_safety () noexcept |
disable thread safety More... | |
virtual bool | empty () const noexcept |
return true if this container is empty | |
virtual void | enable_thread_safety () noexcept |
enable thread safety More... | |
virtual bool | exists (const key_t &key) const noexcept |
return true if an element with key exists | |
virtual elem_t * | get (const key_t &key) const noexcept |
returns a read-only pointer to the element with the key key More... | |
virtual elem_t * | get (const key_t &key) noexcept |
returns a read/write pointer to the element with the key key More... | |
virtual data_t & | getData (const key_t &key) const |
returns a read-only reference to the stored data with key key More... | |
virtual data_t & | getData (const key_t &key) |
returns a read/write reference to the stored data with key key More... | |
virtual uint32_t | getHops (const key_t &key) const noexcept |
return the number of "hops" needed when the element was inserted More... | |
virtual uint32_t | grow (uint32_t targetSize) |
grow the size of a hash table More... | |
virtual elem_t * | pop () noexcept |
short alias for pop_back() More... | |
virtual elem_t * | pop_back () noexcept |
alias to remove the last element (tail) More... | |
virtual elem_t * | pop_front () noexcept |
alias to remove the first element (head) More... | |
virtual uint32_t | push (const key_t &key, data_t *data) |
simple wrapper to add() to be conformant with the other container types | |
virtual uint32_t | push (const elem_t &src) |
simple wrapper to add() to be conformant with the other container types | |
virtual uint32_t | push_back (const key_t &key, data_t *data) |
simple wrapper to add() to be conformant with the other container types | |
virtual uint32_t | push_back (const elem_t &src) |
simple wrapper to add() to be conformant with the other container types | |
virtual uint32_t | push_front (const key_t &key, data_t *data) |
simple wrapper to add() to be conformant with the other container types | |
virtual uint32_t | push_front (const elem_t &src) |
simple wrapper to add() to be conformant with the other container types | |
virtual elem_t * | remElem (elem_t &elem) noexcept |
remove the element with the key key More... | |
virtual elem_t * | remKey (const key_t &key) noexcept |
remove the element with the key key More... | |
virtual elem_t * | shift () noexcept |
simple wrapper to pop_front() to be conformant with other containers | |
uint32_t | size () const noexcept |
return the number of stored elements | |
uint32_t | sizeMax () const noexcept |
return the maximum number of places (elements for open, buckets for chained hashes) | |
virtual uint32_t | unshift (const key_t &key, data_t *data) |
simple wrapper to add() to be conformant with other containers | |
virtual uint32_t | unshift (const elem_t &src) |
simple wrapper to add() to be conformant with other containers | |
virtual hash_t & | operator= (const hash_t &rhs) |
assignment operator More... | |
virtual hash_t & | operator+= (const hash_t &rhs) |
addition assignment operator More... | |
virtual hash_t & | operator-= (const hash_t &rhs) |
substraction assignment operator More... | |
virtual const elem_t * | operator[] (const int64_t index) const noexcept |
return a read-only pointer to the element with the given index More... | |
virtual elem_t * | operator[] (int64_t index) noexcept |
return a read/write pointer to the element with the given index More... | |
bool | beThreadSafe () const noexcept |
true if thread safety is turned on More... | |
void | beThreadSafe (bool doLock) noexcept |
set thread safety to doLock More... | |
bool | clear_locks () noexcept |
remove all locks More... | |
bool | destroyed () const noexcept |
if true the object will no longer lock More... | |
void | do_locking (bool doLock) noexcept |
set thread safety to doLock More... | |
bool | is_locked () const noexcept |
return true if this object is locked More... | |
bool | is_locking () const noexcept |
true if thread safety is turned on More... | |
void | lock () noexcept |
lock this object More... | |
uint32_t | lock_count () const noexcept |
number of locks this thread holds on this object More... | |
bool | try_lock () noexcept |
try to lock and return at once More... | |
void | unlock () noexcept |
unlock this object More... | |
Protected Member Functions | |
virtual uint32_t | protDelete (elem_t *removed) |
Delete the element removed. More... | |
virtual uint32_t | protGetHash (const key_t *key) const |
use hashBuilder to generate a hash out of a key More... | |
bool | protIsVacated (const uint32_t index) const noexcept |
return true if the specified position is vacated More... | |
Protected Attributes | |
void(* | destroy )(data_t *data) = nullptr |
uint32_t(* | hash_user )(const key_t *key) = nullptr |
uint32_t(* | hash_limited )(const key_t *key, uint32_t keyLen) = nullptr |
aui32_t | clearing = ATOMIC_VAR_INIT(0) |
Needed by the control macros. | |
eChainHashMethod | CHMethod = CHM_Division |
Which Hashing method is used. | |
aui32_t | growing = ATOMIC_VAR_INIT(0) |
Needed by the control macros. | |
CHashBuilder | hashBuilder |
instance that will handle the key generation | |
aui32_t | hashSize |
number of places to maintain | |
elem_t ** | hashTable |
the central array that is our hash | |
aui32_t | inserting = ATOMIC_VAR_INIT(0) |
Needed by the control macros. | |
aui32_t | removing = ATOMIC_VAR_INIT(0) |
Needed by the control macros. | |
char * | vacChar |
alias pointer to get around the empty elem_t ctor restriction | |
elem_t * | vacated |
The Open Hash sets empty places to point at this. | |
abool_t | isDestroyed |
Should be set to true by the destructors of deriving classes. | |
abool_t | doRenumber = ATOMIC_VAR_INIT(false) |
If set to true, a renumbering is done before retrieving elements by index. | |
aui32_t | eCount = ATOMIC_VAR_INIT(0) |
Current number of elements. | |
mord_t | memOrdLoad |
to be used with atomic::load() | |
mord_t | memOrdStore |
to be used with atomic::store() | |
Virtual base class for hash containers.
There are two basic hash table containers, TChainHash and TOpenHash. The difference is the way the hash tables order their data and resolve collisions. While the chained hash table TChainHash uses buckets, the open hash table TOpenHash uses double hash probing.
However, most operations are the same once the place for an element evaluated out of its key is known. These common operations are done in this base class, which call pure virtual private methods, that are then defined in TChainHash and TOpenHash to provide the proper collision resolving.
|
inline |
default constructor
The default destructor takes a length for the initial size and a length for the key. Further it initializes the hash table.
The key length is only needed if you use C-String keys without 0-byte delimiter or if you are using C-Strings or std::string keys that can be so long that you want to limit the length of the key itself and ignore further characters.
To set any of the user methods, one of the specialized constructors can be used.
[in] | initSize | Initial size of the hash table. |
[in] | keyLen_ | Length of the key to limit hash generation. |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
full constructor with key length
The full constructor initializes an empty hash with user defined delete method, hashing method and key length. The initial size is the initSize
[in] | initSize | The initial size of the table. |
[in] | destroy_ | A pointer to a function that is to be used to destroy the data |
[in] | hash_ | A pointer to a function that can hash the keys that are stored and takes an optional keyLen |
[in] | keyLen_ | optional limiting key length for C-Strings and std::string keys |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inline |
full constructor without key length
The full constructor initializes an empty hash with user defined delete method and hashing method withour key length. The initial size is the initSize
[in] | initSize | The initial size of the table. |
[in] | destroy_ | A pointer to a function that is to be used to destroy the data |
[in] | hash_ | A pointer to a function that can hash the keys that are stored |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
limiting user method constructor
This constructor only takes a destroy method and a hash method with explicit key length.
[in] | destroy_ | A pointer to a function that is to be used to destroy the data |
[in] | hash__ | A pointer to a function that can hash the keys that are stored and takes an optional keyLen |
[in] | keyLen_ | optional limiting key length for C-Strings and std::string keys |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
user method constructor
This constructor only takes a destroy method and a hash method without explicit key length.
[in] | destroy_ | A pointer to a function that is to be used to destroy the data |
[in] | hash__ | A pointer to a function that can hash the keys that are stored and takes an optional keyLen |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
destroy method constructor
This constructor only takes a destroy method.
[in] | destroy_ | A pointer to a function that is to be used to destroy the data |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
key length constructor
This constructor only takes a key length and sets the destroy and hash methods to nullptr.
[in] | keyLen_ | optional limiting key length for C-Strings and std::string keys |
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inlinenoexcept |
pseudo empty constructor
The pseudo empty constructor uses the default constructor to set the data destroy method and the hash method to the null pointer with full key usage.
However, because of the very different needs of chained versus open hash tables, both the maximum load factor and the dynamic growth rate must be set. A true empty constructor is not possible.
[in] | maxLoad_ | maximum load factor that triggers automatic growth. |
[in] | dynGrow_ | growth rate applied when the maximum load factor is reached. |
|
inline |
copy constructor
Builds a copy of all elements of src.
If a new element can not be created, a pwx::CException with the name "ElementCreationFailed" is thrown.
[in] | src | reference of the hash to copy. |
|
virtualnoexcept |
default destructor
This destructor will delete all elements currently stored. There is no need to clean up manually before deleting the hash.
|
inlinevirtual |
add an element to the hash
this method copies the element src into the hash table if the key of the element can not be found, yet.
[in] | src | reference of the element to copy |
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator+=(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::push(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::push_back(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::push_front(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::unshift().
|
inlinevirtual |
add a key-data-pair to the hash
this method adds a new element to the hash if key is not present, yet.
[in] | key | the key of the new element |
[in] | data | pointer to the data of the new element |
|
noexceptinherited |
true if thread safety is turned on
return true if thread safety mode is turned on
Referenced by pwx::private_::CThreadElementStore::clear(), pwx::private_::CThreadElementStore::curr(), pwx::private_::CThreadElementStore::disable_thread_safety(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::disable_thread_safety(), pwx::private_::CThreadElementStore::enable_thread_safety(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::enable_thread_safety(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator+=(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator=().
|
noexceptinherited |
set thread safety to doLock
set thread safety mode to doLock This is just an alias for do_locking().
|
inlinevirtualnoexcept |
delete all elements
This is a quick way to get rid of all elements at once. If a destroy() function was set, it is used for the data deletion. Otherwise it is assumed that data_t responds to the delete operator.
Reimplemented from pwx::VContainer.
Referenced by pwx::operator-(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator-=(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator=().
|
noexceptinherited |
remove all locks
clear all locks from this thread.
If this thread is the current owner of the lock, and if there are locks in place, they are all cleared.
If this thread is not the owner, the method simply returns false.
References CURRENT_THREAD_ID.
|
inlinevirtual |
delete the element elem
If the hash table does not contain this element, nothing happens.
To only remove the element from the hash for further usage, use remElem(elem) instead.
If the deletion of the element throws an exception, it will be turned into a pwx CException and passed on.
Warning: The element elem is invalid after this operation!
elem | reference to the element to delete |
|
inlinevirtual |
delete the element with the key key
If the hash table does not contain an element with the key key, nothing happens.
To only remove the element from the hash for further usage, use remKey(key) instead.
If the deletion of the element throws an exception, it will be turned into a pwx CException and passed on.
key | reference to the key to search for |
|
noexceptinherited |
if true the object will no longer lock
returns true if the data was destroyed
The destructor of TSingleElement and TDoubleElement will try to get a final lock on the element when it is destroyed. If another thread acquires a lock between the data destruction and this final dtor lock, destroyed() will return "true".
References pwx::CLockable::isDestroyed, and pwx::CLockable::memOrdLoad.
Referenced by pwx::TSingleElement< data_t >::insertBefore(), pwx::THashElement< size_t, curr_t >::insertNext(), pwx::TDoubleElement< data_t >::insertNext(), pwx::TSingleElement< data_t >::insertNext(), and pwx::TDoubleElement< data_t >::insertPrev().
|
inlinevirtualnoexcept |
disable thread safety
This method disables all thread safety measures.
Warning: It is completely unchecked whether the container is used by more than one thread. If concurrent threads work with this container while this method is called, the outcome is unpredictable.
Further this method disables all locking mechanisms in all elements stored and all elements that are added after calling this method. Calling this method with a lot of elements stored is therefore rather costly!
Reimplemented from pwx::VContainer.
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator+=().
|
noexceptinherited |
set thread safety to doLock
switch whether to really use locking or not.
With this method you can switch the locking mechanics on/off for objects to be used in concurrency or strictly single threaded. The default is to turn locking on.
[in] | doLock | true to turn locking on, false to turn it off. |
References CURRENT_THREAD_ID.
Referenced by pwx::VElement::disable_thread_safety(), and pwx::VElement::enable_thread_safety().
|
inlinevirtualnoexcept |
enable thread safety
This method enables all thread safety measures.
Warning: This method enables all locking mechanisms in all elements stored and all elements that are added after calling this method. Calling this method with a lot of elements stored is therefore rather costly!
Reimplemented from pwx::VContainer.
|
inlinevirtualnoexcept |
returns a read-only pointer to the element with the key key
[in] | key | the key to search for |
|
inlinevirtualnoexcept |
returns a read/write pointer to the element with the key key
[in] | key | the key to search for |
|
inlinevirtual |
returns a read-only reference to the stored data with key key
If the data pointer is nullptr, a pwx::CException with the name "NullDataException" is thrown.
[in] | key | the key to search for |
|
inlinevirtual |
returns a read/write reference to the stored data with key key
If the data pointer is nullptr, a pwx::CException with the name "NullDataException" is thrown.
[in] | key | the key to search for |
|
inlinevirtualnoexcept |
return the number of "hops" needed when the element was inserted
This method returns the number of hops (or collisions) that were needed when inserting the element.
If the element is nowhere inserted, it returns zero.
[in] | key | The key to search for |
|
inlinevirtual |
grow the size of a hash table
This method increases the hash table by creating a new table and moving all elements into the new one.
This method does not shrink a table. It does nothing if targetSize is not larger than the current size. Therefore the resulting size is returned for you to check.
[in] | targetSize | the new size of the hash. |
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::add(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator+=(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator=().
|
noexceptinherited |
return true if this object is locked
return true if this object is currently locked
References pwx::CLockable::memOrdLoad.
|
noexceptinherited |
true if thread safety is turned on
return true if the locking is turned on.
|
noexceptinherited |
lock this object
lock
Lock this object for the current thread if locking is enabled.
References CURRENT_THREAD_ID, pwx::CLockable::isDestroyed, and pwx::CLockable::memOrdLoad.
Referenced by pwx::private_::CThreadElementStore::curr().
|
noexceptinherited |
number of locks this thread holds on this object
return the number of locks on this object this thread has
References CURRENT_THREAD_ID.
|
inlinevirtual |
addition assignment operator
Add all elements from rhs to this hash.
Warning: The table size is increased if rhs has a larger size, no matter whether the element count makes this neccessary or not!
[in] | rhs | reference of the hash to add. |
|
inlinevirtual |
substraction assignment operator
Remove all elements from rhs from this hash.
[in] | rhs | reference of the hash to substract. |
|
inlinevirtual |
assignment operator
Clears this hash and copies all elements from rhs into this hash. The destroy and hash methods are copied as well as the thread safety state
[in] | rhs | reference of the hash to copy. |
|
inlinevirtualnoexcept |
return a read-only pointer to the element with the given index
This operator retrieves an element by index like an array. The pointer given back is read-only.
There will be no exception if the index is out of range, it will be wrapped to press it into the valid range. This means that an index of -1 can be used to retrieve the last element (tail) for instance.
If there is no element at the specific position of the hash table, the operator returns nullptr.
[in] | index | the index of the element to find. |
|
inlinevirtualnoexcept |
return a read/write pointer to the element with the given index
This operator retrieves an element by index like an array. The pointer given back is write enabled, so use with care.
There will be no exception if the index is out of range, it will be wrapped to press it into the valid range. This means that an index of -1 can be used to retrieve the last element (tail) for instance.
If the hash is empty, the operator returns nullptr.
If you use this operator to quickly access head or tail, neither the currently used internal pointer nor number are changed. Head and tail are given back directly.
[in] | index | the index of the element to find. |
|
inlinevirtualnoexcept |
short alias for pop_back()
This is a convenience function that removes the last element found in the table. As it has to traverse the table, this operation can be costly for large tables that only have elements somewhere at the beginning.
You have to delete the removed element by yourself.
If the hash table is empty, nullptr is returned.
|
inlinevirtualnoexcept |
alias to remove the last element (tail)
You have to delete the removed element by yourself. If you do not intent to work with the removed element, use delNext instead.
If the list is empty, nullptr is returned.
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::pop().
|
inlinevirtualnoexcept |
alias to remove the first element (head)
This is a convenience function that removes the first element found in the table. As it has to traverse the table, this operation can be costly for large tables that only have elements somewhere at the end.
You have to delete the removed element by yourself.
If the hash table is empty, nullptr is returned.
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::shift().
|
inlineprotectedvirtual |
Delete the element removed.
Important: this method will throw "illegal_delete" if removed is actually not removed from the hash. Making sure this method is only called with a removed element allows to use it without a lock on the hash itself.
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::delElem(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::delKey(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator-=().
|
inlineprotectedvirtual |
use hashBuilder to generate a hash out of a key
key | pointer to the key to hash |
|
inlineprotectednoexcept |
return true if the specified position is vacated
If index is out of range, false is returned.
[in] | index | the index to check |
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::disable_thread_safety(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::enable_thread_safety(), pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator+=(), and pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator-=().
|
inlinevirtualnoexcept |
remove the element with the key key
If the hash table does not contain an element with the key key, nullptr is returned.
If you remove an element from the hash, you are responsible to delete the element yourself. If you do not need to use the element, use delElem(key) instead.
elem | reference of the element to search for |
|
inlinevirtualnoexcept |
remove the element with the key key
If the hash table does not contain an element with the key key, nullptr is returned.
If you remove an element from the hash, you are responsible to delete the element yourself. If you do not need to use the element, use delKey(key) instead.
key | reference to the key to search for |
Referenced by pwx::VTHashBase< key_t, data_t, THashElement< key_t, data_t > >::operator-=().
|
noexceptinherited |
try to lock and return at once
try_lock
Try to lock this object.
References CURRENT_THREAD_ID, pwx::CLockable::isDestroyed, and pwx::CLockable::memOrdLoad.
Referenced by pwx::try_locks().
|
noexceptinherited |
unlock this object
unlock
If locking is disabled or if the current thread does not hold the lock, nothing happens. Otherwise the last lock is released.
References CURRENT_THREAD_ID.
Referenced by pwx::private_::CThreadElementStore::curr(), pwx::try_locks(), and pwx::unlock_all().