summaryrefslogtreecommitdiffstats
path: root/src/dmclock/support/src/indirect_intrusive_heap.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/dmclock/support/src/indirect_intrusive_heap.h567
1 files changed, 567 insertions, 0 deletions
diff --git a/src/dmclock/support/src/indirect_intrusive_heap.h b/src/dmclock/support/src/indirect_intrusive_heap.h
new file mode 100644
index 000000000..d84a48784
--- /dev/null
+++ b/src/dmclock/support/src/indirect_intrusive_heap.h
@@ -0,0 +1,567 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+/*
+ * Copyright (C) 2016 Red Hat Inc.
+ *
+ * Author: J. Eric Ivancich <ivancich@redhat.com>
+ *
+ * This is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License version
+ * 2.1, as published by the Free Software Foundation. See file
+ * COPYING.
+ */
+
+
+#pragma once
+
+
+#include <memory>
+#include <vector>
+#include <string>
+#include <iostream>
+#include <functional>
+#include <algorithm>
+
+#include "assert.h"
+
+
+namespace crimson {
+ using IndIntruHeapData = size_t;
+
+ /* T is the ultimate data that's being stored in the heap, although
+ * through indirection.
+ *
+ * I is the indirect type that will actually be stored in the heap
+ * and that must allow dereferencing (via operator*) to yield a
+ * T&.
+ *
+ * C is a functor when given two T&'s will return true if the first
+ * must precede the second.
+ *
+ * heap_info is a data member pointer as to where the heap data in T
+ * is stored.
+ *
+ * K is the branching factor of the heap, default is 2 (binary heap).
+ */
+ template<typename I,
+ typename T,
+ IndIntruHeapData T::*heap_info,
+ typename C,
+ unsigned K = 2>
+ class IndIntruHeap {
+
+ // shorthand
+ using HeapIndex = IndIntruHeapData;
+
+ static_assert(
+ std::is_same<T,typename std::pointer_traits<I>::element_type>::value,
+ "class I must resolve to class T by indirection (pointer dereference)");
+
+ static_assert(
+ std::is_same<bool,
+ typename std::result_of<C(const T&,const T&)>::type>::value,
+ "class C must define operator() to take two const T& and return a bool");
+
+ static_assert(K >= 2, "K (degree of branching) must be at least 2");
+
+ class Iterator {
+ friend IndIntruHeap<I, T, heap_info, C, K>;
+
+ IndIntruHeap<I, T, heap_info, C, K>* heap;
+ HeapIndex index;
+
+ Iterator(IndIntruHeap<I, T, heap_info, C, K>& _heap, HeapIndex _index) :
+ heap(&_heap),
+ index(_index)
+ {
+ // empty
+ }
+
+ public:
+
+ Iterator(Iterator&& other) :
+ heap(other.heap),
+ index(other.index)
+ {
+ // empty
+ }
+
+ Iterator(const Iterator& other) :
+ heap(other.heap),
+ index(other.index)
+ {
+ // empty
+ }
+
+ Iterator& operator=(Iterator&& other) {
+ std::swap(heap, other.heap);
+ std::swap(index, other.index);
+ return *this;
+ }
+
+ Iterator& operator=(const Iterator& other) {
+ heap = other.heap;
+ index = other.index;
+ }
+
+ Iterator& operator++() {
+ if (index <= heap->count) {
+ ++index;
+ }
+ return *this;
+ }
+
+ bool operator==(const Iterator& other) const {
+ return heap == other.heap && index == other.index;
+ }
+
+ bool operator!=(const Iterator& other) const {
+ return !(*this == other);
+ }
+
+ T& operator*() {
+ return *heap->data[index];
+ }
+
+ T* operator->() {
+ return &(*heap->data[index]);
+ }
+
+#if 0
+ // the item this iterator refers to
+ void increase() {
+ heap.sift_up(index);
+ }
+#endif
+ }; // class Iterator
+
+
+ class ConstIterator {
+ friend IndIntruHeap<I, T, heap_info, C, K>;
+
+ const IndIntruHeap<I, T, heap_info, C, K>* heap;
+ HeapIndex index;
+
+ ConstIterator(const IndIntruHeap<I, T, heap_info, C, K>& _heap,
+ HeapIndex _index) :
+ heap(&_heap),
+ index(_index)
+ {
+ // empty
+ }
+
+ public:
+
+ ConstIterator(ConstIterator&& other) :
+ heap(other.heap),
+ index(other.index)
+ {
+ // empty
+ }
+
+ ConstIterator(const ConstIterator& other) :
+ heap(other.heap),
+ index(other.index)
+ {
+ // empty
+ }
+
+ ConstIterator& operator=(ConstIterator&& other) {
+ std::swap(heap, other.heap);
+ std::swap(index, other.index);
+ return *this;
+ }
+
+ ConstIterator& operator=(const ConstIterator& other) {
+ heap = other.heap;
+ index = other.index;
+ }
+
+ ConstIterator& operator++() {
+ if (index <= heap->count) {
+ ++index;
+ }
+ return *this;
+ }
+
+ bool operator==(const ConstIterator& other) const {
+ return heap == other.heap && index == other.index;
+ }
+
+ bool operator!=(const ConstIterator& other) const {
+ return !(*this == other);
+ }
+
+ const T& operator*() {
+ return *heap->data[index];
+ }
+
+ const T* operator->() {
+ return &(*heap->data[index]);
+ }
+ }; // class ConstIterator
+
+
+ protected:
+
+ std::vector<I> data;
+ HeapIndex count;
+ C comparator;
+
+ public:
+
+ IndIntruHeap() :
+ count(0)
+ {
+ // empty
+ }
+
+ IndIntruHeap(const IndIntruHeap<I,T,heap_info,C,K>& other) :
+ count(other.count)
+ {
+ for (HeapIndex i = 0; i < other.count; ++i) {
+ data.push_back(other.data[i]);
+ }
+ }
+
+ bool empty() const { return 0 == count; }
+
+ size_t size() const { return (size_t) count; }
+
+ T& top() { return *data[0]; }
+
+ const T& top() const { return *data[0]; }
+
+ I& top_ind() { return data[0]; }
+
+ const I& top_ind() const { return data[0]; }
+
+ void push(I&& item) {
+ HeapIndex i = count++;
+ intru_data_of(item) = i;
+ data.emplace_back(std::move(item));
+ sift_up(i);
+ }
+
+ void push(const I& item) {
+ I copy(item);
+ push(std::move(copy));
+ }
+
+ void pop() {
+ remove(HeapIndex(0));
+ }
+
+ void remove(Iterator& i) {
+ remove(i.index);
+ i = end();
+ }
+
+ Iterator find(const I& ind_item) {
+ for (HeapIndex i = 0; i < count; ++i) {
+ if (data[i] == ind_item) {
+ return Iterator(*this, i);
+ }
+ }
+ return end();
+ }
+
+ // when passing in value we do a comparison via operator==
+ Iterator find(const T& item) {
+ for (HeapIndex i = 0; i < count; ++i) {
+ if (*data[i] == item) {
+ return Iterator(*this, i);
+ }
+ }
+ return end();
+ }
+
+ // reverse find -- start looking from bottom of heap
+ Iterator rfind(const I& ind_item) {
+ // HeapIndex is unsigned, so we can't allow to go negative; so
+ // we'll keep it one more than actual index
+ for (HeapIndex i = count; i > 0; --i) {
+ if (data[i-1] == ind_item) {
+ return Iterator(*this, i-1);
+ }
+ }
+ return end();
+ }
+
+ // reverse find -- start looking from bottom of heap
+ Iterator rfind(const T& item) {
+ // HeapIndex is unsigned, so we can't allow to go negative; so
+ // we'll keep it one more than actual index
+ for (HeapIndex i = count; i > 0; --i) {
+ if (*data[i-1] == item) {
+ return Iterator(*this, i-1);
+ }
+ }
+ return end();
+ }
+
+ ConstIterator find(const I& ind_item) const {
+ for (HeapIndex i = 0; i < count; ++i) {
+ if (data[i] == ind_item) {
+ return ConstIterator(*this, i);
+ }
+ }
+ return cend();
+ }
+
+ // when passing in value we do a comparison via operator==
+ ConstIterator find(const T& item) const {
+ for (HeapIndex i = 0; i < count; ++i) {
+ if (*data[i] == item) {
+ return ConstIterator(*this, i);
+ }
+ }
+ return cend();
+ }
+
+ // reverse find -- start looking from bottom of heap
+ ConstIterator rfind(const I& ind_item) const {
+ // HeapIndex is unsigned, so we can't allow to go negative; so
+ // we'll keep it one more than actual index
+ for (HeapIndex i = count; i > 0; --i) {
+ if (data[i-1] == ind_item) {
+ return ConstIterator(*this, i-1);
+ }
+ }
+ return cend();
+ }
+
+ // reverse find -- start looking from bottom of heap
+ ConstIterator rfind(const T& item) const {
+ // HeapIndex is unsigned, so we can't allow to go negative; so
+ // we'll keep it one more than actual index
+ for (HeapIndex i = count; i > 0; --i) {
+ if (*data[i-1] == item) {
+ return ConstIterator(*this, i-1);
+ }
+ }
+ return cend();
+ }
+
+ Iterator at(const I& ind_item) {
+ auto ind = intru_data_of(ind_item);
+ if (ind >= count) {
+ throw std::out_of_range(
+ std::to_string(ind) + " >= " + std::to_string(count));
+ }
+ assert(data[ind] == ind_item);
+ return Iterator(*this, ind);
+ }
+
+ void promote(T& item) {
+ sift_up(item.*heap_info);
+ }
+
+ void demote(T& item) {
+ sift_down(item.*heap_info);
+ }
+
+ void adjust(T& item) {
+ sift(item.*heap_info);
+ }
+
+ Iterator begin() {
+ return Iterator(*this, 0);
+ }
+
+ Iterator end() {
+ return Iterator(*this, count);
+ }
+
+ ConstIterator cbegin() const {
+ return ConstIterator(*this, 0);
+ }
+
+ ConstIterator cend() const {
+ return ConstIterator(*this, count);
+ }
+
+ friend std::ostream& operator<<(std::ostream& out, const IndIntruHeap& h) {
+ auto i = h.data.cbegin();
+ if (i != h.data.cend()) {
+ out << **i;
+ ++i;
+ while (i != h.data.cend()) {
+ out << ", " << **i;
+ }
+ }
+ return out;
+ }
+
+ // can only be called if I is copiable; copies heap into a vector
+ // and sorts it before displaying it
+ std::ostream&
+ display_sorted(std::ostream& out,
+ std::function<bool(const T&)> filter = all_filter) const {
+ static_assert(std::is_copy_constructible<I>::value,
+ "cannot call display_sorted when class I is not copy"
+ " constructible");
+ auto compare = [this] (const I first, const I second) -> bool {
+ return this->comparator(*first, *second);
+ };
+ std::vector<I> copy(data);
+ std::sort(copy.begin(), copy.end(), compare);
+
+ bool first = true;
+ for (auto c = copy.begin(); c != copy.end(); ++c) {
+ if (filter(**c)) {
+ if (!first) {
+ out << ", ";
+ } else {
+ first = false;
+ }
+ out << **c;
+ }
+ }
+
+ return out;
+ }
+
+
+ protected:
+
+ static IndIntruHeapData& intru_data_of(const I& item) {
+ return (*item).*heap_info;
+ }
+
+ void remove(HeapIndex i) {
+ std::swap(data[i], data[--count]);
+ intru_data_of(data[i]) = i;
+
+ // the following needs to be sift (and not sift_down) as it can
+ // go up or down the heap; imagine the heap vector contains 0,
+ // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
+ // would have to be sifted upwards
+ // sift(i);
+ sift(i);
+
+ data.pop_back();
+ }
+
+ // default value of filter parameter to display_sorted
+ static bool all_filter(const T& data) { return true; }
+
+ // when i is negative?
+ static inline HeapIndex parent(HeapIndex i) {
+ assert(0 != i);
+ return (i - 1) / K;
+ }
+
+ // index of left child when K==2, index of left-most child when K>2
+ static inline HeapIndex lhs(HeapIndex i) { return K*i + 1; }
+
+ // index of right child when K==2, index of right-most child when K>2
+ static inline HeapIndex rhs(HeapIndex i) { return K*i + K; }
+
+ void sift_up(HeapIndex i) {
+ while (i > 0) {
+ HeapIndex pi = parent(i);
+ if (!comparator(*data[i], *data[pi])) {
+ break;
+ }
+
+ std::swap(data[i], data[pi]);
+ intru_data_of(data[i]) = i;
+ intru_data_of(data[pi]) = pi;
+ i = pi;
+ }
+ } // sift_up
+
+ // use this sift_down definition when K>2; it's more general and
+ // uses a loop; EnableBool insures template uses a template
+ // parameter
+ template<bool EnableBool=true>
+ typename std::enable_if<(K>2)&&EnableBool,void>::type sift_down(HeapIndex i) {
+ if (i >= count) return;
+ while (true) {
+ HeapIndex li = lhs(i);
+
+ if (li < count) {
+ HeapIndex ri = std::min(rhs(i), count - 1);
+
+ // find the index of min. child
+ HeapIndex min_i = li;
+ for (HeapIndex k = li + 1; k <= ri; ++k) {
+ if (comparator(*data[k], *data[min_i])) {
+ min_i = k;
+ }
+ }
+
+ if (comparator(*data[min_i], *data[i])) {
+ std::swap(data[i], data[min_i]);
+ intru_data_of(data[i]) = i;
+ intru_data_of(data[min_i]) = min_i;
+ i = min_i;
+ } else {
+ // no child is smaller
+ break;
+ }
+ } else {
+ // no children
+ break;
+ }
+ }
+ } // sift_down
+
+ // use this sift_down definition when K==2; EnableBool insures
+ // template uses a template parameter
+ template<bool EnableBool=true>
+ typename std::enable_if<K==2&&EnableBool,void>::type sift_down(HeapIndex i) {
+ if (i >= count) return;
+ while (true) {
+ const HeapIndex li = lhs(i);
+ const HeapIndex ri = 1 + li;
+
+ if (li < count) {
+ if (comparator(*data[li], *data[i])) {
+ if (ri < count && comparator(*data[ri], *data[li])) {
+ std::swap(data[i], data[ri]);
+ intru_data_of(data[i]) = i;
+ intru_data_of(data[ri]) = ri;
+ i = ri;
+ } else {
+ std::swap(data[i], data[li]);
+ intru_data_of(data[i]) = i;
+ intru_data_of(data[li]) = li;
+ i = li;
+ }
+ } else if (ri < count && comparator(*data[ri], *data[i])) {
+ std::swap(data[i], data[ri]);
+ intru_data_of(data[i]) = i;
+ intru_data_of(data[ri]) = ri;
+ i = ri;
+ } else {
+ // no child is smaller
+ break;
+ }
+ } else {
+ // no children
+ break;
+ }
+ } // while
+ } // sift_down
+
+ void sift(HeapIndex i) {
+ if (i == 0) {
+ // if we're at top, can only go down
+ sift_down(i);
+ } else {
+ HeapIndex pi = parent(i);
+ if (comparator(*data[i], *data[pi])) {
+ // if we can go up, we will
+ sift_up(i);
+ } else {
+ // otherwise we'll try to go down
+ sift_down(i);
+ }
+ }
+ } // sift
+ }; // class IndIntruHeap
+
+} // namespace crimson
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-23 09:46:05 +0000