Linux Assemblycollection of fast libraries

List ADTList.h

Doubly linked list is a linked data structure that consists of a set of sequentially 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. 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 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) ListRW
AllowWritingsRW(copy constructor) ListRW
BwdGoNextRW(destructor) ~ListRW
BwdGoPrevRWAllowReadingsRW
BwdToFwdRWAllowWritingsRW
BwdToHeadRWBwdGoNextRW
BwdToIndexRWBwdGoPrevRW
BwdToTailRWBwdToFwdRW
CapacityROBwdToHeadRW
CheckDupROBwdToIndexRW
CheckSortAscROBwdToTailRW
CheckSortDscROCapacityRO
CompareROCheckDupRO
CompareFunctionROCheckSortAscRO
CopyAfterBwdRWCheckSortDscRO
CopyAfterFwdRWCompareRO
CopyBeforeBwdRWCompareFunctionRO
CopyBeforeFwdRWCopyAfterBwdRW
CopyFunctionROCopyAfterFwdRW
CopyIntoHeadRWCopyBeforeBwdRW
CopyIntoTailRWCopyBeforeFwdRW
CopyListRWCopyFunctionRO
CountKeyBwdROCopyIntoHeadRW
CountKeyFwdROCopyIntoTailRW
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
FreeListRWFindNonDscIterBwdRO
FwdGoNextRWFindNonDscIterFwdRO
FwdGoPrevRWFwdGoNextRW
FwdToBwdRWFwdGoPrevRW
FwdToHeadRWFwdToBwdRW
FwdToIndexRWFwdToHeadRW
FwdToTailRWFwdToIndexRW
GetBwdROFwdToTailRW
GetBwdPosROGetBwdRO
GetFwdROGetBwdPosRO
GetFwdPosROGetFwdRO
GetHeadROGetFwdPosRO
GetIterROGetHeadRO
GetIterPosROGetIterRO
GetTailROGetIterPosRO
InitListRWGetTailRO
InsertAfterBwdRWInsertAfterBwdRW
InsertAfterFwdRWInsertAfterFwdRW
InsertBeforeBwdRWInsertBeforeBwdRW
InsertBeforeFwdRWInsertBeforeFwdRW
InsertIntoHeadRWInsertIntoHeadRW
InsertIntoTailRWInsertIntoTailRW
IsEmptyROIsEmptyRO
IsEqualROIsEqualRO
IsInitROIsInitRO
IterGoBwdROIterGoBwdRO
IterGoFwdROIterGoFwdRO
IterToBwdROIterToBwdRO
IterToFwdROIterToFwdRO
IterToHeadROIterToHeadRO
IterToIndexROIterToIndexRO
IterToTailROIterToTailRO
KeyTypeROKeyTypeRO
LockReadingsRWLockReadingsRW
LockWritingsRWLockWritingsRW
MaxBwdRWMaxBwdRW
MaxFwdRWMaxFwdRW
MaxIterBwdROMaxIterBwdRO
MaxIterFwdROMaxIterFwdRO
MergeAscRWMergeAscRW
MergeDscRWMergeDscRW
MinBwdRWMinBwdRW
MinFwdRWMinFwdRW
MinIterBwdROMinIterBwdRO
MinIterFwdROMinIterFwdRO
MoveAfterBwdRWMoveAfterBwdRW
MoveAfterFwdRWMoveAfterFwdRW
MoveBeforeBwdRWMoveBeforeBwdRW
MoveBeforeFwdRWMoveBeforeFwdRW
MoveIntoHeadRWMoveIntoHeadRW
MoveIntoTailRWMoveIntoTailRW
RemoveBwdRWRemoveBwdRW
RemoveFwdRWRemoveFwdRW
RemoveHeadRWRemoveHeadRW
RemoveTailRWRemoveTailRW
ReverseBwdRWReverseBwdRW
ReverseFwdRWReverseFwdRW
ReverseHeadRWReverseHeadRW
ReverseTailRWReverseTailRW
SetBwdRWSetBwdRW
SetFwdRWSetFwdRW
SetHeadRWSetHeadRW
SetTailRWSetTailRW
SizeROSizeRO
SortAscRWSortAscRW
SortDscRWSortDscRW
SwapRWSwapRW
SwapFwdBwdRWSwapFwdBwdRW
UniqueRWUniqueRW
UserDataROUserDataRO
C function nameAccess typeC++ function nameAccess type

