2 * Copyright (c) 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
3 * Copyright (c) 2023 Philippe Proulx <pproulx@efficios.com>
5 * SPDX-License-Identifier: MIT
8 #ifndef BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP
9 #define BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP
12 #include <type_traits>
16 #include "common/assert.h"
21 * A templated C++ version of what used to be the `bt_heap_` C API,
22 * written by Mathieu Desnoyers, which implements an efficient heap data
25 * This implements a static-sized priority heap based on CLRS,
28 * This version copies instances of `T` during its operations, so it's
29 * best to use with small objects such as pointers, integers, and small
32 * `T` must be default-constructible, copy-constructible, and
35 * `CompT` is the type of the callable comparator. It must be possible
36 * to call an instance `comp` of `CompT` as such:
40 * `comp` accepts two different `const T&` values and returns a value
41 * contextually convertible to `bool` which must be true if `a` appears
44 * The benefit of this version over `std::priority_queue` is the
45 * replaceTop() method which you can call to remove the top (greatest)
46 * element and then insert a new one immediately afterwards with a
47 * single heap rebalance.
49 template <typename T, typename CompT = std::greater<T>>
52 static_assert(std::is_default_constructible<T>::value, "`T` is default-constructible.");
53 static_assert(std::is_copy_constructible<T>::value, "`T` is copy-constructible.");
54 static_assert(std::is_copy_assignable<T>::value, "`T` is copy-assignable.");
58 * Builds a priority heap using the comparator `comp` and with an
59 * initial capacity of `cap` elements.
61 explicit PrioHeap(CompT comp, const std::size_t cap) : _mComp {std::move(comp)}
67 * Builds a priority heap using the comparator `comp` and with an
68 * initial capacity of zero.
70 explicit PrioHeap(CompT comp) : PrioHeap {std::move(comp), 0}
75 * Builds a priority heap using a default comparator and with an
76 * initial capacity of zero.
78 explicit PrioHeap() : PrioHeap {CompT {}, 0}
83 * Number of contained elements.
85 std::size_t len() const noexcept
87 return _mElems.size();
91 * Whether or not this heap is empty.
93 bool isEmpty() const noexcept
95 return _mElems.empty();
99 * Removes all the elements.
107 * Current top (greatest) element (`const` version).
109 const T& top() const noexcept
111 BT_ASSERT_DBG(!this->isEmpty());
113 return _mElems.front();
117 * Current top (greatest) element.
121 BT_ASSERT_DBG(!this->isEmpty());
123 return _mElems.front();
127 * Inserts a copy of the element `elem`.
129 void insert(const T& elem)
131 /* Default-construct the new one */
132 _mElems.resize(_mElems.size() + 1);
134 auto pos = this->len() - 1;
136 while (pos > 0 && this->_gt(elem, this->_parentElem(pos))) {
137 /* Move parent down until we find the right spot */
138 _mElems[pos] = this->_parentElem(pos);
139 pos = this->_parentPos(pos);
147 * Removes the top (greatest) element.
149 * This heap must not be empty.
153 BT_ASSERT_DBG(!this->isEmpty());
155 if (_mElems.size() == 1) {
156 /* Fast path for a single element */
162 * Shrink, replace the current top by the previous last element,
165 const auto lastElem = _mElems.back();
167 _mElems.resize(_mElems.size() - 1);
168 return this->replaceTop(lastElem);
172 * Removes the top (greatest) element, and inserts a copy of `elem`.
174 * Equivalent to using removeTop() and then insert(), but more
175 * efficient (single rebalance).
177 * This heap must not be empty.
179 void replaceTop(const T& elem)
181 BT_ASSERT_DBG(!this->isEmpty());
183 /* Replace the current top and heapify */
189 static std::size_t _parentPos(const std::size_t pos) noexcept
191 return (pos - 1) >> 1;
194 void _heapify(std::size_t pos)
197 std::size_t largestPos;
198 const auto leftPos = (pos << 1) + 1;
200 if (leftPos < this->len() && this->_gt(_mElems[leftPos], _mElems[pos])) {
201 largestPos = leftPos;
206 const auto rightPos = (pos << 1) + 2;
208 if (rightPos < this->len() && this->_gt(_mElems[rightPos], _mElems[largestPos])) {
209 largestPos = rightPos;
212 if (G_UNLIKELY(largestPos == pos)) {
216 const auto tmpElem = _mElems[pos];
218 _mElems[pos] = _mElems[largestPos];
219 _mElems[largestPos] = tmpElem;
226 T& _parentElem(const std::size_t pos) noexcept
228 return _mElems[this->_parentPos(pos)];
231 bool _gt(const T& a, const T& b) const
233 /* Forward to user comparator */
237 void _validate() const noexcept
240 if (_mElems.empty()) {
244 for (std::size_t i = 1; i < _mElems.size(); ++i) {
245 BT_ASSERT_DBG(!this->_gt(_mElems[i], _mElems.front()));
247 #endif /* BT_DEBUG_MODE */
251 std::vector<T> _mElems;
254 } /* namespace bt2c */
256 #endif /* BABELTRACE_CPP_COMMON_BT2C_PRIO_HEAP_HPP */