Constructor

Cvoid MultiTree_InitMultiTree (struct MultiTree *tree, size_t capacity, KeyCmp kfunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);

C++MultiTree::MultiTree (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 MultiTree_CopyMultiTree (struct MultiTree *tree, const struct MultiTree *source);

C++MultiTree::MultiTree (const MultiTree &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 MultiTree_FreeMultiTree (struct MultiTree *tree);

C++MultiTree::~MultiTree (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 MultiTree_LockReadings (struct MultiTree *tree, bool wait);

C++bool MultiTree::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 MultiTree_LockWritings (struct MultiTree *tree, bool wait);

C++bool MultiTree::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 MultiTree_AllowReadings (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_AllowWritings (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_CopyFwd (struct MultiTree *tree, const struct MultiTree *source, size_t count);
size_t MultiTree_CopyBwd (struct MultiTree *tree, const struct MultiTree *source, size_t count);

C++size_t MultiTree::CopyFwd (const MultiTree *source, size_t count);
size_t MultiTree::CopyBwd (const MultiTree *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.

Moving elements

Csize_t MultiTree_MoveFwd (struct MultiTree *tree, struct MultiTree *source, size_t count);
size_t MultiTree_MoveBwd (struct MultiTree *tree, struct MultiTree *source, size_t count);

C++size_t MultiTree::MoveFwd (MultiTree *source, size_t count);
size_t MultiTree::MoveBwd (MultiTree *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.

Insertion of element

Cbool MultiTree_Insert (struct MultiTree *tree, const struct pair_t *data);

C++bool MultiTree::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 functions are called from read only section, started by LockWritings access predicate.

Removing of element

By element index

Cbool MultiTree_RemoveIndex (struct MultiTree *tree, size_t index);

C++bool MultiTree::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 MultiTree_RemoveFwd (struct MultiTree *tree);
bool MultiTree_RemoveBwd (struct MultiTree *tree);

C++bool MultiTree::RemoveFwd (void);
bool MultiTree::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 MultiTree_SetIndex (struct MultiTree *tree, const struct pair_t *data, size_t index);

C++bool MultiTree::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 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 MultiTree_SetFwd (struct MultiTree *tree, const struct pair_t *data);
bool MultiTree_SetBwd (struct MultiTree *tree, const struct pair_t *data);

C++bool MultiTree::SetFwd (const pair_t *data);
bool MultiTree::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 functions are called from read only section, started by LockWritings access predicate.

Getting element value

By element index

Cbool MultiTree_GetIndex (const struct MultiTree *tree, struct pair_t *data, size_t index);

C++bool MultiTree::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 MultiTree_GetFwd (const struct MultiTree *tree, struct pair_t *data);
bool MultiTree_GetBwd (const struct MultiTree *tree, struct pair_t *data);

C++bool MultiTree::GetFwd (pair_t *data) const;
bool MultiTree::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 MultiTree_GetIter (const struct MultiTree *tree, struct pair_t *data, ptr_t iter);

C++bool MultiTree::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.

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, 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 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 MultiTree_FwdToIndex (struct MultiTree *tree, size_t index);

C++void MultiTree::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 MultiTree_FwdToMin (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_FwdToMax (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_FwdToBwd (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_GetFwdPos (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_FwdGoNext (struct MultiTree *tree, size_t pos);

C++bool MultiTree::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 MultiTree_FwdGoPrev (struct MultiTree *tree, size_t pos);

C++bool MultiTree::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, 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 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 MultiTree_BwdToIndex (struct MultiTree *tree, size_t index);

C++void MultiTree::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 MultiTree_BwdToMin (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_BwdToMax (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_BwdToFwd (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_GetBwdPos (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_BwdGoNext (struct MultiTree *tree, size_t pos);

C++bool MultiTree::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 MultiTree_BwdGoPrev (struct MultiTree *tree, size_t pos);

C++bool MultiTree::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 MultiTree_IterToIndex (const struct MultiTree *tree, size_t index);

C++ptr_t MultiTree::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 MultiTree_IterToMin (const struct MultiTree *tree);

C++ptr_t MultiTree::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 MultiTree_IterToMax (const struct MultiTree *tree);

C++ptr_t MultiTree::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 MultiTree_IterToFwd (const struct MultiTree *tree);

C++ptr_t MultiTree::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 MultiTree_IterToBwd (const struct MultiTree *tree);

C++ptr_t MultiTree::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 MultiTree_GetIterPos (const struct MultiTree *tree, ptr_t iter);

C++size_t MultiTree::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 MultiTree_IterGoFwd (const struct MultiTree *tree, size_t pos, ptr_t *iter);

C++bool MultiTree::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 MultiTree_IterGoBwd (const struct MultiTree *tree, size_t pos, ptr_t *iter);

C++bool MultiTree::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 MultiTree_SwapFwdBwd (struct MultiTree *tree);

C++void MultiTree::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 MultiTree_MinFwd (struct MultiTree *tree, struct pair_t *data);
bool MultiTree_MinBwd (struct MultiTree *tree, struct pair_t *data);

C++bool MultiTree::MinFwd (pair_t *data);
bool MultiTree::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 MultiTree_MinIterFwd (const struct MultiTree *tree, struct pair_t *data, ptr_t *iter);
bool MultiTree_MinIterBwd (const struct MultiTree *tree, struct pair_t *data, ptr_t *iter);

C++bool MultiTree::MinIterFwd (pair_t *data, ptr_t *iter) const;
bool MultiTree::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 MultiTree_MaxFwd (struct MultiTree *tree, struct pair_t *data);
bool MultiTree_MaxBwd (struct MultiTree *tree, struct pair_t *data);

C++bool MultiTree::MaxFwd (pair_t *data);
bool MultiTree::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 MultiTree_MaxIterFwd (const struct MultiTree *tree, struct pair_t *data, ptr_t *iter);
bool MultiTree_MaxIterBwd (const struct MultiTree *tree, struct pair_t *data, ptr_t *iter);

C++bool MultiTree::MaxIterFwd (pair_t *data, ptr_t *iter) const;
bool MultiTree::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 MultiTree_FindEqualFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
bool MultiTree_FindEqualBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++bool MultiTree::FindEqualFwd (pair_t *data, adt_t key);
bool MultiTree::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 MultiTree_FindEqualIterFwd (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
bool MultiTree_FindEqualIterBwd (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++bool MultiTree::FindEqualIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
bool MultiTree::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 MultiTree_FindGreatFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
bool MultiTree_FindGreatBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++bool MultiTree::FindGreatFwd (pair_t *data, adt_t key);
bool MultiTree::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 MultiTree_FindGreatIter (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++bool MultiTree::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 MultiTree_FindGreatOrEqualFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
bool MultiTree_FindGreatOrEqualBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++bool MultiTree::FindGreatOrEqualFwd (pair_t *data, adt_t key);
bool MultiTree::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 MultiTree_FindGreatOrEqualIter (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++bool MultiTree::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 MultiTree_FindLessFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
bool MultiTree_FindLessBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++bool MultiTree::FindLessFwd (pair_t *data, adt_t key);
bool MultiTree::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 MultiTree_FindLessIter (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++bool MultiTree::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 MultiTree_FindLessOrEqualFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
bool MultiTree_FindLessOrEqualBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++bool MultiTree::FindLessOrEqualFwd (pair_t *data, adt_t key);
bool MultiTree::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 MultiTree_FindLessOrEqualIter (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++bool MultiTree::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.

Sequence searching

Csize_t MultiTree_FindSequenceFwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);
size_t MultiTree_FindSequenceBwd (struct MultiTree *tree, struct pair_t *data, union adt_t key);

C++size_t MultiTree::FindSequenceFwd (pair_t *data, adt_t key);
size_t MultiTree::FindSequenceBwd (pair_t *data, adt_t key);

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

• tree - pointer to the tree
• data - address where to return the value of the first/last found element
• key - key value to process

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 MultiTree_FindSequenceIterFwd (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);
size_t MultiTree_FindSequenceIterBwd (const struct MultiTree *tree, struct pair_t *data, union adt_t key, ptr_t *iter);

C++size_t MultiTree::FindSequenceIterFwd (pair_t *data, adt_t key, ptr_t *iter) const;
size_t MultiTree::FindSequenceIterBwd (pair_t *data, adt_t key, ptr_t *iter) const;

Description: Scan the tree for sequence of elements, which are equal to the key, in forward (FindSequenceIterFwd) or backward (FindSequenceIterFwd) 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:

• tree - pointer to the tree
• data - address where to return the value of the first/last found element
• key - key value to process
• iter - address of external iterator, which is used to point to tree 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 tree elements. They don't change any object parameters.

Vectorized searching

Csize_t MultiTree_FindVectorFwd (struct MultiTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);
size_t MultiTree_FindVectorBwd (struct MultiTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize);

C++size_t MultiTree::FindVectorFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize);
size_t MultiTree::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 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:

• 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 MultiTree_FindVectorIterFwd (const struct MultiTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);
size_t MultiTree_FindVectorIterBwd (const struct MultiTree *tree, struct pair_t data[], size_t size, struct pair_t vector[], size_t *vsize, ptr_t *iter);

C++size_t MultiTree::FindVectorIterFwd (pair_t data[], size_t size, pair_t vector[], size_t *vsize, ptr_t *iter) const;
size_t MultiTree::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 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:

• 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.

Duplicates searching

Cbool MultiTree_FindDupFwd (struct MultiTree *tree, struct pair_t *data, size_t count);
bool MultiTree_FindDupBwd (struct MultiTree *tree, struct pair_t *data, size_t count);

C++bool MultiTree::FindDupFwd (pair_t *data, size_t count);
bool MultiTree::FindDupBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the tree in forward/backward 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:

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

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 MultiTree_FindDupIterFwd (const struct MultiTree *tree, struct pair_t *data, size_t count, ptr_t *iter) const;
bool MultiTree_FindDupIterBwd (const struct MultiTree *tree, struct pair_t *data, size_t count, ptr_t *iter) const;

C++bool MultiTree::FindDupIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool MultiTree::FindDupIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the tree in forward/backward 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:

• tree - pointer to target tree
• data - address where to return the value of non unique element
• count - number of elements to check (-1 means all available elements)
• iter - address of external iterator, which is used to point to tree 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 tree elements. They don't change any object parameters.

Searching for differences

Cbool MultiTree_FindDiffFwd (struct MultiTree *tree, struct pair_t *data, const struct MultiTree *source, size_t count);
bool MultiTree_FindDiffBwd (struct MultiTree *tree, struct pair_t *data, const struct MultiTree *source, size_t count);

C++bool MultiTree::FindDiffFwd (pair_t *data, const MultiTree *source, size_t count);
bool MultiTree::FindDiffBwd (pair_t *data, const MultiTree *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 MultiTree_FindDiffIterFwd (const struct MultiTree *tree, struct pair_t *data, const struct MultiTree *source, size_t count, ptr_t *titer, ptr_t siter);
bool MultiTree_FindDiffIterBwd (const struct MultiTree *tree, struct pair_t *data, const struct MultiTree *source, size_t count, ptr_t *titer, ptr_t siter);

C++bool MultiTree::FindDiffIterFwd (pair_t *data, const MultiTree *source, size_t count, ptr_t *titer, ptr_t siter) const;
bool MultiTree::FindDiffIterBwd (pair_t *data, const MultiTree *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 MultiTree_CountKey (const struct MultiTree *tree, union adt_t key);

C++size_t MultiTree::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 MultiTree_CountKeys (const struct MultiTree *tree, const union adt_t keys[], size_t size);

C++size_t MultiTree::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.

Unique values

Csize_t MultiTree_Unique (struct MultiTree *tree, const struct MultiTree *source);

C++size_t MultiTree::Unique (const MultiTree *source);

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

Access type: RW

Parameters:

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

Return value:

• Count of unique elements were found in source tree.
• -1 if target tree 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 tree is empty. If it already has any elements, then operation will fail.

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

Comparison of multi trees

Csint64_t MultiTree_Compare (const struct MultiTree *tree, const struct MultiTree *source);

C++sint64_t MultiTree::Compare (const MultiTree *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 duplicate values

Cbool MultiTree_CheckDup (const struct MultiTree *tree);

C++bool MultiTree::CheckDup (void) const;

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

Access type: RO

Parameters:

• tree - pointer to target tree

Return value:

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

Check for equality

Cbool MultiTree_IsEqual (const struct MultiTree *tree, const struct MultiTree *source);

C++bool MultiTree::IsEqual (const MultiTree *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 MultiTree_KeyType (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_CompareFunction (const struct MultiTree *tree);

C++KeyCmp MultiTree::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 MultiTree_CopyFunction (const struct MultiTree *tree);

C++CopyFunc MultiTree::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 MultiTree_DeleteFunction (const struct MultiTree *tree);

C++DelFunc MultiTree::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* MultiTree_UserData (const struct MultiTree *tree);

C++void* MultiTree::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 MultiTree_Capacity (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_Size (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_Height (const struct MultiTree *tree);

C++size_t MultiTree::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 MultiTree_IsEmpty (const struct MultiTree *tree);

C++bool MultiTree::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 MultiTree_IsInit (const struct MultiTree *tree);

C++bool MultiTree::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.