From c07ad72f016930e2aba6471d0e2e9625b935bf9a Mon Sep 17 00:00:00 2001 From: Mauro Sardara Date: Thu, 24 Jan 2019 17:52:53 +0100 Subject: Remove cframework files from master Change-Id: I02f17ede1cf97986a8b8852ed6d6a28fc016f590 Signed-off-by: Mauro Sardara --- libparc/parc/algol/parc_PriorityQueue.c | 387 -------------------------------- 1 file changed, 387 deletions(-) delete mode 100755 libparc/parc/algol/parc_PriorityQueue.c (limited to 'libparc/parc/algol/parc_PriorityQueue.c') diff --git a/libparc/parc/algol/parc_PriorityQueue.c b/libparc/parc/algol/parc_PriorityQueue.c deleted file mode 100755 index c6c003b1..00000000 --- a/libparc/parc/algol/parc_PriorityQueue.c +++ /dev/null @@ -1,387 +0,0 @@ -/* - * 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 - -#include - -#include -#include -#include - -#include -#include - -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) -{ - parcAssertNotNull(elementPtr, "Double pointer must be non-null"); - parcAssertNotNull(*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) -{ - parcAssertNotNull(compare, "Parameter compare must be non-null"); - - size_t initialSize = 128; - PARCPriorityQueue *queue = parcMemory_AllocateAndClear(sizeof(PARCPriorityQueue)); - parcAssertNotNull(queue, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(PARCPriorityQueue)); - queue->array = parcMemory_AllocateAndClear(sizeof(HeapEntry) * initialSize); - parcAssertNotNull(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) -{ - parcAssertNotNull(queuePtr, "Double pointer must be non-null"); - parcAssertNotNull(*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) -{ - parcAssertNotNull(queue, "Parameter queue must be non-null"); - parcAssertNotNull(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) -{ - parcAssertNotNull(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) -{ - parcAssertNotNull(queue, "Parameter queue must be non-null"); - if (queue->size > 0) { - return queue->array[0].data; - } - return NULL; -} - -void * -parcPriorityQueue_Poll(PARCPriorityQueue *queue) -{ - parcAssertNotNull(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) -{ - parcAssertNotNull(queue, "Parameter queue must be non-null"); - return queue->size; -} -- cgit 1.2.3-korg