Merge "Adding gitreview config file for this branch sub project"

1 files changed, 223 insertions, 0 deletions

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 <stdlib.h>
+#include <stdbool.h>
+
+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