jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/IntrusiveRedBlackTree.h>
10#include <AK/NonnullOwnPtr.h>
11#include <AK/Random.h>
12#include <AK/Vector.h>
13
14class IntrusiveTest {
15public:
16 IntrusiveTest(int value)
17 : m_some_value(value)
18 {
19 }
20
21 IntrusiveRedBlackTreeNode<int, IntrusiveTest, RawPtr<IntrusiveTest>> m_tree_node;
22 int m_some_value;
23};
24using IntrusiveRBTree = IntrusiveRedBlackTree<&IntrusiveTest::m_tree_node>;
25
26TEST_CASE(construct)
27{
28 IntrusiveRBTree empty;
29 EXPECT(empty.is_empty());
30 EXPECT(empty.size() == 0);
31}
32
33TEST_CASE(ints)
34{
35 IntrusiveRBTree test;
36 IntrusiveTest first { 10 };
37 test.insert(1, first);
38 IntrusiveTest second { 20 };
39 test.insert(3, second);
40 IntrusiveTest third { 30 };
41 test.insert(2, third);
42 EXPECT_EQ(test.size(), 3u);
43 EXPECT_EQ(test.find(3)->m_some_value, 20);
44 EXPECT_EQ(test.find(2)->m_some_value, 30);
45 EXPECT_EQ(test.find(1)->m_some_value, 10);
46 EXPECT(!test.remove(4));
47 EXPECT(test.remove(2));
48 EXPECT(test.remove(1));
49 EXPECT(test.remove(3));
50 EXPECT_EQ(test.size(), 0u);
51}
52
53TEST_CASE(largest_smaller_than)
54{
55 IntrusiveRBTree test;
56 IntrusiveTest first { 10 };
57 test.insert(1, first);
58 IntrusiveTest second { 20 };
59 test.insert(11, second);
60 IntrusiveTest third { 30 };
61 test.insert(21, third);
62 EXPECT_EQ(test.size(), 3u);
63 EXPECT_EQ(test.find_largest_not_above(3)->m_some_value, 10);
64 EXPECT_EQ(test.find_largest_not_above(17)->m_some_value, 20);
65 EXPECT_EQ(test.find_largest_not_above(22)->m_some_value, 30);
66 EXPECT_EQ(test.find_largest_not_above(-5), nullptr);
67 VERIFY(test.remove(1));
68 VERIFY(test.remove(11));
69 VERIFY(test.remove(21));
70}
71
72TEST_CASE(key_ordered_iteration)
73{
74 constexpr auto amount = 10000;
75 IntrusiveRBTree test;
76 Vector<NonnullOwnPtr<IntrusiveTest>> m_entries;
77 Array<int, amount> keys {};
78
79 // generate random key order
80 for (int i = 0; i < amount; i++) {
81 keys[i] = i;
82 }
83 for (size_t i = 0; i < amount; i++) {
84 swap(keys[i], keys[get_random<size_t>() % amount]);
85 }
86
87 // insert random keys
88 for (size_t i = 0; i < amount; i++) {
89 auto entry = make<IntrusiveTest>(keys[i]);
90 test.insert(keys[i], *entry);
91 m_entries.append(move(entry));
92 }
93
94 // check key-ordered iteration
95 int index = 0;
96 for (auto& value : test) {
97 EXPECT(value.m_some_value == index++);
98 }
99
100 // ensure we can remove all of them (aka, tree structure is not destroyed somehow)
101 for (size_t i = 0; i < amount; i++) {
102 EXPECT(test.remove(i));
103 }
104}
105
106TEST_CASE(clear)
107{
108 IntrusiveRBTree test;
109 Vector<NonnullOwnPtr<IntrusiveTest>> m_entries;
110 for (size_t i = 0; i < 1000; i++) {
111 auto entry = make<IntrusiveTest>(i);
112 test.insert(i, *entry);
113 m_entries.append(move(entry));
114 }
115 test.clear();
116 EXPECT_EQ(test.size(), 0u);
117}
118
119class IntrusiveRefPtrTest : public RefCounted<IntrusiveRefPtrTest> {
120public:
121 IntrusiveRefPtrTest()
122 {
123 }
124
125 IntrusiveRedBlackTreeNode<int, IntrusiveRefPtrTest, RefPtr<IntrusiveRefPtrTest>> m_tree_node;
126};
127using IntrusiveRefPtrRBTree = IntrusiveRedBlackTree<&IntrusiveRefPtrTest::m_tree_node>;
128
129TEST_CASE(intrusive_ref_ptr_no_ref_leaks)
130{
131 auto item = adopt_ref(*new IntrusiveRefPtrTest());
132 EXPECT_EQ(1u, item->ref_count());
133 IntrusiveRefPtrRBTree ref_tree;
134
135 ref_tree.insert(0, *item);
136 EXPECT_EQ(2u, item->ref_count());
137
138 ref_tree.remove(0);
139 EXPECT_EQ(1u, item->ref_count());
140}
141
142TEST_CASE(intrusive_ref_ptr_clear)
143{
144 auto item = adopt_ref(*new IntrusiveRefPtrTest());
145 EXPECT_EQ(1u, item->ref_count());
146 IntrusiveRefPtrRBTree ref_tree;
147
148 ref_tree.insert(0, *item);
149 EXPECT_EQ(2u, item->ref_count());
150
151 ref_tree.clear();
152 EXPECT_EQ(1u, item->ref_count());
153}
154
155TEST_CASE(intrusive_ref_ptr_destructor)
156{
157 auto item = adopt_ref(*new IntrusiveRefPtrTest());
158 EXPECT_EQ(1u, item->ref_count());
159
160 {
161 IntrusiveRefPtrRBTree ref_tree;
162 ref_tree.insert(0, *item);
163 EXPECT_EQ(2u, item->ref_count());
164 }
165
166 EXPECT_EQ(1u, item->ref_count());
167}
168
169class IntrusiveNonnullRefPtrTest : public RefCounted<IntrusiveNonnullRefPtrTest> {
170public:
171 IntrusiveNonnullRefPtrTest()
172 {
173 }
174
175 IntrusiveRedBlackTreeNode<int, IntrusiveNonnullRefPtrTest, NonnullRefPtr<IntrusiveNonnullRefPtrTest>> m_tree_node;
176};
177using IntrusiveNonnullRefPtrRBTree = IntrusiveRedBlackTree<&IntrusiveNonnullRefPtrTest::m_tree_node>;
178
179TEST_CASE(intrusive_nonnull_ref_ptr_intrusive)
180{
181 auto item = adopt_ref(*new IntrusiveNonnullRefPtrTest());
182 EXPECT_EQ(1u, item->ref_count());
183 IntrusiveNonnullRefPtrRBTree nonnull_ref_tree;
184
185 nonnull_ref_tree.insert(0, *item);
186 EXPECT_EQ(2u, item->ref_count());
187 EXPECT(!nonnull_ref_tree.is_empty());
188
189 nonnull_ref_tree.remove(0);
190 EXPECT_EQ(1u, item->ref_count());
191
192 EXPECT(nonnull_ref_tree.is_empty());
193}