Linux Assemblycollection of fast libraries

Unique hash ADTUniqueHash.h

A hash table is a data structure used to implement an associative array, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found. In a hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Hash table also allows arbitrary insertions and deletions of key-value pairs, at constant average cost per operation.

In many situations, hash tables turn out to be more efficient than b-trees or any other table lookup structure (see the benchmarks). For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

This implementation of hash table allows to store only unique keys, instead of multi hash abstract data type, which stores multiple instances of the same key.

Contents

Function list

C function nameAccess typeC++ function nameAccess type
AllowReadingsRW(constructor) UniqueHashRW
AllowWritingsRW(copy constructor) UniqueHashRW
BwdGoNextRW(destructor) ~UniqueHashRW
BwdGoPrevRWAllowReadingsRW
BwdToFwdRWAllowWritingsRW
BwdToHeadRWBwdGoNextRW
BwdToTailRWBwdGoPrevRW
CapacityROBwdToFwdRW
CompareFunctionROBwdToHeadRW
CopyFunctionROBwdToTailRW
CopyUniqueHashRWCapacityRO
CountKeyROCompareFunctionRO
CountKeysROCopyFunctionRO
DeleteFunctionROCountKeyRO
FindKeyBwdRWCountKeysRO
FindKeyFwdRWDeleteFunctionRO
FindKeyIterBwdROFindKeyBwdRW
FindKeyIterFwdROFindKeyFwdRW
FindKeysBwdRWFindKeyIterBwdRO
FindKeysFwdRWFindKeyIterFwdRO
FindKeysIterBwdROFindKeysBwdRW
FindKeysIterFwdROFindKeysFwdRW
FindVectorBwdRWFindKeysIterBwdRO
FindVectorFwdRWFindKeysIterFwdRO
FindVectorIterBwdROFindVectorBwdRW
FindVectorIterFwdROFindVectorFwdRW
FreeUniqueHashRWFindVectorIterBwdRO
FwdGoNextRWFindVectorIterFwdRO
FwdGoPrevRWFwdGoNextRW
FwdToBwdRWFwdGoPrevRW
FwdToHeadRWFwdToBwdRW
FwdToTailRWFwdToHeadRW
GetBwdROFwdToTailRW
GetFwdROGetBwdRO
GetIterROGetFwdRO
HashFunctionROGetIterRO
InitUniqueHashRWHashFunctionRO
InsertRWInsertRW
IsEmptyROIsEmptyRO
IsInitROIsInitRO
IterGoBwdROIterGoBwdRO
IterGoFwdROIterGoFwdRO
IterToBwdROIterToBwdRO
IterToFwdROIterToFwdRO
IterToHeadROIterToHeadRO
IterToTailROIterToTailRO
KeyTypeROKeyTypeRO
LockReadingsRWLockReadingsRW
LockWritingsRWLockWritingsRW
MaxBwdRWMaxBwdRW
MaxFwdRWMaxFwdRW
MaxIterBwdROMaxIterBwdRO
MaxIterFwdROMaxIterFwdRO
MinBwdRWMinBwdRW
MinFwdRWMinFwdRW
MinIterBwdROMinIterBwdRO
MinIterFwdROMinIterFwdRO
OverrideRWOverrideRW
RemoveBwdRWRemoveBwdRW
RemoveFwdRWRemoveFwdRW
SetBwdRWSetBwdRW
SetFwdRWSetFwdRW
SizeROSizeRO
SwapFwdBwdRWSwapFwdBwdRW
UserDataROUserDataRO
C function nameAccess typeC++ function nameAccess type

Constructor

