From 19fcec84d8d7d21e796c7624e521b60d28ee21ed Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:45:59 +0200 Subject: Adding upstream version 16.2.11+ds. Signed-off-by: Daniel Baumann --- src/dmclock/support/test/CMakeLists.txt | 26 + src/dmclock/support/test/test_ind_intru_heap.cc | 89 ++ .../support/test/test_indirect_intrusive_heap.cc | 1022 ++++++++++++++++++++ src/dmclock/support/test/test_intrusive_heap.cc | 93 ++ 4 files changed, 1230 insertions(+) create mode 100644 src/dmclock/support/test/CMakeLists.txt create mode 100644 src/dmclock/support/test/test_ind_intru_heap.cc create mode 100644 src/dmclock/support/test/test_indirect_intrusive_heap.cc create mode 100644 src/dmclock/support/test/test_intrusive_heap.cc (limited to 'src/dmclock/support/test') 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 + * + * 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 +#include +#include + +#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, Test1, &Test1::heap_data, TestCompare> my_heap; + + const std::shared_ptr d99 = std::make_shared(99); + + my_heap.push(std::make_shared(2)); + my_heap.push(d99); + my_heap.push(std::make_shared(1)); + my_heap.push(std::make_shared(-5)); + my_heap.push(std::make_shared(12)); + my_heap.push(std::make_shared(-12)); + my_heap.push(std::make_shared(-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 + * + * 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 +#include +#include +#include +#include + +#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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + std::shared_ptr data1, data2, data3, data4, data5, data6, data7; + + void SetUp() { + data1 = std::make_shared(2); + data2 = std::make_shared(99); + data3 = std::make_shared(1); + data4 = std::make_shared(-5); + data5 = std::make_shared(12); + data6 = std::make_shared(-12); + data7 = std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + EXPECT_TRUE(heap.empty()); + + heap.push(std::make_shared(2)); + + EXPECT_FALSE(heap.empty()); + + heap.push(std::make_shared(99)); + heap.push(std::make_shared(1)); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + EXPECT_TRUE(heap.empty()); + + heap.push(std::unique_ptr(new Elem(2))); + + EXPECT_FALSE(heap.empty()); + + heap.push(std::unique_ptr(new Elem(99))); + heap.push(std::unique_ptr(new Elem(1))); + heap.push(std::unique_ptr(new Elem(-5))); + heap.push(std::unique_ptr(new Elem(12))); + heap.push(std::unique_ptr(new Elem(-12))); + heap.push(std::unique_ptr(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 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, + Elem, + &Elem::heap_data, + ElemCompare, + 3> heap; + + EXPECT_TRUE(heap.empty()); + + heap.push(std::make_shared(2)); + + EXPECT_FALSE(heap.empty()); + + heap.push(std::make_shared(99)); + heap.push(std::make_shared(1)); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare, + 4> heap; + + EXPECT_TRUE(heap.empty()); + + heap.push(std::make_shared(2)); + + EXPECT_FALSE(heap.empty()); + + heap.push(std::make_shared(99)); + heap.push(std::make_shared(1)); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare, + 10> heap; + + EXPECT_TRUE(heap.empty()); + + heap.push(std::make_shared(2)); + + EXPECT_FALSE(heap.empty()); + + heap.push(std::make_shared(99)); + heap.push(std::make_shared(1)); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare, + 2> heap2; + + crimson::IndIntruHeap, + Elem, + &Elem::heap_data, + ElemCompare, + 3> heap3; + + crimson::IndIntruHeap, + Elem, + &Elem::heap_data, + ElemCompare, + 4> heap4; + + crimson::IndIntruHeap, + 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(value); + heap2.push(data); + heap3.push(data); + heap4.push(data); + heap10.push(data); + } + + auto bound = std::numeric_limits::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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + heap.push(std::unique_ptr(new Elem(2))); + heap.push(std::unique_ptr(new Elem(99))); + heap.push(std::unique_ptr(new Elem(1))); + heap.push(std::unique_ptr(new Elem(-5))); + heap.push(std::unique_ptr(new Elem(12))); + heap.push(std::unique_ptr(new Elem(-12))); + heap.push(std::unique_ptr(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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + heap.push(std::unique_ptr(new Elem(2))); + heap.push(std::unique_ptr(new Elem(99))); + heap.push(std::unique_ptr(new Elem(1))); + heap.push(std::unique_ptr(new Elem(-5))); + heap.push(std::unique_ptr(new Elem(12))); + heap.push(std::unique_ptr(new Elem(-12))); + heap.push(std::unique_ptr(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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + auto data1 = std::make_shared(1); + + heap.push(std::make_shared(2)); + heap.push(std::make_shared(99)); + heap.push(data1); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare> heap; + + auto data1 = std::make_shared(1); + + heap.push(std::make_shared(2)); + heap.push(std::make_shared(99)); + heap.push(data1); + heap.push(std::make_shared(-5)); + heap.push(std::make_shared(12)); + heap.push(std::make_shared(-12)); + heap.push(std::make_shared(-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, + Elem, + &Elem::heap_data, + ElemCompare, + 2> heap; + + heap.push(std::make_shared(0)); + heap.push(std::make_shared(10)); + heap.push(std::make_shared(100)); + heap.push(std::make_shared(20)); + heap.push(std::make_shared(30)); + heap.push(std::make_shared(200)); + heap.push(std::make_shared(300)); + heap.push(std::make_shared(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, + Elem, + &Elem::heap_data, + ElemCompare, + 2> heap; + + const int num = 4096; + std::vector toinsert; + toinsert.reserve(num); + std::vector toremove; + toremove.reserve(num - (num/4)); + std::vector 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(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,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 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 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(-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(-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(-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(-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 top3 = heap.top_ind(); + EXPECT_EQ(-12, top3->data); + + const std::shared_ptr 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 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 + * + * 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 +#include + +#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 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; +} -- cgit v1.2.3