cpp-common/bt2c/lib-str.hpp \
cpp-common/bt2c/libc-up.hpp \
cpp-common/bt2c/logging.hpp \
+ cpp-common/bt2c/prio-heap.hpp \
cpp-common/bt2c/read-fixed-len-int.hpp \
cpp-common/bt2c/safe-ops.hpp \
cpp-common/bt2c/std-int.hpp \
lib/plugin/plugin.h \
lib/plugin/plugin-so.c \
lib/plugin/plugin-so.h \
- lib/prio-heap/prio-heap.c \
- lib/prio-heap/prio-heap.h \
lib/trace-ir/attributes.c \
lib/trace-ir/attributes.h \
lib/trace-ir/clock-class.c \
--- /dev/null
+/*
+ * SPDX-License-Identifier: MIT
+ *
+ * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * Static-sized priority heap containing pointers. Based on CLRS,
+ * chapter 6.
+ */
+
+#include "common/macros.h"
+#include "common/assert.h"
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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;
+}
--- /dev/null
+/*
+ * SPDX-License-Identifier: MIT
+ *
+ * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ *
+ * Static-sized priority heap containing pointers. Based on CLRS,
+ * chapter 6.
+ */
+
+#ifndef BABELTRACE_COMMON_PRIO_HEAP_H
+#define BABELTRACE_COMMON_PRIO_HEAP_H
+
+#include <unistd.h>
+#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 */
--- /dev/null
+/*
+ * Copyright (c) 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ * Copyright (c) 2023 Philippe Proulx <pproulx@efficios.com>
+ *
+ * SPDX-License-Identifier: MIT
+ */
+
+#ifndef BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP
+#define BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP
+
+#include <functional>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include "common/assert.h"
+
+namespace bt2c {
+
+/*
+ * A templated C++ version of what used to be the `bt_heap_` C API,
+ * written by Mathieu Desnoyers, which implements an efficient heap data
+ * structure.
+ *
+ * This implements a static-sized priority heap based on CLRS,
+ * chapter 6.
+ *
+ * This version copies instances of `T` during its operations, so it's
+ * best to use with small objects such as pointers, integers, and small
+ * PODs.
+ *
+ * `T` must be default-constructible, copy-constructible, and
+ * copy-assignable.
+ *
+ * `CompT` is the type of the callable comparator. It must be possible
+ * to call an instance `comp` of `CompT` as such:
+ *
+ * comp(a, b)
+ *
+ * `comp` accepts two different `const T&` values and returns a value
+ * contextually convertible to `bool` which must be true if `a` appears
+ * _after_ `b`.
+ *
+ * The benefit of this version over `std::priority_queue` is the
+ * replaceTop() method which you can call to remove the top (greatest)
+ * element and then insert a new one immediately afterwards with a
+ * single heap rebalance.
+ */
+template <typename T, typename CompT = std::greater<T>>
+class PrioHeap final
+{
+ static_assert(std::is_default_constructible<T>::value, "`T` is default-constructible.");
+ static_assert(std::is_copy_constructible<T>::value, "`T` is copy-constructible.");
+ static_assert(std::is_copy_assignable<T>::value, "`T` is copy-assignable.");
+
+public:
+ /*
+ * Builds a priority heap using the comparator `comp` and with an
+ * initial capacity of `cap` elements.
+ */
+ explicit PrioHeap(CompT comp, const std::size_t cap) : _mComp {std::move(comp)}
+ {
+ _mElems.reserve(cap);
+ }
+
+ /*
+ * Builds a priority heap using the comparator `comp` and with an
+ * initial capacity of zero.
+ */
+ explicit PrioHeap(CompT comp) : PrioHeap {std::move(comp), 0}
+ {
+ }
+
+ /*
+ * Builds a priority heap using a default comparator and with an
+ * initial capacity of zero.
+ */
+ explicit PrioHeap() : PrioHeap {CompT {}, 0}
+ {
+ }
+
+ /*
+ * Number of contained elements.
+ */
+ std::size_t len() const noexcept
+ {
+ return _mElems.size();
+ }
+
+ /*
+ * Whether or not this heap is empty.
+ */
+ bool isEmpty() const noexcept
+ {
+ return _mElems.empty();
+ }
+
+ /*
+ * Removes all the elements.
+ */
+ void clear()
+ {
+ _mElems.clear();
+ }
+
+ /*
+ * Current top (greatest) element (`const` version).
+ */
+ const T& top() const noexcept
+ {
+ BT_ASSERT_DBG(!this->isEmpty());
+ this->_validate();
+ return _mElems.front();
+ }
+
+ /*
+ * Current top (greatest) element.
+ */
+ T& top() noexcept
+ {
+ BT_ASSERT_DBG(!this->isEmpty());
+ this->_validate();
+ return _mElems.front();
+ }
+
+ /*
+ * Inserts a copy of the element `elem`.
+ */
+ void insert(const T& elem)
+ {
+ /* Default-construct the new one */
+ _mElems.resize(_mElems.size() + 1);
+
+ auto pos = this->len() - 1;
+
+ while (pos > 0 && this->_gt(elem, this->_parentElem(pos))) {
+ /* Move parent down until we find the right spot */
+ _mElems[pos] = this->_parentElem(pos);
+ pos = this->_parentPos(pos);
+ }
+
+ _mElems[pos] = elem;
+ this->_validate();
+ }
+
+ /*
+ * Removes the top (greatest) element.
+ *
+ * This heap must not be empty.
+ */
+ void removeTop()
+ {
+ BT_ASSERT_DBG(!this->isEmpty());
+
+ if (_mElems.size() == 1) {
+ /* Fast path for a single element */
+ _mElems.clear();
+ return;
+ }
+
+ /*
+ * Shrink, replace the current top by the previous last element,
+ * and heapify.
+ */
+ const auto lastElem = _mElems.back();
+
+ _mElems.resize(_mElems.size() - 1);
+ return this->replaceTop(lastElem);
+ }
+
+ /*
+ * Removes the top (greatest) element, and inserts a copy of `elem`.
+ *
+ * Equivalent to using removeTop() and then insert(), but more
+ * efficient (single rebalance).
+ *
+ * This heap must not be empty.
+ */
+ void replaceTop(const T& elem)
+ {
+ BT_ASSERT_DBG(!this->isEmpty());
+
+ /* Replace the current top and heapify */
+ _mElems[0] = elem;
+ this->_heapify(0);
+ }
+
+private:
+ static std::size_t _parentPos(const std::size_t pos) noexcept
+ {
+ return (pos - 1) >> 1;
+ }
+
+ void _heapify(std::size_t pos)
+ {
+ while (true) {
+ std::size_t largestPos;
+ const auto leftPos = (pos << 1) + 1;
+
+ if (leftPos < this->len() && this->_gt(_mElems[leftPos], _mElems[pos])) {
+ largestPos = leftPos;
+ } else {
+ largestPos = pos;
+ }
+
+ const auto rightPos = (pos << 1) + 2;
+
+ if (rightPos < this->len() && this->_gt(_mElems[rightPos], _mElems[largestPos])) {
+ largestPos = rightPos;
+ }
+
+ if (G_UNLIKELY(largestPos == pos)) {
+ break;
+ }
+
+ const auto tmpElem = _mElems[pos];
+
+ _mElems[pos] = _mElems[largestPos];
+ _mElems[largestPos] = tmpElem;
+ pos = largestPos;
+ }
+
+ this->_validate();
+ }
+
+ T& _parentElem(const std::size_t pos) noexcept
+ {
+ return _mElems[this->_parentPos(pos)];
+ }
+
+ bool _gt(const T& a, const T& b) const
+ {
+ /* Forward to user comparator */
+ return _mComp(a, b);
+ }
+
+ void _validate() const noexcept
+ {
+#ifdef BT_DEBUG_MODE
+ if (_mElems.empty()) {
+ return;
+ }
+
+ for (std::size_t i = 1; i < _mElems.size(); ++i) {
+ BT_ASSERT_DBG(!this->_gt(_mElems[i], _mElems.front()));
+ }
+#endif /* BT_DEBUG_MODE */
+ }
+
+ CompT _mComp;
+ std::vector<T> _mElems;
+};
+
+} /* namespace bt2c */
+
+#endif /* BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP */
+++ /dev/null
-/*
- * SPDX-License-Identifier: MIT
- *
- * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
- *
- * Static-sized priority heap containing pointers. Based on CLRS,
- * chapter 6.
- */
-
-#include "common/macros.h"
-#include "common/assert.h"
-#include <errno.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "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;
-}
+++ /dev/null
-/*
- * SPDX-License-Identifier: MIT
- *
- * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
- *
- * Static-sized priority heap containing pointers. Based on CLRS,
- * chapter 6.
- */
-
-#ifndef _BABELTRACE_PRIO_HEAP_H
-#define _BABELTRACE_PRIO_HEAP_H
-
-#include <unistd.h>
-#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_PRIO_HEAP_H */
projects / babeltrace.git / commitdiff
