Linux Assemblycollection of fast libraries

Ring ADTRing.h

Circular doubly linked list is a linked data structure that consists of a set of circularly linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. Nodes are wrapped in the ring, where last element is pointing to first element in the list and vice versa. The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly-linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

This implementation of circular doubly linked list has wide list nodes, that hold more than one value in the node, and can efficiently use cache-memory of modern CPUs. See the benchmarks.

Contents


Function list

C function nameAccess typeC++ function nameAccess type
AllowReadingsRW(constructor) RingRW
AllowWritingsRW(copy constructor) RingRW
BwdGoNextRW(destructor) ~RingRW
BwdGoPrevRWAllowReadingsRW
BwdToFwdRWAllowWritingsRW
BwdToIndexRWBwdGoNextRW
BwdToLinkRWBwdGoPrevRW
CapacityROBwdToFwdRW
CheckDupROBwdToIndexRW
CheckSortAscROBwdToLinkRW
CheckSortDscROCapacityRO
CompareROCheckDupRO
CompareFunctionROCheckSortAscRO
CopyAfterBwdRWCheckSortDscRO
CopyAfterFwdRWCompareRO
CopyAfterLinkRWCompareFunctionRO
CopyBeforeBwdRWCopyAfterBwdRW
CopyBeforeFwdRWCopyAfterFwdRW
CopyBeforeLinkRWCopyAfterLinkRW
CopyFunctionROCopyBeforeBwdRW
CopyRingRWCopyBeforeFwdRW
CountKeyBwdROCopyBeforeLinkRW
CountKeyFwdROCopyFunctionRO
CountKeyIterBwdROCountKeyBwdRO
CountKeyIterFwdROCountKeyFwdRO
CountKeysBwdROCountKeyIterBwdRO
CountKeysFwdROCountKeyIterFwdRO
CountKeysIterBwdROCountKeysBwdRO
CountKeysIterFwdROCountKeysFwdRO
DeleteFunctionROCountKeysIterBwdRO
FindDiffBwdRWCountKeysIterFwdRO
FindDiffFwdRWDeleteFunctionRO
FindDiffIterBwdROFindDiffBwdRW
FindDiffIterFwdROFindDiffFwdRW
FindDupBwdRWFindDiffIterBwdRO
FindDupFwdRWFindDiffIterFwdRO
FindDupIterBwdROFindDupBwdRW
FindDupIterFwdROFindDupFwdRW
FindKeyBwdRWFindDupIterBwdRO
FindKeyFwdRWFindDupIterFwdRO
FindKeyIterBwdROFindKeyBwdRW
FindKeyIterFwdROFindKeyFwdRW
FindKeysBwdRWFindKeyIterBwdRO
FindKeysFwdRWFindKeyIterFwdRO
FindKeysIterBwdROFindKeysBwdRW
FindKeysIterFwdROFindKeysFwdRW
FindNonAscBwdRWFindKeysIterBwdRO
FindNonAscFwdRWFindKeysIterFwdRO
FindNonAscIterBwdROFindNonAscBwdRW
FindNonAscIterFwdROFindNonAscFwdRW
FindNonDscBwdRWFindNonAscIterBwdRO
FindNonDscFwdRWFindNonAscIterFwdRO
FindNonDscIterBwdROFindNonDscBwdRW
FindNonDscIterFwdROFindNonDscFwdRW
FreeRingRWFindNonDscIterBwdRO
FwdGoNextRWFindNonDscIterFwdRO
FwdGoPrevRWFwdGoNextRW
FwdToBwdRWFwdGoPrevRW
FwdToIndexRWFwdToBwdRW
FwdToLinkRWFwdToIndexRW
GetBwdROFwdToLinkRW
GetBwdPosROGetBwdRO
GetFwdROGetBwdPosRO
GetFwdPosROGetFwdRO
GetIterROGetFwdPosRO
GetIterPosROGetIterRO
GetLinkROGetIterPosRO
InitRingRWGetLinkRO
InsertAfterBwdRWInsertAfterBwdRW
InsertAfterFwdRWInsertAfterFwdRW
InsertAfterLinkRWInsertAfterLinkRW
InsertBeforeBwdRWInsertBeforeBwdRW
InsertBeforeFwdRWInsertBeforeFwdRW
InsertBeforeLinkRWInsertBeforeLinkRW
IsEmptyROIsEmptyRO
IsEqualROIsEqualRO
IsInitROIsInitRO
IterGoBwdROIterGoBwdRO
IterGoFwdROIterGoFwdRO
IterToBwdROIterToBwdRO
IterToFwdROIterToFwdRO
IterToIndexROIterToIndexRO
IterToLinkROIterToLinkRO
KeyTypeROKeyTypeRO
LockReadingsRWLockReadingsRW
LockWritingsRWLockWritingsRW
MaxBwdRWMaxBwdRW
MaxFwdRWMaxFwdRW
MaxIterBwdROMaxIterBwdRO
MaxIterFwdROMaxIterFwdRO
MergeAscRWMergeAscRW
MergeDscRWMergeDscRW
MinBwdRWMinBwdRW
MinFwdRWMinFwdRW
MinIterBwdROMinIterBwdRO
MinIterFwdROMinIterFwdRO
MoveAfterBwdRWMoveAfterBwdRW
MoveAfterFwdRWMoveAfterFwdRW
MoveAfterLinkRWMoveAfterLinkRW
MoveBeforeBwdRWMoveBeforeBwdRW
MoveBeforeFwdRWMoveBeforeFwdRW
MoveBeforeLinkRWMoveBeforeLinkRW
RemoveBwdRWRemoveBwdRW
RemoveFwdRWRemoveFwdRW
RemoveLinkRWRemoveLinkRW
ReverseBwdRWReverseBwdRW
ReverseFwdRWReverseFwdRW
ReverseLinkRWReverseLinkRW
SetBwdRWSetBwdRW
SetFwdRWSetFwdRW
SetLinkRWSetLinkRW
SizeROSizeRO
SortAscRWSortAscRW
SortDscRWSortDscRW
SwapRWSwapRW
SwapFwdBwdRWSwapFwdBwdRW
UniqueRWUniqueRW
UserDataROUserDataRO
C function nameAccess typeC++ function nameAccess type