Constructor

Cvoid List_InitList (struct List *list, size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);
C++List::List (size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new list instance.

Access type: RW

Parameters:

  • list - pointer to the list
  • capacity - initial count of elements that the list can hold. List 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 List_CopyList (struct List *list, const struct List *source);
C++List::List (const List &source);

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

Access type: RW

Parameters:

  • list - pointer to target list
  • source - pointer to source list

Return value: None.

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

Destructor

Cvoid List_FreeList (struct List *list);
C++List::~List (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

Access predicates

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

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

Access type: RW

Parameters:

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

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

Access type: RW

Parameters:

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

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

Releasing of exclusive lock

Cvoid List_AllowReadings (struct List *list);
C++void List::AllowReadings (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

Releasing of read only lock

Cvoid List_AllowWritings (struct List *list);
C++void List::AllowWritings (void);

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

  • list - pointer to the list

Return value: None.

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

Copying elements

Into list head

Csize_t List_CopyIntoHead (struct List *list, const struct List *source, size_t count);
C++size_t List::CopyIntoHead (const List *source, size_t count);

Description: Copy "count" elements, from source list into head of target list. Functions copy data, starting from current position of backward iterator of source list in negative direction (from last to first element), until all "count" elements are copied into target list. Source list stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were copied from source list.
  • -1 if target list 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.

Into list tail

Csize_t List_CopyIntoTail (struct List *list, const struct List *source, size_t count);
C++size_t List::CopyIntoTail (const List *source, size_t count);

Description: Copy "count" elements, from source list into tail of target list. Functions copy data, starting from current position of forward iterator of source list in positive direction (from first to last element), until all "count" elements are copied into target list. Source list stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were copied from source list.
  • -1 if target list 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 List_CopyAfterFwd (struct List *list, const struct List *source, size_t count);
size_t List_CopyBeforeFwd (struct List *list, const struct List *source, size_t count);
C++size_t List::CopyAfterFwd (const List *source, size_t count);
size_t List::CopyBeforeFwd (const List *source, size_t count);

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

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were copied from source list.
  • -1 if target list 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 List_CopyAfterBwd (struct List *list, const struct List *source, size_t count);
size_t List_CopyBeforeBwd (struct List *list, const struct List *source, size_t count);
C++size_t List::CopyAfterBwd (const List *source, size_t count);
size_t List::CopyBeforeBwd (const List *source, size_t count);

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

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were copied from source list.
  • -1 if target list 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

Into list head

Csize_t List_MoveIntoHead (struct List *list, struct List *source, size_t count);
C++size_t List::MoveIntoHead (List *source, size_t count);

Description: Move "count" elements, from source list into head of target list. Functions move data, starting from current position of backward iterator of source list in negative direction (from last to first element), until all "count" elements are moved into target list.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were moved from source list.
  • -1 if target list 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.

Into list tail

Csize_t List_MoveIntoTail (struct List *list, struct List *source, size_t count);
C++size_t List::MoveIntoTail (List *source, size_t count);

Description: Move "count" elements, from source list into tail of target list. Functions move data, starting from current position of forward iterator of source list in positive direction (from first to last element), until all "count" elements are moved into target list.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were moved from source list.
  • -1 if target list 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 List_MoveAfterFwd (struct List *list, struct List *source, size_t count);
size_t List_MoveBeforeFwd (struct List *list, struct List *source, size_t count);
C++size_t List::MoveAfterFwd (List *source, size_t count);
size_t List::MoveBeforeFwd (List *source, size_t count);

Description: Move "count" elements, from source list into target list after/before position of forward iterator. Functions move data, starting from current position of forward iterator of source list in positive direction (from first to last element), until all "count" elements are moved into target list.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were moved from source list.
  • -1 if target list 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 List_MoveAfterBwd (struct List *list, struct List *source, size_t count);
size_t List_MoveBeforeBwd (struct List *list, struct List *source, size_t count);
C++size_t List::MoveAfterBwd (List *source, size_t count);
size_t List::MoveBeforeBwd (List *source, size_t count);

Description: Move "count" elements, from source list into target list after/before position of backward iterator. Functions move data, starting from current position of backward iterator of source list in negative direction (from last to first element), until all "count" elements are moved into target list.

Access type: RW

Parameters:

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

Return value:

  • Real count of elements, which were moved from source list.
  • -1 if target list 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

Into list head

Cbool List_InsertIntoHead (struct List *list, const struct pair_t *data);
C++bool List::InsertIntoHead (const pair_t *data);

Description: Insert new element into the list head.

Access type: RW

Parameters:

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

Return value:

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

Into list tail

Cbool List_InsertIntoTail (struct List *list, const struct pair_t *data);
C++bool List::InsertIntoTail (const pair_t *data);

Description: Insert new element into the list tail.

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if element was successfully inserted into the list.
  • FALSE (0) if the list 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 List_InsertAfterFwd (struct List *list, const struct pair_t *data);
bool List_InsertBeforeFwd (struct List *list, const struct pair_t *data);
C++bool List::InsertAfterFwd (const pair_t *data);
bool List::InsertBeforeFwd (const pair_t *data);

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

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if element was successfully inserted into the list.
  • FALSE (0) if the list 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 List_InsertAfterBwd (struct List *list, const struct pair_t *data);
bool List_InsertBeforeBwd (struct List *list, const struct pair_t *data);
C++bool List::InsertAfterBwd (const pair_t *data);
bool List::InsertBeforeBwd (const pair_t *data);

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

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if element was successfully inserted into the list.
  • FALSE (0) if the list 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 List_RemoveHead (struct List *list);
bool List_RemoveTail (struct List *list);
bool List_RemoveFwd (struct List *list);
bool List_RemoveBwd (struct List *list);
C++bool List::RemoveHead (void);
bool List::RemoveTail (void);
bool List::RemoveFwd (void);
bool List::RemoveBwd (void);

Description: Remove element, which is pointed by head/tail/forward/backward iterator.

Access type: RW

Parameters:

  • list - pointer to the list

Return value:

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

Setting element value

Cbool List_SetHead (struct List *list, const struct pair_t *data);
bool List_SetTail (struct List *list, const struct pair_t *data);
bool List_SetFwd (struct List *list, const struct pair_t *data);
bool List_SetBwd (struct List *list, const struct pair_t *data);
C++bool List::SetHead (const pair_t *data);
bool List::SetTail (const pair_t *data);
bool List::SetFwd (const pair_t *data);
bool List::SetBwd (const pair_t *data);

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

Access type: RW

Parameters:

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

Return value:

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

Getting element value

Cbool List_GetHead (const struct List *list, struct pair_t *data);
bool List_GetTail (const struct List *list, struct pair_t *data);
bool List_GetFwd (const struct List *list, struct pair_t *data);
bool List_GetBwd (const struct List *list, struct pair_t *data);
C++bool List::GetHead (pair_t *data) const;
bool List::GetTail (pair_t *data) const;
bool List::GetFwd (pair_t *data) const;
bool List::GetBwd (pair_t *data) const;

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

Access type: RO

Parameters:

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

Return value:

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

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

Access type: RO

Parameters:

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

Return value:

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

Changing elements order

Reversing elements order

Csize_t List_ReverseHead (struct List *list, size_t count);
size_t List_ReverseTail (struct List *list, size_t count);
size_t List_ReverseFwd (struct List *list, size_t count);
size_t List_ReverseBwd (struct List *list, size_t count);
C++size_t List::ReverseHead (size_t count);
size_t List::ReverseTail (size_t count);
size_t List::ReverseFwd (size_t count);
size_t List::ReverseBwd (size_t count);

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

Access type: RW

Parameters:

  • list - pointer to the 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 List_Swap (struct List *list);
C++bool List::Swap (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value:

  • TRUE (1) if both iterators point to list 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 list 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 list 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 list 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 list.

Set iterator position

These functions set iterator position to head, to tail or to any list element by its index or by the value of another iterator. List elements are treated as ordered array of keys, starting from head element, which has zero index, to tail element (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 List_FwdToIndex (struct List *list, size_t index);
C++void List::FwdToIndex (size_t index);

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

Access type: RW

Parameters:

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

Return value: None.

To head element

Cvoid List_FwdToHead (struct List *list);
C++void List::FwdToHead (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

To tail element

Cvoid List_FwdToTail (struct List *list);
C++void List::FwdToTail (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

To backward iterator

Cvoid List_FwdToBwd (struct List *list);
C++void List::FwdToBwd (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

Get iterator position

Csize_t List_GetFwdPos (const struct List *list);
C++size_t List::GetFwdPos (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the 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 list elements and get neighbor elements for current element.

Move to next position

Cbool List_FwdGoNext (struct List *list, size_t pos);
C++bool List::FwdGoNext (size_t pos);

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

Access type: RW

Parameters:

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

Return value:

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

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

Access type: RW

Parameters:

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

Return value:

  • TRUE (1) if iterator points to any list 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 list 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 list 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 list 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 list.

Set iterator position

These functions set iterator position to head, to tail or to any list element by its index or by the value of another iterator. List elements are treated as ordered array of keys, starting from head element, which has zero index, to tail element (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 List_BwdToIndex (struct List *list, size_t index);
C++void List::BwdToIndex (size_t index);

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

Access type: RW

Parameters:

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

Return value: None.

To head element

Cvoid List_BwdToHead (struct List *list);
C++void List::BwdToHead (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

To tail element

Cvoid List_BwdToTail (struct List *list);
C++void List::BwdToTail (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

To forward iterator

Cvoid List_BwdToFwd (struct List *list);
C++void List::BwdToFwd (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

Get iterator position

Csize_t List_GetBwdPos (const struct List *list);
C++size_t List::GetBwdPos (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the 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 list elements and get neighbor elements for current element.

Move to next position

Cbool List_BwdGoNext (struct List *list, size_t pos);
C++bool List::BwdGoNext (size_t pos);

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

Access type: RW

Parameters:

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

Return value:

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

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

Access type: RW

Parameters:

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

Return value:

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

Set iterator position

These functions set external iterator position to head (first), to tail (last) or to any list element by its index or by the value of another iterator. List elements are treated as ordered array of keys, starting from head element, which has zero index, to tail element (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 list structure or keys.

By index

Cptr_t List_IterToIndex (const struct List *list, size_t index);
C++ptr_t List::IterToIndex (size_t index) const;

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

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

To head element

Cptr_t List_IterToHead (const struct List *list);
C++ptr_t List::IterToHead (void) const;

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

  • list - pointer to the list

Return value:

  • Head iterator value.
  • Negative value if list is empty.

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

To tail element

Cptr_t List_IterToTail (const struct List *list);
C++ptr_t List::IterToTail (void) const;

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

  • list - pointer to the list

Return value:

  • Tail iterator value.
  • Negative value if list is empty.

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

To forward iterator

Cptr_t List_IterToFwd (const struct List *list);
C++ptr_t List::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:

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

To backward iterator

Cptr_t List_IterToBwd (const struct List *list);
C++ptr_t List::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:

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

Get iterator position

Csize_t List_GetIterPos (const struct List *list, ptr_t iter);
C++size_t List::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:

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

Move in forward direction

Cbool List_IterGoFwd (const struct List *list, size_t pos, ptr_t *iter);
C++bool List::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:

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

Return value:

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

Move in backward direction

Cbool List_IterGoBwd (const struct List *list, size_t pos, ptr_t *iter);
C++bool List::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:

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

Return value:

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

Swapping iterators

Cvoid List_SwapFwdBwd (struct List *list);
C++void List::SwapFwdBwd (void);

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

Access type: RW

Parameters:

  • list - pointer to the list

Return value: None.

Minimum and maximum value

Minimum value

Cbool List_MinFwd (struct List *list, struct pair_t *data, size_t count);
bool List_MinBwd (struct List *list, struct pair_t *data, size_t count);
C++bool List::MinFwd (pair_t *data, size_t count);
bool List::MinBwd (pair_t *data, size_t count);

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

  • list - pointer to the 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 list is empty, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool List_MinIterFwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
bool List_MinIterBwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
C++bool List::MinIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool List::MinIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

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

  • list - pointer to the 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 list element

Return value:

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

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

Maximum value

Cbool List_MaxFwd (struct List *list, struct pair_t *data, size_t count);
bool List_MaxBwd (struct List *list, struct pair_t *data, size_t count);
C++bool List::MaxFwd (pair_t *data, size_t count);
bool List::MaxBwd (pair_t *data, size_t count);

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

  • list - pointer to the 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 list is empty, or iterator is not set, or functions are called from read only section, started by LockWritings access predicate.
Cbool List_MaxIterFwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
bool List_MaxIterBwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
C++bool List::MaxIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool List::MaxIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

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

  • list - pointer to the 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 list element

Return value:

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

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

Key searching

Following functions check list 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 List_FindKeyFwd (struct List *list, struct pair_t *data, union adt_t key, size_t count);
bool List_FindKeyBwd (struct List *list, struct pair_t *data, union adt_t key, size_t count);
C++bool List::FindKeyFwd (pair_t *data, adt_t key, size_t count);
bool List::FindKeyBwd (pair_t *data, adt_t key, size_t count);

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

  • list - pointer to the 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 list.
  • FALSE (0) if the iterator is not set, or the list has no keys, which satisfy the search condition, or functions are called from read only section, started by LockWritings access predicate.
Cbool List_FindKeyIterFwd (const struct List *list, struct pair_t *data, union adt_t key, size_t count, ptr_t *iter);
bool List_FindKeyIterBwd (const struct List *list, struct pair_t *data, union adt_t key, size_t count, ptr_t *iter);
C++bool List::FindKeyIterFwd (pair_t *data, adt_t key, size_t count, ptr_t *iter) const;
bool List::FindKeyIterBwd (pair_t *data, adt_t key, size_t count, ptr_t *iter) const;

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

  • list - pointer to the 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 list element

Return value:

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

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

Keys set searching

Cbool List_FindKeysFwd (struct List *list, struct pair_t *data, const union adt_t keys[], size_t size, size_t count);
bool List_FindKeysBwd (struct List *list, struct pair_t *data, const union adt_t keys[], size_t size, size_t count);
C++bool List::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size, size_t count);
bool List::FindKeysBwd (pair_t *data, const adt_t keys[], size_t size, size_t count);

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

  • list - pointer to the list
  • data - address where to return the value of the found element
  • keys - array of keys to find in the 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 list.
  • FALSE (0) if the iterator is not set, or the list has no keys, which satisfy the search condition, or functions are called from read only section, started by LockWritings access predicate.
Cbool List_FindKeysIterFwd (const struct List *list, struct pair_t *data, const union adt_t keys[], size_t size, size_t count, ptr_t *iter);
bool List_FindKeysIterBwd (const struct List *list, struct pair_t *data, const union adt_t keys[], size_t size, size_t count, ptr_t *iter);
C++bool List::FindKeysIterFwd (pair_t *data, const adt_t keys[], size_t size, size_t count, ptr_t *iter) const;
bool List::FindKeysIterBwd (pair_t *data, const adt_t keys[], size_t size, size_t count, ptr_t *iter) const;

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

  • list - pointer to the list
  • data - address where to return the value of the found element
  • keys - array of keys to find in the 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 list element

Return value:

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

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

Duplicates searching

Cbool List_FindDupFwd (struct List *list, struct pair_t *data, size_t count);
bool List_FindDupBwd (struct List *list, struct pair_t *data, size_t count);
C++bool List::FindDupFwd (pair_t *data, size_t count);
bool List::FindDupBwd (pair_t *data, size_t count);

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

  • list - pointer to target 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 lists, regardless of sort order. To use them with regular lists they should be sorted first.

Cbool List_FindDupIterFwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
bool List_FindDupIterBwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
C++bool List::FindDupIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool List::FindDupIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

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

  • list - pointer to target 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 list 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 lists, regardless of sort order. To use them with regular lists they should be sorted first.

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

Unordered elements searching

Following functions check lists 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 List_FindNonAscFwd (struct List *list, struct pair_t *data, size_t count);
bool List_FindNonAscBwd (struct List *list, struct pair_t *data, size_t count);
C++bool List::FindNonAscFwd (pair_t *data, size_t count);
bool List::FindNonAscBwd (pair_t *data, size_t count);

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

  • list - pointer to target 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 List_FindNonAscIterFwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
bool List_FindNonAscIterBwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
C++bool List::FindNonAscIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool List::FindNonAscIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

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

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

Descending sort order

Cbool List_FindNonDscFwd (struct List *list, struct pair_t *data, size_t count);
bool List_FindNonDscBwd (struct List *list, struct pair_t *data, size_t count);
C++bool List::FindNonDscFwd (pair_t *data, size_t count);
bool List::FindNonDscBwd (pair_t *data, size_t count);

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

  • list - pointer to target 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 List_FindNonDscIterFwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
bool List_FindNonDscIterBwd (const struct List *list, struct pair_t *data, size_t count, ptr_t *iter);
C++bool List::FindNonDscIterFwd (pair_t *data, size_t count, ptr_t *iter) const;
bool List::FindNonDscIterBwd (pair_t *data, size_t count, ptr_t *iter) const;

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

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

Searching for differences

Cbool List_FindDiffFwd (struct List *list, struct pair_t *data, const struct List *source, size_t count);
bool List_FindDiffBwd (struct List *list, struct pair_t *data, const struct List *source, size_t count);
C++bool List::FindDiffFwd (pair_t *data, const List *source, size_t count);
bool List::FindDiffBwd (pair_t *data, const List *source, size_t count);

Description: Compare "count" elements of two list 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 list, 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 list is always accessed in read only mode.

Access type: RW

Parameters:

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

Description: Compare "count" elements of two list 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 list, 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:

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

Return value:

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

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

Key counting

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

Single key counting

Csize_t List_CountKeyFwd (const struct List *list, union adt_t key, size_t count);
size_t List_CountKeyBwd (const struct List *list, union adt_t key, size_t count);
C++size_t List::CountKeyFwd (adt_t key, size_t count) const;
size_t List::CountKeyBwd (adt_t key, size_t count) const;

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

  • list - pointer to the list
  • key - key value to find in the 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 List_CountKeyIterFwd (const struct List *list, union adt_t key, size_t count, ptr_t iter);
size_t List_CountKeyIterBwd (const struct List *list, union adt_t key, size_t count, ptr_t iter);
C++size_t List::CountKeyIterFwd (adt_t key, size_t count, ptr_t iter) const;
size_t List::CountKeyIterBwd (adt_t key, size_t count, ptr_t iter) const;

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

  • list - pointer to the list
  • key - key value to find in the list
  • count - number of elements to check (-1 means all available elements)
  • iter - value of external iterator, which is used to point to list 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 list elements. They don't change any object parameters.

Keys set counting

Csize_t List_CountKeysFwd (const struct List *list, const union adt_t keys[], size_t size, size_t count);
size_t List_CountKeysBwd (const struct List *list, const union adt_t keys[], size_t size, size_t count);
C++size_t List::CountKeysFwd (const adt_t keys[], size_t size, size_t count) const;
size_t List::CountKeysBwd (const adt_t keys[], size_t size, size_t count) const;

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

  • list - pointer to the list
  • keys - array of keys to find in the 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 List_CountKeysIterFwd (const struct List *list, const union adt_t keys[], size_t size, size_t count, ptr_t iter);
size_t List_CountKeysIterBwd (const struct List *list, const union adt_t keys[], size_t size, size_t count, ptr_t iter);
C++size_t List::CountKeysIterFwd (const adt_t keys[], size_t size, size_t count, ptr_t iter) const;
size_t List::CountKeysIterBwd (const adt_t keys[], size_t size, size_t count, ptr_t iter) const;

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

  • list - pointer to the list
  • keys - array of keys to find in the 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 list elements. They don't change any object parameters.

Sorting

Sort functions reorder list elements in ascending or descending sort order. They also invalidate forward and backward iterators, but do not touch head and tail iterators. Sorting functions check only the key field of elements but do not check the assigned data. To compare list 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 List_SortAsc (struct List *list);
C++size_t List::SortAsc (void);

Description: Sort list in ascending order.

Access type: RW

Parameters:

  • list - pointer to the 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 List_SortDsc (struct List *list);
C++size_t List::SortDsc (void);

Description: Sort list in descending order.

Access type: RW

Parameters:

  • list - pointer to the 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 lists

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

Ascending sort order

Csize_t List_MergeAsc (struct List *list, struct List *source);
C++size_t List::MergeAsc (List *source);

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

Access type: RW

Parameters:

  • list - pointer to target list
  • source - pointer to source list

Return value:

  • Count of the elements, which were copied from source list.
  • -1 if merge functions were not able to extend capacity of the list 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 list into target list.

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

Descending sort order

Csize_t List_MergeDsc (struct List *list, struct List *source);
C++size_t List::MergeDsc (List *source);

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

Access type: RW

Parameters:

  • list - pointer to target list
  • source - pointer to source list

Return value:

  • Count of the elements, which were copied from source list.
  • -1 if merge functions were not able to extend capacity of the list 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 list into target list.

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

Unique values

Csize_t List_Unique (struct List *list, const struct List *source);
C++size_t List::Unique (const List *source);

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

Access type: RW

Parameters:

  • list - pointer to target list
  • source - pointer to source list

Return value:

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

Warning:Unique functions do not make deep copy of keys from source list, but use only reference to original objects from source list. Do not delete objects from source list 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 lists, regardless of sort order. To use them with regular lists they should be sorted first.

Comparison of lists

Csint64_t List_Compare (const struct List *list, const struct List *source);
C++sint64_t List::Compare (const List *source) const;

Description: Compare two list 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:

  • list - pointer to target list
  • source - pointer to source list

Return value:

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

Checks

Check for sort order

Following functions check lists 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 List_CheckSortAsc (const struct List *list);
C++bool List::CheckSortAsc (void) const;

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

Access type: RO

Parameters:

  • list - pointer to target 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 List_CheckSortDsc (const struct List *list);
C++bool List::CheckSortDsc (void) const;

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

Access type: RO

Parameters:

  • list - pointer to target 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 List_CheckDup (const struct List *list);
C++bool List::CheckDup (void) const;

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

Access type: RO

Parameters:

  • list - pointer to target list

Return value:

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

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

Check for equality

Cbool List_IsEqual (const struct List *list, const struct List *source);
C++bool List::IsEqual (const List *source) const;

Description: Check if both lists 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:

  • list - pointer to target list
  • source - pointer to source list

Return value:

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

List properties

List built-in key type

Csize_t List_KeyType (const struct List *list);
C++size_t List::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 list.

Access type: RO

Parameters:

  • list - pointer to the 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.

List key compare function

CKeyCmp List_CompareFunction (const struct List *list);
C++KeyCmp List::CompareFunction (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the list

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

List pair copy function

CCopyFunc List_CopyFunction (const struct List *list);
C++CopyFunc List::CopyFunction (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the list

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

List pair delete function

CDelFunc List_DeleteFunction (const struct List *list);
C++DelFunc List::DeleteFunction (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the list

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

List user's data

Cvoid* List_UserData (const struct List *list);
C++void* List::UserData (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the list

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

List capacity

Csize_t List_Capacity (const struct List *list);
C++size_t List::Capacity (void) const;

Description: Return the list capacity.

Access type: RO

Parameters:

  • list - pointer to the list

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

List size

Csize_t List_Size (const struct List *list);
C++size_t List::Size (void) const;

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

Access type: RO

Parameters:

  • list - pointer to the list

Return value: Count of allocated objects inside the list.

Check if list is empty

Cbool List_IsEmpty (const struct List *list);
C++bool List::IsEmpty (void) const;

Description: Check if the list is empty.

Access type: RO

Parameters:

  • list - pointer to the list

Return value:

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

Check if list is initialized

Cbool List_IsInit (const struct List *list);
C++bool List::IsInit (void) const;

Description: Check if the list is initialized.

Access type: RO

Parameters:

  • list - pointer to the list

Return value:

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