From ef5ebbacf896c2e012e682d2bf262c795c360b6b Mon Sep 17 00:00:00 2001 From: Philippe Proulx Date: Wed, 22 Nov 2023 16:27:39 -0500 Subject: [PATCH] cpp-common/bt2c: add `bt2c::PrioHeap` (C++ version of `bt_heap_` C API) This new class template is a templated C++ version of `src/lib/prio-heap/prio-heap.*` (C API), written by Mathieu Desnoyers, which implements an efficient heap data structure. In true C++ spirit, it accepts and stores a comparator (which may be an object; `std::greatest` instance by default) instead of a simple function pointer, making it possible for the user to store some context. 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. A benefit over `std::priority_queue`, which offers a similar interface, is the replaceTop() method which performs a single heap rebalance when you need to remove the top (greatest) element and immediately insert one (possibly the same one). `src/lib/prio-heap/prio-heap.*` are removed because they're not used anywhere in the project and we only plan to write new C++ code anyway in the future. Signed-off-by: Philippe Proulx Change-Id: I830ab79ef067c0ebb2fc33466b3dc831c617a049 Reviewed-on: https://review.lttng.org/c/babeltrace/+/11419 Tested-by: jenkins Reviewed-by: Simon Marchi CI-Build: Simon Marchi --- src/Makefile.am | 3 +- src/{lib/prio-heap => common}/prio-heap.c | 2 +- src/{lib/prio-heap => common}/prio-heap.h | 6 +- src/cpp-common/bt2c/prio-heap.hpp | 256 ++++++++++++++++++++++ 4 files changed, 261 insertions(+), 6 deletions(-) rename src/{lib/prio-heap => common}/prio-heap.c (99%) rename src/{lib/prio-heap => common}/prio-heap.h (96%) create mode 100644 src/cpp-common/bt2c/prio-heap.hpp diff --git a/src/Makefile.am b/src/Makefile.am index 98a358cf..2166e36d 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -49,6 +49,7 @@ noinst_HEADERS = \ 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 \ @@ -409,8 +410,6 @@ lib_libbabeltrace2_la_SOURCES = \ 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 \ diff --git a/src/lib/prio-heap/prio-heap.c b/src/common/prio-heap.c similarity index 99% rename from src/lib/prio-heap/prio-heap.c rename to src/common/prio-heap.c index d137aed8..55ed5e81 100644 --- a/src/lib/prio-heap/prio-heap.c +++ b/src/common/prio-heap.c @@ -13,7 +13,7 @@ #include #include -#include "prio-heap.h" +#include "common/prio-heap.h" #ifdef DEBUG_HEAP void check_heap(const struct ptr_heap *heap) diff --git a/src/lib/prio-heap/prio-heap.h b/src/common/prio-heap.h similarity index 96% rename from src/lib/prio-heap/prio-heap.h rename to src/common/prio-heap.h index 06f72a11..7e56521b 100644 --- a/src/lib/prio-heap/prio-heap.h +++ b/src/common/prio-heap.h @@ -7,8 +7,8 @@ * chapter 6. */ -#ifndef _BABELTRACE_PRIO_HEAP_H -#define _BABELTRACE_PRIO_HEAP_H +#ifndef BABELTRACE_COMMON_PRIO_HEAP_H +#define BABELTRACE_COMMON_PRIO_HEAP_H #include #include "common/macros.h" @@ -113,4 +113,4 @@ extern void *bt_heap_replace_max(struct ptr_heap *heap, void *p); */ extern int bt_heap_copy(struct ptr_heap *dst, struct ptr_heap *src); -#endif /* _BABELTRACE_PRIO_HEAP_H */ +#endif /* BABELTRACE_COMMON_PRIO_HEAP_H */ diff --git a/src/cpp-common/bt2c/prio-heap.hpp b/src/cpp-common/bt2c/prio-heap.hpp new file mode 100644 index 00000000..34ff0fc9 --- /dev/null +++ b/src/cpp-common/bt2c/prio-heap.hpp @@ -0,0 +1,256 @@ +/* + * Copyright (c) 2011 Mathieu Desnoyers + * Copyright (c) 2023 Philippe Proulx + * + * SPDX-License-Identifier: MIT + */ + +#ifndef BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP +#define BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP + +#include +#include +#include +#include + +#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 > +class PrioHeap final +{ + static_assert(std::is_default_constructible::value, "`T` is default-constructible."); + static_assert(std::is_copy_constructible::value, "`T` is copy-constructible."); + static_assert(std::is_copy_assignable::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 _mElems; +}; + +} /* namespace bt2c */ + +#endif /* BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP */ -- 2.34.1