diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
commit | 19fcec84d8d7d21e796c7624e521b60d28ee21ed (patch) | |
tree | 42d26aa27d1e3f7c0b8bd3fd14e7d7082f5008dc /src/dmclock/support | |
parent | Initial commit. (diff) | |
download | ceph-19fcec84d8d7d21e796c7624e521b60d28ee21ed.tar.xz ceph-19fcec84d8d7d21e796c7624e521b60d28ee21ed.zip |
Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/dmclock/support/src/debug.h | 24 | ||||
-rw-r--r-- | src/dmclock/support/src/heap.h | 247 | ||||
-rw-r--r-- | src/dmclock/support/src/indirect_intrusive_heap.h | 567 | ||||
-rw-r--r-- | src/dmclock/support/src/intrusive_heap.h | 221 | ||||
-rw-r--r-- | src/dmclock/support/src/profile.h | 121 | ||||
-rw-r--r-- | src/dmclock/support/src/run_every.cc | 94 | ||||
-rw-r--r-- | src/dmclock/support/src/run_every.h | 81 | ||||
-rw-r--r-- | src/dmclock/support/test/CMakeLists.txt | 26 | ||||
-rw-r--r-- | src/dmclock/support/test/test_ind_intru_heap.cc | 89 | ||||
-rw-r--r-- | src/dmclock/support/test/test_indirect_intrusive_heap.cc | 1022 | ||||
-rw-r--r-- | src/dmclock/support/test/test_intrusive_heap.cc | 93 |
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; +} |