Linux Assemblycollection of fast libraries

Unique tree ADTUniqueTree.h

Unique tree is a b-tree based data structure, which allows to store only one instance of each key. A tree data structure keeps data sorted and allows searches, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems, where most operations to the main memory is too slow, and should be minimized. Modern systems have very fast cache memory and relatively slow RAM memory. In memory b-trees minimize cache misses and significantly improve main tree operations. See the benchmarks.

Contents


Function list

C function nameAccess typeC++ function nameAccess type
AllowReadingsRW(constructor) UniqueTreeRW
AllowWritingsRW(copy constructor) UniqueTreeRW
BwdGoNextRW(destructor) ~UniqueTreeRW
BwdGoPrevRWAllowReadingsRW
BwdToFwdRWAllowWritingsRW
BwdToIndexRWBwdGoNextRW
BwdToMaxRWBwdGoPrevRW
BwdToMinRWBwdToFwdRW
CapacityROBwdToIndexRW
CompareROBwdToMaxRW
CompareFunctionROBwdToMinRW
CopyBwdRWCapacityRO
CopyFunctionROCompareRO
CopyFwdRWCompareFunctionRO
CopyUniqueTreeRWCopyBwdRW
CountKeyROCopyFunctionRO
CountKeysROCopyFwdRW
DeleteFunctionROCountKeyRO
FindDiffBwdRWCountKeysRO
FindDiffFwdRWDeleteFunctionRO
FindDiffIterBwdROFindDiffBwdRW
FindDiffIterFwdROFindDiffFwdRW
FindEqualBwdRWFindDiffIterBwdRO
FindEqualFwdRWFindDiffIterFwdRO
FindEqualIterBwdROFindEqualBwdRW
FindEqualIterFwdROFindEqualFwdRW
FindGreatBwdRWFindEqualIterBwdRO
FindGreatFwdRWFindEqualIterFwdRO
FindGreatIterROFindGreatBwdRW
FindGreatOrEqualBwdRWFindGreatFwdRW
FindGreatOrEqualFwdRWFindGreatIterRO
FindGreatOrEqualIterROFindGreatOrEqualBwdRW
FindLessBwdRWFindGreatOrEqualFwdRW
FindLessFwdRWFindGreatOrEqualIterRO
FindLessIterROFindLessBwdRW
FindLessOrEqualBwdRWFindLessFwdRW
FindLessOrEqualFwdRWFindLessIterRO
FindLessOrEqualIterROFindLessOrEqualBwdRW
FindVectorBwdRWFindLessOrEqualFwdRW
FindVectorFwdRWFindLessOrEqualIterRO
FindVectorIterBwdROFindVectorBwdRW
FindVectorIterFwdROFindVectorFwdRW
FreeUniqueTreeRWFindVectorIterBwdRO
FwdGoNextRWFindVectorIterFwdRO
FwdGoPrevRWFwdGoNextRW
FwdToBwdRWFwdGoPrevRW
FwdToIndexRWFwdToBwdRW
FwdToMaxRWFwdToIndexRW
FwdToMinRWFwdToMaxRW
GetBwdROFwdToMinRW
GetBwdPosROGetBwdRO
GetFwdROGetBwdPosRO
GetFwdPosROGetFwdRO
GetIndexROGetFwdPosRO
GetIterROGetIndexRO
GetIterPosROGetIterRO
HeightROGetIterPosRO
InitUniqueTreeRWHeightRO
InsertRWInsertRW
IsEmptyROIsEmptyRO
IsEqualROIsEqualRO
IsInitROIsInitRO
IterGoBwdROIterGoBwdRO
IterGoFwdROIterGoFwdRO
IterToBwdROIterToBwdRO
IterToFwdROIterToFwdRO
IterToIndexROIterToIndexRO
IterToMaxROIterToMaxRO
IterToMinROIterToMinRO
KeyTypeROKeyTypeRO
LockReadingsRWLockReadingsRW
LockWritingsRWLockWritingsRW
MaxBwdRWMaxBwdRW
MaxFwdRWMaxFwdRW
MaxIterBwdROMaxIterBwdRO
MaxIterFwdROMaxIterFwdRO
MinBwdRWMinBwdRW
MinFwdRWMinFwdRW
MinIterBwdROMinIterBwdRO
MinIterFwdROMinIterFwdRO
MoveBwdRWMoveBwdRW
MoveFwdRWMoveFwdRW
OverrideRWOverrideRW
RemoveBwdRWRemoveBwdRW
RemoveFwdRWRemoveFwdRW
RemoveIndexRWRemoveIndexRW
SetBwdRWSetBwdRW
SetFwdRWSetFwdRW
SetIndexRWSetIndexRW
SizeROSizeRO
SwapFwdBwdRWSwapFwdBwdRW
UserDataROUserDataRO
C function nameAccess typeC++ function nameAccess type

