From ec688b4723a041044226358bcd4dd6e2da39da49 Mon Sep 17 00:00:00 2001 From: Luca Muscariello Date: Thu, 23 Feb 2017 17:01:02 +0100 Subject: Initial commit: cframework. Longbow and Libparc Change-Id: I90378dbd30da6033b20fb1f829b3b822cf366c59 Signed-off-by: Luca Muscariello --- libparc/parc/algol/parc_PriorityQueue.h | 223 ++++++++++++++++++++++++++++++++ 1 file changed, 223 insertions(+) create mode 100755 libparc/parc/algol/parc_PriorityQueue.h (limited to 'libparc/parc/algol/parc_PriorityQueue.h') diff --git a/libparc/parc/algol/parc_PriorityQueue.h b/libparc/parc/algol/parc_PriorityQueue.h new file mode 100755 index 00000000..45a6ffab --- /dev/null +++ b/libparc/parc/algol/parc_PriorityQueue.h @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file parc_PriorityQueue.h + * @ingroup datastructures + * @brief A priority queue (heap), where the top item is the minimum by the sort function. + * + * The user provides a sort function and the top item will be the minimum + * as per the < relation. + * + */ + +#ifndef libparc_parc_PriorityQueue_h +#define libparc_parc_PriorityQueue_h + +#include +#include + +struct parc_priority_queue; +typedef struct parc_priority_queue PARCPriorityQueue; + +typedef int (PARCPriorityQueueCompareTo)(const void *a, const void *b); +typedef void (PARCPriorityQueueDestroyer)(void **elementPtr); + +/** + * Calls {@link parcMemory_Deallocate} to free the element + * + * A simple destroyer that only uses {@link parcMemory_Deallocate}. + * + * @param [in,out] elementPtr Double pointer to data item, will be NULL'd + * + * Example: + * @code + * + * PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer); + * uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t)); + * objectid = 100; + * + * // this will use parcPriorityQueue_Uint64CompareTo sort order + * parcPriorityQueue_Add(q, objectid); + * + * // this will use the ParcFreeDestroyer + * parcPriorityQueue_Destroy(&q); + * @endcode + */ +void parcPriorityQueue_ParcFreeDestroyer(void **elementPtr); + +/** + * Treats the parameters as `uint64_t` pointers and compares them via natural sort order. + * + * Treats the parameters as `uint64_t` pointers and compares them via natural sort order. + * Obeys standared CompareTo semantics. + * + * @param [in] a uint64_t pointer + * @param [in] b uint64_t pointer + * + * @return -1 if a < b + * @return 0 if a == b + * @return +1 if a > b + * + * Example: + * @code + * + * PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer); + * uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t)); + * objectid = 100; + * + * // this will use parcPriorityQueue_Uint64CompareTo sort order + * parcPriorityQueue_Add(q, objectid); + * + * // this will use the ParcFreeDestroyer + * parcPriorityQueue_Destroy(&q); + * @endcode + */ +int parcPriorityQueue_Uint64CompareTo(const void *a, const void *b); + + +/** + * Creates a priority queue with a given sort function. + * + * The sort function defines the ordering of the Priorty Queue. The minimum element + * will always be the head of the queue. + * + * The destroyer is called on data elements from {@link parcPriorityQueue_Clear()} and + * {@link parcPriorityQueue_Destroy()}. You may use {@linkparcPriorityQueue_ParcFreeDestroyer()} for + * elements that can be freed by only calling {@link parcMemory_Deallocate}. + * + * @param [in] compare Defines the sort order of the priority queue + * @param [in] destroyer Called for Clear and Destroy operations, may be NULL. + * + * @return non-null A pointer to a `PARCPriorityQueue` + * + * Example: + * @code + * PARCPriorityQueue *q = parcPriorityQueue_Create(parcPriorityQueue_Uint64CompareTo, parcPriorityQueue_ParcFreeDestroyer); + * uint64_t *objectid = parcMemory_Allocate(sizeof(uint64_t)); + * objectid = 100; + * + * // this will use parcPriorityQueue_Uint64CompareTo sort order + * parcPriorityQueue_Add(q, objectid); + * + * // this will use the ParcFreeDestroyer + * parcPriorityQueue_Destroy(&q); + * @endcode + */ +PARCPriorityQueue *parcPriorityQueue_Create(PARCPriorityQueueCompareTo *compare, PARCPriorityQueueDestroyer *destroyer); + + +/** + * Destroy the queue and free remaining elements. + * + * Destroys the queue. If the destroyer was set in Create, then it will be called + * on all the remaining elements. + * + * @param [in,out] queuePtr Double pointer to allocated queue. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void parcPriorityQueue_Destroy(PARCPriorityQueue **queuePtr); + +/** + * Add an element to the priority queue, returning true if changed + * + * A "duplicate" is a data item that compares as equal to another item. The priority + * queue supports duplicates. It is not stable in regard to the ordering of duplicates. + * Because it supports duplicates, Add will always return true. + * + * The priority queue is unbounded. + * + * @param [in,out] queue The queue to modify + * @param [in] data The data to add to the queue, which must be comparable and not NULL + * + * @return true The data structure was modified by adding the new value + * @return false The data structure was not modified + * + * Example: + * @code + * <#example#> + * @endcode + */ +bool parcPriorityQueue_Add(PARCPriorityQueue *queue, void *data); + +/** + * Removes all elements, calling the data structure's destroyer on each + * + * Remvoes all elements. If the data structure's destroyer is non-NULL, it will be called + * on each element. + * + * @param [in,out] queue The queue to modify + * + * Example: + * @code + * <#example#> + * @endcode + */ +void parcPriorityQueue_Clear(PARCPriorityQueue *queue); + +/** + * Returns the head element, but does not remove it. + * + * Returns the head element. The data structure is not modified. If the + * priority queue is empty, will return NULL. + * + * @param [in] queue The `PARCPriorityQueue` to query. + * + * @return non-null The head element + * @return null The queue is empty + * + * Example: + * @code + * <#example#> + * @endcode + */ +void *parcPriorityQueue_Peek(PARCPriorityQueue *queue); + +/** + * Removes the head element from the queue and returns it. + * + * Removes the head element from the queue and returns it. If the queue is empty, + * it returns NULL. + * + * @param [in,out] queue The queue to query and modify. + * + * @return non-null The head element + * @return null The queue is empty + * + * Example: + * @code + * <#example#> + * @endcode + */ +void *parcPriorityQueue_Poll(PARCPriorityQueue *queue); + +/** + * Returns the number of elements in the queue. + * + * @param [in] queue The `PARCPriorityQueue` to query. + * + * @return number The number of elements in the queue. + * + * Example: + * @code + * <#example#> + * @endcode + */ +size_t parcPriorityQueue_Size(const PARCPriorityQueue *queue); +#endif // libparc_parc_PriorityQueue_h -- cgit 1.2.3-korg