1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
5 * Copyright (C) 2016 Red Hat Inc.
12 #include "gtest/gtest.h"
14 #include "indirect_intrusive_heap.h"
20 crimson::IndIntruHeapData heap_data;
21 crimson::IndIntruHeapData heap_data_alt;
23 Elem(int _data) : data(_data) { }
25 bool operator==(const Elem& other) {
26 return data == other.data;
29 friend std::ostream& operator<<(std::ostream& out, const Elem& d) {
38 bool operator()(const Elem& d1, const Elem& d2) const {
39 return d1.data < d2.data;
44 // first all evens precede all odds, then they're sorted high to low
45 struct ElemCompareAlt {
46 bool operator()(const Elem& d1, const Elem& d2) {
47 if (0 == d1.data % 2) {
48 if (0 == d2.data % 2) {
49 return d1.data > d2.data;
53 } else if (0 == d2.data % 2) {
56 return d1.data > d2.data;
62 class HeapFixture1: public ::testing::Test {
66 crimson::IndIntruHeap<std::shared_ptr<Elem>,
71 std::shared_ptr<Elem> data1, data2, data3, data4, data5, data6, data7;
74 data1 = std::make_shared<Elem>(2);
75 data2 = std::make_shared<Elem>(99);
76 data3 = std::make_shared<Elem>(1);
77 data4 = std::make_shared<Elem>(-5);
78 data5 = std::make_shared<Elem>(12);
79 data6 = std::make_shared<Elem>(-12);
80 data7 = std::make_shared<Elem>(-7);
94 }; // class HeapFixture1
96 TEST(IndIntruHeap, shared_ptr) {
97 crimson::IndIntruHeap<std::shared_ptr<Elem>,
102 EXPECT_TRUE(heap.empty());
104 heap.push(std::make_shared<Elem>(2));
106 EXPECT_FALSE(heap.empty());
108 heap.push(std::make_shared<Elem>(99));
109 heap.push(std::make_shared<Elem>(1));
110 heap.push(std::make_shared<Elem>(-5));
111 heap.push(std::make_shared<Elem>(12));
112 heap.push(std::make_shared<Elem>(-12));
113 heap.push(std::make_shared<Elem>(-7));
115 // std::cout << heap << std::endl;
117 EXPECT_FALSE(heap.empty());
119 EXPECT_EQ(-12, heap.top().data);
121 EXPECT_EQ(-7, heap.top().data);
123 EXPECT_EQ(-5, heap.top().data);
125 EXPECT_EQ(1, heap.top().data);
127 EXPECT_EQ(2, heap.top().data);
129 EXPECT_EQ(12, heap.top().data);
131 EXPECT_EQ(99, heap.top().data);
133 EXPECT_FALSE(heap.empty());
135 EXPECT_TRUE(heap.empty());
139 TEST(IndIntruHeap, unique_ptr) {
140 crimson::IndIntruHeap<std::unique_ptr<Elem>,
145 EXPECT_TRUE(heap.empty());
147 heap.push(std::unique_ptr<Elem>(new Elem(2)));
149 EXPECT_FALSE(heap.empty());
151 heap.push(std::unique_ptr<Elem>(new Elem(99)));
152 heap.push(std::unique_ptr<Elem>(new Elem(1)));
153 heap.push(std::unique_ptr<Elem>(new Elem(-5)));
154 heap.push(std::unique_ptr<Elem>(new Elem(12)));
155 heap.push(std::unique_ptr<Elem>(new Elem(-12)));
156 heap.push(std::unique_ptr<Elem>(new Elem(-7)));
158 EXPECT_FALSE(heap.empty());
160 EXPECT_EQ(-12, heap.top().data);
162 EXPECT_EQ(-7, heap.top().data);
164 EXPECT_EQ(-5, heap.top().data);
166 EXPECT_EQ(1, heap.top().data);
168 EXPECT_EQ(2, heap.top().data);
170 EXPECT_EQ(12, heap.top().data);
172 EXPECT_EQ(99, heap.top().data);
174 EXPECT_FALSE(heap.empty());
176 EXPECT_TRUE(heap.empty());
180 TEST(IndIntruHeap, regular_ptr) {
181 crimson::IndIntruHeap<Elem*, Elem, &Elem::heap_data, ElemCompare> heap;
183 EXPECT_TRUE(heap.empty());
185 heap.push(new Elem(2));
187 EXPECT_FALSE(heap.empty());
189 heap.push(new Elem(99));
190 heap.push(new Elem(1));
191 heap.push(new Elem(-5));
192 heap.push(new Elem(12));
193 heap.push(new Elem(-12));
194 heap.push(new Elem(-7));
196 EXPECT_FALSE(heap.empty());
198 EXPECT_EQ(-12, heap.top().data);
201 EXPECT_EQ(-7, heap.top().data);
204 EXPECT_EQ(-5, heap.top().data);
207 EXPECT_EQ(1, heap.top().data);
210 EXPECT_EQ(2, heap.top().data);
213 EXPECT_EQ(12, heap.top().data);
216 EXPECT_EQ(99, heap.top().data);
220 EXPECT_FALSE(heap.empty());
222 EXPECT_TRUE(heap.empty());
226 TEST(IndIntruHeap, K_3) {
227 crimson::IndIntruHeap<std::shared_ptr<Elem>,
233 EXPECT_TRUE(heap.empty());
235 heap.push(std::make_shared<Elem>(2));
237 EXPECT_FALSE(heap.empty());
239 heap.push(std::make_shared<Elem>(99));
240 heap.push(std::make_shared<Elem>(1));
241 heap.push(std::make_shared<Elem>(-5));
242 heap.push(std::make_shared<Elem>(12));
243 heap.push(std::make_shared<Elem>(-12));
244 heap.push(std::make_shared<Elem>(-7));
246 // std::cout << heap << std::endl;
248 EXPECT_FALSE(heap.empty());
250 EXPECT_EQ(-12, heap.top().data);
252 EXPECT_EQ(-7, heap.top().data);
254 EXPECT_EQ(-5, heap.top().data);
256 EXPECT_EQ(1, heap.top().data);
258 EXPECT_EQ(2, heap.top().data);
260 EXPECT_EQ(12, heap.top().data);
262 EXPECT_EQ(99, heap.top().data);
264 EXPECT_FALSE(heap.empty());
266 EXPECT_TRUE(heap.empty());
270 TEST(IndIntruHeap, K_4) {
271 crimson::IndIntruHeap<std::shared_ptr<Elem>,
277 EXPECT_TRUE(heap.empty());
279 heap.push(std::make_shared<Elem>(2));
281 EXPECT_FALSE(heap.empty());
283 heap.push(std::make_shared<Elem>(99));
284 heap.push(std::make_shared<Elem>(1));
285 heap.push(std::make_shared<Elem>(-5));
286 heap.push(std::make_shared<Elem>(12));
287 heap.push(std::make_shared<Elem>(-12));
288 heap.push(std::make_shared<Elem>(-7));
290 // std::cout << heap << std::endl;
292 EXPECT_FALSE(heap.empty());
294 EXPECT_EQ(-12, heap.top().data);
296 EXPECT_EQ(-7, heap.top().data);
298 EXPECT_EQ(-5, heap.top().data);
300 EXPECT_EQ(1, heap.top().data);
302 EXPECT_EQ(2, heap.top().data);
304 EXPECT_EQ(12, heap.top().data);
306 EXPECT_EQ(99, heap.top().data);
308 EXPECT_FALSE(heap.empty());
310 EXPECT_TRUE(heap.empty());
314 TEST(IndIntruHeap, K_10) {
315 crimson::IndIntruHeap<std::shared_ptr<Elem>,
321 EXPECT_TRUE(heap.empty());
323 heap.push(std::make_shared<Elem>(2));
325 EXPECT_FALSE(heap.empty());
327 heap.push(std::make_shared<Elem>(99));
328 heap.push(std::make_shared<Elem>(1));
329 heap.push(std::make_shared<Elem>(-5));
330 heap.push(std::make_shared<Elem>(12));
331 heap.push(std::make_shared<Elem>(-12));
332 heap.push(std::make_shared<Elem>(-7));
334 // std::cout << heap << std::endl;
336 EXPECT_FALSE(heap.empty());
338 EXPECT_EQ(-12, heap.top().data);
340 EXPECT_EQ(-7, heap.top().data);
342 EXPECT_EQ(-5, heap.top().data);
344 EXPECT_EQ(1, heap.top().data);
346 EXPECT_EQ(2, heap.top().data);
348 EXPECT_EQ(12, heap.top().data);
350 EXPECT_EQ(99, heap.top().data);
352 EXPECT_FALSE(heap.empty());
354 EXPECT_TRUE(heap.empty());
358 TEST(IndIntruHeap, multi_K) {
359 crimson::IndIntruHeap<std::shared_ptr<Elem>,
365 crimson::IndIntruHeap<std::shared_ptr<Elem>,
371 crimson::IndIntruHeap<std::shared_ptr<Elem>,
377 crimson::IndIntruHeap<std::shared_ptr<Elem>,
383 // 250 should give us at least 4 levels on all heaps
384 constexpr size_t count = 250;
386 std::srand(std::time(0)); // use current time as seed for random generator
388 // insert same set of random values into the four heaps
389 for (size_t i = 0; i < count; ++i) {
390 int value = std::rand() % 201 - 100; // -100...+100
391 auto data = std::make_shared<Elem>(value);
398 auto bound = std::numeric_limits<decltype(Elem::data)>::min();
400 for (size_t i = 0; i < count; ++i) {
401 auto current = heap2.top().data;
403 EXPECT_GE(current, bound) <<
404 "we should never go down, only increase or remain the same";
405 EXPECT_EQ(current, heap3.top().data) <<
406 "heap1's data and heap3's data should match";
407 EXPECT_EQ(current, heap4.top().data) <<
408 "heap1's data and heap4's data should match";
409 EXPECT_EQ(current, heap10.top().data) <<
410 "heap1's data and heap10's data should match";
420 EXPECT_TRUE(heap2.empty()) << "should be empty after all elements popped";
421 EXPECT_TRUE(heap3.empty()) << "should be empty after all elements popped";
422 EXPECT_TRUE(heap4.empty()) << "should be empty after all elements popped";
423 EXPECT_TRUE(heap10.empty()) << "should be empty after all elements popped";
427 TEST(IndIntruHeap, demote) {
428 crimson::IndIntruHeap<std::unique_ptr<Elem>,
433 heap.push(std::unique_ptr<Elem>(new Elem(2)));
434 heap.push(std::unique_ptr<Elem>(new Elem(99)));
435 heap.push(std::unique_ptr<Elem>(new Elem(1)));
436 heap.push(std::unique_ptr<Elem>(new Elem(-5)));
437 heap.push(std::unique_ptr<Elem>(new Elem(12)));
438 heap.push(std::unique_ptr<Elem>(new Elem(-12)));
439 heap.push(std::unique_ptr<Elem>(new Elem(-7)));
441 heap.top().data = 24;
443 heap.demote(heap.top());
445 EXPECT_EQ(-7, heap.top().data);
453 EXPECT_EQ(24, heap.top().data);
457 TEST(IndIntruHeap, demote_not) {
458 crimson::IndIntruHeap<std::unique_ptr<Elem>,
463 heap.push(std::unique_ptr<Elem>(new Elem(2)));
464 heap.push(std::unique_ptr<Elem>(new Elem(99)));
465 heap.push(std::unique_ptr<Elem>(new Elem(1)));
466 heap.push(std::unique_ptr<Elem>(new Elem(-5)));
467 heap.push(std::unique_ptr<Elem>(new Elem(12)));
468 heap.push(std::unique_ptr<Elem>(new Elem(-12)));
469 heap.push(std::unique_ptr<Elem>(new Elem(-7)));
471 heap.top().data = -99;
473 heap.demote(heap.top());
475 EXPECT_EQ(-99, heap.top().data);
479 EXPECT_EQ(-7, heap.top().data);
483 TEST(IndIntruHeap, promote_and_demote) {
484 crimson::IndIntruHeap<std::shared_ptr<Elem>,
489 auto data1 = std::make_shared<Elem>(1);
491 heap.push(std::make_shared<Elem>(2));
492 heap.push(std::make_shared<Elem>(99));
494 heap.push(std::make_shared<Elem>(-5));
495 heap.push(std::make_shared<Elem>(12));
496 heap.push(std::make_shared<Elem>(-12));
497 heap.push(std::make_shared<Elem>(-7));
499 EXPECT_EQ(-12, heap.top().data);
502 heap.promote(*data1);
504 EXPECT_EQ(-99, heap.top().data);
509 EXPECT_EQ(-12, heap.top().data);
512 heap.promote(*data1);
514 heap.pop(); // remove -12
515 heap.pop(); // remove -7
516 heap.pop(); // remove -5
517 heap.pop(); // remove 2
519 EXPECT_EQ(9, heap.top().data);
523 TEST(IndIntruHeap, adjust) {
524 crimson::IndIntruHeap<std::shared_ptr<Elem>,
529 auto data1 = std::make_shared<Elem>(1);
531 heap.push(std::make_shared<Elem>(2));
532 heap.push(std::make_shared<Elem>(99));
534 heap.push(std::make_shared<Elem>(-5));
535 heap.push(std::make_shared<Elem>(12));
536 heap.push(std::make_shared<Elem>(-12));
537 heap.push(std::make_shared<Elem>(-7));
539 // heap.display_sorted(std::cout);
541 EXPECT_EQ(-12, heap.top().data);
546 EXPECT_EQ(-12, heap.top().data);
551 EXPECT_EQ(-99, heap.top().data);
556 EXPECT_EQ(-12, heap.top().data);
558 heap.pop(); // remove -12
559 heap.pop(); // remove -7
560 heap.pop(); // remove -5
561 heap.pop(); // remove 2
563 EXPECT_EQ(9, heap.top().data);
567 TEST(IndIntruHeap, remove_careful) {
568 // here we test whether a common mistake in implementing remove is
569 // done; if after we remove an item and move the last element of the
570 // heap to the position of the removed element, we need to sift it
571 // rather than sift_down it.
573 crimson::IndIntruHeap<std::shared_ptr<Elem>,
579 heap.push(std::make_shared<Elem>(0));
580 heap.push(std::make_shared<Elem>(10));
581 heap.push(std::make_shared<Elem>(100));
582 heap.push(std::make_shared<Elem>(20));
583 heap.push(std::make_shared<Elem>(30));
584 heap.push(std::make_shared<Elem>(200));
585 heap.push(std::make_shared<Elem>(300));
586 heap.push(std::make_shared<Elem>(40));
588 auto k = heap.find(Elem(200));
589 EXPECT_NE(heap.end(), k) <<
590 "we should have found an element with the value 200, which we'll remove";
593 auto i = heap.cbegin();
594 EXPECT_EQ(0, i->data);
596 EXPECT_EQ(10, i->data);
598 EXPECT_EQ(40, i->data) <<
599 "this needs to be 40 or there's a mistake in implementation";
601 EXPECT_EQ(20, i->data);
603 EXPECT_EQ(30, i->data);
605 EXPECT_EQ(100, i->data) <<
606 "this needs to be 100 or there's a mistake in implementation";
610 TEST_F(HeapFixture1, shared_data) {
612 crimson::IndIntruHeap<std::shared_ptr<Elem>,Elem,&Elem::heap_data_alt,ElemCompareAlt> heap2;
624 heap2.adjust(*data3);
626 EXPECT_EQ(-12, heap.top().data);
628 EXPECT_EQ(-7, heap.top().data);
630 EXPECT_EQ(-5, heap.top().data);
632 EXPECT_EQ(2, heap.top().data);
634 EXPECT_EQ(12, heap.top().data);
636 EXPECT_EQ(32, heap.top().data);
638 EXPECT_EQ(99, heap.top().data);
640 EXPECT_EQ(32, heap2.top().data);
642 EXPECT_EQ(12, heap2.top().data);
644 EXPECT_EQ(2, heap2.top().data);
646 EXPECT_EQ(-12, heap2.top().data);
648 EXPECT_EQ(99, heap2.top().data);
650 EXPECT_EQ(-5, heap2.top().data);
652 EXPECT_EQ(-7, heap2.top().data);
656 TEST_F(HeapFixture1, iterator_basics) {
659 for(auto i = heap.begin(); i != heap.end(); ++i) {
663 EXPECT_EQ(7u, count) << "count should be 7";
666 auto i1 = heap.begin();
668 EXPECT_EQ(-12, i1->data) <<
669 "first member with * operator must be smallest";
671 EXPECT_EQ(-12, (*i1).data) <<
672 "first member with -> operator must be smallest";
675 EXPECT_EQ(-12, e1.data) <<
676 "first member with -> operator must be smallest";
679 std::set<int> values;
688 for(auto i = heap.begin(); i != heap.end(); ++i) {
690 EXPECT_NE(values.end(), values.find(v.data)) <<
691 "value in heap must be part of original set";
692 values.erase(v.data);
694 EXPECT_EQ(0u, values.size()) << "all values must have been seen";
699 TEST_F(HeapFixture1, const_iterator_basics) {
700 const auto& cheap = heap;
704 for(auto i = cheap.cbegin(); i != cheap.cend(); ++i) {
708 EXPECT_EQ(7u, count) << "count should be 7";
711 auto i1 = heap.cbegin();
713 EXPECT_EQ(-12, i1->data) <<
714 "first member with * operator must be smallest";
716 EXPECT_EQ(-12, (*i1).data) <<
717 "first member with -> operator must be smallest";
719 const Elem& e1 = *i1;
720 EXPECT_EQ(-12, e1.data) <<
721 "first member with -> operator must be smallest";
724 std::set<int> values;
733 for(auto i = heap.cbegin(); i != heap.cend(); ++i) {
735 EXPECT_NE(values.end(), values.find(v.data)) <<
736 "value in heap must be part of original set";
737 values.erase(v.data);
739 EXPECT_EQ(0u, values.size()) << "all values must have been seen";
744 TEST_F(HeapFixture1, iterator_find_rfind) {
746 auto it1 = heap.find(data7);
747 EXPECT_NE(heap.end(), it1) <<
748 "find by indirection for included element should succeed";
749 EXPECT_EQ(-7, it1->data) <<
750 "find by indirection for included element should result in right value";
752 auto fake_data = std::make_shared<Elem>(-7);
753 auto it2 = heap.find(fake_data);
754 EXPECT_EQ(heap.end(), it2) <<
755 "find by indirection for not included element should fail";
759 auto it1 = heap.find(Elem(-7));
760 EXPECT_NE(heap.end(), it1) <<
761 "find by value for included element should succeed";
762 EXPECT_EQ(-7, it1->data) <<
763 "find by value for included element should result in right value";
765 auto it2 = heap.find(Elem(7));
766 EXPECT_EQ(heap.end(), it2) <<
767 "find by value for not included element should fail";
771 auto it1 = heap.rfind(data7);
772 EXPECT_NE(heap.end(), it1) <<
773 "reverse find by indirecton for included element should succeed";
774 EXPECT_EQ(-7, it1->data) <<
775 "reverse find by indirection for included element should result "
778 auto fake_data = std::make_shared<Elem>(-7);
779 auto it2 = heap.rfind(fake_data);
780 EXPECT_EQ(heap.end(), it2) <<
781 "reverse find by indirection for not included element should fail";
785 auto it1 = heap.rfind(Elem(-7));
786 EXPECT_NE(heap.end(), it1) <<
787 "reverse find by value for included element should succeed";
788 EXPECT_EQ(-7, it1->data) <<
789 "reverse find by value for included element should result "
792 auto it2 = heap.rfind(Elem(7));
793 EXPECT_EQ(heap.end(), it2) <<
794 "reverse find by value for not included element should fail";
799 TEST_F(HeapFixture1, const_iterator_find_rfind) {
800 const auto& c_heap = heap;
803 auto it1 = c_heap.find(data7);
804 EXPECT_NE(c_heap.cend(), it1) <<
805 "find by indirection for included element should succeed";
806 EXPECT_EQ(-7, it1->data) <<
807 "find by indirection for included element should result in right value";
809 auto fake_data = std::make_shared<Elem>(-7);
810 auto it2 = c_heap.find(fake_data);
811 EXPECT_EQ(c_heap.cend(), it2) <<
812 "find by indirection for not included element should fail";
816 auto it1 = c_heap.find(Elem(-7));
817 EXPECT_NE(c_heap.cend(), it1) <<
818 "find by value for included element should succeed";
819 EXPECT_EQ(-7, it1->data) <<
820 "find by value for included element should result in right value";
822 auto it2 = c_heap.find(Elem(7));
823 EXPECT_EQ(c_heap.cend(), it2) <<
824 "find by value for not included element should fail";
828 auto it1 = c_heap.rfind(data7);
829 EXPECT_NE(c_heap.cend(), it1) <<
830 "reverse find by indirecton for included element should succeed";
831 EXPECT_EQ(-7, it1->data) <<
832 "reverse find by indirection for included element should result "
835 auto fake_data = std::make_shared<Elem>(-7);
836 auto it2 = c_heap.rfind(fake_data);
837 EXPECT_EQ(c_heap.cend(), it2) <<
838 "reverse find by indirection for not included element should fail";
842 auto it1 = c_heap.rfind(Elem(-7));
843 EXPECT_NE(c_heap.cend(), it1) <<
844 "reverse find by value for included element should succeed";
845 EXPECT_EQ(-7, it1->data) <<
846 "reverse find by value for included element should result "
849 auto it2 = c_heap.rfind(Elem(7));
850 EXPECT_EQ(c_heap.cend(), it2) <<
851 "reverse find by value for not included element should fail";
856 TEST_F(HeapFixture1, iterator_remove) {
857 auto it1 = heap.find(data7);
858 EXPECT_NE(heap.end(), it1) << "find for included element should succeed";
862 auto it2 = heap.find(data7);
863 EXPECT_EQ(heap.end(), it2) << "find for removed element should fail";
865 for (auto it3 = heap.begin(); it3 != heap.end(); ++it3) {
866 EXPECT_NE(-7, it3->data) <<
867 "iterating through heap should not find removed value";
870 // move through heap without -7
871 EXPECT_EQ(-12, heap.top().data);
873 EXPECT_EQ(-5, heap.top().data);
875 EXPECT_EQ(1, heap.top().data);
877 EXPECT_EQ(2, heap.top().data);
879 EXPECT_EQ(12, heap.top().data);
881 EXPECT_EQ(99, heap.top().data);
886 TEST_F(HeapFixture1, four_tops) {
887 Elem& top1 = heap.top();
888 EXPECT_EQ(-12, top1.data);
890 const Elem& top2 = heap.top();
891 EXPECT_EQ(-12, top2.data);
893 std::shared_ptr<Elem> top3 = heap.top_ind();
894 EXPECT_EQ(-12, top3->data);
896 const std::shared_ptr<Elem> top4 = heap.top_ind();
897 EXPECT_EQ(-12, top4->data);
899 const auto& c_heap = heap;
901 const Elem& top5 = c_heap.top();
902 EXPECT_EQ(-12, top5.data);
904 const std::shared_ptr<Elem> top6 = c_heap.top_ind();
905 EXPECT_EQ(-12, top6->data);
909 TEST_F(HeapFixture1, display_sorted) {
910 std::stringstream ss;
912 heap.display_sorted(ss);
914 std::string s = ss.str();
916 EXPECT_GT(s.length(), 0u);
918 auto negseven = s.find("-7");
919 EXPECT_NE(negseven, std::string::npos);
921 auto ninetynine = s.find("99");
922 EXPECT_NE(ninetynine, std::string::npos);
924 // index of -7 should be less than index of 99
925 EXPECT_LT(negseven, ninetynine);
928 std::cout << s << std::endl;