Linux Assemblycollection of fast libraries

Multi hash ADTMultiHash.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 multiple instances of the same key, instead of unique hash abstract data type, which stores only unique keys.

Contents

Function list

C function nameAccess typeC++ function nameAccess type
AllowReadingsRW(constructor) MultiHashRW
AllowWritingsRW(copy constructor) MultiHashRW
BwdGoNextRW(destructor) ~MultiHashRW
BwdGoPrevRWAllowReadingsRW
BwdToFwdRWAllowWritingsRW
BwdToHeadRWBwdGoNextRW
BwdToTailRWBwdGoPrevRW
CapacityROBwdToFwdRW
CheckDupROBwdToHeadRW
CompareFunctionROBwdToTailRW
CopyFunctionROCapacityRO
CopyMultiHashRWCheckDupRO
CountKeyROCompareFunctionRO
CountKeysROCopyFunctionRO
DeleteFunctionROCountKeyRO
FindDupBwdRWCountKeysRO
FindDupFwdRWDeleteFunctionRO
FindDupIterBwdROFindDupBwdRW
FindDupIterFwdROFindDupFwdRW
FindKeyBwdRWFindDupIterBwdRO
FindKeyFwdRWFindDupIterFwdRO
FindKeyIterBwdROFindKeyBwdRW
FindKeyIterFwdROFindKeyFwdRW
FindKeysBwdRWFindKeyIterBwdRO
FindKeysFwdRWFindKeyIterFwdRO
FindKeysIterBwdROFindKeysBwdRW
FindKeysIterFwdROFindKeysFwdRW
FindSequenceBwdRWFindKeysIterBwdRO
FindSequenceFwdRWFindKeysIterFwdRO
FindSequenceIterBwdROFindSequenceBwdRW
FindSequenceIterFwdROFindSequenceFwdRW
FindVectorBwdRWFindSequenceIterBwdRO
FindVectorFwdRWFindSequenceIterFwdRO
FindVectorIterBwdROFindVectorBwdRW
FindVectorIterFwdROFindVectorFwdRW
FreeMultiHashRWFindVectorIterBwdRO
FwdGoNextRWFindVectorIterFwdRO
FwdGoPrevRWFwdGoNextRW
FwdToBwdRWFwdGoPrevRW
FwdToHeadRWFwdToBwdRW
FwdToTailRWFwdToHeadRW
GetBwdROFwdToTailRW
GetFwdROGetBwdRO
GetIterROGetFwdRO
HashFunctionROGetIterRO
InitMultiHashRWHashFunctionRO
InsertRWInsertRW
IsEmptyROIsEmptyRO
IsInitROIsInitRO
IterGoBwdROIterGoBwdRO
IterGoFwdROIterGoFwdRO
IterToBwdROIterToBwdRO
IterToFwdROIterToFwdRO
IterToHeadROIterToHeadRO
IterToTailROIterToTailRO
KeyTypeROKeyTypeRO
LockReadingsRWLockReadingsRW
LockWritingsRWLockWritingsRW
MaxBwdRWMaxBwdRW
MaxFwdRWMaxFwdRW
MaxIterBwdROMaxIterBwdRO
MaxIterFwdROMaxIterFwdRO
MinBwdRWMinBwdRW
MinFwdRWMinFwdRW
MinIterBwdROMinIterBwdRO
MinIterFwdROMinIterFwdRO
RemoveBwdRWRemoveBwdRW
RemoveFwdRWRemoveFwdRW
SetBwdRWSetBwdRW
SetFwdRWSetFwdRW
SizeROSizeRO
SwapFwdBwdRWSwapFwdBwdRW
UniqueRWUniqueRW
UserDataROUserDataRO
C function nameAccess typeC++ function nameAccess type

Constructor

