Branch data Line data Source code
1 : : // Splay tree utilities -*- C++ -*-
2 : : // Copyright (C) 2020-2024 Free Software Foundation, Inc.
3 : : //
4 : : // This file is part of GCC.
5 : : //
6 : : // GCC is free software; you can redistribute it and/or modify it under
7 : : // the terms of the GNU General Public License as published by the Free
8 : : // Software Foundation; either version 3, or (at your option) any later
9 : : // version.
10 : : //
11 : : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : // for more details.
15 : : //
16 : : // You should have received a copy of the GNU General Public License
17 : : // along with GCC; see the file COPYING3. If not see
18 : : // <http://www.gnu.org/licenses/>.
19 : :
20 : : #define INCLUDE_ALGORITHM
21 : : #define INCLUDE_ARRAY
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "pretty-print.h"
26 : : #include "splay-tree-utils.h"
27 : : #include "selftest.h"
28 : :
29 : : #if CHECKING_P
30 : : namespace {
31 : : // A simple test node for rootless_splay_tree.
32 : : struct rootless_test_node
33 : : {
34 : : int data;
35 : : rootless_test_node *m_parent;
36 : : rootless_test_node *m_children[2];
37 : : };
38 : : }
39 : :
40 : : namespace selftest {
41 : :
42 : : // Random input data.
43 : : static const size_t MAX_DATA = 32768;
44 : : static const int data[] = {
45 : : 1379, 14643, 30579, 28160, 31750, 22280, 5502, 4720, 30075, 27595,
46 : : 8395, 19410, 518, 19709, 29694, 19865, 25372, 11752, 15485, 21547,
47 : : 25153, 25072, 10146, 3341, 15625, 3038, 10189, 19943, 1322, 11762,
48 : : 807, 430, 11284, 11841, 23965, 32008, 4547, 8087, 13225, 23054,
49 : : 22284, 13756, 2182, 26450, 30482, 32502, 23348, 20265, 29509, 3290,
50 : : 10807, 1242, 3212, 32178, 25354, 22032, 30509, 16157, 22432, 1295,
51 : : 8348, 23342, 24678, 193, 31016, 10316, 3872, 13521, 19211, 30594,
52 : : 12229, 4794, 25083, 16098, 28144, 27896, 4801, 20689, 31450, 15614,
53 : : 19597, 13731, 30309, 24846, 11042, 31929, 18306, 28520, 16907, 12488,
54 : : 15001, 18487, 3438, 1706, 4829, 20892, 6226, 18204, 15776, 30717,
55 : : 19398, 2480, 19434, 2838, 2605, 3994, 22538, 12269, 6486, 1314,
56 : : 30301, 9919, 31405, 30847, 25000, 24013, 22196, 30220, 31415, 14630,
57 : : 26319, 4880, 21292, 20217, 20078, 14679, 25686, 28675, 13883, 14853,
58 : : 2872, 2428, 3636, 14131, 2952, 2133, 4470, 25808, 12576, 31395,
59 : : 5938, 28393, 14553, 4494, 14928, 24310, 17394, 17436, 23385, 22792,
60 : : 9785, 13118, 22338, 23320, 27059, 17663, 16434, 14954, 16962, 31088,
61 : : 22247, 22600, 7980, 1344, 15635, 13611, 32739, 3283, 12924, 17904,
62 : : 28216, 7542, 9212, 28308, 18873, 3912, 5473, 4666, 11900, 21420,
63 : : 20072, 27662, 16445, 29848, 24444, 31668, 30664, 14287, 13754, 29276,
64 : : 21462, 25517, 17632, 8105, 32510, 16677, 11162, 20734, 26873, 5097
65 : : };
66 : :
67 : : // Look up VALUE in TREE using the single-comparator lookup function.
68 : : static int
69 : 3208 : lookup1 (splay_tree<int> &tree, int value)
70 : : {
71 : 34540 : auto compare = [&](splay_tree_node<int> *node)
72 : : {
73 : 31332 : return value - node->value ();
74 : 3208 : };
75 : 2400 : return tree.lookup (compare);
76 : : }
77 : :
78 : : // Look up VALUE in TREE using the double-comparator lookup function.
79 : : static int
80 : 2400 : lookup2 (splay_tree<int> &tree, int value)
81 : : {
82 : 28868 : auto want_something_smaller = [&](splay_tree_node<int> *node)
83 : : {
84 : 26468 : return value < node->value ();
85 : 2400 : };
86 : 19224 : auto want_something_bigger = [&](splay_tree_node<int> *node)
87 : : {
88 : 16824 : return value > node->value ();
89 : 2400 : };
90 : 2400 : return tree.lookup (want_something_smaller, want_something_bigger);
91 : : }
92 : :
93 : : // Test printing TREE to a pretty printer. Don't check the output against
94 : : // anything; just make sure that it doesn't crash.
95 : : static void
96 : 4 : test_print (splay_tree<int> &tree)
97 : : {
98 : 804 : auto print_node = [](pretty_printer *pp, splay_tree_node<int> *node)
99 : : {
100 : 800 : pp_decimal_int (pp, node->value ());
101 : 800 : };
102 : 4 : pretty_printer pp;
103 : 4 : tree.print (&pp, print_node);
104 : 4 : }
105 : :
106 : : // Test various lookups on TREE using LOOKUP, where lookup returns the
107 : : // same kind of value as the rooted_splay_tree lookup functions.
108 : : static void
109 : 8 : test_lookup (splay_tree<int> &tree, int (*lookup) (splay_tree<int> &, int))
110 : : {
111 : : // Look up values that are known to exist.
112 : 1608 : for (int value : data)
113 : 1600 : ASSERT_EQ (lookup (tree, value), 0);
114 : :
115 : : // Look up values that are 1 less than values that are known to exist.
116 : 1608 : for (int value : data)
117 : : {
118 : 1600 : int result = lookup (tree, value - 1);
119 : 1600 : if (result == 0)
120 : 0 : ASSERT_EQ (tree->value (), value - 1);
121 : 1600 : else if (result < 0)
122 : : // VALUE - 1 is less than the root.
123 : 1372 : ASSERT_EQ (tree->value (), value);
124 : 228 : else if (result > 0)
125 : : {
126 : : // VALUE - 1 is greater than the root.
127 : 228 : ASSERT_TRUE (tree->value () < value - 1);
128 : 228 : if (tree.splay_next_node ())
129 : 228 : ASSERT_EQ (tree->value (), value);
130 : : }
131 : : }
132 : :
133 : : // Look up values that are 1 greater than values that are known to exist.
134 : 1608 : for (int value : data)
135 : : {
136 : 1600 : int result = lookup (tree, value + 1);
137 : 1600 : if (result == 0)
138 : 0 : ASSERT_EQ (tree->value (), value + 1);
139 : 1600 : else if (result < 0)
140 : : {
141 : : // VALUE + 1 is less than the root.
142 : 448 : ASSERT_TRUE (tree->value () > value + 1);
143 : 448 : if (tree.splay_prev_node ())
144 : 448 : ASSERT_EQ (tree->value (), value);
145 : : }
146 : 1152 : else if (result > 0)
147 : : // VALUE + 1 is greater than the root.
148 : 1152 : ASSERT_EQ (tree->value (), value);
149 : : }
150 : 8 : }
151 : :
152 : : // Run all tests for this module.
153 : : void
154 : 4 : splay_tree_cc_tests ()
155 : : {
156 : 4 : obstack ob;
157 : 4 : gcc_obstack_init (&ob);
158 : :
159 : : // Build up the splay tree.
160 : 4 : splay_tree<int> tree;
161 : 804 : for (int value : data)
162 : : {
163 : 800 : auto *node = XOBNEW (&ob, splay_tree_node<int>);
164 : 800 : new (node) splay_tree_node<int> (value);
165 : 8072 : auto compare = [&](splay_tree_node<int> *other_node)
166 : : {
167 : 7272 : return value - other_node->value ();
168 : 800 : };
169 : 800 : bool inserted = tree.insert (node, compare);
170 : 800 : ASSERT_TRUE (inserted);
171 : : }
172 : :
173 : : // Test the single-comparator lookup function.
174 : 4 : test_lookup (tree, lookup1);
175 : :
176 : : // Sort the input data.
177 : 4 : std::array<int, ARRAY_SIZE (data)> sorted;
178 : 4 : std::copy (data, data + ARRAY_SIZE (data), sorted.begin ());
179 : 4 : std::sort (sorted.begin (), sorted.end ());
180 : :
181 : : // Iterate over the tree in ascending order.
182 : 4 : tree.splay_min_node ();
183 : 4 : bool result = true;
184 : 804 : for (int value : sorted)
185 : : {
186 : 800 : ASSERT_TRUE (result);
187 : 800 : ASSERT_EQ (tree->value (), value);
188 : 800 : result = tree.splay_next_node ();
189 : : }
190 : 4 : ASSERT_FALSE (result);
191 : 4 : ASSERT_EQ (tree.min_node ()->value (), sorted.front ());
192 : :
193 : : // Test the double-comparator lookup function.
194 : 4 : test_lookup (tree, lookup2);
195 : :
196 : : // Test printing the tree now, while it's still bushy.
197 : 4 : test_print (tree);
198 : :
199 : : // Iterate over the tree in descending order.
200 : 4 : tree.splay_max_node ();
201 : 4 : result = true;
202 : 808 : for (auto it = sorted.rbegin (); it != sorted.rend (); ++it)
203 : : {
204 : 800 : ASSERT_TRUE (result);
205 : 800 : ASSERT_EQ (tree->value (), *it);
206 : 800 : result = tree.splay_prev_node ();
207 : : }
208 : 4 : ASSERT_FALSE (result);
209 : 4 : ASSERT_EQ (tree.max_node ()->value (), sorted.back ());
210 : :
211 : : // Try splitting the tree into three.
212 : 4 : int mid_min = sorted[sorted.size () / 3];
213 : 4 : int mid_max = sorted[sorted.size () * 2 / 3];
214 : 4 : ASSERT_EQ (lookup1 (tree, mid_min), 0);
215 : 4 : splay_tree<int> left = tree.split_before_root ();
216 : 4 : ASSERT_EQ (lookup1 (tree, mid_max), 0);
217 : 4 : splay_tree<int> right = tree.split_after_root ();
218 : :
219 : : // Test removing all the nodes from their respective trees.
220 : 804 : for (int value : data)
221 : : {
222 : 800 : splay_tree<int> &t = (value < mid_min ? left
223 : : : value > mid_max ? right : tree);
224 : 800 : ASSERT_EQ (lookup1 (t, value), 0);
225 : 800 : t.remove_root ();
226 : : }
227 : 4 : ASSERT_EQ (left.root (), nullptr);
228 : 4 : ASSERT_EQ (tree.root (), nullptr);
229 : 4 : ASSERT_EQ (right.root (), nullptr);
230 : :
231 : 4 : using rootless = default_rootless_splay_tree<rootless_test_node *>;
232 : :
233 : : // Build a tree in ascending order with the lowest element as the root.
234 : 4 : auto *nodes = XOBNEWVEC (&ob, rootless_test_node *, MAX_DATA);
235 : 4 : rootless_test_node *parent = nullptr;
236 : 804 : for (int data : sorted)
237 : : {
238 : 800 : auto *node = XOBNEW (&ob, rootless_test_node);
239 : 1600 : new (node) rootless_test_node ();
240 : 800 : node->data = data;
241 : 800 : nodes[data] = node;
242 : 800 : if (parent)
243 : 796 : rootless::insert_child (parent, 1, node);
244 : 800 : parent = node;
245 : : }
246 : :
247 : : // Try comparing nodes to make sure that their order matches the data.
248 : 800 : for (size_t i = 1; i < ARRAY_SIZE (data); ++i)
249 : : {
250 : 796 : int data1 = data[i - 1];
251 : 796 : int data2 = data[i];
252 : 796 : int comparison = rootless::compare_nodes (nodes[data1], nodes[data2]);
253 : 796 : if (data1 < data2)
254 : 396 : ASSERT_TRUE (comparison < 0);
255 : 400 : else if (data1 > data2)
256 : 400 : ASSERT_TRUE (comparison > 0);
257 : : else
258 : 796 : ASSERT_EQ (comparison, 0);
259 : : }
260 : :
261 : 4 : obstack_free (&ob, nullptr);
262 : 4 : }
263 : : }
264 : : #endif // CHECKING_P
|