Constructor

Cvoid UniqueTree_InitUniqueTree (struct UniqueTree *tree, size_t capacity, KeyCmp kfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);
C++UniqueTree::UniqueTree (size_t capacity, KeyCmp kfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new tree instance.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • capacity - initial count of elements that the tree can hold. Tree capacity is auto extended if required.
  • kfunc - pointer to key compare function to sort elements in the tree. Compare 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 UniqueTree_CopyUniqueTree (struct UniqueTree *tree, const struct UniqueTree *source);
C++UniqueTree::UniqueTree (const UniqueTree &source);

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

Access type: RW

Parameters:

  • tree - pointer to target tree
  • source - pointer to source tree

Return value: None.

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

Destructor

Cvoid UniqueTree_FreeUniqueTree (struct UniqueTree *tree);
C++UniqueTree::~UniqueTree (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

Access predicates

Access predicates is an easy and efficient way to write multithreaded highly concurrent code. Tree 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 tree. 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 tree. 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 tree 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 UniqueTree_LockReadings (struct UniqueTree *tree, bool wait);
C++bool UniqueTree::LockReadings (bool wait);

Description: Lock read and write operations from other threads and provide exclusive access for tree 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 tree modifications, or do something else if lock is not taken.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • 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 the tree.
  • 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 UniqueTree_LockWritings (struct UniqueTree *tree, bool wait);
C++bool UniqueTree::LockWritings (bool wait);

Description: Lock write operations from all threads and provide read only access to tree. 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 tree readings, or do something else if lock is not taken.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • 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 the tree.
  • FALSE (0) if the wait flag was not set and read only lock is not taken.

Warning:Tree 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 tree have any of them. Each lock function should always call release function to prevent dead locks.

Releasing of exclusive lock

Cvoid UniqueTree_AllowReadings (struct UniqueTree *tree);
C++void UniqueTree::AllowReadings (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

Releasing of read only lock

Cvoid UniqueTree_AllowWritings (struct UniqueTree *tree);
C++void UniqueTree::AllowWritings (void);

Description: Release read only lock and allow tree 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:

  • tree - pointer to the tree

Return value: None.

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

Copying elements

Csize_t UniqueTree_CopyFwd (struct UniqueTree *tree, const struct UniqueTree *source, size_t count);
size_t UniqueTree_CopyBwd (struct UniqueTree *tree, const struct UniqueTree *source, size_t count);
C++size_t UniqueTree::CopyFwd (const UniqueTree *source, size_t count);
size_t UniqueTree::CopyBwd (const UniqueTree *source, size_t count);

Description: Copy "count" elements, from source tree into target tree. Source elements are iterated in forward direction (CopyFwd), and backward direction (CopyBwd), using forward/backward iterator. Functions copy data starting from current position of forward/backward iterator, in positive direction, until all "count" elements are copied into target tree. Source tree stay unchanged and accessed in read only mode.

For forward iterator the positive direction is from min to max element, and for backward iterator the positive direction is from max to min element.

Access type: RW

Parameters:

  • tree - pointer to target tree
  • source - pointer to source tree
  • count - number of elements to copy (-1 means all available elements)

Return value:

  • Real count of elements, which were copied from source tree.
  • -1 if target tree was not able to extend its capacity for new elements, or source tree has incorrect iterator value, or functions are called from read only section, started by LockWritings access predicate.

Note:If target tree already has any key from source tree, then functions interrupt the operation, and return count of already copied elements before that element.

Moving elements

Csize_t UniqueTree_MoveFwd (struct UniqueTree *tree, struct UniqueTree *source, size_t count);
size_t UniqueTree_MoveBwd (struct UniqueTree *tree, struct UniqueTree *source, size_t count);
C++size_t UniqueTree::MoveFwd (UniqueTree *source, size_t count);
size_t UniqueTree::MoveBwd (UniqueTree *source, size_t count);

Description: Move "count" elements, from source tree into target tree. Source elements are iterated in forward direction (MoveFwd), and backward direction (MoveBwd), using forward/backward iterator. Functions move data starting from current position of forward/backward iterator, in positive direction, until all "count" elements are moved into target tree.

For forward iterator the positive direction is from min to max element, and for backward iterator the positive direction is from max to min element.

Access type: RW

Parameters:

  • tree - pointer to target tree
  • source - pointer to source tree
  • count - number of elements to move (-1 means all available elements)

Return value:

  • Real count of elements, which were moved from source tree.
  • -1 if target tree was not able to extend its capacity for new elements, or source tree has incorrect iterator value, or functions are called from read only section, started by LockWritings access predicate.

Note:If target tree already has any key from source tree, then functions interrupt the operation, and return count of already moved elements before that element.

Insertion of element

Cbool UniqueTree_Insert (struct UniqueTree *tree, const struct pair_t *data);
C++bool UniqueTree::Insert (const pair_t *data);

Description: Insert new element into the tree.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • data - pointer to the new element

Return value:

  • TRUE (1) if element was successfully inserted into the tree.
  • FALSE (0) if the tree 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

By element index

Cbool UniqueTree_RemoveIndex (struct UniqueTree *tree, size_t index);
C++bool UniqueTree::RemoveIndex (size_t index);

Description: Remove element from selected position in the tree.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • index - element index in the tree

Return value:

  • TRUE (1) if element position is less than the tree size.
  • FALSE (0) if element with target position does not exist, or functions are called from read only section, started by LockWritings access predicate.

Note:Position is calculated from the min key of the tree. Min key has zero index, Max key has size - 1 index.

Using iterators

Cbool UniqueTree_RemoveFwd (struct UniqueTree *tree);
bool UniqueTree_RemoveBwd (struct UniqueTree *tree);
C++bool UniqueTree::RemoveFwd (void);
bool UniqueTree::RemoveBwd (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value:

  • TRUE (1) if forward/backward iterator points to any tree 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

By element index

Cbool UniqueTree_SetIndex (struct UniqueTree *tree, const struct pair_t *data, size_t index);
C++bool UniqueTree::SetIndex (const pair_t *data, size_t index);

Description: Set value of the element in selected position in the tree and reorder all the elements to restore correct tree order.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • data - pointer to the new value of the element
  • index - element index in the tree

Return value:

  • TRUE (1) if element position is less than the tree size.
  • FALSE (0) if element with target position does not exist, or memory allocation was failed, or new key already exists, or functions are called from read only section, started by LockWritings access predicate.

Note:Position is calculated from the min key of the tree. Min key has zero index, Max key has size - 1 index.

Using iterators

Cbool UniqueTree_SetFwd (struct UniqueTree *tree, const struct pair_t *data);
bool UniqueTree_SetBwd (struct UniqueTree *tree, const struct pair_t *data);
C++bool UniqueTree::SetFwd (const pair_t *data);
bool UniqueTree::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:

  • tree - pointer to the tree
  • data - pointer to the new value of the element

Return value:

  • TRUE (1) if forward/backward iterator points to any tree element.
  • FALSE (0) if forward/backward iterator 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

By element index

Cbool UniqueTree_GetIndex (const struct UniqueTree *tree, struct pair_t *data, size_t index);
C++bool UniqueTree::GetIndex (pair_t *data, size_t index) const;

Description: Get value of the element in selected position in the tree. The tree stay unchanged.

Access type: RO

Parameters:

  • tree - pointer to the tree
  • data - address where to return the value of the element
  • index - element index in the tree

Return value:

  • TRUE (1) if element position is less than the tree size.
  • FALSE (0) if element with target position does not exist.

Note:Position is calculated from the min key of the tree. Min key has zero index, Max key has size - 1 index.

Using iterators

Cbool UniqueTree_GetFwd (const struct UniqueTree *tree, struct pair_t *data);
bool UniqueTree_GetBwd (const struct UniqueTree *tree, struct pair_t *data);
C++bool UniqueTree::GetFwd (pair_t *data) const;
bool UniqueTree::GetBwd (pair_t *data) const;

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

Access type: RO

Parameters:

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

Return value:

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

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

Access type: RO

Parameters:

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

Return value:

  • TRUE (1) if external iterator points to any tree 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 tree elements. It doesn't change any object parameters.

Overriding element value

Cbool UniqueTree_Override (struct UniqueTree *tree, const struct pair_t *data);
C++bool UniqueTree::Override (const pair_t *data);

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

Access type: RW

Parameters:

  • tree - pointer to the tree
  • data - pointer to the new element

Return value:

  • TRUE (1) if element was successfully inserted into the tree.
  • FALSE (0) if the tree 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 tree in very fast and efficient way. The main goal of this iterator to enumerate elements in forward (positive) direction: from min to max key. But it can also move in backward (negative) direction: from max to min key. It always points to tree 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 tree 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 tree.

Set iterator position

These functions set iterator position to min, max or any tree element by its index or by the value of another iterator. Tree elements are treated as ordered array of keys, starting from min key, which has zero index, to max key (index equal to size - 1). When you insert new elements or delete existing keys, the indexes are changed, but the iterators still point to the same elements. To set they initial position, you may use these functions.

By index

Cvoid UniqueTree_FwdToIndex (struct UniqueTree *tree, size_t index);
C++void UniqueTree::FwdToIndex (size_t index);

Description: Move iterator position to element with chosen index in the tree. Min element has 0 index, max element has size - 1 index. If index is greater than or equal to tree size, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree
  • index - index of the element to move to

Return value: None.

To min element

Cvoid UniqueTree_FwdToMin (struct UniqueTree *tree);
C++void UniqueTree::FwdToMin (void);

Description: Move iterator position to min element of the tree. If tree is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

To max element

Cvoid UniqueTree_FwdToMax (struct UniqueTree *tree);
C++void UniqueTree::FwdToMax (void);

Description: Move iterator position to max element of the tree. If tree is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

To backward iterator

Cvoid UniqueTree_FwdToBwd (struct UniqueTree *tree);
C++void UniqueTree::FwdToBwd (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

Get iterator position

Csize_t UniqueTree_GetFwdPos (const struct UniqueTree *tree);
C++size_t UniqueTree::GetFwdPos (void) const;

Description: Return index of the element which is pointed by the forward iterator, or -1 if the iterator is not set.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value:

  • Index of the element, which is pointed by the forward iterator.
  • -1 if the iterator is not set.

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 tree elements and get neighbor keys for current key.

Move to next position

Cbool UniqueTree_FwdGoNext (struct UniqueTree *tree, size_t pos);
C++bool UniqueTree::FwdGoNext (size_t pos);

Description: Move forward iterator to "pos" positions in forward direction: from min to max key.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any tree 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 UniqueTree_FwdGoPrev (struct UniqueTree *tree, size_t pos);
C++bool UniqueTree::FwdGoPrev (size_t pos);

Description: Move forward iterator to "pos" positions in backward direction: from max to min key.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any tree 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 tree in very fast and efficient way. The main goal of this iterator to enumerate elements in backward (positive) direction: from max to min key. But it can also move in forward (negative) direction: from min to max key. It always points to tree 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 tree 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 tree.

Set iterator position

These functions set iterator position to min, max or any tree element by its index or by the value of another iterator. Tree elements are treated as ordered array of keys, starting from min key, which has zero index, to max key (index equal to size - 1). When you insert new elements or delete existing keys, the indexes are changed, but the iterators still point to the same elements. To set they initial position, you may use these functions.

By index

Cvoid UniqueTree_BwdToIndex (struct UniqueTree *tree, size_t index);
C++void UniqueTree::BwdToIndex (size_t index);

Description: Move iterator position to element with chosen index in the tree. Min element has 0 index, max element has size - 1 index. If index is greater than or equal to tree size, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree
  • index - index of the element to move to

Return value: None.

To min element

Cvoid UniqueTree_BwdToMin (struct UniqueTree *tree);
C++void UniqueTree::BwdToMin (void);

Description: Move iterator position to min element of the tree. If tree is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

To max element

Cvoid UniqueTree_BwdToMax (struct UniqueTree *tree);
C++void UniqueTree::BwdToMax (void);

Description: Move iterator position to max element of the tree. If tree is empty, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

To forward iterator

Cvoid UniqueTree_BwdToFwd (struct UniqueTree *tree);
C++void UniqueTree::BwdToFwd (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

Get iterator position

Csize_t UniqueTree_GetBwdPos (const struct UniqueTree *tree);
C++size_t UniqueTree::GetBwdPos (void) const;

Description: Return index of the element, which is pointed by the backward iterator, or -1 if the iterator is not set.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value:

  • Index of the element, which is pointed by the backward iterator.
  • -1 if the iterator is not set.

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 tree elements and get neighbor keys for current key.

Move to next position

Cbool UniqueTree_BwdGoNext (struct UniqueTree *tree, size_t pos);
C++bool UniqueTree::BwdGoNext (size_t pos);

Description: Move backward iterator to "pos" positions in forward direction: from max to min key.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any tree 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 UniqueTree_BwdGoPrev (struct UniqueTree *tree, size_t pos);
C++bool UniqueTree::BwdGoPrev (size_t pos);

Description: Move backward iterator to "pos" positions in backward direction: from min to max key.

Access type: RW

Parameters:

  • tree - pointer to the tree
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any tree 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 tree 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 tree structure (insert, remove set or overwrite its elements). In such case you should each time to reassign external iterator to tree min/max element or current position of forward/backward iterator after changing tree elements.

Set iterator position

These functions set external iterator position to min, to max or to any tree element by its index or by the value of another iterator. Tree elements are treated as ordered array of keys, starting from min key, which has zero index, to max key (index equal to size - 1). 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 tree structure or keys.

By index

Cptr_t UniqueTree_IterToIndex (const struct UniqueTree *tree, size_t index);
C++ptr_t UniqueTree::IterToIndex (size_t index) const;

Description: Return iterator value, which points to element with chosen index in the tree. Min element has 0 index, max element has size - 1 index. If index is greater than or equal to tree size, 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:

  • tree - pointer to the tree
  • index - index of the element to move to

Return value:

  • External iterator value.
  • Negative value if index is incorrect.

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

To min element

Cptr_t UniqueTree_IterToMin (const struct UniqueTree *tree);
C++ptr_t UniqueTree::IterToMin (void) const;

Description: Return iterator value, which points to min element of the tree. If tree 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:

  • tree - pointer to the tree

Return value:

  • Min iterator value.
  • Negative value if tree is empty.

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

To max element

Cptr_t UniqueTree_IterToMax (const struct UniqueTree *tree);
C++ptr_t UniqueTree::IterToMax (void) const;

Description: Return iterator value, which points to max element of the tree. If tree 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:

  • tree - pointer to the tree

Return value:

  • Max iterator value.
  • Negative value if tree is empty.

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

To forward iterator

Cptr_t UniqueTree_IterToFwd (const struct UniqueTree *tree);
C++ptr_t UniqueTree::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:

  • tree - pointer to the tree

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 tree elements. It doesn't change any object parameters.

To backward iterator

Cptr_t UniqueTree_IterToBwd (const struct UniqueTree *tree);
C++ptr_t UniqueTree::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:

  • tree - pointer to the tree

Return value:

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

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

Get iterator position

Csize_t UniqueTree_GetIterPos (const struct UniqueTree *tree, ptr_t iter);
C++size_t UniqueTree::GetIterPos (ptr_t iter) const;

Description: Return index of the element, which is pointed by external iterator, or -1 if the iterator has non valid value (points to non existing element).

Access type: RO

Parameters:

  • tree - pointer to the tree
  • iter - value of external iterator, which is used to point to the tree element

Return value:

  • Index of the element, which is pointed by the external iterator.
  • -1 if the iterator is not set (has negative value).

Tip:This function is optimal choice for multithreaded highly concurrent read only access to tree 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 tree elements and get neighbor keys for current key.

Move in forward direction

Cbool UniqueTree_IterGoFwd (const struct UniqueTree *tree, size_t pos, ptr_t *iter);
C++bool UniqueTree::IterGoFwd (size_t pos, ptr_t *iter) const;

Description: Move external iterator to "pos" positions in forward direction: from min to max key.

Access type: RO

Parameters:

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

Return value:

  • TRUE (1) if external iterator points to any tree 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 tree elements. It doesn't change any object parameters.

Move in backward direction

Cbool UniqueTree_IterGoBwd (const struct UniqueTree *tree, size_t pos, ptr_t *iter);
C++bool UniqueTree::IterGoBwd (size_t pos, ptr_t *iter) const;

Description: Move external iterator to "pos" positions in backward direction: from max to min key.

Access type: RO

Parameters:

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

Return value:

  • TRUE (1) if external iterator points to any tree 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 tree elements. It doesn't change any object parameters.

Swapping iterators

Cvoid UniqueTree_SwapFwdBwd (struct UniqueTree *tree);
C++void UniqueTree::SwapFwdBwd (void);

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

Access type: RW

Parameters:

  • tree - pointer to the tree

Return value: None.

Minimum and maximum value

Minimum value

Cbool UniqueTree_MinFwd (struct UniqueTree *tree, struct pair_t *data);
bool UniqueTree_MinBwd (struct UniqueTree *tree, struct pair_t *data);
C++bool UniqueTree::MinFwd (pair_t *data);
bool UniqueTree::MinBwd (pair_t *data);

Description: Scan elements in the tree 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:

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

Return value:

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

Description: Scan elements in the tree 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:

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

Return value:

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

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

Maximum value

Cbool UniqueTree_MaxFwd (struct UniqueTree *tree, struct pair_t *data);
bool UniqueTree_MaxBwd (struct UniqueTree *tree, struct pair_t *data);
C++bool UniqueTree::MaxFwd (pair_t *data);
bool UniqueTree::MaxBwd (pair_t *data);

Description: Scan elements in the tree 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:

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

Return value:

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

Description: Scan elements in the tree 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:

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

Return value:

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

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

Key searching

Key searching into the tree is very efficient procedure, which takes log(n) compare operations to find the key, which conforms to the specified search conditions. Key searching functions can find equal, less and greater keys into the tree. They also check the tree for sequence of duplicated keys, returning first or last element in the sequence and total count of elements into the sequence. So they can be iterated sequentially, using iterator manipulation functions.

Single key searching

Following functions do binary searching, and look for first/last element, which satisfy target condition, 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.

Searching for equal key

Cbool UniqueTree_FindEqualFwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
bool UniqueTree_FindEqualBwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
C++bool UniqueTree::FindEqualFwd (pair_t *data, adt_t key);
bool UniqueTree::FindEqualBwd (pair_t *data, adt_t key);

Description: Scan the tree for first element (FindEqualFwd) or last element (FindEqualBwd), 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:

  • tree - pointer to the tree
  • 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 tree.
  • FALSE (0) if the tree 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 UniqueTree_FindEqualIterFwd (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
bool UniqueTree_FindEqualIterBwd (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueTree::FindEqualIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
bool UniqueTree::FindEqualIterBwd (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for first element (FindEqualIterFwd) or last element (FindEqualIterBwd), 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:

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

Return value:

  • TRUE (1) if required element was found in the tree.
  • FALSE (0) if the tree 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 tree elements. They don't change any object parameters.

Searching for greater key

Cbool UniqueTree_FindGreatFwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
bool UniqueTree_FindGreatBwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
C++bool UniqueTree::FindGreatFwd (pair_t *data, adt_t key);
bool UniqueTree::FindGreatBwd (pair_t *data, adt_t key);

Description: Scan the tree for first element, which is greater than 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:

  • tree - pointer to the tree
  • 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 tree.
  • FALSE (0) if the tree 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 UniqueTree_FindGreatIter (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueTree::FindGreatIter (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for first element, which is greater than 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:

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

Return value:

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

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

Searching for greater or equal key

Cbool UniqueTree_FindGreatOrEqualFwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
bool UniqueTree_FindGreatOrEqualBwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
C++bool UniqueTree::FindGreatOrEqualFwd (pair_t *data, adt_t key);
bool UniqueTree::FindGreatOrEqualBwd (pair_t *data, adt_t key);

Description: Scan the tree for first element, which is greater than or 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:

  • tree - pointer to the tree
  • 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 tree.
  • FALSE (0) if the tree 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 UniqueTree_FindGreatOrEqualIter (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueTree::FindGreatOrEqualIter (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for first element, which is greater than or 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:

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

Return value:

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

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

Searching for less key

Cbool UniqueTree_FindLessFwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
bool UniqueTree_FindLessBwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
C++bool UniqueTree::FindLessFwd (pair_t *data, adt_t key);
bool UniqueTree::FindLessBwd (pair_t *data, adt_t key);

Description: Scan the tree for last element, which is less than 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:

  • tree - pointer to the tree
  • 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 tree.
  • FALSE (0) if the tree 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 UniqueTree_FindLessIter (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueTree::FindLessIter (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for last element, which is less than 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:

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

Return value:

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

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

Searching for less or equal key

Cbool UniqueTree_FindLessOrEqualFwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
bool UniqueTree_FindLessOrEqualBwd (struct UniqueTree *tree, struct pair_t *data, union adt_t key);
C++bool UniqueTree::FindLessOrEqualFwd (pair_t *data, adt_t key);
bool UniqueTree::FindLessOrEqualBwd (pair_t *data, adt_t key);

Description: Scan the tree for last element, which is less than or 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:

  • tree - pointer to the tree
  • 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 tree.
  • FALSE (0) if the tree 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 UniqueTree_FindLessOrEqualIter (const struct UniqueTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
C++bool UniqueTree::FindLessOrEqualIter (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for last element, which is less than or 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:

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

Return value:

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

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

Vectorized searching

Csize_t UniqueTree_FindVectorFwd (struct UniqueTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
size_t UniqueTree_FindVectorBwd (struct UniqueTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
C++size_t UniqueTree::FindVectorFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);
size_t UniqueTree::FindVectorBwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);

Description: Scan the tree 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:

  • tree - pointer to the tree
  • 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 tree
  • 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 UniqueTree_FindVectorIterFwd (const struct UniqueTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
size_t UniqueTree_FindVectorIterBwd (const struct UniqueTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
C++size_t UniqueTree::FindVectorIterFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;
size_t UniqueTree::FindVectorIterBwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;

Description: Scan the tree 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:

  • tree - pointer to the tree
  • 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 tree
  • 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 tree 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 tree elements. They don't change any object parameters.

Searching for differences

Cbool UniqueTree_FindDiffFwd (struct UniqueTree *tree, struct pair_t *data, const struct UniqueTree *source, size_t count);
bool UniqueTree_FindDiffBwd (struct UniqueTree *tree, struct pair_t *data, const struct UniqueTree *source, size_t count);
C++bool UniqueTree::FindDiffFwd (pair_t *data, const UniqueTree *source, size_t count);
bool UniqueTree::FindDiffBwd (pair_t *data, const UniqueTree *source, size_t count);

Description: Compare "count" elements of two tree objects (key by key) from min to max element (FindDiffFwd) or from max to min element (FindDiffBwd), starting from current position of forward/backward iterator, and set iterator to first non equal element in target tree, then return value of that element into the data structure is pointed by "data" pointer. Functions do not compare assigned data fields, but only the keys. If no different keys were found during "count" elements, then functions return FALSE and the iterator position stay unchanged. Source tree is always accessed in read only mode.

Access type: RW

Parameters:

  • tree - pointer to target tree
  • data - address where to return the value of non equal element
  • source - pointer to source tree
  • count - number of elements to check (-1 means all available elements)

Return value:

  • TRUE (1) if different keys were found.
  • FALSE (0) if all "count" keys were equal to each other, or the trees have incorrect iterators, or functions are called from read only section, started by LockWritings access predicate.
Cbool UniqueTree_FindDiffIterFwd (const struct UniqueTree *tree, struct pair_t *data, const struct UniqueTree *source, size_t count, ptr_t *titer, ptr_t siter);
bool UniqueTree_FindDiffIterBwd (const struct UniqueTree *tree, struct pair_t *data, const struct UniqueTree *source, size_t count, ptr_t *titer, ptr_t siter);
C++bool UniqueTree::FindDiffIterFwd (pair_t *data, const UniqueTree *source, size_t count, ptr_t *titer, ptr_t siter) const;
bool UniqueTree::FindDiffIterBwd (pair_t *data, const UniqueTree *source, size_t count, ptr_t *titer, ptr_t siter) const;

Description: Compare "count" elements of two tree objects (key by key) from min to max element (FindDiffIterFwd) or from max to min element (FindDiffIterBwd), starting from current position of "titer" and "siter" iterators, and set "titer" iterator to first non equal element in target tree, then return value of that element into the data structure is pointed by "data" pointer. Functions do not compare assigned data fields, but only the keys. If no different keys were found during "count" elements, then functions return FALSE and the "titer" iterator position stay unchanged.

Access type: RO

Parameters:

  • tree - pointer to target tree
  • data - address where to return the value of non equal element
  • source - pointer to source tree
  • count - number of elements to check (-1 means all available elements)
  • titer - address of external iterator, which is used to point to target tree element
  • siter - value of external iterator, which is used to point to source tree element

Return value:

  • TRUE (1) if different keys were found.
  • FALSE (0) if all "count" keys were equal to each other, or the trees have incorrect iterators (any of them has negative value).

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

Key counting

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

Single key counting

Csize_t UniqueTree_CountKey (const struct UniqueTree *tree, union adt_t key);
C++size_t UniqueTree::CountKey (adt_t key) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree
  • key - key value to find in the tree

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

Keys set counting

Csize_t UniqueTree_CountKeys (const struct UniqueTree *tree, const union adt_t keys[], size_t size);
C++size_t UniqueTree::CountKeys (const adt_t keys[], size_t size) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree
  • keys - array of keys to find in the tree
  • size - size of array of keys

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

Comparison of unique trees

Csint64_t UniqueTree_Compare (const struct UniqueTree *tree, const struct UniqueTree *source);
C++sint64_t UniqueTree::Compare (const UniqueTree *source) const;

Description: Compare two tree objects (key by key) starting from min element to max element, using internal key compare function of target tree, and return relations between them (less, equal or greater). These functions do not compare assigned data fields, but only the keys.

Access type: RO

Parameters:

  • tree - pointer to target tree
  • source - pointer to source tree

Return value:

  • -1 if first tree is less than second tree.
  • 0 if first tree is equal to second tree.
  • +1 if first tree is greater than second tree.

Check for equality

Cbool UniqueTree_IsEqual (const struct UniqueTree *tree, const struct UniqueTree *source);
C++bool UniqueTree::IsEqual (const UniqueTree *source) const;

Description: Check if both trees have the same size and key values, using internal key compare function of target tree. These functions do not compare assigned data fields, but only the keys.

Access type: RO

Parameters:

  • tree - pointer to target tree
  • source - pointer to source tree

Return value:

  • TRUE (1) if trees are equal.
  • FALSE (0) if trees are not equal.

Tree properties

Tree built-in key type

Csize_t UniqueTree_KeyType (const struct UniqueTree *tree);
C++size_t UniqueTree::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 tree.

Access type: RO

Parameters:

  • tree - pointer to the tree

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.

Tree key compare function

CKeyCmp UniqueTree_CompareFunction (const struct UniqueTree *tree);
C++KeyCmp UniqueTree::CompareFunction (void) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree

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

Tree pair copy function

CCopyFunc UniqueTree_CopyFunction (const struct UniqueTree *tree);
C++CopyFunc UniqueTree::CopyFunction (void) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree

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

Tree pair delete function

CDelFunc UniqueTree_DeleteFunction (const struct UniqueTree *tree);
C++DelFunc UniqueTree::DeleteFunction (void) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree

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

Tree user's data

Cvoid* UniqueTree_UserData (const struct UniqueTree *tree);
C++void* UniqueTree::UserData (void) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree

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

Tree capacity

Csize_t UniqueTree_Capacity (const struct UniqueTree *tree);
C++size_t UniqueTree::Capacity (void) const;

Description: Return the tree capacity.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value: Max count of objects that tree can hold.

Tree size

Csize_t UniqueTree_Size (const struct UniqueTree *tree);
C++size_t UniqueTree::Size (void) const;

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

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value: Count of allocated objects inside the tree.

Tree height

Csize_t UniqueTree_Height (const struct UniqueTree *tree);
C++size_t UniqueTree::Height (void) const;

Description: Return current height of the tree.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value:

  • Tree height.
  • 0 (zero) if the tree is empty.

Check if tree is empty

Cbool UniqueTree_IsEmpty (const struct UniqueTree *tree);
C++bool UniqueTree::IsEmpty (void) const;

Description: Check if the tree is empty.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value:

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

Check if tree is initialized

Cbool UniqueTree_IsInit (const struct UniqueTree *tree);
C++bool UniqueTree::IsInit (void) const;

Description: Check if the tree is initialized.

Access type: RO

Parameters:

  • tree - pointer to the tree

Return value:

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