summaryrefslogtreecommitdiffstats
path: root/src/dmclock/support
diff options
context:
space:
mode:
Diffstat (limited to 'src/dmclock/support')
-rw-r--r--src/dmclock/support/src/debug.h24
-rw-r--r--src/dmclock/support/src/heap.h247
-rw-r--r--src/dmclock/support/src/indirect_intrusive_heap.h567
-rw-r--r--src/dmclock/support/src/intrusive_heap.h221
-rw-r--r--src/dmclock/support/src/profile.h121
-rw-r--r--src/dmclock/support/src/run_every.cc94
-rw-r--r--src/dmclock/support/src/run_every.h81
-rw-r--r--src/dmclock/support/test/CMakeLists.txt26
-rw-r--r--src/dmclock/support/test/test_ind_intru_heap.cc89
-rw-r--r--src/dmclock/support/test/test_indirect_intrusive_heap.cc1022
-rw-r--r--src/dmclock/support/test/test_intrusive_heap.cc93
11 files changed, 2585 insertions, 0 deletions
diff --git a/src/dmclock/support/src/debug.h b/src/dmclock/support/src/debug.h
new file mode 100644
index 000000000..d8e6713fd
--- /dev/null
+++ b/src/dmclock/support/src/debug.h
@@ -0,0 +1,24 @@
+// -*- 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 <signal.h>
+
+
+inline void debugger() {
+ raise(SIGCONT);
+}
diff --git a/src/dmclock/support/src/heap.h b/src/dmclock/support/src/heap.h
new file mode 100644
index 000000000..6a1f9963a
--- /dev/null
+++ b/src/dmclock/support/src/heap.h
@@ -0,0 +1,247 @@
+// -*- 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 <vector>
+#include <ostream>
+
+#include "assert.h"
+
+
+namespace crimson {
+
+ /*
+ * T : type of data held in the heap.
+ *
+ * C : class that implements operator() with two arguments and
+ * returns a boolean when the first argument is greater than (higher
+ * in priority than) the second.
+ */
+ template<typename T, typename C>
+ class Heap {
+
+ public:
+
+ class iterator {
+
+ friend Heap<T,C>;
+
+ Heap<T,C>& heap;
+ int index;
+
+ iterator(Heap<T,C>& _heap, int _index) :
+ heap(_heap),
+ index(_index)
+ {
+ // empty
+ }
+
+ public:
+
+ iterator(iterator&& other) :
+ heap(other.heap),
+ index(other.index)
+ {
+ // empty
+ }
+
+ iterator& operator++() {
+ ++index;
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const {
+ return index == other.index;
+ }
+
+ bool operator!=(const iterator& other) const {
+ return !(*this == other);
+ }
+
+ T& operator*() {
+ return heap.data[index];
+ }
+
+ // the item this iterator refers to
+ void increase() {
+ heap.siftUp(index);
+ }
+ }; // class iterator
+
+ friend iterator;
+
+ protected:
+
+ std::vector<T> data;
+ int count;
+ C comparator;
+
+ // parent(0) should be a negative value, which it is due to
+ // truncating towards negative infinity
+ static inline int parent(int i) { return (i - 1) / 2; }
+
+ static inline int lhs(int i) { return 2*i + 1; }
+
+ static inline int rhs(int i) { return 2*i + 2; }
+
+ void siftUp(int i) {
+ assert(i < count);
+
+ while (i > 0) {
+ int pi = parent(i);
+ if (!comparator(data[i], data[pi])) {
+ break;
+ }
+
+ std::swap(data[i], data[pi]);
+ i = pi;
+ }
+ }
+
+ void siftDown(int i) {
+ while (i < count) {
+ int li = lhs(i);
+ int ri = rhs(i);
+
+ if (li < count) {
+ if (comparator(data[li], data[i])) {
+ if (ri < count && comparator(data[ri], data[li])) {
+ std::swap(data[i], data[ri]);
+ i = ri;
+ } else {
+ std::swap(data[i], data[li]);
+ i = li;
+ }
+ } else if (ri < count && comparator(data[ri], data[i])) {
+ std::swap(data[i], data[ri]);
+ i = ri;
+ } else {
+ break;
+ }
+ } else {
+ break;
+ }
+ }
+ }
+
+
+ public:
+
+ Heap() :
+ count(0)
+ {
+ // empty
+ }
+
+ Heap(const Heap<T,C>& other) {
+ data.resize(other.data.size());
+ for (int i = 0; i < other.count; ++i) {
+ data[i] = other.data[i];
+ }
+ count = other.count;
+ }
+
+ const Heap<T,C>& operator=(const Heap<T,C>& other) {
+ data.resize(other.data.size());
+ for (int i = 0; i < other.count; ++i) {
+ data[i] = other.data[i];
+ }
+ count = other.count;
+ return *this;
+ }
+
+ bool empty() const { return 0 == count; }
+
+ T& top() { return data[0]; }
+
+ void push(T item) {
+ int i = count++;
+ data.push_back(item);
+ siftUp(i);
+ }
+
+ void pop() {
+ data[0] = data[--count];
+ data.resize(count);
+ siftDown(0);
+ }
+
+ void updateTop() {
+ siftDown(0);
+ }
+
+ void clear() {
+ count = 0;
+ data.resize(0);
+ }
+
+ iterator begin() {
+ return iterator(*this, 0);
+ }
+
+ iterator end() {
+ return iterator(*this, count);
+ }
+
+ std::ostream& displaySorted(std::ostream& out,
+ std::function<bool(const T&)> filter,
+ bool insert_line_breaks = true) const {
+ Heap<T,C> temp = *this;
+
+ bool first = true;
+ out << "[ ";
+
+ while(!temp.empty()) {
+ const T& top = temp.top();
+ if (filter(top)) {
+ if (!first) {
+ out << ", ";
+ }
+ if (insert_line_breaks) {
+ out << std::endl << " ";
+ }
+ out << temp.top();
+ first = false;
+ }
+ temp.pop();
+ }
+
+ out << " ]";
+ if (insert_line_breaks) {
+ out << std::endl;
+ }
+ return out;
+ }
+
+ template<typename T1, typename T2>
+ friend std::ostream& operator<<(std::ostream&, const Heap<T1,T2>&);
+ }; // class Heap
+
+
+ template<typename T1, typename T2>
+ std::ostream& operator<<(std::ostream& out, const Heap<T1,T2>& h) {
+ out << "[ ";
+ if (h.count) {
+ out << h.data[0];
+ }
+ for (int i = 1; i < h.count; i++) {
+ out << ", " << h.data[i];
+ }
+ out << " ]";
+ return out;
+ }
+} // namespace
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
diff --git a/src/dmclock/support/src/intrusive_heap.h b/src/dmclock/support/src/intrusive_heap.h
new file mode 100644
index 000000000..21d3ea9a0
--- /dev/null
+++ b/src/dmclock/support/src/intrusive_heap.h
@@ -0,0 +1,221 @@
+// -*- 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 <vector>
+#include <string>
+#include <iostream>
+#include <functional>
+
+#include "assert.h"
+
+
+namespace crimson {
+ using IntruHeapData = size_t;
+
+ // T = type of data in heap; I = functor that returns a non-const
+ // reference to IntruHeapData; C = functor that compares two const
+ // refs and return true if the first precedes the second
+ template<typename T, typename I, typename C>
+ class IntruHeap {
+
+ static_assert(
+ std::is_same<IntruHeapData&,typename std::result_of<I(T&)>::type>::value,
+ "class I must define operator() to take T& and return a IntruHeapData&.");
+
+ 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.");
+
+
+ protected:
+ using index_t = IntruHeapData;
+
+ std::vector<T> data;
+ index_t count;
+ I intru_data_of;
+ C comparator;
+
+ public:
+
+ IntruHeap() :
+ count(0)
+ {
+ // empty
+ }
+
+ IntruHeap(const IntruHeap<T,I,C>& other) :
+ count(other.count)
+ {
+ for (uint i = 0; i < other.count; ++i) {
+ data.push_back(other.data[i]);
+ }
+ }
+
+ bool empty() const { return 0 == count; }
+
+ T& top() { return data[0]; }
+
+ void push(T&& item) {
+ index_t i = count++;
+ intru_data_of(item) = i;
+ data.emplace_back(item);
+ sift_up(i);
+ }
+
+ void push(const T& item) {
+ T copy(item);
+ push(std::move(copy));
+ }
+
+ void pop() {
+ std::swap(data[0], data[--count]);
+ intru_data_of(data[0]) = 0;
+ data.pop_back();
+ sift_down(0);
+ }
+
+ void adjust_up(T& item) {
+ sift_up(intru_data_of(item));
+ }
+
+ void adjust_down(T& item) {
+ sift_down(intru_data_of(item));
+ }
+
+ void adjust(T& item) {
+ sift(intru_data_of(item));
+ }
+
+ friend std::ostream& operator<<(std::ostream& out, const IntruHeap& h) {
+ for (uint i = 0; i < h.count; ++i) {
+ out << h.data[i] << ", ";
+ }
+ return out;
+ }
+
+ std::ostream&
+ display_sorted(std::ostream& out,
+ bool insert_line_breaks = true,
+ std::function<bool(const T&)> filter = all_filter) const {
+ IntruHeap<T,I,C> copy = *this;
+
+ bool first = true;
+ out << "[ ";
+
+ while(!copy.empty()) {
+ const T& top = copy.top();
+ if (filter(top)) {
+ if (!first) {
+ out << ", ";
+ }
+ if (insert_line_breaks) {
+ out << std::endl << " ";
+ }
+ out << copy.top();
+ first = false;
+ }
+ copy.pop();
+ }
+
+ out << " ]";
+ if (insert_line_breaks) {
+ out << std::endl;
+ }
+
+ return out;
+ }
+
+
+ protected:
+
+ // default value of filter parameter to display_sorted
+ static bool all_filter(const T& data) { return true; }
+
+ // when i is negative?
+ static inline index_t parent(index_t i) {
+ assert(0 != i);
+ return (i - 1) / 2;
+ }
+
+ static inline index_t lhs(index_t i) { return 2*i + 1; }
+
+ static inline index_t rhs(index_t i) { return 2*i + 2; }
+
+ void sift_up(index_t i) {
+ while (i > 0) {
+ index_t 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
+
+ void sift_down(index_t i) {
+ while (i < count) {
+ index_t li = lhs(i);
+ index_t ri = rhs(i);
+
+ 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 {
+ break;
+ }
+ } else {
+ break;
+ }
+ }
+ } // sift_down
+
+ void sift(index_t i) {
+ if (i == 0) {
+ // if we're at top, can only go down
+ sift_down(i);
+ } else {
+ index_t 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 IntruHeap
+} // namespace crimson
diff --git a/src/dmclock/support/src/profile.h b/src/dmclock/support/src/profile.h
new file mode 100644
index 000000000..8b357dbfc
--- /dev/null
+++ b/src/dmclock/support/src/profile.h
@@ -0,0 +1,121 @@
+// -*- 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 <cmath>
+#include <chrono>
+
+
+namespace crimson {
+ template<typename T>
+ class ProfileBase {
+
+ protected:
+
+ using clock = std::chrono::steady_clock;
+
+ uint count = 0;
+ typename T::rep sum = 0;
+ typename T::rep sum_squares = 0;
+ typename T::rep low = 0;
+ typename T::rep high = 0;
+
+ public:
+
+ uint get_count() const { return count; }
+ typename T::rep get_sum() const { return sum; }
+ typename T::rep get_low() const { return low; }
+ typename T::rep get_high() const { return high; }
+ double get_mean() const {
+ if (0 == count) return nan("");
+ return sum / double(count); }
+ double get_std_dev() const {
+ if (0 == count) return nan("");
+ double variance =
+ (count * sum_squares - sum * sum) / double(count * count);
+ return sqrt(variance);
+ }
+ }; // class ProfileBase
+
+
+ // forward declaration for friend
+ template<typename T>
+ class ProfileCombiner;
+
+
+ template<typename T>
+ class ProfileTimer : public ProfileBase<T> {
+ friend ProfileCombiner<T>;
+
+ using super = ProfileBase<T>;
+
+ bool is_timing = false;
+ typename super::clock::time_point start_time;
+
+ public:
+
+ ProfileTimer() {
+ }
+
+ void start() {
+ assert(!is_timing);
+ start_time = super::clock::now();
+ is_timing = true;
+ }
+
+ void stop() {
+ assert(is_timing);
+ T duration = std::chrono::duration_cast<T>(super::clock::now() - start_time);
+ typename T::rep duration_count = duration.count();
+ this->sum += duration_count;
+ this->sum_squares += duration_count * duration_count;
+ if (0 == this->count) {
+ this->low = duration_count;
+ this->high = duration_count;
+ } else {
+ if (duration_count < this->low) this->low = duration_count;
+ else if (duration_count > this->high) this->high = duration_count;
+ }
+ ++this->count;
+ is_timing = false;
+ }
+ }; // class ProfileTimer
+
+
+ template<typename T>
+ class ProfileCombiner : public ProfileBase<T> {
+
+ using super = ProfileBase<T>;
+
+ public:
+
+ ProfileCombiner() {}
+
+ void combine(const ProfileTimer<T>& timer) {
+ if (0 == this->count) {
+ this->low = timer.low;
+ this->high = timer.high;
+ } else {
+ if (timer.low < this->low) this->low = timer.low;
+ else if (timer.high > this->high) this->high = timer.high;
+ }
+ this->count += timer.count;
+ this->sum += timer.sum;
+ this->sum_squares += timer.sum_squares;
+ }
+ }; // class ProfileCombiner
+} // namespace crimson
diff --git a/src/dmclock/support/src/run_every.cc b/src/dmclock/support/src/run_every.cc
new file mode 100644
index 000000000..14f1452b9
--- /dev/null
+++ b/src/dmclock/support/src/run_every.cc
@@ -0,0 +1,94 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+/*
+ * Copyright (C) 2017 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.
+ */
+
+
+#include "run_every.h"
+
+
+// can define ADD_MOVE_SEMANTICS, although not fully debugged and tested
+
+
+namespace chrono = std::chrono;
+
+
+#ifdef ADD_MOVE_SEMANTICS
+crimson::RunEvery::RunEvery()
+{
+ // empty
+}
+
+
+crimson::RunEvery& crimson::RunEvery::operator=(crimson::RunEvery&& other)
+{
+ // finish run every thread
+ {
+ Guard g(mtx);
+ finishing = true;
+ cv.notify_one();
+ }
+ if (thd.joinable()) {
+ thd.join();
+ }
+
+ // transfer info over from previous thread
+ finishing.store(other.finishing);
+ wait_period = other.wait_period;
+ body = other.body;
+
+ // finish other thread
+ other.finishing.store(true);
+ other.cv.notify_one();
+
+ // start this thread
+ thd = std::thread(&RunEvery::run, this);
+
+ return *this;
+}
+#endif
+
+
+crimson::RunEvery::~RunEvery() {
+ join();
+}
+
+
+void crimson::RunEvery::join() {
+ {
+ Guard l(mtx);
+ if (finishing) return;
+ finishing = true;
+ cv.notify_all();
+ }
+ thd.join();
+}
+
+// mtx must be held by caller
+void crimson::RunEvery::try_update(milliseconds _wait_period) {
+ if (_wait_period != wait_period) {
+ wait_period = _wait_period;
+ }
+}
+
+void crimson::RunEvery::run() {
+ Lock l(mtx);
+ while(!finishing) {
+ TimePoint until = chrono::steady_clock::now() + wait_period;
+ while (!finishing && chrono::steady_clock::now() < until) {
+ cv.wait_until(l, until);
+ }
+ if (!finishing) {
+ body();
+ }
+ }
+}
diff --git a/src/dmclock/support/src/run_every.h b/src/dmclock/support/src/run_every.h
new file mode 100644
index 000000000..f93961db1
--- /dev/null
+++ b/src/dmclock/support/src/run_every.h
@@ -0,0 +1,81 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+/*
+ * Copyright (C) 2017 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 <chrono>
+#include <mutex>
+#include <condition_variable>
+#include <thread>
+#include <functional>
+
+
+namespace crimson {
+ using std::chrono::duration_cast;
+ using std::chrono::milliseconds;
+
+ // runs a given simple function object waiting wait_period
+ // milliseconds between; the destructor stops the other thread
+ // immediately
+ class RunEvery {
+ using Lock = std::unique_lock<std::mutex>;
+ using Guard = std::lock_guard<std::mutex>;
+ using TimePoint = std::chrono::steady_clock::time_point;
+
+ bool finishing = false;
+ std::chrono::milliseconds wait_period;
+ std::function<void()> body;
+ std::mutex mtx;
+ std::condition_variable cv;
+
+ // put threads last so all other variables are initialized first
+
+ std::thread thd;
+
+ public:
+
+#ifdef ADD_MOVE_SEMANTICS
+ RunEvery();
+#endif
+
+ template<typename D>
+ RunEvery(D _wait_period,
+ const std::function<void()>& _body) :
+ wait_period(duration_cast<milliseconds>(_wait_period)),
+ body(_body)
+ {
+ thd = std::thread(&RunEvery::run, this);
+ }
+
+ RunEvery(const RunEvery& other) = delete;
+ RunEvery& operator=(const RunEvery& other) = delete;
+ RunEvery(RunEvery&& other) = delete;
+#ifdef ADD_MOVE_SEMANTICS
+ RunEvery& operator=(RunEvery&& other);
+#else
+ RunEvery& operator=(RunEvery&& other) = delete;
+#endif
+
+ ~RunEvery();
+
+ void join();
+ // update wait period in milliseconds
+ void try_update(milliseconds _wait_period);
+
+ protected:
+
+ void run();
+ };
+}
diff --git a/src/dmclock/support/test/CMakeLists.txt b/src/dmclock/support/test/CMakeLists.txt
new file mode 100644
index 000000000..24b352157
--- /dev/null
+++ b/src/dmclock/support/test/CMakeLists.txt
@@ -0,0 +1,26 @@
+include_directories(../src)
+
+set(local_flags "-Wall -pthread")
+
+# dmclock does not use intrusive heap (but it does use indirect
+# intrusive heap), so we won't use this code
+if(false)
+ set(srcs
+ test_intrusive_heap.cc)
+ add_executable(test_intru_heap test_intrusive_heap.cc)
+ set_source_files_properties(${srcs}
+ PROPERTIES
+ COMPILE_FLAGS "${local_flags}")
+endif(false)
+
+set(test_srcs test_indirect_intrusive_heap.cc)
+
+set_source_files_properties(${test_srcs}
+ PROPERTIES
+ COMPILE_FLAGS "${local_flags}"
+ )
+
+add_executable(dmclock-data-struct-tests ${test_srcs})
+
+target_link_libraries(dmclock-data-struct-tests
+ LINK_PRIVATE GTest::GTest GTest::Main Threads::Threads)
diff --git a/src/dmclock/support/test/test_ind_intru_heap.cc b/src/dmclock/support/test/test_ind_intru_heap.cc
new file mode 100644
index 000000000..8e7ee6931
--- /dev/null
+++ b/src/dmclock/support/test/test_ind_intru_heap.cc
@@ -0,0 +1,89 @@
+// -*- 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.
+ */
+
+
+#include <memory>
+#include <string>
+#include <iostream>
+
+#include "indirect_intrusive_heap.h"
+
+
+class TestCompare;
+
+
+class Test1 {
+ friend TestCompare;
+
+ int data;
+
+public:
+
+ crimson::IndIntruHeapData heap_data;
+
+ explicit Test1(int _data) : data(_data) {}
+
+ friend std::ostream& operator<<(std::ostream& out, const Test1& d) {
+ out << d.data << " (" << d.heap_data << ")";
+ return out;
+ }
+
+ int& the_data() { return data; }
+};
+
+
+struct TestCompare {
+ bool operator()(const Test1& d1, const Test1& d2) {
+ return d1.data < d2.data;
+ }
+};
+
+
+int main(int argc, char** argv) {
+ Test1 d1(2);
+ Test1 d2(3);
+ Test1 d3(1);
+ Test1 d4(-5);
+
+ crimson::IndIntruHeap<std::shared_ptr<Test1>, Test1, &Test1::heap_data, TestCompare> my_heap;
+
+ const std::shared_ptr<Test1> d99 = std::make_shared<Test1>(99);
+
+ my_heap.push(std::make_shared<Test1>(2));
+ my_heap.push(d99);
+ my_heap.push(std::make_shared<Test1>(1));
+ my_heap.push(std::make_shared<Test1>(-5));
+ my_heap.push(std::make_shared<Test1>(12));
+ my_heap.push(std::make_shared<Test1>(-12));
+ my_heap.push(std::make_shared<Test1>(-7));
+
+ std::cout << my_heap << std::endl;
+
+ auto& t = my_heap.top();
+ t.the_data() = 17;
+ my_heap.adjust_down(t);
+
+ std::cout << my_heap << std::endl;
+
+ my_heap.display_sorted(std::cout);
+
+ while (!my_heap.empty()) {
+ auto& top = my_heap.top();
+ std::cout << top << std::endl;
+ my_heap.pop();
+ std::cout << my_heap << std::endl;
+ }
+
+ return 0;
+}
diff --git a/src/dmclock/support/test/test_indirect_intrusive_heap.cc b/src/dmclock/support/test/test_indirect_intrusive_heap.cc
new file mode 100644
index 000000000..e74c3181e
--- /dev/null
+++ b/src/dmclock/support/test/test_indirect_intrusive_heap.cc
@@ -0,0 +1,1022 @@
+// -*- 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.
+ */
+
+
+#include <iostream>
+#include <memory>
+#include <set>
+#include <algorithm>
+#include <random>
+
+#include "gtest/gtest.h"
+
+#include "indirect_intrusive_heap.h"
+
+
+struct Elem {
+ int data;
+
+ crimson::IndIntruHeapData heap_data;
+ crimson::IndIntruHeapData heap_data_alt;
+
+ explicit Elem(int _data) : data(_data) { }
+
+ bool operator==(const Elem& other) const {
+ return data == other.data;
+ }
+
+ bool operator<(const Elem& other) const {
+ return data < other.data;
+ }
+
+ friend std::ostream& operator<<(std::ostream& out, const Elem& d) {
+ out << d.data;
+ return out;
+ }
+};
+
+
+// sorted low to high
+struct ElemCompare {
+ bool operator()(const Elem& d1, const Elem& d2) const {
+ return d1.data < d2.data;
+ }
+};
+
+
+// first all evens precede all odds, then they're sorted high to low
+struct ElemCompareAlt {
+ bool operator()(const Elem& d1, const Elem& d2) {
+ if (0 == d1.data % 2) {
+ if (0 == d2.data % 2) {
+ return d1.data > d2.data;
+ } else {
+ return true;
+ }
+ } else if (0 == d2.data % 2) {
+ return false;
+ } else {
+ return d1.data > d2.data;
+ }
+ }
+};
+
+
+class HeapFixture1: public ::testing::Test {
+
+public:
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ std::shared_ptr<Elem> data1, data2, data3, data4, data5, data6, data7;
+
+ void SetUp() {
+ data1 = std::make_shared<Elem>(2);
+ data2 = std::make_shared<Elem>(99);
+ data3 = std::make_shared<Elem>(1);
+ data4 = std::make_shared<Elem>(-5);
+ data5 = std::make_shared<Elem>(12);
+ data6 = std::make_shared<Elem>(-12);
+ data7 = std::make_shared<Elem>(-7);
+
+ heap.push(data1);
+ heap.push(data2);
+ heap.push(data3);
+ heap.push(data4);
+ heap.push(data5);
+ heap.push(data6);
+ heap.push(data7);
+ }
+
+ void TearDown() {
+ // nothing to do
+ }
+}; // class HeapFixture1
+
+TEST(IndIntruHeap, shared_ptr) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(2));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(std::make_shared<Elem>(1));
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ // std::cout << heap << std::endl;
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, unique_ptr) {
+ crimson::IndIntruHeap<std::unique_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(std::unique_ptr<Elem>(new Elem(2)));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(std::unique_ptr<Elem>(new Elem(99)));
+ heap.push(std::unique_ptr<Elem>(new Elem(1)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-5)));
+ heap.push(std::unique_ptr<Elem>(new Elem(12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-7)));
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, regular_ptr) {
+ crimson::IndIntruHeap<Elem*, Elem, &Elem::heap_data, ElemCompare> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(new Elem(2));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(new Elem(99));
+ heap.push(new Elem(1));
+ heap.push(new Elem(-5));
+ heap.push(new Elem(12));
+ heap.push(new Elem(-12));
+ heap.push(new Elem(-7));
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(-7, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(-5, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(1, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(2, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(12, heap.top().data);
+ {
+ auto i = &heap.top();
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_EQ(99, heap.top().data);
+ {
+ auto i = &heap.top();
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ delete i;
+ }
+
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, K_3) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 3> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(2));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(std::make_shared<Elem>(1));
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ // std::cout << heap << std::endl;
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, K_4) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 4> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(2));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(std::make_shared<Elem>(1));
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ // std::cout << heap << std::endl;
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, K_10) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 10> heap;
+
+ EXPECT_TRUE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(2));
+
+ EXPECT_FALSE(heap.empty());
+
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(std::make_shared<Elem>(1));
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ // std::cout << heap << std::endl;
+
+ EXPECT_FALSE(heap.empty());
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_FALSE(heap.empty());
+ heap.pop();
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST(IndIntruHeap, multi_K) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 2> heap2;
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 3> heap3;
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 4> heap4;
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 10> heap10;
+
+ // 250 should give us at least 4 levels on all heaps
+ constexpr size_t count = 250;
+
+ std::srand(std::time(0)); // use current time as seed for random generator
+
+ // insert same set of random values into the four heaps
+ for (size_t i = 0; i < count; ++i) {
+ int value = std::rand() % 201 - 100; // -100...+100
+ auto data = std::make_shared<Elem>(value);
+ heap2.push(data);
+ heap3.push(data);
+ heap4.push(data);
+ heap10.push(data);
+ }
+
+ auto bound = std::numeric_limits<decltype(Elem::data)>::min();
+
+ for (size_t i = 0; i < count; ++i) {
+ auto current = heap2.top().data;
+
+ EXPECT_GE(current, bound) <<
+ "we should never go down, only increase or remain the same";
+ EXPECT_EQ(current, heap3.top().data) <<
+ "heap1's data and heap3's data should match";
+ EXPECT_EQ(current, heap4.top().data) <<
+ "heap1's data and heap4's data should match";
+ EXPECT_EQ(current, heap10.top().data) <<
+ "heap1's data and heap10's data should match";
+
+ heap2.pop();
+ heap3.pop();
+ heap4.pop();
+ heap10.pop();
+
+ bound = current;
+ }
+
+ EXPECT_TRUE(heap2.empty()) << "should be empty after all elements popped";
+ EXPECT_TRUE(heap3.empty()) << "should be empty after all elements popped";
+ EXPECT_TRUE(heap4.empty()) << "should be empty after all elements popped";
+ EXPECT_TRUE(heap10.empty()) << "should be empty after all elements popped";
+}
+
+
+TEST(IndIntruHeap, demote) {
+ crimson::IndIntruHeap<std::unique_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ heap.push(std::unique_ptr<Elem>(new Elem(2)));
+ heap.push(std::unique_ptr<Elem>(new Elem(99)));
+ heap.push(std::unique_ptr<Elem>(new Elem(1)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-5)));
+ heap.push(std::unique_ptr<Elem>(new Elem(12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-7)));
+
+ heap.top().data = 24;
+
+ heap.demote(heap.top());
+
+ EXPECT_EQ(-7, heap.top().data);
+
+ heap.pop();
+ heap.pop();
+ heap.pop();
+ heap.pop();
+ heap.pop();
+
+ EXPECT_EQ(24, heap.top().data);
+}
+
+
+TEST(IndIntruHeap, demote_not) {
+ crimson::IndIntruHeap<std::unique_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ heap.push(std::unique_ptr<Elem>(new Elem(2)));
+ heap.push(std::unique_ptr<Elem>(new Elem(99)));
+ heap.push(std::unique_ptr<Elem>(new Elem(1)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-5)));
+ heap.push(std::unique_ptr<Elem>(new Elem(12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-12)));
+ heap.push(std::unique_ptr<Elem>(new Elem(-7)));
+
+ heap.top().data = -99;
+
+ heap.demote(heap.top());
+
+ EXPECT_EQ(-99, heap.top().data);
+
+ heap.pop();
+
+ EXPECT_EQ(-7, heap.top().data);
+}
+
+
+TEST(IndIntruHeap, promote_and_demote) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ auto data1 = std::make_shared<Elem>(1);
+
+ heap.push(std::make_shared<Elem>(2));
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(data1);
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ EXPECT_EQ(-12, heap.top().data);
+
+ data1->data = -99;
+ heap.promote(*data1);
+
+ EXPECT_EQ(-99, heap.top().data);
+
+ data1->data = 999;
+ heap.demote(*data1);
+
+ EXPECT_EQ(-12, heap.top().data);
+
+ data1->data = 9;
+ heap.promote(*data1);
+
+ heap.pop(); // remove -12
+ heap.pop(); // remove -7
+ heap.pop(); // remove -5
+ heap.pop(); // remove 2
+
+ EXPECT_EQ(9, heap.top().data);
+}
+
+
+TEST(IndIntruHeap, adjust) {
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare> heap;
+
+ auto data1 = std::make_shared<Elem>(1);
+
+ heap.push(std::make_shared<Elem>(2));
+ heap.push(std::make_shared<Elem>(99));
+ heap.push(data1);
+ heap.push(std::make_shared<Elem>(-5));
+ heap.push(std::make_shared<Elem>(12));
+ heap.push(std::make_shared<Elem>(-12));
+ heap.push(std::make_shared<Elem>(-7));
+
+ // heap.display_sorted(std::cout);
+
+ EXPECT_EQ(-12, heap.top().data);
+
+ data1->data = 999;
+ heap.adjust(*data1);
+
+ EXPECT_EQ(-12, heap.top().data);
+
+ data1->data = -99;
+ heap.adjust(*data1);
+
+ EXPECT_EQ(-99, heap.top().data);
+
+ data1->data = 9;
+ heap.adjust(*data1);
+
+ EXPECT_EQ(-12, heap.top().data);
+
+ heap.pop(); // remove -12
+ heap.pop(); // remove -7
+ heap.pop(); // remove -5
+ heap.pop(); // remove 2
+
+ EXPECT_EQ(9, heap.top().data);
+}
+
+
+TEST(IndIntruHeap, remove_careful) {
+ // here we test whether a common mistake in implementing remove is
+ // done; if after we remove an item and move the last element of the
+ // heap to the position of the removed element, we need to sift it
+ // rather than sift_down it.
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 2> heap;
+
+ heap.push(std::make_shared<Elem>(0));
+ heap.push(std::make_shared<Elem>(10));
+ heap.push(std::make_shared<Elem>(100));
+ heap.push(std::make_shared<Elem>(20));
+ heap.push(std::make_shared<Elem>(30));
+ heap.push(std::make_shared<Elem>(200));
+ heap.push(std::make_shared<Elem>(300));
+ heap.push(std::make_shared<Elem>(40));
+
+ auto k = heap.find(Elem(200));
+ EXPECT_NE(heap.end(), k) <<
+ "we should have found an element with the value 200, which we'll remove";
+ heap.remove(k);
+
+ auto i = heap.cbegin();
+ EXPECT_EQ(0, i->data);
+ ++i;
+ EXPECT_EQ(10, i->data);
+ ++i;
+ EXPECT_EQ(40, i->data) <<
+ "this needs to be 40 or there's a mistake in implementation";
+ ++i;
+ EXPECT_EQ(20, i->data);
+ ++i;
+ EXPECT_EQ(30, i->data);
+ ++i;
+ EXPECT_EQ(100, i->data) <<
+ "this needs to be 100 or there's a mistake in implementation";
+}
+
+
+TEST(IndIntruHeap, remove_greatest) {
+ // See bug #43376 -- removing the greatest element causes an oob
+ // vector reference
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,
+ Elem,
+ &Elem::heap_data,
+ ElemCompare,
+ 2> heap;
+
+ const int num = 4096;
+ std::vector<int> toinsert;
+ toinsert.reserve(num);
+ std::vector<int> toremove;
+ toremove.reserve(num - (num/4));
+ std::vector<int> tocheck;
+ tocheck.reserve(num/4);
+ for (int i = 0; i < num; ++i) {
+ toinsert.push_back(i);
+ if (i < (num/2)) {
+ tocheck.push_back(i);
+ } else {
+ toremove.push_back(i);
+ }
+ }
+
+ std::default_random_engine generator(0);
+ std::shuffle(
+ toinsert.begin(),
+ toinsert.end(),
+ generator);
+
+ for (auto i: toinsert) {
+ heap.push(std::make_shared<Elem>(i));
+ }
+
+ for (auto i: toremove) {
+ auto k = heap.find(Elem(i));
+ EXPECT_NE(heap.end(), k) <<
+ "we should have found an element with the value 300, which we'll remove";
+ heap.remove(k);
+ }
+
+ for (auto i: tocheck) {
+ EXPECT_FALSE(heap.empty());
+ EXPECT_EQ(Elem(i), heap.top());
+ heap.pop();
+ }
+ EXPECT_TRUE(heap.empty());
+}
+
+
+TEST_F(HeapFixture1, shared_data) {
+
+ crimson::IndIntruHeap<std::shared_ptr<Elem>,Elem,&Elem::heap_data_alt,ElemCompareAlt> heap2;
+
+ heap2.push(data1);
+ heap2.push(data2);
+ heap2.push(data3);
+ heap2.push(data4);
+ heap2.push(data5);
+ heap2.push(data6);
+ heap2.push(data7);
+
+ data3->data = 32;
+ heap.adjust(*data3);
+ heap2.adjust(*data3);
+
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-7, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(32, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+
+ EXPECT_EQ(32, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(12, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(2, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(-12, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(99, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(-5, heap2.top().data);
+ heap2.pop();
+ EXPECT_EQ(-7, heap2.top().data);
+}
+
+
+TEST_F(HeapFixture1, iterator_basics) {
+ {
+ unsigned count = 0;
+ for(auto i = heap.begin(); i != heap.end(); ++i) {
+ ++count;
+ }
+
+ EXPECT_EQ(7u, count) << "count should be 7";
+ }
+
+ auto i1 = heap.begin();
+
+ EXPECT_EQ(-12, i1->data) <<
+ "first member with * operator must be smallest";
+
+ EXPECT_EQ(-12, (*i1).data) <<
+ "first member with -> operator must be smallest";
+
+ Elem& e1 = *i1;
+ EXPECT_EQ(-12, e1.data) <<
+ "first member with -> operator must be smallest";
+
+ {
+ std::set<int> values;
+ values.insert(2);
+ values.insert(99);
+ values.insert(1);
+ values.insert(-5);
+ values.insert(12);
+ values.insert(-12);
+ values.insert(-7);
+
+ for(auto i = heap.begin(); i != heap.end(); ++i) {
+ auto v = *i;
+ EXPECT_NE(values.end(), values.find(v.data)) <<
+ "value in heap must be part of original set";
+ values.erase(v.data);
+ }
+ EXPECT_EQ(0u, values.size()) << "all values must have been seen";
+ }
+}
+
+
+TEST_F(HeapFixture1, const_iterator_basics) {
+ const auto& cheap = heap;
+
+ {
+ unsigned count = 0;
+ for(auto i = cheap.cbegin(); i != cheap.cend(); ++i) {
+ ++count;
+ }
+
+ EXPECT_EQ(7u, count) << "count should be 7";
+ }
+
+ auto i1 = heap.cbegin();
+
+ EXPECT_EQ(-12, i1->data) <<
+ "first member with * operator must be smallest";
+
+ EXPECT_EQ(-12, (*i1).data) <<
+ "first member with -> operator must be smallest";
+
+ const Elem& e1 = *i1;
+ EXPECT_EQ(-12, e1.data) <<
+ "first member with -> operator must be smallest";
+
+ {
+ std::set<int> values;
+ values.insert(2);
+ values.insert(99);
+ values.insert(1);
+ values.insert(-5);
+ values.insert(12);
+ values.insert(-12);
+ values.insert(-7);
+
+ for(auto i = heap.cbegin(); i != heap.cend(); ++i) {
+ auto v = *i;
+ EXPECT_NE(values.end(), values.find(v.data)) <<
+ "value in heap must be part of original set";
+ values.erase(v.data);
+ }
+ EXPECT_EQ(0u, values.size()) << "all values must have been seen";
+ }
+}
+
+
+TEST_F(HeapFixture1, iterator_find_rfind) {
+ {
+ auto it1 = heap.find(data7);
+ EXPECT_NE(heap.end(), it1) <<
+ "find by indirection for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "find by indirection for included element should result in right value";
+
+ auto fake_data = std::make_shared<Elem>(-7);
+ auto it2 = heap.find(fake_data);
+ EXPECT_EQ(heap.end(), it2) <<
+ "find by indirection for not included element should fail";
+ }
+
+ {
+ auto it1 = heap.find(Elem(-7));
+ EXPECT_NE(heap.end(), it1) <<
+ "find by value for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "find by value for included element should result in right value";
+
+ auto it2 = heap.find(Elem(7));
+ EXPECT_EQ(heap.end(), it2) <<
+ "find by value for not included element should fail";
+ }
+
+ {
+ auto it1 = heap.rfind(data7);
+ EXPECT_NE(heap.end(), it1) <<
+ "reverse find by indirecton for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "reverse find by indirection for included element should result "
+ "in right value";
+
+ auto fake_data = std::make_shared<Elem>(-7);
+ auto it2 = heap.rfind(fake_data);
+ EXPECT_EQ(heap.end(), it2) <<
+ "reverse find by indirection for not included element should fail";
+ }
+
+ {
+ auto it1 = heap.rfind(Elem(-7));
+ EXPECT_NE(heap.end(), it1) <<
+ "reverse find by value for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "reverse find by value for included element should result "
+ "in right value";
+
+ auto it2 = heap.rfind(Elem(7));
+ EXPECT_EQ(heap.end(), it2) <<
+ "reverse find by value for not included element should fail";
+ }
+}
+
+
+TEST_F(HeapFixture1, const_iterator_find_rfind) {
+ const auto& c_heap = heap;
+
+ {
+ auto it1 = c_heap.find(data7);
+ EXPECT_NE(c_heap.cend(), it1) <<
+ "find by indirection for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "find by indirection for included element should result in right value";
+
+ auto fake_data = std::make_shared<Elem>(-7);
+ auto it2 = c_heap.find(fake_data);
+ EXPECT_EQ(c_heap.cend(), it2) <<
+ "find by indirection for not included element should fail";
+ }
+
+ {
+ auto it1 = c_heap.find(Elem(-7));
+ EXPECT_NE(c_heap.cend(), it1) <<
+ "find by value for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "find by value for included element should result in right value";
+
+ auto it2 = c_heap.find(Elem(7));
+ EXPECT_EQ(c_heap.cend(), it2) <<
+ "find by value for not included element should fail";
+ }
+
+ {
+ auto it1 = c_heap.rfind(data7);
+ EXPECT_NE(c_heap.cend(), it1) <<
+ "reverse find by indirecton for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "reverse find by indirection for included element should result "
+ "in right value";
+
+ auto fake_data = std::make_shared<Elem>(-7);
+ auto it2 = c_heap.rfind(fake_data);
+ EXPECT_EQ(c_heap.cend(), it2) <<
+ "reverse find by indirection for not included element should fail";
+ }
+
+ {
+ auto it1 = c_heap.rfind(Elem(-7));
+ EXPECT_NE(c_heap.cend(), it1) <<
+ "reverse find by value for included element should succeed";
+ EXPECT_EQ(-7, it1->data) <<
+ "reverse find by value for included element should result "
+ "in right value";
+
+ auto it2 = c_heap.rfind(Elem(7));
+ EXPECT_EQ(c_heap.cend(), it2) <<
+ "reverse find by value for not included element should fail";
+ }
+}
+
+
+TEST_F(HeapFixture1, iterator_remove) {
+ auto it1 = heap.find(data7);
+ EXPECT_NE(heap.end(), it1) << "find for included element should succeed";
+
+ heap.remove(it1);
+
+ auto it2 = heap.find(data7);
+ EXPECT_EQ(heap.end(), it2) << "find for removed element should fail";
+
+ for (auto it3 = heap.begin(); it3 != heap.end(); ++it3) {
+ EXPECT_NE(-7, it3->data) <<
+ "iterating through heap should not find removed value";
+ }
+
+ // move through heap without -7
+ EXPECT_EQ(-12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(-5, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(1, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(2, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(12, heap.top().data);
+ heap.pop();
+ EXPECT_EQ(99, heap.top().data);
+ heap.pop();
+}
+
+
+TEST_F(HeapFixture1, four_tops) {
+ Elem& top1 = heap.top();
+ EXPECT_EQ(-12, top1.data);
+
+ const Elem& top2 = heap.top();
+ EXPECT_EQ(-12, top2.data);
+
+ std::shared_ptr<Elem> top3 = heap.top_ind();
+ EXPECT_EQ(-12, top3->data);
+
+ const std::shared_ptr<Elem> top4 = heap.top_ind();
+ EXPECT_EQ(-12, top4->data);
+
+ const auto& c_heap = heap;
+
+ const Elem& top5 = c_heap.top();
+ EXPECT_EQ(-12, top5.data);
+
+ const std::shared_ptr<Elem> top6 = c_heap.top_ind();
+ EXPECT_EQ(-12, top6->data);
+}
+
+
+TEST_F(HeapFixture1, display_sorted) {
+ std::stringstream ss;
+
+ heap.display_sorted(ss);
+
+ std::string s = ss.str();
+
+ EXPECT_GT(s.length(), 0u);
+
+ auto negseven = s.find("-7");
+ EXPECT_NE(negseven, std::string::npos);
+
+ auto ninetynine = s.find("99");
+ EXPECT_NE(ninetynine, std::string::npos);
+
+ // index of -7 should be less than index of 99
+ EXPECT_LT(negseven, ninetynine);
+
+#if 0
+ std::cout << s << std::endl;
+#endif
+}
diff --git a/src/dmclock/support/test/test_intrusive_heap.cc b/src/dmclock/support/test/test_intrusive_heap.cc
new file mode 100644
index 000000000..18d770f31
--- /dev/null
+++ b/src/dmclock/support/test/test_intrusive_heap.cc
@@ -0,0 +1,93 @@
+// -*- 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.
+ */
+
+
+#include <string>
+#include <iostream>
+
+#include "intrusive_heap.h"
+
+
+struct TestCompare;
+struct TestIntruData;
+
+
+class Test1 {
+ friend TestCompare;
+ friend TestIntruData;
+
+ int data;
+ crimson::IntruHeapData heap_data;
+
+public:
+ explicit Test1(int _data) : data(_data) {}
+
+ friend std::ostream& operator<<(std::ostream& out, const Test1& d) {
+ out << d.data << " (" << d.heap_data << ")";
+ return out;
+ }
+
+ int& the_data() { return data; }
+};
+
+
+struct TestCompare {
+ bool operator()(const Test1& d1, const Test1& d2) {
+ return d1.data < d2.data;
+ }
+};
+
+
+struct TestIntruData {
+ crimson::IntruHeapData& operator()(Test1& d) {
+ return d.heap_data;
+ }
+};
+
+
+int main(int argc, char** argv) {
+ Test1 d1(2);
+ Test1 d2(3);
+ Test1 d3(1);
+ Test1 d4(-5);
+
+ crimson::IntruHeap<Test1, TestIntruData, TestCompare> my_heap;
+
+ my_heap.push(d1);
+ my_heap.push(d2);
+ my_heap.push(d3);
+ my_heap.push(d4);
+ my_heap.push(Test1(-9));
+ my_heap.push(Test1(99));
+ my_heap.push(Test1(0));
+
+ std::cout << my_heap << std::endl;
+
+ auto& t = my_heap.top();
+ t.the_data() = 17;
+ my_heap.adjust_down(t);
+
+ std::cout << my_heap << std::endl;
+
+ my_heap.display_sorted(std::cout);
+
+ while (!my_heap.empty()) {
+ auto& top = my_heap.top();
+ std::cout << top << std::endl;
+ my_heap.pop();
+ std::cout << my_heap << std::endl;
+ }
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-05 01:09:57 +0000