Constructor

Cvoid MinHeap_InitMinHeap (struct MinHeap *heap, size_t capacity, KeyCmp kfunc, HeapIndex ifunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);

C++MinHeap::MinHeap (size_t capacity, KeyCmp kfunc, HeapIndex ifunc, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new heap instance.

Access type: RW

Parameters:

• heap - pointer to the heap
• capacity - initial count of elements that the heap can hold. Heap capacity is auto extended if required.
• kfunc - pointer to key compare function to sort elements in the heap. Compare function should follow this prototype.
• ifunc - pointer to heap index call back function. Call back function should follow this prototype.
• cfunc - pointer to copy function for element fields: key and data, or NULL. Copy function should follow this prototype.
• dfunc - pointer to delete function to call for removing elements, or NULL. Delete function should follow this prototype.
• ptr - pointer to user's data, required by element copy and delete functions, or NULL.

Return value: None.

Copy constructor

Cvoid MinHeap_CopyMinHeap (struct MinHeap *heap, const struct MinHeap *source);

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

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

Access type: RW

Parameters:

• heap - pointer to target heap
• source - pointer to source heap

Return value: None.

Destructor

Cvoid MinHeap_FreeMinHeap (struct MinHeap *heap);

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

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

Access type: RW

Parameters:

• heap - pointer to the heap

Return value: None.

Access predicates

Access predicates is an easy and efficient way to write multithreaded highly concurrent code. Heap 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 heap. 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 heap. 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 heap 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 MinHeap_LockReadings (struct MinHeap *heap, bool wait);

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

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

Access type: RW

Parameters:

• heap - pointer to the heap
• 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 heap.
• 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 MinHeap_LockWritings (struct MinHeap *heap, bool wait);

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

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

Access type: RW

Parameters:

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

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

Releasing of exclusive lock

Cvoid MinHeap_AllowReadings (struct MinHeap *heap);

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

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

Access type: RW

Parameters:

• heap - pointer to the heap

Return value: None.

Releasing of read only lock

Cvoid MinHeap_AllowWritings (struct MinHeap *heap);

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

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

• heap - pointer to the heap

Return value: None.

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

Addition of element

Cbool MinHeap_Push (struct MinHeap *heap, const struct pair_t *data);

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

Description: Push new element into the heap.

Access type: RW

Parameters:

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

Return value:

• TRUE (1) if element was successfully inserted into the heap.
• FALSE (0) if the heap 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 MinHeap_Pop (struct MinHeap *heap);

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

Description: Pop min element from the top of the heap.

Access type: RW

Parameters:

• heap - pointer to the heap

Return value:

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

Extraction of element

Cbool MinHeap_Extract (struct MinHeap *heap, size_t pos);

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

Description: Delete element in the selected position in the heap.

Access type: RW

Parameters:

• heap - pointer to the heap
• pos - element position in the heap

Return value:

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

Note:The "pos" value is raw position in the heap, treating top element as element with zero index, and iterating bottom elements from left to right, row by row.

Setting element value

Cbool MinHeap_Set (struct MinHeap *heap, const struct pair_t *data, size_t pos);

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

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

Access type: RW

Parameters:

• heap - pointer to the heap
• data - pointer to the new value of the element
• pos - element position in the heap

Return value:

• TRUE (1) if element position is less than the heap 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:The "pos" value is raw position in the heap, treating top element as element with zero index, and iterating bottom elements from left to right, row by row.

Getting element value

Cbool MinHeap_Get (const struct MinHeap *heap, struct pair_t *data, size_t pos);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap
• data - address where to return the value of the element
• pos - element position in the heap

Return value:

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

Note:The "pos" value is raw position in the heap, treating top element as element with zero index, and iterating bottom elements from left to right, row by row.

Key searching

Following functions scan the heap from the top element to the least right bottom element, doing it row by row, and return position of the first element, which is equal to the specified key or to the set of keys. These functions do not change the heap elements, or heap order. Returned position is not ordered element position, but raw position in the heap, treating top element as element with zero index, and iterating bottom elements from left to right, row by row. If beginning position is greater than or equal to heap size, then -1 is returned.

Single key searching

Csize_t MinHeap_FindKey (const struct MinHeap *heap, struct pair_t *data, union adt_t key, size_t pos, size_t count);

C++size_t MinHeap::FindKey (pair_t *data, adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the heap from the top element to the least right bottom element, starting from "pos" position, and doing it row by row. Then return position of the first 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:

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

Return value:

• Raw position of the first found element in the heap, assuming that the top element has zero index, and iterating bottom elements from left to right, row by row.
• -1 if no matches were met, or position is greater than or equal to the heap size.

Keys set searching

Csize_t MinHeap_FindKeys (const struct MinHeap *heap, struct pair_t *data, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t MinHeap::FindKeys (pair_t *data, const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the heap from the top element to the least right bottom element, starting from "pos" position, and doing it row by row. Then return position of the first 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:

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

Return value:

• Raw position of the first found element in the heap, assuming that the top element has zero index, and iterating bottom elements from left to right, row by row.
• -1 if no matches were met, or position is greater than or equal to the heap size.

Key counting

Following functions scan the heap from the top element to the least right bottom element, doing it row by row, and return count of matches to the key or to the set of keys. These functions do not change the heap elements, or heap order.

Single key counting

Csize_t MinHeap_CountKey (const struct MinHeap *heap, union adt_t key, size_t pos, size_t count);

C++size_t MinHeap::CountKey (adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the heap from the top element to the least right bottom element, starting from "pos" position, and doing it row by row. Then return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

• heap - pointer to the heap
• key - key value to find in the heap
• pos - beginning raw position to start from
• 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 MinHeap_CountKeys (const struct MinHeap *heap, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t MinHeap::CountKeys (const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the heap from the top element to the least right bottom element, starting from "pos" position, and doing it row by row. Then return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

• heap - pointer to the heap
• keys - array of keys to find in the heap
• size - size of array of keys
• pos - beginning raw position to start from
• 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.

Merging of heaps

Csize_t MinHeap_Merge (struct MinHeap *heap, struct MinHeap *source);

C++size_t MinHeap::Merge (MinHeap *source);

Description: Merge two heaps into one heap (target heap) and restore correct elements order. All elements from source heap are moved to target heap and source heap remains empty after merge operation.

Access type: RW

Parameters:

• heap - pointer to target heap
• source - pointer to source heap

Return value:

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

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

Heap properties

Heap built-in key type

Csize_t MinHeap_KeyType (const struct MinHeap *heap);

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

Access type: RO

Parameters:

• heap - pointer to the heap

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.

Heap key compare function

CKeyCmp MinHeap_CompareFunction (const struct MinHeap *heap);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap

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

Heap index call back function

CHeapIndex MinHeap_IndexFunction (const struct MinHeap *heap);

C++HeapIndex MinHeap::IndexFunction (void) const;

Description: Return pointer to index call back function is used by the heap.

Access type: RO

Parameters:

• heap - pointer to the heap

Return value: Pointer to index call back function, which conforms to this prototype.

Heap pair copy function

CCopyFunc MinHeap_CopyFunction (const struct MinHeap *heap);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap

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

Heap pair delete function

CDelFunc MinHeap_DeleteFunction (const struct MinHeap *heap);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap

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

Heap user's data

Cvoid* MinHeap_UserData (const struct MinHeap *heap);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap

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

Heap capacity

Csize_t MinHeap_Capacity (const struct MinHeap *heap);

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

Description: Return the heap capacity.

Access type: RO

Parameters:

• heap - pointer to the heap

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

Heap size

Csize_t MinHeap_Size (const struct MinHeap *heap);

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

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

Access type: RO

Parameters:

• heap - pointer to the heap

Return value: Count of allocated objects inside the heap.

Check if heap is empty

Cbool MinHeap_IsEmpty (const struct MinHeap *heap);

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

Description: Check if the heap is empty.

Access type: RO

Parameters:

• heap - pointer to the heap

Return value:

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

Check if heap is initialized

Cbool MinHeap_IsInit (const struct MinHeap *heap);

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

Description: Check if the heap is initialized.

Access type: RO

Parameters:

• heap - pointer to the heap

Return value:

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