cpp-common/bt2c: add `bt2c::PrioHeap` (C++ version of `bt_heap_` C API)
authorPhilippe Proulx <eeppeliteloop@gmail.com>
Wed, 22 Nov 2023 21:27:39 +0000 (16:27 -0500)
committerSimon Marchi <simon.marchi@efficios.com>
Thu, 14 Dec 2023 15:57:04 +0000 (10:57 -0500)
commitef5ebbacf896c2e012e682d2bf262c795c360b6b
tree506316c2d88491722c584ce64f6d6b2f5e54a33a
parent84cef782ca04a1d3932f8acd2ff5910ebbaa4797
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 <eeppeliteloop@gmail.com>
Change-Id: I830ab79ef067c0ebb2fc33466b3dc831c617a049
Reviewed-on: https://review.lttng.org/c/babeltrace/+/11419
Tested-by: jenkins <jenkins@lttng.org>
Reviewed-by: Simon Marchi <simon.marchi@efficios.com>
CI-Build: Simon Marchi <simon.marchi@efficios.com>
src/Makefile.am
src/common/prio-heap.c [new file with mode: 0644]
src/common/prio-heap.h [new file with mode: 0644]
src/cpp-common/bt2c/prio-heap.hpp [new file with mode: 0644]
src/lib/prio-heap/prio-heap.c [deleted file]
src/lib/prio-heap/prio-heap.h [deleted file]
This page took 0.024343 seconds and 4 git commands to generate.