Cvoid MultiHash_InitMultiHash (struct MultiHash *hash, size_t capacity, KeyCmp kfunc, HashFunc hfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);
C++MultiHash::MultiHash (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 MultiHash_CopyMultiHash (struct MultiHash *hash, const MultiHash *source);
C++MultiHash::MultiHash (const MultiHash &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 MultiHash_FreeMultiHash (struct MultiHash *hash);
C++MultiHash::~MultiHash (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 MultiHash_LockReadings (struct MultiHash *hash, bool wait);
C++bool MultiHash::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 MultiHash_LockWritings (struct MultiHash *hash, bool wait);
C++bool MultiHash::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 MultiHash_AllowReadings (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_AllowWritings (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_Insert (struct MultiHash *hash, const struct pair_t *data);
C++bool MultiHash::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 functions are called from read only section, started by LockWritings access predicate.

Removing of element

Cbool MultiHash_RemoveFwd (struct MultiHash *hash);
bool MultiHash_RemoveBwd (struct MultiHash *hash);
C++bool MultiHash::RemoveFwd (void);
bool MultiHash::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 MultiHash_SetFwd (struct MultiHash *hash, const struct pair_t *data);
bool MultiHash_SetBwd (struct MultiHash *hash, const struct pair_t *data);
C++bool MultiHash::SetFwd (const pair_t *data);
bool MultiHash::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 functions are called from read only section, started by LockWritings access predicate.

Getting element value

Cbool MultiHash_GetFwd (const struct MultiHash *hash, struct pair_t *data);
bool MultiHash_GetBwd (const struct MultiHash *hash, struct pair_t *data);
C++bool MultiHash::GetFwd (pair_t *data) const;
bool MultiHash::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 MultiHash_GetIter (const struct MultiHash *hash, struct pair_t *data, ptr_t iter);
C++bool MultiHash::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.

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 MultiHash_FwdToHead (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_FwdToTail (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_FwdToBwd (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_FwdGoNext (struct MultiHash *hash, size_t pos);
C++bool MultiHash::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 MultiHash_FwdGoPrev (struct MultiHash *hash, size_t pos);
C++bool MultiHash::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 MultiHash_BwdToHead (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_BwdToTail (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_BwdToFwd (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_BwdGoNext (struct MultiHash *hash, size_t pos);
C++bool MultiHash::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 MultiHash_BwdGoPrev (struct MultiHash *hash, size_t pos);
C++bool MultiHash::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 MultiHash_IterToHead (const struct MultiHash *hash);
C++ptr_t MultiHash::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 MultiHash_IterToTail (const struct MultiHash *hash);
C++ptr_t MultiHash::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 MultiHash_IterToFwd (const struct MultiHash *hash);
C++ptr_t MultiHash::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 MultiHash_IterToBwd (const struct MultiHash *hash);
C++ptr_t MultiHash::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 MultiHash_IterGoFwd (const struct MultiHash *hash, size_t pos, ptr_t *iter);
C++bool MultiHash::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 MultiHash_IterGoBwd (const struct MultiHash *hash, size_t pos, ptr_t *iter);
C++bool MultiHash::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 MultiHash_SwapFwdBwd (struct MultiHash *hash);
C++void MultiHash::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 MultiHash_MinFwd (struct MultiHash *hash, struct pair_t *data);
bool MultiHash_MinBwd (struct MultiHash *hash, struct pair_t *data);
C++bool MultiHash::MinFwd (pair_t *data);
bool MultiHash::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 MultiHash_MinIterFwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
bool MultiHash_MinIterBwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
C++bool MultiHash::MinIterFwd (pair_t *data, ptr_t *iter) const;
bool MultiHash::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 MultiHash_MaxFwd (struct MultiHash *hash, struct pair_t *data);
bool MultiHash_MaxBwd (struct MultiHash *hash, struct pair_t *data);
C++bool MultiHash::MaxFwd (pair_t *data);
bool MultiHash::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 MultiHash_MaxIterFwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
bool MultiHash_MaxIterBwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
C++bool MultiHash::MaxIterFwd (pair_t *data, ptr_t *iter) const;
bool MultiHash::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 MultiHash_FindKeyFwd (struct MultiHash *hash, struct pair_t *data, union adt_t key);
bool MultiHash_FindKeyBwd (struct MultiHash *hash, struct pair_t *data, union adt_t key);
C++bool MultiHash::FindKeyFwd (pair_t *data, adt_t key);
bool MultiHash::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 find

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 MultiHash_FindKeyIterFwd (const struct MultiHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
bool MultiHash_FindKeyIterBwd (const struct MultiHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool MultiHash::FindKeyIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
bool MultiHash::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 MultiHash_FindKeysFwd (struct MultiHash *hash, struct pair_t *data, const union adt_t keys[], size_t size);
bool MultiHash_FindKeysBwd (struct MultiHash *hash, struct pair_t *data, const union adt_t keys[], size_t size);
C++bool MultiHash::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size);
bool MultiHash::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
  • keys - array of keys to find in the hash table
  • size - size of array of keys

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 MultiHash_FindKeysIterFwd (const struct MultiHash *hash, struct pair_t *data, const union adt_t keys[], size_t size, ptr_t *iter);
bool MultiHash_FindKeysIterBwd (const struct MultiHash *hash, struct pair_t *data, const union adt_t keys[], size_t size, ptr_t *iter);
C++bool MultiHash::FindKeysIterFwd (pair_t *data, const adt_t keys[], size_t size, ptr_t *iter) const;
bool MultiHash::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.

Sequence searching

Csize_t MultiHash_FindSequenceFwd (struct MultiHash *hash, struct pair_t *data, union adt_t key);
size_t MultiHash_FindSequenceBwd (struct MultiHash *hash, struct pair_t *data, union adt_t key);
C++size_t MultiHash::FindSequenceFwd (pair_t *data, adt_t key);
size_t MultiHash::FindSequenceBwd (pair_t *data, adt_t key);

Description: Scan the hash table for sequence of elements, which are equal to the key, in forward (FindSequenceFwd) or backward (FindSequenceBwd) direction, and set forward/backward iterator position to first/last element. If required sequence is found, then functions store value of first/last element into the data structure is pointed by "data" pointer, and return total count of matches were met. 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 find

Return value:

  • Count of elements into the sequence.
  • 0 (zero) if no element is found, or functions are called from read only section, started by LockWritings access predicate.
Csize_t MultiHash_FindSequenceIterFwd (const struct MultiHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
size_t MultiHash_FindSequenceIterBwd (const struct MultiHash *hash, struct pair_t *data, union adt_t key, ptr_t *iter);
C++size_t MultiHash::FindSequenceIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
size_t MultiHash::FindSequenceIterBwd (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the hash table for sequence of elements, which are equal to the key, in forward (FindSequenceIterFwd) or backward (FindSequenceIterBwd) direction, and set external iterator position to first/last element. If required sequence is found, then functions store value of first/last element into the data structure is pointed by "data" pointer, and return total count of matches were met. 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:

  • Count of elements into the sequence.
  • 0 (zero) if no element is found.

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 MultiHash_FindVectorFwd (struct MultiHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
size_t MultiHash_FindVectorBwd (struct MultiHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
C++size_t MultiHash::FindVectorFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);
size_t MultiHash::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 all occurrences 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 MultiHash_FindVectorIterFwd (const struct MultiHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
size_t MultiHash_FindVectorIterBwd (const struct MultiHash *hash, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
C++size_t MultiHash::FindVectorIterFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;
size_t MultiHash::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 all occurrences 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.

Duplicates searching

Cbool MultiHash_FindDupFwd (struct MultiHash *hash, struct pair_t *data);
bool MultiHash_FindDupBwd (struct MultiHash *hash, struct pair_t *data);
C++bool MultiHash::FindDupFwd (pair_t *data);
bool MultiHash::FindDupBwd (pair_t *data);

Description: Scan the hash table in forward (FindDupFwd) or backward (FindDupBwd) direction from current position of forward/backward iterator, and set iterator position to first non unique element, then return value of that element into the data structure is pointed by "data" pointer. If no duplicates were found, then functions return FALSE and the iterator position stay unchanged.

Access type: RW

Parameters:

  • hash - pointer to target hash
  • data - address where to return the value of non unique element

Return value:

  • TRUE (1) if non unique element was found.
  • FALSE (0) if no duplicated keys were met, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool MultiHash_FindDupIterFwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
bool MultiHash_FindDupIterBwd (const struct MultiHash *hash, struct pair_t *data, ptr_t *iter);
C++bool MultiHash::FindDupIterFwd (pair_t *data, ptr_t *iter) const;
bool MultiHash::FindDupIterBwd (pair_t *data, ptr_t *iter) const;

Description: Scan the hash table in forward (FindDupIterFwd) or backward (FindDupIterBwd) direction from current position of external iterator, and set iterator position to first non unique element, then return value of that element into the data structure is pointed by "data" pointer. If no duplicates were found, then functions return FALSE and the iterator position stay unchanged.

Access type: RO

Parameters:

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

Return value:

  • TRUE (1) if non unique element was found.
  • FALSE (0) if no duplicated keys were met, or iterator is not set (has negative value).

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 MultiHash_CountKey (const struct MultiHash *hash, union adt_t key);
C++size_t MultiHash::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 MultiHash_CountKeys (const struct MultiHash *hash, const union adt_t keys[], size_t size);
C++size_t MultiHash::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.

Unique values

Csize_t MultiHash_Unique (struct MultiHash *hash, const MultiHash *source);
C++size_t MultiHash::Unique (const MultiHash *source);

Description: Extract only unique keys from source hash table, and store them into target hash table. When this operation is done, target hash table will have only unique keys and count of duplicates that each key had in source hash table. Number of duplicates is stored into data field of the elements.

Access type: RW

Parameters:

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

Return value:

  • Count of unique elements were found in source hash table.
  • -1 if target hash table was not able to extend its capacity for new elements, or it was not empty, or functions are called from read only section, started by LockWritings access predicate.

Warning:These functions assume that target hash table is empty. If it already has any elements, then operation will fail.

Warning:Unique functions do not make deep copy of keys from source hash table, but use only reference to original objects from source hash table. Do not delete objects from source hash table until you finish all operations with unique keys. In other case you may have broken pointers or undefined behavior of your program.

Check for duplicate values

Cbool MultiHash_CheckDup (const struct MultiHash *hash);
C++bool MultiHash::CheckDup (void) const;

Description: Check multi hash table for non unique values (duplicates).

Access type: RO

Parameters:

  • hash - pointer to target hash table

Return value:

  • TRUE (1) if duplicates were found.
  • FALSE (0) if hash table has no duplicated values.

Hash table properties

Hash table built-in key type

Csize_t MultiHash_KeyType (const struct MultiHash *hash);
C++size_t MultiHash::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 MultiHash_CompareFunction (const struct MultiHash *hash);
C++KeyCmp MultiHash::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 MultiHash_HashFunction (const struct MultiHash *hash);
C++HashFunc MultiHash::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 MultiHash_CopyFunction (const struct MultiHash *hash);
C++CopyFunc MultiHash::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 MultiHash_DeleteFunction (const struct MultiHash *hash);
C++DelFunc MultiHash::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* MultiHash_UserData (const struct MultiHash *hash);
C++void* MultiHash::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 MultiHash_Capacity (const struct MultiHash *hash);
C++size_t MultiHash::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 MultiHash_Size (const struct MultiHash *hash);
C++size_t MultiHash::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 MultiHash_IsEmpty (const struct MultiHash *hash);
C++bool MultiHash::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 MultiHash_IsInit (const struct MultiHash *hash);
C++bool MultiHash::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.