Cvoid UniqueHash_InitUniqueHash (struct UniqueHash *hash, size_t capacity, KeyCmp kfunc, HashFunc hfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);
C++UniqueHash::UniqueHash (size_t capacity, KeyCmp kfunc, HashFunc hfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new hash table instance.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • capacity - initial count of elements that the hash table can hold. Hash table capacity is auto extended if required.
  • kfunc - pointer to key compare function to sort elements in the hash table. Compare function should follow this prototype.
  • hfunc - pointer to hash function to compute element index in the hash table. Hash function should follow this prototype.
  • cfunc - pointer to copy function for element fields: key and data, or NULL. Copy function should follow this prototype.
  • dfunc - pointer to delete function to call for removing elements, or NULL. Delete function should follow this prototype.
  • ptr - pointer to user's data, required by element copy and delete functions, or NULL.

Return value: None.

Copy constructor

Cvoid UniqueHash_CopyUniqueHash (struct UniqueHash *hash, const UniqueHash *source);
C++UniqueHash::UniqueHash (const UniqueHash &source);

Description: Init new instance of the hash table and copy all elements from the source hash table inside the new one. New hash table has its own data space and doesn't share any memory blocks with the source hash table. Source hash table stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

  • hash - pointer to target hash table
  • source - pointer to source hash table

Return value: None.

Note:Copy constructor does not copy position of forward and backward iterators from source hash table object. New instance should init them before use.

Destructor

Cvoid UniqueHash_FreeUniqueHash (struct UniqueHash *hash);
C++UniqueHash::~UniqueHash (void);

Description: Reset the hash table instance and release all memory blocks are used by the object.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Access predicates

Access predicates is an easy and efficient way to write multithreaded highly concurrent code. Hash table functions may change container elements or manipulate with built in iterators. This can result to data inconsistency among different threads. To solve this possible issue, you have to separate read and write operations to hash table. Write operation can not be invoked in the same time with other write or read operations, and should get exclusive access to the container. Read operations can be processed simultaneously with each other, but not with write operation (because of possible dirty reads).

Access predicates solve these problems and support lock methods for exclusive writes and concurrent reads from different threads. Lock functions return TRUE state only when you get appropriate access to the hash table. They support wait and no wait behaviors. If wait flag is set, then lock functions wait until the lock is taken. In no wait mode they try to get lock for some short period of time (spinlock cycle). And if no success, then return FALSE. Your code may check the return status and do something else instead of just waiting.

Lock operations

Lock operations give you appropriate access type to the hash table and return TRUE, if you get such access, or FALSE, if lock is taken by other thread, and you chose no wait behavior (wait flag is set to FALSE). You can check lock status and run some code while other threads hold the lock. If the thread get the lock, then you can be sure that other threads do not process unsafe operations on the container. To guarantee this other threads also should use lock functions and check returned lock result. When you complete the operations, then release the lock by calling release functions, described below. This will wake up waiting threads for further data processing.

Exclusive access

Cbool UniqueHash_LockReadings (struct UniqueHash *hash, bool wait);
C++bool UniqueHash::LockReadings (bool wait);

Description: Lock read and write operations from other threads and provide exclusive access for hash table modifications (data changes and manipulations with internal iterators). All other threads are waiting until the lock is released by AllowReadings procedure. To guarantee that the thread has exclusive access, all concurrent threads also should use either of lock functions like LockReadings or LockWritings to wait.

Wait flag, is used by the functions, can change their behavior from always wait, until the lock is taken, to no wait behavior. No wait variant tries to get the lock in spinlock cycle, and if no success, then return FALSE state. User's code can check the functions status, and if exclusive lock is taken, then process the hash table modifications, or do something else if lock is not taken.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

  • TRUE (1) if you have exclusive access to hash table.
  • FALSE (0) if the wait flag was not set and exclusive lock is not taken.

Warning:Exclusive lock operation is not recursive. It should be called only once and then released. Thread can do it many times but not in recursive mode.

Note:Do not forget to release exclusive lock when you finished. Use the AllowReadings procedure.

Read only access

Cbool UniqueHash_LockWritings (struct UniqueHash *hash, bool wait);
C++bool UniqueHash::LockWritings (bool wait);

Description: Lock write operations from all threads and provide read only access to hash table. All write threads, are waiting until the lock is released by AllowWritings procedure. All reading threads continue to work. To guarantee that the thread has read only access, all concurrent threads also should use either of lock functions like LockReadings or LockWritings to wait.

Wait flag, is used by the functions, can change their behavior from always wait, until the lock is taken, to no wait behavior. No wait variant tries to get the lock in spinlock cycle, and if no success, then return FALSE state. User's code can check the functions status, and if read only lock is taken, then process the hash table readings, or do something else if lock is not taken.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

  • TRUE (1) if you have read only access to hash table.
  • FALSE (0) if the wait flag was not set and read only lock is not taken.

Warning:Hash table built in futex collects count of concurrent reading threads. So each succeed read lock should always have appropriate release call.

Note:Do not forget to release read only lock when you finished. Use the AllowWritings procedure.

Release operations

Release operations unlock the built in futex and wake up waiters for further data processing. AllowReadings procedure release exclusive lock and wake all writing and reading threads. AllowWritings procedure wake anyone of writing threads if hash table have any of them. Each lock function should always call release function to prevent dead locks.

Releasing of exclusive lock

Cvoid UniqueHash_AllowReadings (struct UniqueHash *hash);
C++void UniqueHash::AllowReadings (void);

Description: Release exclusive lock and allow hash table readings and writings from other threads.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Releasing of read only lock

Cvoid UniqueHash_AllowWritings (struct UniqueHash *hash);
C++void UniqueHash::AllowWritings (void);

Description: Release read only lock and allow hash table writings from other threads. If you have multiple reading threads, then only the last reading thread really release the lock and wake up the writing thread.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Warning:Hash table built in futex collects count of concurrent reading threads. So each succeed read lock should always have appropriate release call.

Insertion of element

Cbool UniqueHash_Insert (struct UniqueHash *hash, const struct pair_t *data);
C++bool UniqueHash::Insert (const pair_t *data);

Description: Insert new element into the hash table.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - pointer to the new element

Return value:

  • TRUE (1) if element was successfully inserted into the hash table.
  • FALSE (0) if the hash table was not able to extend its capacity for the new element, or target key already exists, or functions are called from read only section, started by LockWritings access predicate.

Removing of element

Cbool UniqueHash_RemoveFwd (struct UniqueHash *hash);
bool UniqueHash_RemoveBwd (struct UniqueHash *hash);
C++bool UniqueHash::RemoveFwd (void);
bool UniqueHash::RemoveBwd (void);

Description: Remove element, which is pointed by forward/backward iterator, from the hash table.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value:

  • TRUE (1) if forward/backward iterator points to any hash table element.
  • FALSE (0) if forward/backward iterator is not set, or functions are called from read only section, started by LockWritings access predicate.

Setting element value

Cbool UniqueHash_SetFwd (struct UniqueHash *hash, const struct pair_t *data);
bool UniqueHash_SetBwd (struct UniqueHash *hash, const struct pair_t *data);
C++bool UniqueHash::SetFwd (const pair_t *data);
bool UniqueHash::SetBwd (const pair_t *data);

Description: Set value of the element, which is pointed by forward/backward iterator. If the new key value of the element is the same as the old key, then these functions just replace assigned element data. In other case they remove original element, is pointed by the iterator, then try to insert a new element you provide.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - pointer to the new value of the element

Return value:

  • TRUE (1) if forward/backward iterator points to any hash table element.
  • FALSE (0) if forward/backward iterator position is not set, or memory allocation was failed, or new key already exists, or functions are called from read only section, started by LockWritings access predicate.

Getting element value

Cbool UniqueHash_GetFwd (const struct UniqueHash *hash, struct pair_t *data);
bool UniqueHash_GetBwd (const struct UniqueHash *hash, struct pair_t *data);
C++bool UniqueHash::GetFwd (pair_t *data) const;
bool UniqueHash::GetBwd (pair_t *data) const;

Description: Get value of the element, which is pointed by forward/backward iterator.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the element

Return value:

  • TRUE (1) if forward/backward iterator points to any hash table element.
  • FALSE (0) if forward/backward iterator is not set.
Cbool UniqueHash_GetIter (const struct UniqueHash *hash, struct pair_t *data, ptr_t iter);
C++bool UniqueHash::GetIter (pair_t *data, ptr_t iter) const;

Description: Get value of the element, which is pointed by external iterator.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the element
  • iter - value of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if external iterator points to any hash table element.
  • FALSE (0) if external iterator is not set (has negative value).

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

Overriding element value

Cbool UniqueHash_Override (struct UniqueHash *hash, const struct pair_t *data);
C++bool UniqueHash::Override (const pair_t *data);

Description: Try to insert new element into the hash table. If such key already exists, then functions replace this element with the new value. If hash table has no such key, then functions just insert new value into the hash table.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - pointer to the new element

Return value:

  • TRUE (1) if element was successfully inserted into the hash table.
  • FALSE (0) if the hash table was not able to extend its capacity for the new element, or functions are called from read only section, started by LockWritings access predicate.

Tip:This is a good choice in case you need to have latest snapshot of data. Use it instead of insert function. All existent elements will be replaced with no errors.

Manipulation with forward iterator

Forward iterator allows to walk through the hash table in very fast and efficient way. The main goal of this iterator to enumerate elements in forward (positive) direction: from head (first) to tail (last) element. But it can also move in backward (negative) direction: from tail (last) to head (first) element. It always points to hash table elements, except you did not set its position or went outside the last element. It stays pointing to the same key, even if you insert a new value into the hash table or delete existing element before/after it. If you remove an element, which is pointed by forward iterator, it automatically moves to the next key in forward direction. This trick work well if you need to remove all the elements from the hash table.

Set iterator position

These functions set iterator position to head (first), to tail (last) or to any hash table element by the value of another iterator. When you insert new elements or delete existing keys, the iterators still point to the same elements. To set they initial position, you may use these functions.

To head element

Cvoid UniqueHash_FwdToHead (struct UniqueHash *hash);
C++void UniqueHash::FwdToHead (void);

Description: Move iterator position to head (first) element of the hash table. If hash table is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

To tail element

Cvoid UniqueHash_FwdToTail (struct UniqueHash *hash);
C++void UniqueHash::FwdToTail (void);

Description: Move iterator position to tail (last) element of the hash table. If hash table is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

To backward iterator

Cvoid UniqueHash_FwdToBwd (struct UniqueHash *hash);
C++void UniqueHash::FwdToBwd (void);

Description: Set forward iterator position to current position of backward iterator.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Change iterator position

These functions change iterator position and allow you to move to next and previous elements relatively to current position of the iterator. They are designed to walk through the hash table elements and get neighbor keys for current key.

Move to next position

Cbool UniqueHash_FwdGoNext (struct UniqueHash *hash, size_t pos);
C++bool UniqueHash::FwdGoNext (size_t pos);

Description: Move forward iterator to "pos" positions in forward direction: from head (first) to tail (last) element.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any hash table element.
  • FALSE (0) if iterator is not set, or functions are called from read only section, started by LockWritings access predicate.

Move to prev position

Cbool UniqueHash_FwdGoPrev (struct UniqueHash *hash, size_t pos);
C++bool UniqueHash::FwdGoPrev (size_t pos);

Description: Move forward iterator to "pos" positions in backward direction: from tail (last) to head (first) element.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any hash table element.
  • FALSE (0) if iterator is not set, or functions are called from read only section, started by LockWritings access predicate.

Manipulation with backward iterator

Backward iterator allows to walk through the hash table in very fast and efficient way. The main goal of this iterator to enumerate elements in backward (positive) direction: from tail (last) to head (first) element. But it can also move in forward (negative) direction: from head (first) to tail (last) element. It always points to hash table elements, except you did not set its position or went outside the first element. It stays pointing to the same key, even if you insert a new value into the hash table or delete existing element before/after it. If you remove an element, which is pointed by backward iterator, it automatically moves to the next key in backward direction. This trick work well if you need to remove all the elements from the hash table.

Set iterator position

These functions set iterator position to head (first), to tail (last) or to any hash table element by the value of another iterator. When you insert new elements or delete existing keys, the iterators still point to the same elements. To set they initial position, you may use these functions.

To head element

Cvoid UniqueHash_BwdToHead (struct UniqueHash *hash);
C++void UniqueHash::BwdToHead (void);

Description: Move iterator position to head (first) element of the hash table. If hash table is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

To tail element

Cvoid UniqueHash_BwdToTail (struct UniqueHash *hash);
C++void UniqueHash::BwdToTail (void);

Description: Move iterator position to tail (last) element of the hash table. If hash table is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

To backward iterator

Cvoid UniqueHash_BwdToFwd (struct UniqueHash *hash);
C++void UniqueHash::BwdToFwd (void);

Description: Set backward iterator position to current position of forward iterator.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Change iterator position

These functions change iterator position and allow you to move to next and previous elements relatively to current position of the iterator. They are designed to walk through the hash table elements and get neighbor keys for current key.

Move to next position

Cbool UniqueHash_BwdGoNext (struct UniqueHash *hash, size_t pos);
C++bool UniqueHash::BwdGoNext (size_t pos);

Description: Move backward iterator to "pos" positions in forward direction: from tail (last) to head (first) element.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any hash table element.
  • FALSE (0) if iterator is not set, or functions are called from read only section, started by LockWritings access predicate.

Move to prev position

Cbool UniqueHash_BwdGoPrev (struct UniqueHash *hash, size_t pos);
C++bool UniqueHash::BwdGoPrev (size_t pos);

Description: Move backward iterator to "pos" positions in backward direction: from head (first) to tail (last) element.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any hash table element.
  • FALSE (0) if iterator is not set, or functions are called from read only section, started by LockWritings access predicate.

Manipulation with external iterator

External iterator allows to walk through the hash table in very fast and efficient way. The main goal of this iterator to enumerate elements in highly concurrent multithreaded applications with read only access to all elements. You can not change data, using this iterator, but can do non blocking multithreaded access for reading, searching and counting elements. In opposite to forward and backward iterators the external iterator lost its actual position when you change hash table structure (insert, remove set or overwrite its elements). In such case you should each time to reassign external iterator to hash table head, tail, or current position of forward/backward iterator after changing hash table elements.

Set iterator position

These functions set external iterator position to head (first), to tail (last) or to any hash table element by the value of another iterator. When you insert new element, change its value or delete existing key, the iterator drops its actual position and should be reassign each time you change hash table structure or keys.

To head element

Cptr_t UniqueHash_IterToHead (const struct UniqueHash *hash);
C++ptr_t UniqueHash::IterToHead (void) const;

Description: Return iterator value, which points to head (first) element of the hash table. If hash table is empty, then function returns negative value. This should be treated as non valid value, that means iterator points to non existing element.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • Head iterator value.
  • Negative value if hash table is empty.

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

To tail element

Cptr_t UniqueHash_IterToTail (const struct UniqueHash *hash);
C++ptr_t UniqueHash::IterToTail (void) const;

Description: Return iterator value, which points to tail (last) element of the hash table. If hash table is empty, then function returns negative value. This should be treated as non valid value, that means iterator points to non existing element.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • Tail iterator value.
  • Negative value if hash table is empty.

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

To forward iterator

Cptr_t UniqueHash_IterToFwd (const struct UniqueHash *hash);
C++ptr_t UniqueHash::IterToFwd (void) const;

Description: Return iterator value, which points to the same element as forward iterator. If forward iterator is not set, then function returns negative value. This should be treated as non valid value, that means iterator points to non existing element.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • Forward iterator value.
  • Negative value if forward iterator is not set.

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

To backward iterator

Cptr_t UniqueHash_IterToBwd (const struct UniqueHash *hash);
C++ptr_t UniqueHash::IterToBwd (void) const;

Description: Return iterator value, which points to the same element as backward iterator. If backward iterator is not set, then function returns negative value. This should be treated as non valid value, that means iterator points to non existing element.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • Backward iterator value.
  • Negative value if forward iterator is not set.

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

Change iterator position

These functions change external iterator position and allow you to move in forward and backward direction relatively to current position of the iterator. They are designed to walk through the hash table elements and get neighbor keys for current key.

Move in forward direction

Cbool UniqueHash_IterGoFwd (const struct UniqueHash *hash, size_t pos, ptr_t *iter);
C++bool UniqueHash::IterGoFwd (size_t pos, ptr_t *iter) const;

Description: Move external iterator to "pos" positions in forward direction: from head (first) to tail (last) element.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if external iterator points to any hash table element.
  • FALSE (0) if external iterator is not set (has negative value).

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

Move in backward direction

Cbool UniqueHash_IterGoBwd (const struct UniqueHash *hash, size_t pos, ptr_t *iter);
C++bool UniqueHash::IterGoBwd (size_t pos, ptr_t *iter) const;

Description: Move external iterator to "pos" positions in backward direction: from tail (last) to head (first) element.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • pos - number of positions to move iterator
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if external iterator points to any hash table element.
  • FALSE (0) if external iterator is not set (has negative value).

Tip:This function is optimal choice for multithreaded highly concurrent read only access to hash table elements. It doesn't change any object parameters.

Swapping iterators

Cvoid UniqueHash_SwapFwdBwd (struct UniqueHash *hash);
C++void UniqueHash::SwapFwdBwd (void);

Description: Swap values of forward and backward iterators. Elements, which are pointed by the iterators, stay unchanged.

Access type: RW

Parameters:

  • hash - pointer to the hash table

Return value: None.

Minimum and maximum value

Minimum value

Cbool UniqueHash_MinFwd (struct UniqueHash *hash, struct pair_t *data);
bool UniqueHash_MinBwd (struct UniqueHash *hash, struct pair_t *data);
C++bool UniqueHash::MinFwd (pair_t *data);
bool UniqueHash::MinBwd (pair_t *data);

Description: Scan elements in the hash table in forward/backward direction for element, which has the minimum value of the key. Then set forward/backward iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the hash table is empty, or functions are called from read only section, started by LockWritings access predicate.
Cbool UniqueHash_MinIterFwd (const struct UniqueHash *hash, struct pair_t *data, ptr_t *iter);
bool UniqueHash_MinIterBwd (const struct UniqueHash *hash, struct pair_t *data, ptr_t *iter);
C++bool UniqueHash::MinIterFwd (pair_t *data, ptr_t *iter) const;
bool UniqueHash::MinIterBwd (pair_t *data, ptr_t *iter) const;

Description: Scan elements in the hash table in forward/backward direction for element, which has the minimum value of the key. Then set external iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the hash table is empty.

Tip:These functions are optimal choice for multithreaded highly concurrent read only access to hash table elements. They don't change any object parameters.

Maximum value

Cbool UniqueHash_MaxFwd (struct UniqueHash *hash, struct pair_t *data);
bool UniqueHash_MaxBwd (struct UniqueHash *hash, struct pair_t *data);
C++bool UniqueHash::MaxFwd (pair_t *data);
bool UniqueHash::MaxBwd (pair_t *data);

Description: Scan elements in the hash table in forward/backward direction for element, which has the maximum value of the key. Then set forward/backward iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the hash table is empty, or functions are called from read only section, started by LockWritings access predicate.
Cbool UniqueHash_MaxIterFwd (const struct UniqueHash *hash, struct pair_t *data, ptr_t *iter);
bool UniqueHash_MaxIterBwd (const struct UniqueHash *hash, struct pair_t *data, ptr_t *iter);
C++bool UniqueHash::MaxIterFwd (pair_t *data, ptr_t *iter) const;
bool UniqueHash::MaxIterBwd (pair_t *data, ptr_t *iter) const;

Description: Scan elements in the hash table in forward/backward direction for element, which has the maximum value of the key. Then set external iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the hash table is empty.

Tip:These functions are optimal choice for multithreaded highly concurrent read only access to hash table elements. They don't change any object parameters.

Key searching

Following functions search hash table for first/last element, which is equal to the required key, then set forward/backward iterator position to that element. If required element is found, then they store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position and "data" structure stay unchanged.

Single key searching

Cbool UniqueHash_FindKeyFwd (struct UniqueHash *hash, struct pair_t *data, union adt_t key);
bool UniqueHash_FindKeyBwd (struct UniqueHash *hash, struct pair_t *data, union adt_t key);
C++bool UniqueHash::FindKeyFwd (pair_t *data, adt_t key);
bool UniqueHash::FindKeyBwd (pair_t *data, adt_t key);

Description: Scan the hash table for first (FindKeyFwd) or last (FindKeyBwd) element, which is equal to the key, and set forward/backward iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position stay unchanged.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • key - key value to process

Return value:

  • TRUE (1) if required element was found in the hash table.
  • FALSE (0) if the hash table is empty, or has no key, which satisfy the search condition, or functions are called from read only section, started by LockWritings access predicate.
Cbool UniqueHash_FindKeyIterFwd (const struct UniqueHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
bool UniqueHash_FindKeyIterBwd (const struct UniqueHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueHash::FindKeyIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
bool UniqueHash::FindKeyIterBwd (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the hash table for first (FindKeyIterFwd) or last (FindKeyIterBwd) element, which is equal to the key, and set external iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position stay unchanged.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • key - key value to find
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if required element was found in the hash table.
  • FALSE (0) if the hash table is empty, or has no key, which satisfy the search condition.

Tip:These functions are optimal choice for multithreaded highly concurrent read only access to hash table elements. They don't change any object parameters.

Keys set searching

Cbool UniqueHash_FindKeysFwd (struct UniqueHash *hash, struct pair_t *data, const union adt_t keys[], size_t size);
bool UniqueHash_FindKeysBwd (struct UniqueHash *hash, struct pair_t *data, const union adt_t keys[], size_t size);
C++bool UniqueHash::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size);
bool UniqueHash::FindKeysBwd (pair_t *data, const adt_t keys[], size_t size);

Description: Scan the hash table for first (FindKeysFwd) or last (FindKeysBwd) element, which is equal to any key in the set of keys, and set forward/backward iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position stay unchanged.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • key - key value to process

Return value:

  • TRUE (1) if required element was found in the hash table.
  • FALSE (0) if the hash table is empty, or has no keys, which satisfy the search condition, or functions are called from read only section, started by LockWritings access predicate.
Cbool UniqueHash_FindKeysIterFwd (const struct UniqueHash *hash, struct pair_t *data, const union adt_t keys[], size_t size, ptr_t *iter);
bool UniqueHash_FindKeysIterBwd (const struct UniqueHash *hash, struct pair_t *data, const union adt_t keys[], size_t size, ptr_t *iter);
C++bool UniqueHash::FindKeysIterFwd (pair_t *data, const adt_t keys[], size_t size, ptr_t *iter) const;
bool UniqueHash::FindKeysIterBwd (pair_t *data, const adt_t keys[], size_t size, ptr_t *iter) const;

Description: Scan the hash table for first (FindKeysIterFwd) or last (FindKeysIterBwd) element, which is equal to any key in the set of keys, and set external iterator position to that element. If required element is found, then functions store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position stay unchanged.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - address where to return the value of the found element
  • keys - array of keys to find in the hash table
  • size - size of array of keys
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • TRUE (1) if required element was found in the hash table.
  • FALSE (0) if the hash table is empty, or has no keys, which satisfy the search condition.

Tip:These functions are optimal choice for multithreaded highly concurrent read only access to hash table elements. They don't change any object parameters.

Vectorized searching

Csize_t UniqueHash_FindVectorFwd (struct UniqueHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
size_t UniqueHash_FindVectorBwd (struct UniqueHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
C++size_t UniqueHash::FindVectorFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);
size_t UniqueHash::FindVectorBwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);

Description: Scan the hash table for set of keys are placed in vector of pairs, and return an occurrence of each key, starting from first element (FindVectorFwd) or last element (FindVectorBwd). If required element is found, then functions store its value into data array, while it has enough space or until all of keys are done.
If key set processing is terminated by no more space in output data array, then functions set forward/backward iterator position to last found element, and decrement "vsize" variable to reflect count of elements need to be processed by sequential function call. In such case you may recall this functions one more time until they return 0 (means the input vector is empty now and all elements in it are processed).
If no values were found, then the iterator position stay unchanged and functions return 0.

Access type: RW

Parameters:

  • hash - pointer to the hash table
  • data - pointer to output vector of found pairs
  • size - size of output vector (count of elements that buffer can hold)
  • vector - array of pairs, which key fields hold keys to find in the hash table
  • vsize - pointer to the variable that holds size of input array of pairs. It will be decremented by each sequential function call.

Return value:

  • Count of elements into the output vector of pairs.
  • 0 (zero) if no element is found, or input vector is empty, or functions are called from read only section, started by LockWritings access predicate.

Note:Functions may internally reorder elements into input array of pairs to accelerate processing of vector elements. You should not assume that output keys order will reflect input keys order. To have correct sort order for output pairs just do post sorting procedure.

Csize_t UniqueHash_FindVectorIterFwd (const struct UniqueHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
size_t UniqueHash_FindVectorIterBwd (const struct UniqueHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
C++size_t UniqueHash::FindVectorIterFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;
size_t UniqueHash::FindVectorIterBwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;

Description: Scan the hash table for set of keys are placed in vector of pairs, and return an occurrence of each key, starting from first element (FindVectorIterFwd) or last element (FindVectorIterBwd). If required element is found, then functions store its value into data array, while it has enough space or until all of keys are done.
If key set processing is terminated by no more space in output data array, then functions set external iterator position to last found element, and decrement "vsize" variable to reflect count of elements need to be processed by sequential function call. In such case you may recall this functions one more time until they return 0 (means the input vector is empty now and all elements in it are processed).
If no values were found, then the iterator position stay unchanged and functions return 0.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • data - pointer to output vector of found pairs
  • size - size of output vector (count of elements that buffer can hold)
  • vector - array of pairs, which key fields hold keys to find in the hash table
  • vsize - pointer to the variable that holds size of input array of pairs. It will be decremented by each sequential function call.
  • iter - address of external iterator, which is used to point to hash table element

Return value:

  • Count of elements into the output vector of pairs.
  • 0 (zero) if no element is found, or input vector is empty.

Note:Functions may internally reorder elements into input array of pairs to accelerate processing of vector elements. You should not assume that output keys order will reflect input keys order. To have correct sort order for output pairs just do post sorting procedure.

Tip:These functions are optimal choice for multithreaded highly concurrent read only access to hash table elements. They don't change any object parameters.

Key counting

Following functions scan elements in the hash table, and return count of matches to the key or to the set of keys.

Single key counting

Csize_t UniqueHash_CountKey (const struct UniqueHash *hash, union adt_t key);
C++size_t UniqueHash::CountKey (adt_t key) const;

Description: Scan elements in the hash table and return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • key - key value to find in the hash table

Return value: Count of the elements, which are equal to the specified key.

Keys set counting

Csize_t UniqueHash_CountKeys (const struct UniqueHash *hash, const union adt_t keys[], size_t size);
C++size_t UniqueHash::CountKeys (const adt_t keys[], size_t size) const;

Description: Scan elements in the hash table and return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

  • hash - pointer to the hash table
  • keys - array of keys to find in the hash table
  • size - size of array of keys

Return value: Count of the elements, which are equal to any key in the set of keys.

Hash table properties

Hash table built-in key type

Csize_t UniqueHash_KeyType (const struct UniqueHash *hash);
C++size_t UniqueHash::KeyType (void) const;

Description: Return built-in key type and built-in key compare function, is assigned to this type, which internally used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Built-in key type and corresponding built-in key compare function. Full list of such types is defined in built-in key types table.

Hash table key compare function

CKeyCmp UniqueHash_CompareFunction (const struct UniqueHash *hash);
C++KeyCmp UniqueHash::CompareFunction (void) const;

Description: Return pointer to key compare function is used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Pointer to key compare function, which conforms to this prototype.

Hash table hash function

CHashFunc UniqueHash_HashFunction (const struct UniqueHash *hash);
C++HashFunc UniqueHash::HashFunction (void) const;

Description: Return pointer to hash function is used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Pointer to hash function, which conforms to this prototype.

Hash table pair copy function

CCopyFunc UniqueHash_CopyFunction (const struct UniqueHash *hash);
C++CopyFunc UniqueHash::CopyFunction (void) const;

Description: Return pointer to copy function for element fields: key and data, is used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Pointer to copy function for element fields, which conforms to this prototype.

Hash table pair delete function

CDelFunc UniqueHash_DeleteFunction (const struct UniqueHash *hash);
C++DelFunc UniqueHash::DeleteFunction (void) const;

Description: Return pointer to delete function to call for removing elements, which is used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Pointer to delete function to call for removing elements, which conforms to this prototype.

Hash table user's data

Cvoid* UniqueHash_UserData (const struct UniqueHash *hash);
C++void* UniqueHash::UserData (void) const;

Description: Return pointer to user's data, required by element copy and delete functions, are used by the hash table.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Pointer to user's data, required by element copy and delete functions.

Hash table capacity

Csize_t UniqueHash_Capacity (const struct UniqueHash *hash);
C++size_t UniqueHash::Capacity (void) const;

Description: Return the hash table capacity.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Max count of objects that hash table can hold.

Hash table size

Csize_t UniqueHash_Size (const struct UniqueHash *hash);
C++size_t UniqueHash::Size (void) const;

Description: Return current size of the hash table (count of allocated objects).

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value: Count of allocated objects inside the hash table.

Check if hash table is empty

Cbool UniqueHash_IsEmpty (const struct UniqueHash *hash);
C++bool UniqueHash::IsEmpty (void) const;

Description: Check if the hash table is empty.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • TRUE (1) if hash table is empty.
  • FALSE (0) if hash table is not empty.

Check if hash table is initialized

Cbool UniqueHash_IsInit (const struct UniqueHash *hash);
C++bool UniqueHash::IsInit (void) const;

Description: Check if the hash table is initialized.

Access type: RO

Parameters:

  • hash - pointer to the hash table

Return value:

  • TRUE (1) if hash table is initialized.
  • FALSE (0) if hash table is not initialized.
Copyright 2012-2016 Jack Black. All rights reserved.