From: Simon Marchi Date: Thu, 9 May 2024 16:03:58 +0000 (-0400) Subject: common: remove `prio-heap.{c,h}` X-Git-Url: https://git.efficios.com/?p=babeltrace.git;a=commitdiff_plain;h=HEAD common: remove `prio-heap.{c,h}` Change-Id: Iec4f0a14efceb21aa67bedd58153e14bdd9662d9 Signed-off-by: Simon Marchi Reviewed-on: https://review.lttng.org/c/babeltrace/+/12538 Reviewed-by: Philippe Proulx Tested-by: jenkins --- diff --git a/src/common/prio-heap.c b/src/common/prio-heap.c deleted file mode 100644 index 55ed5e81..00000000 --- a/src/common/prio-heap.c +++ /dev/null @@ -1,220 +0,0 @@ -/* - * SPDX-License-Identifier: MIT - * - * Copyright 2011 Mathieu Desnoyers - * - * Static-sized priority heap containing pointers. Based on CLRS, - * chapter 6. - */ - -#include "common/macros.h" -#include "common/assert.h" -#include -#include -#include - -#include "common/prio-heap.h" - -#ifdef DEBUG_HEAP -void check_heap(const struct ptr_heap *heap) -{ - size_t i; - - if (!heap->len) - return; - - for (i = 1; i < heap->len; i++) - BT_ASSERT_DBG(!heap->gt(heap->ptrs[i], heap->ptrs[0])); -} -#endif - -static -size_t parent(size_t i) -{ - return (i - 1) >> 1; -} - -static -size_t left(size_t i) -{ - return (i << 1) + 1; -} - -static -size_t right(size_t i) -{ - return (i << 1) + 2; -} - -/* - * Copy of heap->ptrs pointer is invalid after heap_grow. - */ -static -int heap_grow(struct ptr_heap *heap, size_t new_len) -{ - void **new_ptrs; - - if (G_LIKELY(heap->alloc_len >= new_len)) - return 0; - - heap->alloc_len = bt_max_t(size_t, new_len, heap->alloc_len << 1); - new_ptrs = calloc(heap->alloc_len, sizeof(void *)); - if (G_UNLIKELY(!new_ptrs)) - return -ENOMEM; - if (G_LIKELY(heap->ptrs)) - memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *)); - free(heap->ptrs); - heap->ptrs = new_ptrs; - return 0; -} - -static -int heap_set_len(struct ptr_heap *heap, size_t new_len) -{ - int ret; - - ret = heap_grow(heap, new_len); - if (G_UNLIKELY(ret)) - return ret; - heap->len = new_len; - return 0; -} - -int bt_heap_init(struct ptr_heap *heap, size_t alloc_len, - int gt(void *a, void *b)) -{ - heap->ptrs = NULL; - heap->len = 0; - heap->alloc_len = 0; - heap->gt = gt; - /* - * Minimum size allocated is 1 entry to ensure memory allocation - * never fails within bt_heap_replace_max. - */ - return heap_grow(heap, bt_max_t(size_t, 1, alloc_len)); -} - -void bt_heap_free(struct ptr_heap *heap) -{ - free(heap->ptrs); -} - -static void heapify(struct ptr_heap *heap, size_t i) -{ - void **ptrs = heap->ptrs; - size_t l, r, largest; - - for (;;) { - void *tmp; - - l = left(i); - r = right(i); - if (l < heap->len && heap->gt(ptrs[l], ptrs[i])) - largest = l; - else - largest = i; - if (r < heap->len && heap->gt(ptrs[r], ptrs[largest])) - largest = r; - if (G_UNLIKELY(largest == i)) - break; - tmp = ptrs[i]; - ptrs[i] = ptrs[largest]; - ptrs[largest] = tmp; - i = largest; - } - check_heap(heap); -} - -void *bt_heap_replace_max(struct ptr_heap *heap, void *p) -{ - void *res; - - if (G_UNLIKELY(!heap->len)) { - (void) heap_set_len(heap, 1); - heap->ptrs[0] = p; - check_heap(heap); - return NULL; - } - - /* Replace the current max and heapify */ - res = heap->ptrs[0]; - heap->ptrs[0] = p; - heapify(heap, 0); - return res; -} - -int bt_heap_insert(struct ptr_heap *heap, void *p) -{ - void **ptrs; - size_t pos; - int ret; - - ret = heap_set_len(heap, heap->len + 1); - if (G_UNLIKELY(ret)) - return ret; - ptrs = heap->ptrs; - pos = heap->len - 1; - while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) { - /* Move parent down until we find the right spot */ - ptrs[pos] = ptrs[parent(pos)]; - pos = parent(pos); - } - ptrs[pos] = p; - check_heap(heap); - return 0; -} - -void *bt_heap_remove(struct ptr_heap *heap) -{ - switch (heap->len) { - case 0: - return NULL; - case 1: - (void) heap_set_len(heap, 0); - return heap->ptrs[0]; - } - /* Shrink, replace the current max by previous last entry and heapify */ - heap_set_len(heap, heap->len - 1); - /* len changed. previous last entry is at heap->len */ - return bt_heap_replace_max(heap, heap->ptrs[heap->len]); -} - -void *bt_heap_cherrypick(struct ptr_heap *heap, void *p) -{ - size_t pos, len = heap->len; - - for (pos = 0; pos < len; pos++) - if (G_UNLIKELY(heap->ptrs[pos] == p)) - goto found; - return NULL; -found: - if (G_UNLIKELY(heap->len == 1)) { - (void) heap_set_len(heap, 0); - check_heap(heap); - return heap->ptrs[0]; - } - /* Replace p with previous last entry and heapify. */ - heap_set_len(heap, heap->len - 1); - /* len changed. previous last entry is at heap->len */ - heap->ptrs[pos] = heap->ptrs[heap->len]; - heapify(heap, pos); - return p; -} - -int bt_heap_copy(struct ptr_heap *dst, struct ptr_heap *src) -{ - int ret; - - ret = bt_heap_init(dst, src->alloc_len, src->gt); - if (ret < 0) - goto end; - - ret = heap_set_len(dst, src->len); - if (ret < 0) - goto end; - - memcpy(dst->ptrs, src->ptrs, src->len * sizeof(void *)); - -end: - return ret; -} diff --git a/src/common/prio-heap.h b/src/common/prio-heap.h deleted file mode 100644 index 7e56521b..00000000 --- a/src/common/prio-heap.h +++ /dev/null @@ -1,116 +0,0 @@ -/* - * SPDX-License-Identifier: MIT - * - * Copyright 2011 Mathieu Desnoyers - * - * Static-sized priority heap containing pointers. Based on CLRS, - * chapter 6. - */ - -#ifndef BABELTRACE_COMMON_PRIO_HEAP_H -#define BABELTRACE_COMMON_PRIO_HEAP_H - -#include -#include "common/macros.h" - -struct ptr_heap { - size_t len, alloc_len; - void **ptrs; - int (*gt)(void *a, void *b); -}; - -#ifdef DEBUG_HEAP -void check_heap(const struct ptr_heap *heap); -#else -static inline -void check_heap(const struct ptr_heap *heap __attribute__((unused))) -{ -} -#endif - -/** - * bt_heap_maximum - return the largest element in the heap - * @heap: the heap to be operated on - * - * Returns the largest element in the heap, without performing any modification - * to the heap structure. Returns NULL if the heap is empty. - */ -static inline void *bt_heap_maximum(const struct ptr_heap *heap) -{ - check_heap(heap); - return G_LIKELY(heap->len) ? heap->ptrs[0] : NULL; -} - -/** - * bt_heap_init - initialize the heap - * @heap: the heap to initialize - * @alloc_len: number of elements initially allocated - * @gt: function to compare the elements - * - * Returns -ENOMEM if out of memory. - */ -extern int bt_heap_init(struct ptr_heap *heap, - size_t alloc_len, - int gt(void *a, void *b)); - -/** - * bt_heap_free - free the heap - * @heap: the heap to free - */ -extern void bt_heap_free(struct ptr_heap *heap); - -/** - * bt_heap_insert - insert an element into the heap - * @heap: the heap to be operated on - * @p: the element to add - * - * Insert an element into the heap. - * - * Returns -ENOMEM if out of memory. - */ -extern int bt_heap_insert(struct ptr_heap *heap, void *p); - -/** - * bt_heap_remove - remove the largest element from the heap - * @heap: the heap to be operated on - * - * Returns the largest element in the heap. It removes this element from the - * heap. Returns NULL if the heap is empty. - */ -extern void *bt_heap_remove(struct ptr_heap *heap); - -/** - * bt_heap_cherrypick - remove a given element from the heap - * @heap: the heap to be operated on - * @p: the element - * - * Remove the given element from the heap. Return the element if present, else - * return NULL. This algorithm has a complexity of O(n), which is higher than - * O(log(n)) provided by the rest of this API. - */ -extern void *bt_heap_cherrypick(struct ptr_heap *heap, void *p); - -/** - * bt_heap_replace_max - replace the the largest element from the heap - * @heap: the heap to be operated on - * @p: the pointer to be inserted as topmost element replacement - * - * Returns the largest element in the heap. It removes this element from the - * heap. The heap is rebalanced only once after the insertion. Returns NULL if - * the heap is empty. - * - * This is the equivalent of calling bt_heap_remove() and then bt_heap_insert(), but - * it only rebalances the heap once. It never allocates memory. - */ -extern void *bt_heap_replace_max(struct ptr_heap *heap, void *p); - -/** - * bt_heap_copy - copy a heap - * @dst: the destination heap (must be allocated) - * @src: the source heap - * - * Returns -ENOMEM if out of memory. - */ -extern int bt_heap_copy(struct ptr_heap *dst, struct ptr_heap *src); - -#endif /* BABELTRACE_COMMON_PRIO_HEAP_H */