Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 1230 insertions, 0 deletions

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;
+}