Constructor

Cvoid Ring_InitRing (struct Ring *ring, size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);
C++Ring::Ring (size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new ring instance.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • capacity - initial count of elements that the ring can hold. Ring capacity is auto extended if required.
  • 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 Ring_CopyRing (struct Ring *ring, const struct Ring *source);
C++Ring::Ring (const Ring &source);

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

Access type: RW

Parameters:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value: None.

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

Destructor

Cvoid Ring_FreeRing (struct Ring *ring);
C++Ring::~Ring (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

Access predicates

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

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

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • 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 ring.
  • 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 Ring_LockWritings (struct Ring *ring, bool wait);
C++bool Ring::LockWritings (bool wait);

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

Access type: RW

Parameters:

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

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

Releasing of exclusive lock

Cvoid Ring_AllowReadings (struct Ring *ring);
C++void Ring::AllowReadings (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

Releasing of read only lock

Cvoid Ring_AllowWritings (struct Ring *ring);
C++void Ring::AllowWritings (void);

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

  • ring - pointer to the circular list

Return value: None.

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

Copying elements

Using ring link

Csize_t Ring_CopyAfterLink (struct Ring *ring, const struct Ring *source, size_t count);
size_t Ring_CopyBeforeLink (struct Ring *ring, const struct Ring *source, size_t count);
C++size_t Ring::CopyAfterLink (const Ring *source, size_t count);
size_t Ring::CopyBeforeLink (const Ring *source, size_t count);

Description: Copy "count" elements, from source ring into target ring after/before position of ring link. Functions copy data, starting from current position of backward (CopyAfterLink) or forward (CopyBeforeLink) iterator of source ring, until all "count" elements are copied into target ring. Source ring stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

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

Return value:

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

Using forward iterator

Csize_t Ring_CopyAfterFwd (struct Ring *ring, const struct Ring *source, size_t count);
size_t Ring_CopyBeforeFwd (struct Ring *ring, const struct Ring *source, size_t count);
C++size_t Ring::CopyAfterFwd (const Ring *source, size_t count);
size_t Ring::CopyBeforeFwd (const Ring *source, size_t count);

Description: Copy "count" elements, from source ring into target ring after/before position of forward iterator. Functions copy data, starting from current position of forward iterator of source ring in positive direction, until all "count" elements are copied into target ring. Source ring stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

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

Return value:

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

Using backward iterator

Csize_t Ring_CopyAfterBwd (struct Ring *ring, const struct Ring *source, size_t count);
size_t Ring_CopyBeforeBwd (struct Ring *ring, const struct Ring *source, size_t count);
C++size_t Ring::CopyAfterBwd (const Ring *source, size_t count);
size_t Ring::CopyBeforeBwd (const Ring *source, size_t count);

Description: Copy "count" elements, from source ring into target ring after/before position of backward iterator. Functions copy data, starting from current position of backward iterator of source ring in negative direction, until all "count" elements are copied into target ring. Source ring stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

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

Return value:

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

Moving elements

Using ring link

Csize_t Ring_MoveAfterLink (struct Ring *ring, struct Ring *source, size_t count);
size_t Ring_MoveBeforeLink (struct Ring *ring, struct Ring *source, size_t count);
C++size_t Ring::MoveAfterLink (Ring *source, size_t count);
size_t Ring::MoveBeforeLink (Ring *source, size_t count);

Description: Move "count" elements, from source ring into target ring after/before position of ring link. Functions move data, starting from current position of backward (MoveAfterLink) or forward (MoveBeforeLink) iterator of source ring, until all "count" elements are moved into target ring.

Access type: RW

Parameters:

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

Return value:

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

Using forward iterator

Csize_t Ring_MoveAfterFwd (struct Ring *ring, struct Ring *source, size_t count);
size_t Ring_MoveBeforeFwd (struct Ring *ring, struct Ring *source, size_t count);
C++size_t Ring::MoveAfterFwd (Ring *source, size_t count);
size_t Ring::MoveBeforeFwd (Ring *source, size_t count);

Description: Move "count" elements, from source ring into target ring after/before position of forward iterator. Functions move data, starting from current position of forward iterator of source ring in positive direction, until all "count" elements are moved into target ring.

Access type: RW

Parameters:

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

Return value:

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

Using backward iterator

Csize_t Ring_MoveAfterBwd (struct Ring *ring, struct Ring *source, size_t count);
size_t Ring_MoveBeforeBwd (struct Ring *ring, struct Ring *source, size_t count);
C++size_t Ring::MoveAfterBwd (Ring *source, size_t count);
size_t Ring::MoveBeforeBwd (Ring *source, size_t count);

Description: Move "count" elements, from source ring into target ring after/before position of backward iterator. Functions move data, starting from current position of backward iterator of source ring in negative direction, until all "count" elements are moved into target ring.

Access type: RW

Parameters:

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

Return value:

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

Insertion of element

Using ring link

Cbool Ring_InsertAfterLink (struct Ring *ring, const struct pair_t *data);
bool Ring_InsertBeforeLink (struct Ring *ring, const struct pair_t *data);
C++bool Ring::InsertAfterLink (const pair_t *data);
bool Ring::InsertBeforeLink (const pair_t *data);

Description: Insert new element into the ring after/before current position of ring link.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - pointer to the new element

Return value:

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

Using forward iterator

Cbool Ring_InsertAfterFwd (struct Ring *ring, const struct pair_t *data);
bool Ring_InsertBeforeFwd (struct Ring *ring, const struct pair_t *data);
C++bool Ring::InsertAfterFwd (const pair_t *data);
bool Ring::InsertBeforeFwd (const pair_t *data);

Description: Insert new element into the ring after/before current position of forward iterator.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - pointer to the new element

Return value:

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

Using backward iterator

Cbool Ring_InsertAfterBwd (struct Ring *ring, const struct pair_t *data);
bool Ring_InsertBeforeBwd (struct Ring *ring, const struct pair_t *data);
C++bool Ring::InsertAfterBwd (const pair_t *data);
bool Ring::InsertBeforeBwd (const pair_t *data);

Description: Insert new element into the ring after/before current position of backward iterator.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - pointer to the new element

Return value:

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

Removing of element

Cbool Ring_RemoveLink (struct Ring *ring);
bool Ring_RemoveFwd (struct Ring *ring);
bool Ring_RemoveBwd (struct Ring *ring);
C++bool Ring::RemoveLink (void);
bool Ring::RemoveFwd (void);
bool Ring::RemoveBwd (void);

Description: Remove element, which is pointed by forward/backward iterator or ring link.

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value:

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

Setting element value

Cbool Ring_SetLink (struct Ring *ring, const struct pair_t *data);
bool Ring_SetFwd (struct Ring *ring, const struct pair_t *data);
bool Ring_SetBwd (struct Ring *ring, const struct pair_t *data);
C++bool Ring::SetLink (const pair_t *data);
bool Ring::SetFwd (const pair_t *data);
bool Ring::SetBwd (const pair_t *data);

Description: Set value of the element, which is pointed by forward/backward iterator or ring link.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - pointer to the new value of the element

Return value:

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

Getting element value

Cbool Ring_GetLink (const struct Ring *ring, struct pair_t *data);
bool Ring_GetFwd (const struct Ring *ring, struct pair_t *data);
bool Ring_GetBwd (const struct Ring *ring, struct pair_t *data);
C++bool Ring::GetLink (pair_t *data) const;
bool Ring::GetFwd (pair_t *data) const;
bool Ring::GetBwd (pair_t *data) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • data - address where to return the value of the element

Return value:

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

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

Access type: RO

Parameters:

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

Return value:

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

Changing elements order

Reversing elements order

Csize_t Ring_ReverseLink (struct Ring *ring, size_t count);
size_t Ring_ReverseFwd (struct Ring *ring, size_t count);
size_t Ring_ReverseBwd (struct Ring *ring, size_t count);
C++size_t Ring::ReverseLink (size_t count);
size_t Ring::ReverseFwd (size_t count);
size_t Ring::ReverseBwd (size_t count);

Description: Reverse order of "count" elements in the ring starting from current position of forward/backward iterator or ring link, and store them in the same place in new order. Other elements are not modified.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • count - number of elements to reverse (-1 means all available elements)

Return value:

  • Real count of elements, which were reversed.
  • -1 if iterator position is not set, or functions are called from read only section, started by LockWritings access predicate.

Swapping elements

Cbool Ring_Swap (struct Ring *ring);
C++bool Ring::Swap (void);

Description: Swap elements, which are pointed by forward and backward iterators.

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value:

  • TRUE (1) if both iterators point to ring elements.
  • FALSE (0) if the iterators are not set, or functions are called from read only section, started by LockWritings access predicate.

Manipulation with forward iterator

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

Set iterator position

These functions set iterator position to link element, or to any ring element by its index or by the value of another iterator. Ring elements are treated as ordered array of keys, which starts from link element (zero index). Indexes grow in forward direction. When you insert new elements or delete existing keys, the indexes are changed, but the iterators still point to the same elements. To set initial position of iterators, you may use these functions.

By index

Cvoid Ring_FwdToIndex (struct Ring *ring, size_t index);
C++void Ring::FwdToIndex (size_t index);

Description: Move iterator position to element with chosen index in the ring. Link element has 0 index. Indexes grow in forward direction. If index is greater than or equal to ring size, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • index - index of the element to move to

Return value: None.

To link element

Cvoid Ring_FwdToLink (struct Ring *ring);
C++void Ring::FwdToLink (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

To backward iterator

Cvoid Ring_FwdToBwd (struct Ring *ring);
C++void Ring::FwdToBwd (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

Get iterator position

Csize_t Ring_GetFwdPos (const struct Ring *ring);
C++size_t Ring::GetFwdPos (void) const;

Description: Return index of the element, which is pointed by the forward iterator.

Access type: RO

Parameters:

  • ring - pointer to the circular list

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, allow you to move to next and previous elements relatively to current position of the iterator. They are designed to walk through the ring elements and get neighbor elements for current element.

Move to next position

Cbool Ring_FwdGoNext (struct Ring *ring, size_t pos);
C++bool Ring::FwdGoNext (size_t pos);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • pos - number of positions to move iterator

Return value:

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

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

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • pos - number of positions to move iterator

Return value:

  • TRUE (1) if iterator points to any ring 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 ring in very fast and efficient way. The main goal of this iterator to enumerate elements in backward (positive) direction: from last to first element. But it can also move in forward (negative) direction: from first to last element. It always points to ring elements, except the ring is empty. It stays pointing to the same key, even if you insert a new value into the ring or delete existing element before/after it. If you remove an element, which is pointed by backward iterator, it automatically moves to the next element in backward direction. This trick work well if you need to remove all the elements from the ring.

Set iterator position

These functions set iterator position to link element, or to any ring element by its index or by the value of another iterator. Ring elements are treated as ordered array of keys, which starts from link element (zero index). Indexes grow in forward direction. When you insert new elements or delete existing keys, the indexes are changed, but the iterators still point to the same elements. To set initial position of iterators, you may use these functions.

By index

Cvoid Ring_BwdToIndex (struct Ring *ring, size_t index);
C++void Ring::BwdToIndex (size_t index);

Description: Move iterator position to element with chosen index in the ring. Link element has 0 index. Indexes grow in forward direction. If index is greater than or equal to ring size, then iterator is marked as non valid (points to non existing element).

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • index - index of the element to move to

Return value: None.

To link element

Cvoid Ring_BwdToLink (struct Ring *ring);
C++void Ring::BwdToLink (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

To forward iterator

Cvoid Ring_BwdToFwd (struct Ring *ring);
C++void Ring::BwdToFwd (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

Get iterator position

Csize_t Ring_GetBwdPos (const struct Ring *ring);
C++size_t Ring::GetBwdPos (void) const;

Description: Return index of the element, which is pointed by the backward iterator.

Access type: RO

Parameters:

  • ring - pointer to the circular list

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, allow you to move to next and previous elements relatively to current position of the iterator. They are designed to walk through the ring elements and get neighbor elements for current element.

Move to next position

Cbool Ring_BwdGoNext (struct Ring *ring, size_t pos);
C++bool Ring::BwdGoNext (size_t pos);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • pos - number of positions to move iterator

Return value:

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

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

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • pos - number of positions to move iterator

Return value:

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

Set iterator position

These functions set external iterator position to link element, or to any ring element by its index or by the value of another iterator. Ring elements are treated as ordered array of keys, which starts from link element (zero index). Indexes grow in forward direction. 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 ring structure or keys.

By index

Cptr_t Ring_IterToIndex (const struct Ring *ring, size_t index);
C++ptr_t Ring::IterToIndex (size_t index) const;

Description: Return iterator value, which points to element with chosen index in the ring. Link element has 0 index. Indexes grow in forward direction. If index is greater than or equal to ring 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:

  • ring - pointer to the circular list
  • 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 ring elements. It doesn't change any object parameters.

To link element

Cptr_t Ring_IterToLink (const struct Ring *ring);
C++ptr_t Ring::IterToLink (void) const;

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

  • ring - pointer to the circular list

Return value:

  • Link iterator value.
  • Negative value if ring is empty.

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

To forward iterator

Cptr_t Ring_IterToFwd (const struct Ring *ring);
C++ptr_t Ring::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:

  • ring - pointer to the circular list

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

To backward iterator

Cptr_t Ring_IterToBwd (const struct Ring *ring);
C++ptr_t Ring::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:

  • ring - pointer to the circular list

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

Get iterator position

Csize_t Ring_GetIterPos (const struct Ring *ring, ptr_t iter);
C++size_t Ring::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:

  • ring - pointer to the circular list
  • iter - value of external iterator, which is used to point to the ring 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 ring 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 ring elements and get neighbor keys for current key.

Move in forward direction

Cbool Ring_IterGoFwd (const struct Ring *ring, size_t pos, ptr_t *iter);
C++bool Ring::IterGoFwd (size_t pos, ptr_t *iter) const;

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

Access type: RO

Parameters:

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

Return value:

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

Move in backward direction

Cbool Ring_IterGoBwd (const struct Ring *ring, size_t pos, ptr_t *iter);
C++bool Ring::IterGoBwd (size_t pos, ptr_t *iter) const;

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

Access type: RO

Parameters:

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

Return value:

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

Swapping iterators

Cvoid Ring_SwapFwdBwd (struct Ring *ring);
C++void Ring::SwapFwdBwd (void);

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

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value: None.

Minimum and maximum value

Minimum value

Cbool Ring_MinFwd (struct Ring *ring, struct pair_t *data, size_t count);
bool Ring_MinBwd (struct Ring *ring, struct pair_t *data, size_t count);
C++bool Ring::MinFwd (pair_t *data, size_t count);
bool Ring::MinBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the ring in forward/backward direction from current position of forward/backward iterator, 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:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • count - number of elements to check (-1 means all available elements)

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the ring is empty, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_MinIterFwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
bool Ring_MinIterBwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
C++bool Ring::MinIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool Ring::MinIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the ring in forward/backward direction from current position of external iterator, 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:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the ring is empty, or iterator is not set (has negative value).

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

Maximum value

Cbool Ring_MaxFwd (struct Ring *ring, struct pair_t *data, size_t count);
bool Ring_MaxBwd (struct Ring *ring, struct pair_t *data, size_t count);
C++bool Ring::MaxFwd (pair_t *data, size_t count);
bool Ring::MaxBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the ring in forward/backward direction from current position of forward/backward iterator, 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:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • count - number of elements to check (-1 means all available elements)

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the ring is empty, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_MaxIterFwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
bool Ring_MaxIterBwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
C++bool Ring::MaxIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool Ring::MaxIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the ring in forward/backward direction from current position of external iterator, 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:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if operation complete successfully.
  • FALSE (0) if the ring is empty, or iterator is not set (has negative value).

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

Key searching

Following functions check ring elements for first element, which match the key or the set of keys, then set forward/backward iterator position to that element. If required element is found, then they store its value into the data structure is pointed by "data" pointer. If target value was not found, then the iterator position and "data" structure stay unchanged.

Single key searching

Cbool Ring_FindKeyFwd (struct Ring *ring, struct pair_t *data, union adt_t key, size_t count);
bool Ring_FindKeyBwd (struct Ring *ring, struct pair_t *data, union adt_t key, size_t count);
C++bool Ring::FindKeyFwd (pair_t *data, adt_t key, size_t count);
bool Ring::FindKeyBwd (pair_t *data, adt_t key, size_t count);

Description: Scan the ring in forward/backward direction from current position of forward/backward iterator, for first element, which is equal to 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. If target value was not found, then the iterator position stay unchanged.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • key - key value to process
  • count - number of elements to check (-1 means all available elements)

Return value:

  • TRUE (1) if required element was found in the ring.
  • FALSE (0) if the iterator is not set, or the ring has no keys, which satisfy the search condition, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_FindKeyIterFwd (const struct Ring *ring, struct pair_t *data, union adt_t key, size_t count, ptr_t *iter);
bool Ring_FindKeyIterBwd (const struct Ring *ring, struct pair_t *data, union adt_t key, size_t count, ptr_t *iter);
C++bool Ring::FindKeyIterFwd (pair_t *data, adt_t key, size_t count, ptr_t *iter) const;
bool Ring::FindKeyIterBwd (pair_t *data, adt_t key, size_t count, ptr_t *iter) const;

Description: Scan the ring in forward/backward direction from current position of external iterator, for first element, which is equal to 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. If target value was not found, then the iterator position stay unchanged.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • key - key value to process
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if required element was found in the ring.
  • FALSE (0) if the external iterator is not set (has negative value), or the ring has no keys, which satisfy the search condition.

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

Keys set searching

Cbool Ring_FindKeysFwd (struct Ring *ring, struct pair_t *data, const union adt_t keys[], size_t size, size_t count);
bool Ring_FindKeysBwd (struct Ring *ring, struct pair_t *data, const union adt_t keys[], size_t size, size_t count);
C++bool Ring::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size, size_t count);
bool Ring::FindKeysBwd (pair_t *data, const adt_t keys[], size_t size, size_t count);

Description: Scan the ring in forward/backward direction from current position of forward/backward iterator, for first element, which is equal to any key in set set of keys, 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. If target values were not found, then the iterator position stay unchanged.

Access type: RW

Parameters:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • keys - array of keys to find in the circular list
  • size - size of array of keys
  • count - number of elements to check (-1 means all available elements)

Return value:

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

Description: Scan the ring in forward/backward direction from current position of external iterator, for first element, which is equal to any key in set set of keys, 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. If target values were not found, then the iterator position stay unchanged.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • data - address where to return the value of the found element
  • keys - array of keys to find in the circular list
  • size - size of array of keys
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if required element was found in the ring.
  • FALSE (0) if the external iterator is not set (has negative value), or the ring has no keys, which satisfy the search condition.

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

Duplicates searching

Cbool Ring_FindDupFwd (struct Ring *ring, struct pair_t *data, size_t count);
bool Ring_FindDupBwd (struct Ring *ring, struct pair_t *data, size_t count);
C++bool Ring::FindDupFwd (pair_t *data, size_t count);
bool Ring::FindDupBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the ring 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:

  • ring - pointer to target circular list
  • 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.

Note:These functions work only with sorted rings, regardless of sort order. To use them with regular rings they should be sorted first.

Cbool Ring_FindDupIterFwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
bool Ring_FindDupIterBwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
C++bool Ring::FindDupIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool Ring::FindDupIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the ring 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:

  • ring - pointer to target circular list
  • 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 ring 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).

Note:These functions work only with sorted rings, regardless of sort order. To use them with regular rings they should be sorted first.

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

Unordered elements searching

Following functions check rings for required sort order, and return value of the first element, which did not pass the sort condition. Besides the element value, they also set iterator to position of non ordered element.

Ascending sort order

Cbool Ring_FindNonAscFwd (struct Ring *ring, struct pair_t *data, size_t count);
bool Ring_FindNonAscBwd (struct Ring *ring, struct pair_t *data, size_t count);
C++bool Ring::FindNonAscFwd (pair_t *data, size_t count);
bool Ring::FindNonAscBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the ring in forward/backward direction from current position of forward/backward iterator, and set iterator position to first non ascending element, then return value of that element into the data structure is pointed by "data" pointer. If all elements are correctly ordered, then functions return FALSE, and the iterator position stay unchanged.

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if non ordered element was found.
  • FALSE (0) if all elements have correct order, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_FindNonAscIterFwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
bool Ring_FindNonAscIterBwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
C++bool Ring::FindNonAscIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool Ring::FindNonAscIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the ring in forward/backward direction from current position of external iterator, and set iterator position to first non ascending element, then return value of that element into the data structure is pointed by "data" pointer. If all elements are correctly ordered, then functions return FALSE, and the iterator position stay unchanged.

Access type: RO

Parameters:

  • ring - pointer to target circular list
  • data - address where to return the value of non ordered element
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if non ordered element was found.
  • FALSE (0) if all elements have correct order, or iterator is not set (has negative value).

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

Descending sort order

Cbool Ring_FindNonDscFwd (struct Ring *ring, struct pair_t *data, size_t count);
bool Ring_FindNonDscBwd (struct Ring *ring, struct pair_t *data, size_t count);
C++bool Ring::FindNonDscFwd (pair_t *data, size_t count);
bool Ring::FindNonDscBwd (pair_t *data, size_t count);

Description: Scan "count" elements in the ring in forward/backward direction from current position of forward/backward iterator, and set iterator position to first non descending element, then return value of that element into the data structure is pointed by "data" pointer. If all elements are correctly ordered, then functions return FALSE, and the iterator position stay unchanged.

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if non ordered element was found.
  • FALSE (0) if all elements have correct order, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_FindNonDscIterFwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
bool Ring_FindNonDscIterBwd (const struct Ring *ring, struct pair_t *data, size_t count, ptr_t *iter);
C++bool Ring::FindNonDscIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool Ring::FindNonDscIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

Description: Scan "count" elements in the ring in forward/backward direction from current position of external iterator, and set iterator position to first non descending element, then return value of that element into the data structure is pointed by "data" pointer. If all elements are correctly ordered, then functions return FALSE, and the iterator position stay unchanged.

Access type: RO

Parameters:

  • ring - pointer to target circular list
  • data - address where to return the value of non ordered element
  • count - number of elements to check (-1 means all available elements)
  • iter - address of external iterator, which is used to point to ring element

Return value:

  • TRUE (1) if non ordered element was found.
  • FALSE (0) if all elements have correct order, or iterator is not set (has negative value).

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

Searching for differences

Cbool Ring_FindDiffFwd (struct Ring *ring, struct pair_t *data, const struct Ring *source, size_t count);
bool Ring_FindDiffBwd (struct Ring *ring, struct pair_t *data, const struct Ring *source, size_t count);
C++bool Ring::FindDiffFwd (pair_t *data, const Ring *source, size_t count);
bool Ring::FindDiffBwd (pair_t *data, const Ring *source, size_t count);

Description: Compare "count" elements of two ring objects (key by key) from first to last element (FindDiffFwd) or from last to first element (FindDiffBwd), starting from current position of forward/backward iterator, and set iterator to first non equal element in target ring, 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 ring is always accessed in read only mode.

Access type: RW

Parameters:

  • ring - pointer to target circular list
  • data - address where to return the value of non equal element
  • source - pointer to source circular list
  • 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 rings have incorrect iterators, or functions are called from read only section, started by LockWritings access predicate.
Cbool Ring_FindDiffIterFwd (const struct Ring *ring, struct pair_t *data, const struct Ring *source, size_t count, ptr_t *titer, ptr_t siter);
bool Ring_FindDiffIterBwd (const struct Ring *ring, struct pair_t *data, const struct Ring *source, size_t count, ptr_t *titer, ptr_t siter);
C++bool Ring::FindDiffIterFwd (pair_t *data, const Ring *source, size_t count, ptr_t *titer, ptr_t siter) const;
bool Ring::FindDiffIterBwd (pair_t *data, const Ring *source, size_t count, ptr_t *titer, ptr_t siter) const;

Description: Compare "count" elements of two ring objects (key by key) from first to last element (FindDiffIterFwd) or from last to first element (FindDiffIterBwd), starting from current position of "titer" and "siter" iterators, and set "titer" iterator to first non equal element in target ring, 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:

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

Return value:

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

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

Key counting

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

Single key counting

Csize_t Ring_CountKeyFwd (const struct Ring *ring, union adt_t key, size_t count);
size_t Ring_CountKeyBwd (const struct Ring *ring, union adt_t key, size_t count);
C++size_t Ring::CountKeyFwd (adt_t key, size_t count) const;
size_t Ring::CountKeyBwd (adt_t key, size_t count) const;

Description: Scan "count" elements in the ring in forward/backward direction, starting from current position of forward/backward iterator, and return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • key - key value to find in the circular list
  • count - number of elements to check (-1 means all available elements)

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

Csize_t Ring_CountKeyIterFwd (const struct Ring *ring, union adt_t key, size_t count, ptr_t iter);
size_t Ring_CountKeyIterBwd (const struct Ring *ring, union adt_t key, size_t count, ptr_t iter);
C++size_t Ring::CountKeyIterFwd (adt_t key, size_t count, ptr_t iter) const;
size_t Ring::CountKeyIterBwd (adt_t key, size_t count, ptr_t iter) const;

Description: Scan "count" elements in the ring in forward/backward direction, starting from current position of external iterator, and return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • key - key value to find in the circular list
  • count - number of elements to check (-1 means all available elements)
  • iter - value of external iterator, which is used to point to ring element

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

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

Keys set counting

Csize_t Ring_CountKeysFwd (const struct Ring *ring, const union adt_t keys[], size_t size, size_t count);
size_t Ring_CountKeysBwd (const struct Ring *ring, const union adt_t keys[], size_t size, size_t count);
C++size_t Ring::CountKeysFwd (const adt_t keys[], size_t size, size_t count) const;
size_t Ring::CountKeysBwd (const adt_t keys[], size_t size, size_t count) const;

Description: Scan "count" elements in the ring in forward/backward direction, starting from current position of forward/backward iterator, and return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • keys - array of keys to find in the circular list
  • size - size of array of keys
  • count - number of elements to check (-1 means all available elements)

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

Csize_t Ring_CountKeysIterFwd (const struct Ring *ring, const union adt_t keys[], size_t size, size_t count, ptr_t iter);
size_t Ring_CountKeysIterBwd (const struct Ring *ring, const union adt_t keys[], size_t size, size_t count, ptr_t iter);
C++size_t Ring::CountKeysIterFwd (const adt_t keys[], size_t size, size_t count, ptr_t iter) const;
size_t Ring::CountKeysIterBwd (const adt_t keys[], size_t size, size_t count, ptr_t iter) const;

Description: Scan "count" elements in the ring in forward/backward direction, starting from current position of external iterator, and return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

  • ring - pointer to the circular list
  • keys - array of keys to find in the circular list
  • size - size of array of keys
  • count - number of elements to check (-1 means all available elements)
  • iter - value of external iterator, which is used to point to ring element

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

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

Sorting

Sort functions reorder ring elements in ascending or descending sort order. They also invalidate forward and backward iterators, but do not touch link iterator. Sorting functions check only the key field of elements but do not check the assigned data. To compare ring elements these functions use key compare functions, which you provide to the sort procedure. Key compare function should follow this prototype.

Ascending sort order

Csize_t Ring_SortAsc (struct Ring *ring);
C++size_t Ring::SortAsc (void);

Description: Sort ring in ascending order.

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value:

  • Count of the elements, which were sorted.
  • -1 if sort functions were not able to allocate new memory blocks for internal use, or functions are called from read only section, started by LockWritings access predicate.

Note:Sort functions invalidate forward and backward iterators. You should reassign them before use.

Descending sort order

Csize_t Ring_SortDsc (struct Ring *ring);
C++size_t Ring::SortDsc (void);

Description: Sort ring in descending order.

Access type: RW

Parameters:

  • ring - pointer to the circular list

Return value:

  • Count of the elements, which were sorted.
  • -1 if sort functions were not able to allocate new memory blocks for internal use, or functions are called from read only section, started by LockWritings access predicate.

Note:Sort functions invalidate forward and backward iterators. You should reassign them before use.

Merging of sorted rings

Merge functions take two sorted rings and merge them into one sorted ring. These functions just add content of source ring into target ring, according to the sort order. They also invalidate forward and backward iterators, but do not touch link iterator.

Ascending sort order

Csize_t Ring_MergeAsc (struct Ring *ring, struct Ring *source);
C++size_t Ring::MergeAsc (Ring *source);

Description: Merge two sorted in ascending order rings into one sorted ring (target ring). All elements from source ring are moved to target ring and source ring remains empty after merge operation.

Access type: RW

Parameters:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value:

  • Count of the elements, which were copied from source ring.
  • -1 if merge functions were not able to extend capacity of the ring object for the new elements, or functions are called from read only section, started by LockWritings access predicate.

Warning:Merge operation moves all elements from source ring into target ring.

Note:Merge functions work only with sorted in correct order rings. If you try to merge unsorted rings, then result is undefined.

Descending sort order

Csize_t Ring_MergeDsc (struct Ring *ring, struct Ring *source);
C++size_t Ring::MergeDsc (Ring *source);

Description: Merge two sorted in descending order rings into one sorted ring (target ring). All elements from source ring are moved to target ring and source ring remains empty after merge operation.

Access type: RW

Parameters:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value:

  • Count of the elements, which were copied from source ring.
  • -1 if merge functions were not able to extend capacity of the ring object for the new elements, or functions are called from read only section, started by LockWritings access predicate.

Warning:Merge operation moves all elements from source ring into target ring.

Note:Merge functions work only with sorted in correct order rings. If you try to merge unsorted rings, then result is undefined.

Unique values

Csize_t Ring_Unique (struct Ring *ring, const struct Ring *source);
C++size_t Ring::Unique (const Ring *source);

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

Access type: RW

Parameters:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value:

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

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

Note:These functions work only with sorted rings, regardless of sort order. To use them with regular rings they should be sorted first.

Comparison of rings

Csint64_t Ring_Compare (const struct Ring *ring, const struct Ring *source);
C++sint64_t Ring::Compare (const Ring *source) const;

Description: Compare two ring objects (key by key) starting from first element to last element, using provided key compare function, 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:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value:

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

Checks

Check for sort order

Following functions check rings for required sort order, and return status of this check as boolean value. TRUE (1) if elements are correctly sorted and FALSE (0) if not.

Check for ascending sort order

Cbool Ring_CheckSortAsc (const struct Ring *ring);
C++bool Ring::CheckSortAsc (void) const;

Description: Check if ring is sorted in ascending sort order.

Access type: RO

Parameters:

  • ring - pointer to target circular list

Return value:

  • TRUE (1) if elements are sorted in ascending order.
  • FALSE (0) if at least one element does not conform with correct order.

Check for descending sort order

Cbool Ring_CheckSortDsc (const struct Ring *ring);
C++bool Ring::CheckSortDsc (void) const;

Description: Check if ring is sorted in descending sort order.

Access type: RO

Parameters:

  • ring - pointer to target circular list

Return value:

  • TRUE (1) if elements are sorted in descending order.
  • FALSE (0) if at least one element does not conform with correct order.

Check for duplicate values

Cbool Ring_CheckDup (const struct Ring *ring);
C++bool Ring::CheckDup (void) const;

Description: Check ring for non unique values (duplicates).

Access type: RO

Parameters:

  • ring - pointer to target circular list

Return value:

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

Note:These functions work only with sorted rings, regardless of sort order. To use them with regular rings they should be sorted first.

Check for equality

Cbool Ring_IsEqual (const struct Ring *ring, const struct Ring *source);
C++bool Ring::IsEqual (const Ring *source) const;

Description: Check if both rings have the same size, key order and key values, using provided key compare function. These functions do not compare assigned data fields, but only the keys.

Access type: RO

Parameters:

  • ring - pointer to target circular list
  • source - pointer to source circular list

Return value:

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

Ring properties

Ring built-in key type

Csize_t Ring_KeyType (const struct Ring *ring);
C++size_t Ring::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 ring.

Access type: RO

Parameters:

  • ring - pointer to the circular list

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.

Ring key compare function

CKeyCmp Ring_CompareFunction (const struct Ring *ring);
C++KeyCmp Ring::CompareFunction (void) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list

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

Ring pair copy function

CCopyFunc Ring_CopyFunction (const struct Ring *ring);
C++CopyFunc Ring::CopyFunction (void) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list

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

Ring pair delete function

CDelFunc Ring_DeleteFunction (const struct Ring *ring);
C++DelFunc Ring::DeleteFunction (void) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list

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

Ring user's data

Cvoid* Ring_UserData (const struct Ring *ring);
C++void* Ring::UserData (void) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list

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

Ring capacity

Csize_t Ring_Capacity (const struct Ring *ring);
C++size_t Ring::Capacity (void) const;

Description: Return the ring capacity.

Access type: RO

Parameters:

  • ring - pointer to the circular list

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

Ring size

Csize_t Ring_Size (const struct Ring *ring);
C++size_t Ring::Size (void) const;

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

Access type: RO

Parameters:

  • ring - pointer to the circular list

Return value: Count of allocated objects inside the ring.

Check if ring is empty

Cbool Ring_IsEmpty (const struct Ring *ring);
C++bool Ring::IsEmpty (void) const;

Description: Check if the ring is empty.

Access type: RO

Parameters:

  • ring - pointer to the circular list

Return value:

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

Check if ring is initialized

Cbool Ring_IsInit (const struct Ring *ring);
C++bool Ring::IsInit (void) const;

Description: Check if the ring is initialized.

Access type: RO

Parameters:

  • ring - pointer to the circular list

Return value:

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