diff options
Diffstat (limited to 'libparc/parc/algol/parc_PriorityQueue.c')
| -rwxr-xr-x | libparc/parc/algol/parc_PriorityQueue.c | 387 |
1 files changed, 387 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_PriorityQueue.c b/libparc/parc/algol/parc_PriorityQueue.c new file mode 100755 index 00000000..93744b2c --- /dev/null +++ b/libparc/parc/algol/parc_PriorityQueue.c @@ -0,0 +1,387 @@ +/* + * 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. + */ + + +/** + * Priority Queue implemented over a Binary Heap. + * + * A Binary Heap will have average insert of O(1) and delete of O(log n). The worst case + * is O(log n) for both. The average and worst case FindMin is O(1). + * + * The binary heap is implemented as a "0"-based array, so for node index n, the + * children are at 2n+1 and 2n+2. Its parent is at floor((n-1)/2). + * + * The Heap property is a[n] <= a[2n+1] and a[k] <= a[2k+2]. We need to move things around + * sufficiently for this property to remain true. + * + */ + +#include <config.h> + +#include <LongBow/runtime.h> + +#include <stdio.h> +#include <stdbool.h> +#include <string.h> + +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_PriorityQueue.h> + +typedef struct heap_entry { + void *data; +} HeapEntry; + +struct parc_priority_queue { + HeapEntry *array; + size_t capacity; // how many elements are allocated + size_t size; // how many elements are used + + PARCPriorityQueueCompareTo *compare; + PARCPriorityQueueDestroyer *destroyer; +}; + +/** + * 0-based array indexing, so use 2n+1 + */ +static size_t +_leftChildIndex(size_t elementIndex) +{ + return 2 * elementIndex + 1; +} + +/** + * 0-based array indexing, so use 2n+2 + * IMPORTANT: This must be a larger index than the left child, + * as the TrickleDown algorithm assumes that if the right child exists so + * does the left child. + */ +static size_t +_rightChildIndex(size_t elementIndex) +{ + return 2 * elementIndex + 2; +} + +/** + * 0-based array indexing, so use (n-1)/2 + */ +static size_t +_parentIndex(size_t elementIndex) +{ + return (elementIndex - 1) / 2; +} + +/** + * Exchange the data between two array locations + */ +static void +_swap(PARCPriorityQueue *queue, size_t firstIndex, size_t secondIndex) +{ + void *firstData = queue->array[firstIndex].data; + queue->array[firstIndex].data = queue->array[secondIndex].data; + queue->array[secondIndex].data = firstData; +} + +/** + * See parcPriorityQueue_TrickleDown for full details + * + * Case 1: Right child exists and r.value < n.value && r.value < l.value + * In this case, swap(n.index, r.index) and set n.index = r.index. + * 50 6 + * / \ ===> / \ + * 9 6 9 50 + * + * Case 2: Right child exists and r.value < n.value && l.value <= r.value + * In this case swap(n.index, l.index) and set n.index = l.index + * This makes sense by transitivity that l <= r < n, so swap(n,l) satisfies the invariant. + * 50 6 + * / \ ===> / \ + * 6 9 50 9 + */ +static size_t +_trickleRightChild(PARCPriorityQueue *queue, size_t elementIndex, size_t leftChildIndex, size_t rightChildIndex) +{ + if (queue->compare(queue->array[rightChildIndex].data, queue->array[elementIndex].data) < 0) { + if (queue->compare(queue->array[rightChildIndex].data, queue->array[leftChildIndex].data) < 0) { + // Case 1 + _swap(queue, rightChildIndex, elementIndex); + elementIndex = rightChildIndex; + } else { + // Case 2 + _swap(queue, leftChildIndex, elementIndex); + elementIndex = leftChildIndex; + } + } + return elementIndex; +} + +/** + * See parcPriorityQueue_TrickleDown for full details + * + * Case 3: Left child exists (right does not) and l.value < n.value + * In this case, swap(n.index, l.index) and set n.index = l.index + * 50 6 + * / \ ===> / \ + * 6 x 50 x + */ +static size_t +_trickleLeftChild(PARCPriorityQueue *queue, size_t elementIndex, size_t leftChildIndex) +{ + if (queue->compare(queue->array[leftChildIndex].data, queue->array[elementIndex].data) < 0) { + // Case 3 + _swap(queue, leftChildIndex, elementIndex); + elementIndex = leftChildIndex; + } + return elementIndex; +} + +/** + * Moves an element down the heap until it satisfies the heap invariant. + * + * The value of node n must be less than or equal to both the left child and right child, if + * they exist. Here's the algorithm by example. Let r.value, l.value and n.value be the values + * of the right, left and node. Let r.index, l.index, and n.index be their indicies. + * + * Case 1: Right child exists and r.value < n.value && r.value < l.value + * In this case, swap(n.index, r.index) and set n.index = r.index. + * 50 6 + * / \ ===> / \ + * 9 6 9 50 + * + * Case 2: Right child exists and r.value < n.value && l.value <= r.value + * In this case swap(n.index, l.index) and set n.index = l.index + * This makes sense by transitivity that l <= r < n, so swap(n,l) satisfies the invariant. + * 50 6 + * / \ ===> / \ + * 6 9 50 9 + * + * Case 3: Left child exists (right does not) and l.value < n.value + * In this case, swap(n.index, l.index) and set n.index = l.index + * 50 6 + * / \ ===> / \ + * 6 x 50 x + * + * Case 4: No child exists or already satisfies invariant + * Done + * 50 50 + * / \ ===> / \ + * x x x x + * OR + * 4 4 + * / \ ===> / \ + * 9 6 9 6 + * + * + * @param [in] queue The priority queue to manipulate + * @param [in] elementIndex The root element (n above) to trickle down + * + * Example: + * @code + * <#example#> + * @endcode + */ +static void +_trickleDown(PARCPriorityQueue *queue, size_t elementIndex) +{ + bool finished = false; + + while (!finished) { + size_t rightChildIndex = _rightChildIndex(elementIndex); + size_t leftChildIndex = _leftChildIndex(elementIndex); + + if (rightChildIndex < queue->size) { + // Case 1 and Case 2 + elementIndex = _trickleRightChild(queue, elementIndex, leftChildIndex, rightChildIndex); + } else if (leftChildIndex < queue->size) { + // Case 3 + elementIndex = _trickleLeftChild(queue, elementIndex, leftChildIndex); + } else { + // Case 4, we're done + finished = true; + } + } +} + +/** + * Move the item at elementIndex up the tree until it satisfies the invariant. + * + * This is used when we insert an element at the bottom of the heap. We bubble it up + * the heap until it satisfies the heap invariant (i.e. it's parent is less than or + * equal to it). + * + * @param [in] queue The priority queue to manipulate + * @param [in] elementIndex The 0-based index of the element to bubble up + */ +static void +_bubbleUp(PARCPriorityQueue *queue, size_t elementIndex) +{ + size_t parentIndex = _parentIndex(elementIndex); + while (elementIndex > 0 && queue->compare(queue->array[elementIndex].data, queue->array[parentIndex].data) < 0) { + _swap(queue, elementIndex, parentIndex); + // now move up the ladder + elementIndex = parentIndex; + parentIndex = _parentIndex(elementIndex); + } + + // At this point, it is either at the top (elementIndex = 0) or statisfies the heap invariant. +} + +/** + * Add more elements to the backing aray + * + * Expand the array capacity. We use a fixed x2 expansion each time, though this might not + * be desirable when the capacity gets large. + * + * @param [in] queue The priority queue to manipulate + * + * Example: + * @code + * <#example#> + * @endcode + */ +static void +_expand(PARCPriorityQueue *queue) +{ + queue->capacity *= 2; + queue->array = parcMemory_Reallocate(queue->array, sizeof(HeapEntry) * queue->capacity); +} + +// ================================ +// Public API + +void +parcPriorityQueue_ParcFreeDestroyer(void **elementPtr) +{ + assertNotNull(elementPtr, "Double pointer must be non-null"); + assertNotNull(*elementPtr, "Double pointer must dereference to non-null"); + void *element = *elementPtr; + parcMemory_Deallocate((void **) &element); + *elementPtr = NULL; +} + +int +parcPriorityQueue_Uint64CompareTo(const void *a, const void *b) +{ + uint64_t value_a = *((uint64_t *) a); + uint64_t value_b = *((uint64_t *) b); + if (value_a < value_b) { + return -1; + } else if (value_a > value_b) { + return +1; + } + return 0; +} + +PARCPriorityQueue * +parcPriorityQueue_Create(PARCPriorityQueueCompareTo *compare, PARCPriorityQueueDestroyer *destroyer) +{ + assertNotNull(compare, "Parameter compare must be non-null"); + + size_t initialSize = 128; + PARCPriorityQueue *queue = parcMemory_AllocateAndClear(sizeof(PARCPriorityQueue)); + assertNotNull(queue, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(PARCPriorityQueue)); + queue->array = parcMemory_AllocateAndClear(sizeof(HeapEntry) * initialSize); + assertNotNull(queue->array, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(HeapEntry) * initialSize); + queue->capacity = initialSize; + queue->size = 0; + queue->compare = compare; + queue->destroyer = destroyer; + + return queue; +} + +void +parcPriorityQueue_Destroy(PARCPriorityQueue **queuePtr) +{ + assertNotNull(queuePtr, "Double pointer must be non-null"); + assertNotNull(*queuePtr, "Double pointer must dereference to non-null"); + PARCPriorityQueue *queue = *queuePtr; + parcPriorityQueue_Clear(queue); + parcMemory_Deallocate((void **) &(queue->array)); + parcMemory_Deallocate((void **) &queue); + *queuePtr = NULL; +} + +bool +parcPriorityQueue_Add(PARCPriorityQueue *queue, void *data) +{ + assertNotNull(queue, "Parameter queue must be non-null"); + assertNotNull(data, "Parameter data must be non-null"); + + if (queue->size + 1 > queue->capacity) { + _expand(queue); + } + + // insert at the end of the array + queue->array[queue->size].data = data; + + // increment the size before calling bubble up so invariants are true (i.e. + // the index we're giving to BubbleUp is within the array size. + queue->size++; + _bubbleUp(queue, queue->size - 1); + + // we always allow duplicates, so always return true + return true; +} + +void +parcPriorityQueue_Clear(PARCPriorityQueue *queue) +{ + assertNotNull(queue, "Parameter queue must be non-null"); + if (queue->destroyer != NULL) { + for (size_t i = 0; i < queue->size; i++) { + queue->destroyer(&queue->array[i].data); + } + } + + queue->size = 0; +} + +void * +parcPriorityQueue_Peek(PARCPriorityQueue *queue) +{ + assertNotNull(queue, "Parameter queue must be non-null"); + if (queue->size > 0) { + return queue->array[0].data; + } + return NULL; +} + +void * +parcPriorityQueue_Poll(PARCPriorityQueue *queue) +{ + assertNotNull(queue, "Parameter queue must be non-null"); + if (queue->size > 0) { + void *data = queue->array[0].data; + + queue->size--; + + // if size == 1, then this is a no-op + queue->array[0].data = queue->array[queue->size].data; + + // make sure the head satisifies the heap invariant + _trickleDown(queue, 0); + + return data; + } + + return NULL; +} + +size_t +parcPriorityQueue_Size(const PARCPriorityQueue *queue) +{ + assertNotNull(queue, "Parameter queue must be non-null"); + return queue->size; +} |