Constructor

Cvoid Stack_InitStack (struct Stack *stack, size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

C++Stack::Stack (size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new stack instance.

Access type: RW

Parameters:

• stack - pointer to the stack
• capacity - initial count of elements that the stack can hold. Stack 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 Stack_CopyStack (struct Stack *stack, const struct Stack *source);

C++Stack::Stack (const Stack &source);

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

Access type: RW

Parameters:

• stack - pointer to target stack
• source - pointer to source stack

Return value: None.

Destructor

Cvoid Stack_FreeStack (struct Stack *stack);

C++Stack::~Stack (void);

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

Access type: RW

Parameters:

• stack - pointer to the stack

Return value: None.

Access predicates

Access predicates is an easy and efficient way to write multithreaded highly concurrent code. Stack functions may change container elements, add new values and remove the existing ones. This can result to data inconsistency among different threads. To solve this possible issue, you have to separate read and write operations to the stack. 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 stack. 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 stack 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 Stack_LockReadings (struct Stack *stack, bool wait);

C++bool Stack::LockReadings (bool wait);

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

Access type: RW

Parameters:

• stack - pointer to the stack
• wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

• TRUE (1) if you have exclusive access to the stack.
• 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 Stack_LockWritings (struct Stack *stack, bool wait);

C++bool Stack::LockWritings (bool wait);

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

Access type: RW

Parameters:

• stack - pointer to the stack
• wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

• TRUE (1) if you have read only access to the stack.
• FALSE (0) if the wait flag was not set and read only lock is not taken.

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

Releasing of exclusive lock

Cvoid Stack_AllowReadings (struct Stack *stack);

C++void Stack::AllowReadings (void);

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

Access type: RW

Parameters:

• stack - pointer to the stack

Return value: None.

Releasing of read only lock

Cvoid Stack_AllowWritings (struct Stack *stack);

C++void Stack::AllowWritings (void);

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

• stack - pointer to the stack

Return value: None.

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

Copying elements

Csize_t Stack_Copy (struct Stack *stack, size_t tpos, const struct Stack *source, size_t spos, size_t count);

C++size_t Stack::Copy (size_t tpos, const Stack *source, size_t spos, size_t count);

Description: Copy "count" elements from source stack into target stack. Source elements are iterated from top to bottom. Functions copy data starting from "spos" element after source stack top, until all "count" elements are inserted into target stack after "tpos" position. Source stack stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

• stack - pointer to target stack
• tpos - insert position from the top of target stack
• source - pointer to source stack
• spos - starting position from the top of source stack
• count - number of elements to copy (-1 means all available elements)

Return value:

• Real count of elements, which were copied from source stack.
• -1 if target stack was not able to extend its capacity for new elements, or starting position is greater than or equal to target/source stack size, or functions are called from read only section, started by LockWritings access predicate.

Moving elements

Csize_t Stack_Move (struct Stack *stack, size_t tpos, struct Stack *source, size_t spos, size_t count);

C++size_t Stack::Move (size_t tpos, Stack *source, size_t spos, size_t count);

Description: Move "count" elements from source stack into target stack. Source elements are iterated from top to bottom. Functions move data starting from "spos" element after source stack top, until all "count" elements are inserted into target stack after "tpos" position.

Access type: RW

Parameters:

• stack - pointer to target stack
• tpos - insert position from the top of target stack
• source - pointer to source stack
• spos - starting position from the top of source stack
• count - number of elements to move (-1 means all available elements)

Return value:

• Real count of elements, which were moved from source stack.
• -1 if target stack was not able to extend its capacity for new elements, or starting position is greater than or equal to target/source stack size, or functions are called from read only section, started by LockWritings access predicate.

Addition of element

Cbool Stack_Push (struct Stack *stack, const struct pair_t *data);

C++bool Stack::Push (const pair_t *data);

Description: Push new element on top of the the stack.

Access type: RW

Parameters:

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

Return value:

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

Removal of element

Cbool Stack_Pop (struct Stack *stack);

C++bool Stack::Pop (void);

Description: Pop top element from the stack.

Access type: RW

Parameters:

• stack - pointer to the stack

Return value:

• TRUE (1) if stack is not empty.
• FALSE (0) if stack is empty, or functions are called from read only section, started by LockWritings access predicate.

Insertion of element

Cbool Stack_Insert (struct Stack *stack, const struct pair_t *data, size_t pos);

C++bool Stack::Insert (const pair_t *data, size_t pos);

Description: Insert new element into the selected position from the stack top.

Access type: RW

Parameters:

• stack - pointer to the stack
• data - pointer to the new element
• pos - element position in the stack from its top

Return value:

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

Note:Position is calculated from the top of the stack. The top element has zero position.

Extraction of element

Cbool Stack_Extract (struct Stack *stack, size_t pos);

C++bool Stack::Extract (size_t pos);

Description: Delete the element in the selected position from the stack top.

Access type: RW

Parameters:

• stack - pointer to the stack
• pos - element position in the stack from its top

Return value:

• TRUE (1) if element position is less than the stack size.
• FALSE (0) if element position is incorrect, or functions are called from read only section, started by LockWritings access predicate.

Note:Position is calculated from the top of the stack. The top element has zero position.

Setting element value

Cbool Stack_Set (struct Stack *stack, const struct pair_t *data, size_t pos);

C++bool Stack::Set (const pair_t *data, size_t pos);

Description: Set value of the element in selected position from the top of the stack.

Access type: RW

Parameters:

• stack - pointer to the stack
• data - pointer to the new value of the element
• pos - element position in the stack from its top

Return value:

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

Note:Position is calculated from the top of the stack. The top element has zero position.

Getting element value

Cbool Stack_Get (const struct Stack *stack, struct pair_t *data, size_t pos);

C++bool Stack::Get (pair_t *data, size_t pos) const;

Description: Get value of the element in selected position from the top of the stack. The stack stay unchanged.

Access type: RO

Parameters:

• stack - pointer to the stack
• data - address where to return the value of the element
• pos - element position in the stack from its top

Return value:

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

Note:Position is calculated from the top of the stack. The top element has zero position.

Changing elements order

These functions allow to change elements order in the stack and swap the elements.

Reversing elements order

Csize_t Stack_Reverse (struct Stack *stack, size_t pos, size_t count);

C++size_t Stack::Reverse (size_t pos, size_t count);

Description: Reverse order of "count" elements in the stack starting from the "pos" position from the stack top, and store them in the same place in new order. Other elements are not modified.

Access type: RW

Parameters:

• stack - pointer to the stack
• pos - starting position from the top of the stack
• count - number of elements to reverse (-1 means all available elements)

Return value:

• Real count of elements, which were reversed.
• -1 if starting position is greater than or equal to the stack size, or functions are called from read only section, started by LockWritings access predicate.

Swapping elements

Cbool Stack_Swap (struct Stack *stack, size_t pos1, size_t pos2);

C++bool Stack::Swap (size_t pos1, size_t pos2);

Description: Swap selected elements from the stack top element.

Access type: RW

Parameters:

• stack - pointer to the stack
• pos1 - first element position in the stack from its top
• pos2 - second element position in the stack from its top

Return value:

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

Minimum and maximum value

Next functions scan "count" elements in the stack from top element to bottom element and from bottom element to top element, starting from "pos" position, and return position of the first/last element, which has minimum/maximum key value. Returned position is relative position from the stack top element, treating top element as element with zero index.

Minimum value

Csize_t Stack_MinFwd (const struct Stack *stack, struct pair_t *data, size_t pos, size_t count);
size_t Stack_MinBwd (const struct Stack *stack, struct pair_t *data, size_t pos, size_t count);

C++size_t Stack::MinFwd (pair_t *data, size_t pos, size_t count) const;
size_t Stack::MinBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return position of the first/last element, which has minimum value of the key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• stack - pointer to the stack
• data - address where to return the value of the found element
• pos - starting position from the top of the stack
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last element, having minimum value, in the stack, assuming that the top element has zero index.
• -1 if position is greater than or equal to the stack size.

Maximum value

Csize_t Stack_MaxFwd (const struct Stack *stack, struct pair_t *data, size_t pos, size_t count);
size_t Stack_MaxBwd (const struct Stack *stack, struct pair_t *data, size_t pos, size_t count);

C++size_t Stack::MaxFwd (pair_t *data, size_t pos, size_t count) const;
size_t Stack::MaxBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return position of the first/last element, which has maximum value of the key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• stack - pointer to the stack
• data - address where to return the value of the found element
• pos - starting position from the top of the stack
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last element, having maximum value, in the stack, assuming that the top element has zero index.
• -1 if position is greater than or equal to the stack size.

Key searching

Following functions scan "count" elements in the stack from top element to bottom element and from bottom element to top element, starting from "pos" position, and return position of the first/last element, which is equal to the specified key or to the set of keys. Returned position is relative position from the stack top element, treating top element as element with zero index. If beginning position is greater than or equal to stack size, then -1 is returned.

Single key searching

Csize_t Stack_FindKeyFwd (const struct Stack *stack, struct pair_t *data, union adt_t key, size_t pos, size_t count);
size_t Stack_FindKeyBwd (const struct Stack *stack, struct pair_t *data, union adt_t key, size_t pos, size_t count);

C++size_t Stack::FindKeyFwd (pair_t *data, adt_t key, size_t pos, size_t count) const;
size_t Stack::FindKeyBwd (pair_t *data, adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return position of the first/last element, which is equal to the specified key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• stack - pointer to the stack
• data - address where to return the value of the found element
• key - key value to find in the stack
• pos - starting position from the top of the stack
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last found element in the stack, assuming that the top element has zero index.
• -1 if no matches were met, or position is greater than or equal to the stack size.

Keys set searching

Csize_t Stack_FindKeysFwd (const struct Stack *stack, struct pair_t *data, const union adt_t keys[], size_t size, size_t pos, size_t count);
size_t Stack_FindKeysBwd (const struct Stack *stack, struct pair_t *data, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t Stack::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size, size_t pos, size_t count) const;
size_t Stack::FindKeysBwd (pair_t *data, const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return position of the first/last element, which is equal to any key in the set of keys, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• stack - pointer to the stack
• data - address where to return the value of the found element
• keys - array of keys to find in the stack
• size - size of array of keys
• pos - starting position from the top of the stack
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last found element in the stack, assuming that the top element has zero index.
• -1 if no matches were met, or position is greater than or equal to the stack size.

Searching for differences

Csize_t Stack_FindDiffFwd (const struct Stack *stack, struct pair_t *data, size_t tpos, const struct Stack *source, size_t spos, size_t count);
size_t Stack_FindDiffBwd (const struct Stack *stack, struct pair_t *data, size_t tpos, const struct Stack *source, size_t spos, size_t count);

C++size_t Stack::FindDiffFwd (pair_t *data, size_t tpos, const Stack *source, size_t spos, size_t count) const;
size_t Stack::FindDiffBwd (pair_t *data, size_t tpos, const Stack *source, size_t spos, size_t count) const;

Description: Compare "count" elements of two stack objects (key by key) from top element to bottom element and from bottom element to top element, then return position and value of the first/last non equal element in target stack. Target stack is scanned from "tpos" position after its top. And source stack is scanned from "spos" position after its top. These functions do not compare assigned data fields, but only the keys. If no different keys were found during "count" elements, then functions return -1 and do not change data structure, which is pointed by "data" pointer.

Access type: RO

Parameters:

• stack - pointer to target stack
• data - address where to return the value of non equal element
• tpos - starting position from the top of target stack
• source - pointer to source stack
• spos - starting position from the top of source stack
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last non equal element in target stack, assuming that the top element has zero index.
• -1 if no different keys were found during "count" elements, or position is greater than or equal to target/source stack size.

Key counting

Following functions scan "count" elements in the stack from top element to bottom element and from bottom element to top element, starting from "pos" position, and return count of matches to the key or to the set of keys.

Single key counting

Csize_t Stack_CountKeyFwd (const struct Stack *stack, union adt_t key, size_t pos, size_t count);
size_t Stack_CountKeyBwd (const struct Stack *stack, union adt_t key, size_t pos, size_t count);

C++size_t Stack::CountKeyFwd (adt_t key, size_t pos, size_t count) const;
size_t Stack::CountKeyBwd (adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

• stack - pointer to the stack
• key - key value to find in the stack
• pos - starting position from the top of the stack
• count - number of elements to check (-1 means all available elements)

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

Keys set counting

Csize_t Stack_CountKeysFwd (const struct Stack *stack, const union adt_t keys[], size_t size, size_t pos, size_t count);
size_t Stack_CountKeysBwd (const struct Stack *stack, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t Stack::CountKeysFwd (const adt_t keys[], size_t size, size_t pos, size_t count) const;
size_t Stack::CountKeysBwd (const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the stack from top/bottom element to bottom/top element, starting from "pos" position. Then return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

• stack - pointer to the stack
• keys - array of keys to find in the stack
• size - size of array of keys
• pos - starting position from the top of the stack
• 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.

Comparison of stacks

Csint64_t Stack_Compare (const struct Stack *stack, const struct Stack *source);

C++sint64_t Stack::Compare (const Stack *source) const;

Description: Compare two stack objects (key by key) starting from top element to bottom element, 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:

• stack - pointer to target stack
• source - pointer to source stack

Return value:

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

Check for equality

Cbool Stack_IsEqual (const struct Stack *stack, const struct Stack *source);

C++bool Stack::IsEqual (const Stack *source) const;

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

Access type: RO

Parameters:

• stack - pointer to target stack
• source - pointer to source stack

Return value:

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

Stack properties

Stack built-in key type

Csize_t Stack_KeyType (const struct Stack *stack);

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

Access type: RO

Parameters:

• stack - pointer to the stack

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.

Stack key compare function

CKeyCmp Stack_CompareFunction (const struct Stack *stack);

C++KeyCmp Stack::CompareFunction (void) const;

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

Access type: RO

Parameters:

• stack - pointer to the stack

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

Stack pair copy function

CCopyFunc Stack_CopyFunction (const struct Stack *stack);

C++CopyFunc Stack::CopyFunction (void) const;

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

Access type: RO

Parameters:

• stack - pointer to the stack

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

Stack pair delete function

CDelFunc Stack_DeleteFunction (const struct Stack *stack);

C++DelFunc Stack::DeleteFunction (void) const;

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

Access type: RO

Parameters:

• stack - pointer to the stack

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

Stack user's data

Cvoid* Stack_UserData (const struct Stack *stack);

C++void* Stack::UserData (void) const;

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

Access type: RO

Parameters:

• stack - pointer to the stack

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

Stack capacity

Csize_t Stack_Capacity (const struct Stack *stack);

C++size_t Stack::Capacity (void) const;

Description: Return the stack capacity.

Access type: RO

Parameters:

• stack - pointer to the stack

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

Stack size

Csize_t Stack_Size (const struct Stack *stack);

C++size_t Stack::Size (void) const;

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

Access type: RO

Parameters:

• stack - pointer to the stack

Return value: Count of allocated objects inside the stack.

Check if stack is empty

Cbool Stack_IsEmpty (const struct Stack *stack);

C++bool Stack::IsEmpty (void) const;

Description: Check if the stack is empty.

Access type: RO

Parameters:

• stack - pointer to the stack

Return value:

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

Check if stack is initialized

Cbool Stack_IsInit (const struct Stack *stack);

C++bool Stack::IsInit (void) const;

Description: Check if the stack is initialized.

Access type: RO

Parameters:

• stack - pointer to the stack

Return value:

• TRUE (1) if stack is initialized.
• FALSE (0) if stack is not initialized.