intrusive_heap_unittest.cc 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146
  1. // Copyright 2019 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/containers/intrusive_heap.h"
  5. #include "base/callback_helpers.h"
  6. #include "base/check_op.h"
  7. #include "base/memory/ptr_util.h"
  8. #include "base/notreached.h"
  9. #include "base/rand_util.h"
  10. #include "base/test/bind.h"
  11. #include "testing/gmock/include/gmock/gmock.h"
  12. #include "testing/gtest/include/gtest/gtest.h"
  13. namespace base {
  14. namespace {
  15. using IntrusiveHeapInt = IntrusiveHeap<WithHeapHandle<int>>;
  16. // Validates whether or not the given heap satisfies the heap invariant.
  17. template <class H>
  18. void ExpectHeap(const H& heap) {
  19. const auto& less = heap.value_comp();
  20. const auto& handle_access = heap.heap_handle_access();
  21. for (size_t i = 0; i < heap.size(); ++i) {
  22. size_t left = intrusive_heap::LeftIndex(i);
  23. size_t right = left + 1;
  24. if (left < heap.size())
  25. EXPECT_FALSE(less(heap[i], heap[left]));
  26. if (right < heap.size())
  27. EXPECT_FALSE(less(heap[i], heap[right]));
  28. intrusive_heap::CheckInvalidOrEqualTo(handle_access.GetHeapHandle(&heap[i]),
  29. i);
  30. }
  31. }
  32. // A small set of canonical elements, and the a function for validating the
  33. // heap that should be created by those elements. This is used in various
  34. // constructor/insertion tests.
  35. #define CANONICAL_ELEMENTS 3, 1, 2, 4, 5, 6, 7, 0
  36. void ExpectCanonical(const IntrusiveHeapInt& heap) {
  37. ExpectHeap(heap);
  38. // Manual implementation of a max-heap inserting the elements defined by
  39. // CANONICAL_ELEMENTS:
  40. // 3
  41. // 3 1
  42. // 3 1 2
  43. // 3 1 2 4 -> 3 4 2 1 -> 4 3 2 1
  44. // 4 3 2 1 5 -> 4 5 2 1 3 -> 5 4 2 1 3
  45. // 5 4 2 1 3 6 -> 5 4 6 1 3 2 -> 6 4 5 1 3 2
  46. // 6 4 5 1 3 2 7 -> 6 4 7 1 3 2 5 -> 7 4 6 1 3 2 5
  47. // 7 4 6 1 3 2 5 0
  48. std::vector<int> expected{7, 4, 6, 1, 3, 2, 5, 0};
  49. std::vector<int> actual;
  50. for (const auto& element : heap)
  51. actual.push_back(element.value());
  52. ASSERT_THAT(actual, testing::ContainerEq(expected));
  53. }
  54. // Initializes the given heap to be the "canonical" heap from the point of view
  55. // of these tests.
  56. void MakeCanonical(IntrusiveHeapInt* heap) {
  57. static constexpr int kInts[] = {CANONICAL_ELEMENTS};
  58. heap->clear();
  59. heap->insert(kInts, kInts + std::size(kInts));
  60. ExpectCanonical(*heap);
  61. }
  62. // A handful of helper functions and classes related to building an exhaustive
  63. // stress test for IntrusiveHeap, with all combinations of default-constructible
  64. // supports-move-operations and supports-copy-operations value types.
  65. // IntrusiveHeap supports 3 types of operations: those that cause the heap to
  66. // get smaller (deletions), those that keep the heap the same size (updates,
  67. // replaces, etc), and those that cause the heap to get bigger (insertions).
  68. enum OperationTypes : int {
  69. kGrowing,
  70. kShrinking,
  71. kSameSize,
  72. kOperationTypesCount
  73. };
  74. // The operations that cause a heap to get bigger.
  75. enum GrowingOperations : int { kInsert, kEmplace, kGrowingOperationsCount };
  76. // The operations that cause a heap to get smaller. Some of these are only
  77. // supported by move-only value types.
  78. enum ShrinkingOperations : int {
  79. kTake,
  80. kTakeTop,
  81. kErase,
  82. kPop,
  83. kShrinkingOperationsCount
  84. };
  85. // The operations that keep a heap the same size.
  86. enum SameSizeOperations : int {
  87. kReplace,
  88. kReplaceTop,
  89. kUpdate,
  90. kSameSizeOperationsCount
  91. };
  92. // Randomly selects an operation for the GrowingOperations enum, applies it to
  93. // the given heap, and validates that the operation completed as expected.
  94. template <typename T>
  95. void DoGrowingOperation(IntrusiveHeap<T>* heap) {
  96. GrowingOperations op = static_cast<GrowingOperations>(
  97. base::RandInt(0, kGrowingOperationsCount - 1));
  98. int value = base::RandInt(0, 1000);
  99. size_t old_size = heap->size();
  100. typename IntrusiveHeap<T>::const_iterator it;
  101. switch (op) {
  102. case kInsert: {
  103. it = heap->insert(T(value));
  104. break;
  105. }
  106. case kEmplace: {
  107. it = heap->emplace(value);
  108. break;
  109. }
  110. case kGrowingOperationsCount:
  111. NOTREACHED();
  112. }
  113. EXPECT_EQ(old_size + 1, heap->size());
  114. EXPECT_EQ(value, it->value());
  115. EXPECT_EQ(it->GetHeapHandle().index(), heap->ToIndex(it));
  116. }
  117. // Helper struct for determining with the given value type T is movable or not.
  118. // Used to determine whether or not the "take" operations can be used.
  119. template <typename T>
  120. struct NotMovable {
  121. static constexpr bool value = !std::is_nothrow_move_constructible<T>::value &&
  122. std::is_copy_constructible<T>::value;
  123. };
  124. // Invokes "take" if the type is movable, otherwise invokes erase.
  125. template <typename T, bool kNotMovable = NotMovable<T>::value>
  126. struct Take;
  127. template <typename T>
  128. struct Take<T, true> {
  129. static void Do(IntrusiveHeap<T>* heap, size_t index) { heap->erase(index); }
  130. };
  131. template <typename T>
  132. struct Take<T, false> {
  133. static void Do(IntrusiveHeap<T>* heap, size_t index) {
  134. int value = heap->at(index).value();
  135. T t = heap->take(index);
  136. EXPECT_EQ(value, t.value());
  137. EXPECT_FALSE(t.GetHeapHandle().IsValid());
  138. }
  139. };
  140. // Invokes "take_top" if the type is movable, otherwise invokes pop.
  141. template <typename T, bool kNotMovable = NotMovable<T>::value>
  142. struct TakeTop;
  143. template <typename T>
  144. struct TakeTop<T, true> {
  145. static void Do(IntrusiveHeap<T>* heap) { heap->pop(); }
  146. };
  147. template <typename T>
  148. struct TakeTop<T, false> {
  149. static void Do(IntrusiveHeap<T>* heap) {
  150. int value = heap->at(0).value();
  151. T t = heap->take_top();
  152. EXPECT_EQ(value, t.value());
  153. EXPECT_FALSE(t.GetHeapHandle().IsValid());
  154. }
  155. };
  156. // Randomly selects a shrinking operations, applies it to the given |heap| and
  157. // validates that the operation completed as expected and resulted in a valid
  158. // heap. The "take" operations will only be invoked for a value type T that
  159. // supports move operations, otherwise they will be mapped to erase/pop.
  160. template <typename T>
  161. void DoShrinkingOperation(IntrusiveHeap<T>* heap) {
  162. ShrinkingOperations op = static_cast<ShrinkingOperations>(
  163. base::RandInt(0, kShrinkingOperationsCount - 1));
  164. size_t old_size = heap->size();
  165. size_t index = static_cast<size_t>(base::RandInt(0, old_size - 1));
  166. switch (op) {
  167. case kTake: {
  168. Take<T>::Do(heap, index);
  169. break;
  170. }
  171. case kTakeTop: {
  172. TakeTop<T>::Do(heap);
  173. break;
  174. }
  175. case kErase: {
  176. heap->erase(index);
  177. break;
  178. }
  179. case kPop: {
  180. heap->pop();
  181. break;
  182. }
  183. case kShrinkingOperationsCount:
  184. NOTREACHED();
  185. }
  186. EXPECT_EQ(old_size - 1, heap->size());
  187. }
  188. // Randomly selects a same size operation, applies it to the given |heap| and
  189. // validates that the operation completed as expected and resulted in a valid
  190. // heap.
  191. template <typename T>
  192. void DoSameSizeOperation(IntrusiveHeap<T>* heap) {
  193. SameSizeOperations op = static_cast<SameSizeOperations>(
  194. base::RandInt(0, kSameSizeOperationsCount - 1));
  195. size_t old_size = heap->size();
  196. size_t index = static_cast<size_t>(base::RandInt(0, old_size - 1));
  197. if (op == kReplaceTop)
  198. index = 0;
  199. int new_value = base::RandInt(0, 1000);
  200. typename IntrusiveHeap<T>::const_iterator it;
  201. switch (op) {
  202. case kReplace: {
  203. it = heap->Replace(index, T(new_value));
  204. break;
  205. }
  206. case kReplaceTop: {
  207. it = heap->ReplaceTop(T(new_value));
  208. break;
  209. }
  210. case kUpdate: {
  211. it = heap->Modify(
  212. index, [&new_value](T& element) { element.set_value(new_value); });
  213. break;
  214. }
  215. case kSameSizeOperationsCount:
  216. NOTREACHED();
  217. }
  218. EXPECT_EQ(old_size, heap->size());
  219. EXPECT_EQ(new_value, it->value());
  220. EXPECT_EQ(it->GetHeapHandle().index(), heap->ToIndex(it));
  221. }
  222. // Randomly selects an operation, applies it to the given |heap| and validates
  223. // that the operation completed as expected and resulted in a valid heap.
  224. template <typename T>
  225. void DoRandomHeapOperation(IntrusiveHeap<T>* heap) {
  226. static constexpr int kMinHeapSize = 10u;
  227. static constexpr int kMaxHeapSize = 100u;
  228. OperationTypes operation_type =
  229. static_cast<OperationTypes>(base::RandInt(0, kOperationTypesCount - 1));
  230. // Keep the heap size bounded by forcing growing and shrinking operations when
  231. // it exceeds the bounds.
  232. if (heap->size() < kMinHeapSize) {
  233. operation_type = kGrowing;
  234. } else if (heap->size() > kMaxHeapSize) {
  235. operation_type = kShrinking;
  236. }
  237. switch (operation_type) {
  238. case kGrowing:
  239. DoGrowingOperation(heap);
  240. break;
  241. case kShrinking:
  242. DoShrinkingOperation(heap);
  243. break;
  244. case kSameSize:
  245. DoSameSizeOperation(heap);
  246. break;
  247. case kOperationTypesCount:
  248. NOTREACHED();
  249. }
  250. }
  251. // A stress test that is only applicable to value types T that support move
  252. // operations.
  253. template <typename T>
  254. void MoveStressTest() {
  255. IntrusiveHeap<T> heap({2, 4, 6, 8});
  256. EXPECT_EQ(4u, heap.size());
  257. EXPECT_FALSE(heap.empty());
  258. ExpectHeap(heap);
  259. IntrusiveHeap<T> heap2(std::move(heap));
  260. EXPECT_EQ(4u, heap2.size());
  261. EXPECT_FALSE(heap2.empty());
  262. ExpectHeap(heap2);
  263. EXPECT_EQ(0u, heap.size());
  264. EXPECT_TRUE(heap.empty());
  265. ExpectHeap(heap);
  266. heap = std::move(heap2);
  267. EXPECT_EQ(4u, heap.size());
  268. EXPECT_FALSE(heap.empty());
  269. ExpectHeap(heap);
  270. EXPECT_EQ(0u, heap2.size());
  271. EXPECT_TRUE(heap2.empty());
  272. ExpectHeap(heap2);
  273. }
  274. // A stress that that is only applicable to value types T that support copy
  275. // operations.
  276. template <typename T>
  277. void CopyStressTest() {
  278. IntrusiveHeap<T> heap({2, 4, 6, 8});
  279. EXPECT_EQ(4u, heap.size());
  280. EXPECT_FALSE(heap.empty());
  281. ExpectHeap(heap);
  282. IntrusiveHeap<T> heap2(heap);
  283. EXPECT_EQ(4u, heap2.size());
  284. EXPECT_FALSE(heap2.empty());
  285. ExpectHeap(heap2);
  286. EXPECT_EQ(4u, heap.size());
  287. EXPECT_FALSE(heap.empty());
  288. ExpectHeap(heap);
  289. IntrusiveHeap<T> heap3({1, 3, 5});
  290. heap3.clear();
  291. heap3 = heap;
  292. EXPECT_EQ(4u, heap3.size());
  293. EXPECT_FALSE(heap3.empty());
  294. ExpectHeap(heap);
  295. EXPECT_EQ(4u, heap.size());
  296. EXPECT_FALSE(heap.empty());
  297. ExpectHeap(heap);
  298. EXPECT_TRUE(heap == heap2);
  299. EXPECT_FALSE(heap != heap2);
  300. }
  301. // A stress test that is applicable to all value types, whether or not they
  302. // support copy and/or move operations.
  303. template <typename T>
  304. void GeneralStressTest() {
  305. std::vector<int> vector{2, 4, 6, 8};
  306. IntrusiveHeap<T> heap(vector.begin(), vector.end());
  307. EXPECT_EQ(4u, heap.size());
  308. EXPECT_FALSE(heap.empty());
  309. ExpectHeap(heap);
  310. heap.clear();
  311. EXPECT_EQ(0u, heap.size());
  312. EXPECT_TRUE(heap.empty());
  313. ExpectHeap(heap);
  314. // Create an element and get a handle to it.
  315. auto it = heap.insert(T(34));
  316. EXPECT_EQ(1u, heap.size());
  317. HeapHandle* handle = it->handle();
  318. EXPECT_EQ(0u, handle->index());
  319. ExpectHeap(heap);
  320. // Add some other elements.
  321. heap.insert(T(12));
  322. heap.emplace(14);
  323. EXPECT_EQ(3u, heap.size());
  324. ExpectHeap(heap);
  325. // The handle should have tracked the element it is associated with.
  326. EXPECT_EQ(34, heap[*handle].value());
  327. // Replace with a value that shouldn't need moving in the heap.
  328. size_t index = handle->index();
  329. handle = heap.Replace(*handle, T(40))->handle();
  330. EXPECT_EQ(3u, heap.size());
  331. ExpectHeap(heap);
  332. EXPECT_EQ(index, handle->index());
  333. // Replace with a value that should cause the entry to move.
  334. handle = heap.Replace(handle->index(), T(1))->handle();
  335. EXPECT_EQ(3u, heap.size());
  336. ExpectHeap(heap);
  337. EXPECT_NE(index, handle->index());
  338. // Replace the top element.
  339. heap.ReplaceTop(T(65));
  340. EXPECT_EQ(3u, heap.size());
  341. ExpectHeap(heap);
  342. // Insert several more elements.
  343. std::vector<int> elements({13, 17, 19, 23, 29, 31, 37, 41});
  344. heap.insert(elements.begin(), elements.end());
  345. EXPECT_EQ(11u, heap.size());
  346. ExpectHeap(heap);
  347. // Invasively change an element that is already inside the heap, and then
  348. // repair the heap.
  349. T* element = const_cast<T*>(&heap[7]);
  350. element->set_value(97);
  351. heap.Update(7u);
  352. ExpectHeap(heap);
  353. // Safely modify an element that is already inside the heap.
  354. heap.Modify(7u, [](T& element) { element.set_value(128); });
  355. ExpectHeap(heap);
  356. // Do some more updates that are no-ops, just to explore all the flavours of
  357. // ToIndex.
  358. handle = heap[5].handle();
  359. heap.Update(*handle);
  360. heap.Update(heap.begin() + 6);
  361. heap.Update(heap.rbegin() + 8);
  362. ExpectHeap(heap);
  363. handle = heap[5].handle();
  364. EXPECT_TRUE(handle);
  365. EXPECT_EQ(5u, handle->index());
  366. EXPECT_EQ(5u, heap.ToIndex(*handle));
  367. EXPECT_EQ(5u, heap.ToIndex(heap.begin() + 5));
  368. EXPECT_EQ(5u, heap.ToIndex(heap.cbegin() + 5));
  369. EXPECT_EQ(5u, heap.ToIndex(heap.rbegin() + 5));
  370. EXPECT_EQ(5u, heap.ToIndex(heap.crbegin() + 5));
  371. EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.end()));
  372. EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.cend()));
  373. EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.rend()));
  374. EXPECT_EQ(HeapHandle::kInvalidIndex, heap.ToIndex(heap.crend()));
  375. EXPECT_EQ(&heap[0], &heap.at(0));
  376. EXPECT_EQ(&heap[0], &heap.front());
  377. EXPECT_EQ(&heap[0], &heap.top());
  378. EXPECT_EQ(&heap[heap.size() - 1], &heap.back());
  379. EXPECT_EQ(&heap[0], heap.data());
  380. // Do a bunch of random operations on a heap as a stress test.
  381. for (size_t i = 0; i < 1000; ++i) {
  382. DoRandomHeapOperation(&heap);
  383. ExpectHeap(heap);
  384. }
  385. }
  386. // A basic value type that wraps an integer. This is default constructible, and
  387. // supports both move and copy operations.
  388. class Value : public InternalHeapHandleStorage {
  389. public:
  390. explicit Value(int value) : value_(value) {}
  391. Value() : value_(-1) {}
  392. Value(Value&& other) noexcept
  393. : InternalHeapHandleStorage(std::move(other)),
  394. value_(std::exchange(other.value_, -1)) {}
  395. Value(const Value& other) : value_(other.value_) {
  396. HeapHandle h = other.GetHeapHandle();
  397. if (h.IsValid())
  398. SetHeapHandle(h);
  399. }
  400. ~Value() override {}
  401. Value& operator=(Value&& other) noexcept {
  402. InternalHeapHandleStorage::operator=(std::move(other));
  403. value_ = std::exchange(other.value_, -1);
  404. return *this;
  405. }
  406. Value& operator=(const Value& other) {
  407. value_ = other.value_;
  408. return *this;
  409. }
  410. int value() const { return value_; }
  411. void set_value(int value) { value_ = value; }
  412. bool operator==(const Value& rhs) const { return value_ == rhs.value_; }
  413. bool operator!=(const Value& rhs) const { return value_ != rhs.value_; }
  414. bool operator<=(const Value& rhs) const { return value_ <= rhs.value_; }
  415. bool operator>=(const Value& rhs) const { return value_ >= rhs.value_; }
  416. bool operator<(const Value& rhs) const { return value_ < rhs.value_; }
  417. bool operator>(const Value& rhs) const { return value_ > rhs.value_; }
  418. private:
  419. int value_;
  420. };
  421. // Macro for creating versions of Value that selectively enable/disable
  422. // default-constructors, move-operations and copy-operations.
  423. #define DEFINE_VALUE_TYPE(name, default_construct, move, copy) \
  424. class name : public Value { \
  425. public: \
  426. explicit name(int value) : Value(value) {} \
  427. name() = default_construct; \
  428. name(name&&) noexcept = move; \
  429. name(const name&) = copy; \
  430. name& operator=(name&&) noexcept = move; \
  431. name& operator=(const name&) = copy; \
  432. };
  433. DEFINE_VALUE_TYPE(Value_DMC, default, default, default)
  434. DEFINE_VALUE_TYPE(Value_DmC, default, delete, default)
  435. DEFINE_VALUE_TYPE(Value_DMc, default, default, delete)
  436. DEFINE_VALUE_TYPE(Value_dMC, delete, default, default)
  437. DEFINE_VALUE_TYPE(Value_dmC, delete, delete, default)
  438. DEFINE_VALUE_TYPE(Value_dMc, delete, default, delete)
  439. // Used to validate that the generated value types work as expected wrt
  440. // default-constructors, move-operations and copy-operations.
  441. template <typename ValueType, bool D, bool M, bool C>
  442. void ValidateValueType() {
  443. static_assert(std::is_default_constructible<ValueType>::value == D, "oops");
  444. static_assert(std::is_move_constructible<ValueType>::value == M, "oops");
  445. static_assert(std::is_move_assignable<ValueType>::value == M, "oops");
  446. static_assert(std::is_copy_constructible<ValueType>::value == C, "oops");
  447. static_assert(std::is_copy_assignable<ValueType>::value == C, "oops");
  448. }
  449. // A small test element that provides its own HeapHandle storage and implements
  450. // the contract expected of the DefaultHeapHandleAccessor.
  451. struct TestElement {
  452. int key;
  453. HeapHandle* handle;
  454. // Make this a min-heap by return > instead of <.
  455. bool operator<(const TestElement& other) const { return key > other.key; }
  456. void SetHeapHandle(HeapHandle h) {
  457. if (handle)
  458. *handle = h;
  459. }
  460. void ClearHeapHandle() {
  461. if (handle)
  462. handle->reset();
  463. }
  464. HeapHandle GetHeapHandle() const {
  465. if (handle)
  466. return *handle;
  467. return HeapHandle::Invalid();
  468. }
  469. };
  470. } // namespace
  471. ////////////////////////////////////////////////////////////////////////////////
  472. // TEST SUITE 1
  473. //
  474. // Explicit tests of a simple heap using WithHeapHandle<>.
  475. TEST(IntrusiveHeapTest, Constructors) {
  476. {
  477. // Default constructor.
  478. IntrusiveHeapInt heap;
  479. EXPECT_TRUE(heap.empty());
  480. }
  481. {
  482. // Constructor with iterators.
  483. std::vector<int> ints{CANONICAL_ELEMENTS};
  484. IntrusiveHeapInt heap(ints.begin(), ints.end());
  485. ExpectCanonical(heap);
  486. // Move constructor.
  487. IntrusiveHeapInt heap2(std::move(heap));
  488. EXPECT_TRUE(heap.empty());
  489. ExpectCanonical(heap2);
  490. }
  491. {
  492. // Constructor with initializer list.
  493. IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
  494. ExpectCanonical(heap);
  495. }
  496. }
  497. TEST(IntrusiveHeapTest, Assignment) {
  498. IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
  499. // Move assignment.
  500. IntrusiveHeapInt heap2;
  501. heap2 = std::move(heap);
  502. EXPECT_TRUE(heap.empty());
  503. ExpectCanonical(heap2);
  504. }
  505. TEST(IntrusiveHeapTest, Swap) {
  506. IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
  507. IntrusiveHeapInt heap2;
  508. swap(heap, heap2);
  509. EXPECT_TRUE(heap.empty());
  510. ExpectCanonical(heap2);
  511. heap.swap(heap2);
  512. EXPECT_TRUE(heap2.empty());
  513. ExpectCanonical(heap);
  514. }
  515. TEST(IntrusiveHeapTest, ElementAccess) {
  516. IntrusiveHeapInt heap{CANONICAL_ELEMENTS};
  517. EXPECT_EQ(heap.front(), heap[0]);
  518. EXPECT_EQ(heap.back(), heap[7]);
  519. EXPECT_EQ(heap.top(), heap[0]);
  520. for (size_t i = 0; i < heap.size(); ++i) {
  521. EXPECT_EQ(heap[i], heap.at(i));
  522. EXPECT_EQ(heap[i], heap.data()[i]);
  523. }
  524. }
  525. TEST(IntrusiveHeapTest, SizeManagement) {
  526. IntrusiveHeapInt heap;
  527. EXPECT_TRUE(heap.empty());
  528. EXPECT_LE(heap.size(), heap.capacity());
  529. MakeCanonical(&heap);
  530. EXPECT_FALSE(heap.empty());
  531. EXPECT_LE(heap.size(), heap.capacity());
  532. }
  533. TEST(IntrusiveHeapTest, Iterators) {
  534. IntrusiveHeapInt heap;
  535. MakeCanonical(&heap);
  536. size_t i = 0;
  537. for (auto it = heap.begin(); it != heap.end(); ++it) {
  538. EXPECT_EQ(i, heap.ToIndex(it));
  539. EXPECT_EQ(&(*it), heap.data() + i);
  540. ++i;
  541. }
  542. i = heap.size() - 1;
  543. for (auto rit = heap.rbegin(); rit != heap.rend(); ++rit) {
  544. EXPECT_EQ(i, heap.ToIndex(rit));
  545. EXPECT_EQ(&(*rit), heap.data() + i);
  546. --i;
  547. }
  548. }
  549. ////////////////////////////////////////////////////////////////////////////////
  550. // TEST SUITE 2
  551. //
  552. // Exhaustive stress tests with different value types, exploring all
  553. // possibilities of default-constrible, movable and copyable value types.
  554. TEST(IntrusiveHeapTest, MoveOnlyNoDefaultConstructorTest) {
  555. using ValueType = Value_dMc;
  556. ValidateValueType<ValueType, false, true, false>();
  557. MoveStressTest<ValueType>();
  558. GeneralStressTest<ValueType>();
  559. }
  560. TEST(IntrusiveHeapTest, CopyOnlyNoDefaultConstructorTest) {
  561. using ValueType = Value_dmC;
  562. ValidateValueType<ValueType, false, false, true>();
  563. // We cannot perform CopyStressTest nor GeneralStressTest here, because
  564. // Value_dmC has deleted move constructor and assignment operator. See
  565. // crbug.com/1022576.
  566. }
  567. TEST(IntrusiveHeapTest, CopyAndMoveNoDefaultConstructorTest) {
  568. using ValueType = Value_dMC;
  569. ValidateValueType<ValueType, false, true, true>();
  570. CopyStressTest<ValueType>();
  571. MoveStressTest<ValueType>();
  572. GeneralStressTest<ValueType>();
  573. }
  574. TEST(IntrusiveHeapTest, MoveOnlyWithDefaultConstructorTest) {
  575. using ValueType = Value_DMc;
  576. ValidateValueType<ValueType, true, true, false>();
  577. MoveStressTest<ValueType>();
  578. GeneralStressTest<ValueType>();
  579. }
  580. TEST(IntrusiveHeapTest, CopyOnlyWithDefaultConstructorTest) {
  581. using ValueType = Value_DmC;
  582. ValidateValueType<ValueType, true, false, true>();
  583. // We cannot perform CopyStressTest nor GeneralStressTest here, because
  584. // Value_DmC has deleted move constructor and assignment operator. See
  585. // crbug.com/1022576.
  586. }
  587. TEST(IntrusiveHeapTest, CopyAndMoveWithDefaultConstructorTest) {
  588. using ValueType = Value_DMC;
  589. ValidateValueType<ValueType, true, true, true>();
  590. CopyStressTest<ValueType>();
  591. MoveStressTest<ValueType>();
  592. GeneralStressTest<ValueType>();
  593. }
  594. ////////////////////////////////////////////////////////////////////////////////
  595. // TEST SUITE 3
  596. //
  597. // Tests individual functions on a custom type that provides heap handle storage
  598. // externally through raw pointers.
  599. TEST(IntrusiveHeapTest, Basic) {
  600. IntrusiveHeap<TestElement> heap;
  601. EXPECT_TRUE(heap.empty());
  602. EXPECT_EQ(0u, heap.size());
  603. }
  604. TEST(IntrusiveHeapTest, Clear) {
  605. IntrusiveHeap<TestElement> heap;
  606. HeapHandle index1;
  607. heap.insert({11, &index1});
  608. EXPECT_EQ(1u, heap.size());
  609. EXPECT_TRUE(index1.IsValid());
  610. heap.clear();
  611. EXPECT_EQ(0u, heap.size());
  612. EXPECT_FALSE(index1.IsValid());
  613. }
  614. TEST(IntrusiveHeapTest, Destructor) {
  615. HeapHandle index1;
  616. {
  617. IntrusiveHeap<TestElement> heap;
  618. heap.insert({11, &index1});
  619. EXPECT_EQ(1u, heap.size());
  620. EXPECT_TRUE(index1.IsValid());
  621. }
  622. EXPECT_FALSE(index1.IsValid());
  623. }
  624. TEST(IntrusiveHeapTest, Min) {
  625. IntrusiveHeap<TestElement> heap;
  626. heap.insert({9, nullptr});
  627. heap.insert({10, nullptr});
  628. heap.insert({8, nullptr});
  629. heap.insert({2, nullptr});
  630. heap.insert({7, nullptr});
  631. heap.insert({15, nullptr});
  632. heap.insert({22, nullptr});
  633. heap.insert({3, nullptr});
  634. EXPECT_FALSE(heap.empty());
  635. EXPECT_EQ(8u, heap.size());
  636. EXPECT_EQ(2, heap.top().key);
  637. }
  638. TEST(IntrusiveHeapTest, MinDuplicates) {
  639. IntrusiveHeap<TestElement> heap;
  640. heap.insert({2, nullptr});
  641. heap.insert({2, nullptr});
  642. heap.insert({3, nullptr});
  643. EXPECT_FALSE(heap.empty());
  644. EXPECT_EQ(3u, heap.size());
  645. EXPECT_EQ(2, heap.top().key);
  646. }
  647. TEST(IntrusiveHeapTest, InsertAscending) {
  648. IntrusiveHeap<TestElement> heap;
  649. for (int i = 0; i < 50; i++)
  650. heap.insert({i, nullptr});
  651. EXPECT_EQ(0, heap.top().key);
  652. EXPECT_EQ(50u, heap.size());
  653. }
  654. TEST(IntrusiveHeapTest, InsertDescending) {
  655. IntrusiveHeap<TestElement> heap;
  656. for (int i = 0; i < 50; i++)
  657. heap.insert({50 - i, nullptr});
  658. EXPECT_EQ(1, heap.top().key);
  659. EXPECT_EQ(50u, heap.size());
  660. }
  661. TEST(IntrusiveHeapTest, HeapIndex) {
  662. HeapHandle index5;
  663. HeapHandle index4;
  664. HeapHandle index3;
  665. HeapHandle index2;
  666. HeapHandle index1;
  667. IntrusiveHeap<TestElement> heap;
  668. EXPECT_FALSE(index1.IsValid());
  669. EXPECT_FALSE(index2.IsValid());
  670. EXPECT_FALSE(index3.IsValid());
  671. EXPECT_FALSE(index4.IsValid());
  672. EXPECT_FALSE(index5.IsValid());
  673. heap.insert({15, &index5});
  674. heap.insert({14, &index4});
  675. heap.insert({13, &index3});
  676. heap.insert({12, &index2});
  677. heap.insert({11, &index1});
  678. EXPECT_TRUE(index1.IsValid());
  679. EXPECT_TRUE(index2.IsValid());
  680. EXPECT_TRUE(index3.IsValid());
  681. EXPECT_TRUE(index4.IsValid());
  682. EXPECT_TRUE(index5.IsValid());
  683. EXPECT_FALSE(heap.empty());
  684. }
  685. TEST(IntrusiveHeapTest, HeapIndexDuplicates) {
  686. HeapHandle index2;
  687. HeapHandle index1;
  688. IntrusiveHeap<TestElement> heap;
  689. EXPECT_FALSE(index1.IsValid());
  690. EXPECT_FALSE(index2.IsValid());
  691. heap.insert({2, &index2});
  692. heap.insert({2, &index1});
  693. EXPECT_TRUE(index1.IsValid());
  694. EXPECT_TRUE(index2.IsValid());
  695. EXPECT_EQ(2U, heap.size());
  696. }
  697. TEST(IntrusiveHeapTest, Pop) {
  698. IntrusiveHeap<TestElement> heap;
  699. HeapHandle index1;
  700. HeapHandle index2;
  701. heap.insert({11, &index1});
  702. heap.insert({12, &index2});
  703. EXPECT_EQ(2u, heap.size());
  704. EXPECT_TRUE(index1.IsValid());
  705. EXPECT_TRUE(index2.IsValid());
  706. heap.pop();
  707. EXPECT_EQ(1u, heap.size());
  708. EXPECT_FALSE(index1.IsValid());
  709. EXPECT_TRUE(index2.IsValid());
  710. heap.pop();
  711. EXPECT_EQ(0u, heap.size());
  712. EXPECT_FALSE(index1.IsValid());
  713. EXPECT_FALSE(index2.IsValid());
  714. }
  715. TEST(IntrusiveHeapTest, PopMany) {
  716. IntrusiveHeap<TestElement> heap;
  717. for (int i = 0; i < 500; i++)
  718. heap.insert({i, nullptr});
  719. EXPECT_FALSE(heap.empty());
  720. EXPECT_EQ(500u, heap.size());
  721. for (int i = 0; i < 500; i++) {
  722. EXPECT_EQ(i, heap.top().key);
  723. heap.pop();
  724. }
  725. EXPECT_TRUE(heap.empty());
  726. }
  727. TEST(IntrusiveHeapTest, Erase) {
  728. IntrusiveHeap<TestElement> heap;
  729. HeapHandle index12;
  730. heap.insert({15, nullptr});
  731. heap.insert({14, nullptr});
  732. heap.insert({13, nullptr});
  733. heap.insert({12, &index12});
  734. heap.insert({11, nullptr});
  735. EXPECT_EQ(5u, heap.size());
  736. EXPECT_TRUE(index12.IsValid());
  737. heap.erase(index12);
  738. EXPECT_EQ(4u, heap.size());
  739. EXPECT_FALSE(index12.IsValid());
  740. EXPECT_EQ(11, heap.top().key);
  741. heap.pop();
  742. EXPECT_EQ(13, heap.top().key);
  743. heap.pop();
  744. EXPECT_EQ(14, heap.top().key);
  745. heap.pop();
  746. EXPECT_EQ(15, heap.top().key);
  747. heap.pop();
  748. EXPECT_TRUE(heap.empty());
  749. }
  750. TEST(IntrusiveHeapTest, ReplaceTop) {
  751. IntrusiveHeap<TestElement> heap;
  752. for (int i = 0; i < 500; i++)
  753. heap.insert({500 - i, nullptr});
  754. EXPECT_EQ(1, heap.top().key);
  755. for (int i = 0; i < 500; i++)
  756. heap.ReplaceTop({1000 + i, nullptr});
  757. EXPECT_EQ(1000, heap.top().key);
  758. }
  759. TEST(IntrusiveHeapTest, ReplaceTopWithNonLeafNode) {
  760. IntrusiveHeap<TestElement> heap;
  761. for (int i = 0; i < 50; i++) {
  762. heap.insert({i, nullptr});
  763. heap.insert({200 + i, nullptr});
  764. }
  765. EXPECT_EQ(0, heap.top().key);
  766. for (int i = 0; i < 50; i++)
  767. heap.ReplaceTop({100 + i, nullptr});
  768. for (int i = 0; i < 50; i++) {
  769. EXPECT_EQ((100 + i), heap.top().key);
  770. heap.pop();
  771. }
  772. for (int i = 0; i < 50; i++) {
  773. EXPECT_EQ((200 + i), heap.top().key);
  774. heap.pop();
  775. }
  776. EXPECT_TRUE(heap.empty());
  777. }
  778. TEST(IntrusiveHeapTest, ReplaceTopCheckAllFinalPositions) {
  779. HeapHandle index[100];
  780. HeapHandle top_index;
  781. for (int j = -1; j <= 201; j += 2) {
  782. IntrusiveHeap<TestElement> heap;
  783. for (size_t i = 0; i < 100; i++) {
  784. heap.insert({static_cast<int>(i) * 2, &index[i]});
  785. }
  786. heap.ReplaceTop({j, &top_index});
  787. int prev = -2;
  788. while (!heap.empty()) {
  789. DCHECK_GT(heap.top().key, prev);
  790. DCHECK(heap.top().key == j || (heap.top().key % 2) == 0);
  791. DCHECK_NE(heap.top().key, 0);
  792. prev = heap.top().key;
  793. heap.pop();
  794. }
  795. }
  796. }
  797. TEST(IntrusiveHeapTest, ReplaceUp) {
  798. IntrusiveHeap<TestElement> heap;
  799. HeapHandle index[10];
  800. for (size_t i = 0; i < 10; i++) {
  801. heap.insert({static_cast<int>(i) * 2, &index[i]});
  802. }
  803. heap.Replace(index[5], {17, &index[5]});
  804. std::vector<int> results;
  805. while (!heap.empty()) {
  806. results.push_back(heap.top().key);
  807. heap.pop();
  808. }
  809. EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18));
  810. }
  811. TEST(IntrusiveHeapTest, ReplaceUpButDoesntMove) {
  812. IntrusiveHeap<TestElement> heap;
  813. HeapHandle index[10];
  814. for (size_t i = 0; i < 10; i++) {
  815. heap.insert({static_cast<int>(i) * 2, &index[i]});
  816. }
  817. heap.Replace(index[5], {11, &index[5]});
  818. std::vector<int> results;
  819. while (!heap.empty()) {
  820. results.push_back(heap.top().key);
  821. heap.pop();
  822. }
  823. EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18));
  824. }
  825. TEST(IntrusiveHeapTest, ReplaceDown) {
  826. IntrusiveHeap<TestElement> heap;
  827. HeapHandle index[10];
  828. for (size_t i = 0; i < 10; i++) {
  829. heap.insert({static_cast<int>(i) * 2, &index[i]});
  830. }
  831. heap.Replace(index[5], {1, &index[5]});
  832. std::vector<int> results;
  833. while (!heap.empty()) {
  834. results.push_back(heap.top().key);
  835. heap.pop();
  836. }
  837. EXPECT_THAT(results, testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18));
  838. }
  839. TEST(IntrusiveHeapTest, ReplaceDownButDoesntMove) {
  840. IntrusiveHeap<TestElement> heap;
  841. HeapHandle index[10];
  842. for (size_t i = 0; i < 10; i++) {
  843. heap.insert({static_cast<int>(i) * 2, &index[i]});
  844. }
  845. heap.Replace(index[5], {9, &index[5]});
  846. std::vector<int> results;
  847. while (!heap.empty()) {
  848. results.push_back(heap.top().key);
  849. heap.pop();
  850. }
  851. EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18));
  852. }
  853. TEST(IntrusiveHeapTest, ReplaceCheckAllFinalPositions) {
  854. HeapHandle index[100];
  855. for (int j = -1; j <= 201; j += 2) {
  856. IntrusiveHeap<TestElement> heap;
  857. for (size_t i = 0; i < 100; i++) {
  858. heap.insert({static_cast<int>(i) * 2, &index[i]});
  859. }
  860. heap.Replace(index[40], {j, &index[40]});
  861. int prev = -2;
  862. while (!heap.empty()) {
  863. DCHECK_GT(heap.top().key, prev);
  864. DCHECK(heap.top().key == j || (heap.top().key % 2) == 0);
  865. DCHECK_NE(heap.top().key, 80);
  866. prev = heap.top().key;
  867. heap.pop();
  868. }
  869. }
  870. }
  871. TEST(IntrusiveHeapTest, At) {
  872. HeapHandle index[10];
  873. IntrusiveHeap<TestElement> heap;
  874. for (int i = 0; i < 10; i++)
  875. heap.insert({static_cast<int>(i ^ (i + 1)), &index[i]});
  876. for (int i = 0; i < 10; i++) {
  877. EXPECT_EQ(heap.at(index[i]).key, i ^ (i + 1));
  878. EXPECT_EQ(heap.at(index[i]).handle, &index[i]);
  879. }
  880. }
  881. bool IsEven(int i) {
  882. return i % 2 == 0;
  883. }
  884. TEST(IntrusiveHeapTest, EraseIf) {
  885. HeapHandle index[10];
  886. IntrusiveHeap<TestElement> heap;
  887. for (int i = 0; i < 10; i++)
  888. heap.insert({i, &index[i]});
  889. ASSERT_EQ(heap.size(), 10u);
  890. // Remove all even elements.
  891. heap.EraseIf([](const TestElement& element) { return IsEven(element.key); });
  892. ASSERT_EQ(heap.size(), 5u);
  893. // Handles were correctly updated.
  894. for (int i = 0; i < 10; i++)
  895. EXPECT_EQ(IsEven(i), !index[i].IsValid());
  896. // Now iterate over all elements of the heap and check their handles.
  897. for (size_t i = 0; i < heap.size(); i++) {
  898. auto it = heap.begin();
  899. std::advance(it, i);
  900. // Retrieve the value of the element at this position.
  901. int value = it->key;
  902. // Its handle should have the correct index.
  903. EXPECT_EQ(index[value].index(), i);
  904. }
  905. std::vector<int> results;
  906. while (!heap.empty()) {
  907. results.push_back(heap.top().key);
  908. heap.pop();
  909. }
  910. EXPECT_THAT(results, testing::ElementsAre(1, 3, 5, 7, 9));
  911. }
  912. // A comparator class whose sole purpose is to allow the insertion of a
  913. // ScopedClosureRunner inside the heap. The ordering does not matter.
  914. class Comparator {
  915. public:
  916. bool operator()(const WithHeapHandle<ScopedClosureRunner>& lhs,
  917. const WithHeapHandle<ScopedClosureRunner>& rhs) {
  918. // Treat all closures as equal.
  919. return true;
  920. }
  921. };
  922. // Tests that inserting another element from the destructor of an object removed
  923. // during EraseIf() doesn't crash.
  924. TEST(IntrusiveHeapTest, EraseIf_Reentrancy) {
  925. IntrusiveHeap<WithHeapHandle<ScopedClosureRunner>, Comparator> heap;
  926. // The task that will post a new element inside the heap upon destruction of
  927. // the first.
  928. OnceClosure insert_task = BindLambdaForTesting([&]() {
  929. // Insert a null callback so it can be differentiated.
  930. heap.insert(OnceClosure());
  931. });
  932. heap.insert(ScopedClosureRunner(std::move(insert_task)));
  933. // The heap contains the non-null closure.
  934. EXPECT_EQ(heap.size(), 1u);
  935. EXPECT_TRUE(heap.top().value());
  936. // Erase the only element using EraseIf().
  937. heap.EraseIf([](const auto& element) { return true; });
  938. // Now the heap contains the null closure.
  939. EXPECT_EQ(heap.size(), 1u);
  940. EXPECT_FALSE(heap.top().value());
  941. }
  942. } // namespace base