]>
Commit | Line | Data |
---|---|---|
9a0882ef | 1 | // Splay tree utilities -*- C++ -*- |
99dee823 | 2 | // Copyright (C) 2020-2021 Free Software Foundation, Inc. |
9a0882ef RS |
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 | lookup1 (splay_tree<int> &tree, int value) | |
70 | { | |
71 | auto compare = [&](splay_tree_node<int> *node) | |
72 | { | |
73 | return value - node->value (); | |
74 | }; | |
75 | return tree.lookup (compare); | |
76 | } | |
77 | ||
78 | // Look up VALUE in TREE using the double-comparator lookup function. | |
79 | static int | |
80 | lookup2 (splay_tree<int> &tree, int value) | |
81 | { | |
82 | auto want_something_smaller = [&](splay_tree_node<int> *node) | |
83 | { | |
84 | return value < node->value (); | |
85 | }; | |
86 | auto want_something_bigger = [&](splay_tree_node<int> *node) | |
87 | { | |
88 | return value > node->value (); | |
89 | }; | |
90 | 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 | test_print (splay_tree<int> &tree) | |
97 | { | |
98 | auto print_node = [](pretty_printer *pp, splay_tree_node<int> *node) | |
99 | { | |
100 | pp_decimal_int (pp, node->value ()); | |
101 | }; | |
102 | pretty_printer pp; | |
103 | tree.print (&pp, print_node); | |
104 | } | |
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 | test_lookup (splay_tree<int> &tree, int (*lookup) (splay_tree<int> &, int)) | |
110 | { | |
111 | // Look up values that are known to exist. | |
112 | for (int value : data) | |
113 | ASSERT_EQ (lookup (tree, value), 0); | |
114 | ||
115 | // Look up values that are 1 less than values that are known to exist. | |
116 | for (int value : data) | |
117 | { | |
118 | int result = lookup (tree, value - 1); | |
119 | if (result == 0) | |
120 | ASSERT_EQ (tree->value (), value - 1); | |
121 | else if (result < 0) | |
122 | // VALUE - 1 is less than the root. | |
123 | ASSERT_EQ (tree->value (), value); | |
124 | else if (result > 0) | |
125 | { | |
126 | // VALUE - 1 is greater than the root. | |
127 | ASSERT_TRUE (tree->value () < value - 1); | |
128 | if (tree.splay_next_node ()) | |
129 | ASSERT_EQ (tree->value (), value); | |
130 | } | |
131 | } | |
132 | ||
133 | // Look up values that are 1 greater than values that are known to exist. | |
134 | for (int value : data) | |
135 | { | |
136 | int result = lookup (tree, value + 1); | |
137 | if (result == 0) | |
138 | ASSERT_EQ (tree->value (), value + 1); | |
139 | else if (result < 0) | |
140 | { | |
141 | // VALUE + 1 is less than the root. | |
142 | ASSERT_TRUE (tree->value () > value + 1); | |
143 | if (tree.splay_prev_node ()) | |
144 | ASSERT_EQ (tree->value (), value); | |
145 | } | |
146 | else if (result > 0) | |
147 | // VALUE + 1 is greater than the root. | |
148 | ASSERT_EQ (tree->value (), value); | |
149 | } | |
150 | } | |
151 | ||
152 | // Run all tests for this module. | |
153 | void | |
154 | splay_tree_cc_tests () | |
155 | { | |
156 | obstack ob; | |
157 | gcc_obstack_init (&ob); | |
158 | ||
159 | // Build up the splay tree. | |
160 | splay_tree<int> tree; | |
161 | for (int value : data) | |
162 | { | |
163 | auto *node = XOBNEW (&ob, splay_tree_node<int>); | |
164 | new (node) splay_tree_node<int> (value); | |
165 | auto compare = [&](splay_tree_node<int> *other_node) | |
166 | { | |
167 | return value - other_node->value (); | |
168 | }; | |
169 | bool inserted = tree.insert (node, compare); | |
170 | ASSERT_TRUE (inserted); | |
171 | } | |
172 | ||
173 | // Test the single-comparator lookup function. | |
174 | test_lookup (tree, lookup1); | |
175 | ||
176 | // Sort the input data. | |
177 | std::array<int, ARRAY_SIZE (data)> sorted; | |
178 | std::copy (data, data + ARRAY_SIZE (data), sorted.begin ()); | |
179 | std::sort (sorted.begin (), sorted.end ()); | |
180 | ||
181 | // Iterate over the tree in ascending order. | |
182 | tree.splay_min_node (); | |
183 | bool result = true; | |
184 | for (int value : sorted) | |
185 | { | |
186 | ASSERT_TRUE (result); | |
187 | ASSERT_EQ (tree->value (), value); | |
188 | result = tree.splay_next_node (); | |
189 | } | |
190 | ASSERT_FALSE (result); | |
191 | ASSERT_EQ (tree.min_node ()->value (), sorted.front ()); | |
192 | ||
193 | // Test the double-comparator lookup function. | |
194 | test_lookup (tree, lookup2); | |
195 | ||
196 | // Test printing the tree now, while it's still bushy. | |
197 | test_print (tree); | |
198 | ||
199 | // Iterate over the tree in descending order. | |
200 | tree.splay_max_node (); | |
201 | result = true; | |
202 | for (auto it = sorted.rbegin (); it != sorted.rend (); ++it) | |
203 | { | |
204 | ASSERT_TRUE (result); | |
205 | ASSERT_EQ (tree->value (), *it); | |
206 | result = tree.splay_prev_node (); | |
207 | } | |
208 | ASSERT_FALSE (result); | |
209 | ASSERT_EQ (tree.max_node ()->value (), sorted.back ()); | |
210 | ||
211 | // Try splitting the tree into three. | |
212 | int mid_min = sorted[sorted.size () / 3]; | |
213 | int mid_max = sorted[sorted.size () * 2 / 3]; | |
214 | ASSERT_EQ (lookup1 (tree, mid_min), 0); | |
215 | splay_tree<int> left = tree.split_before_root (); | |
216 | ASSERT_EQ (lookup1 (tree, mid_max), 0); | |
217 | splay_tree<int> right = tree.split_after_root (); | |
218 | ||
219 | // Test removing all the nodes from their respective trees. | |
220 | for (int value : data) | |
221 | { | |
222 | splay_tree<int> &t = (value < mid_min ? left | |
223 | : value > mid_max ? right : tree); | |
224 | ASSERT_EQ (lookup1 (t, value), 0); | |
225 | t.remove_root (); | |
226 | } | |
227 | ASSERT_EQ (left.root (), nullptr); | |
228 | ASSERT_EQ (tree.root (), nullptr); | |
229 | ASSERT_EQ (right.root (), nullptr); | |
230 | ||
231 | 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 | auto *nodes = XOBNEWVEC (&ob, rootless_test_node *, MAX_DATA); | |
235 | rootless_test_node *parent = nullptr; | |
236 | for (int data : sorted) | |
237 | { | |
238 | auto *node = XOBNEW (&ob, rootless_test_node); | |
239 | new (node) rootless_test_node (); | |
240 | node->data = data; | |
241 | nodes[data] = node; | |
242 | if (parent) | |
243 | rootless::insert_child (parent, 1, node); | |
244 | parent = node; | |
245 | } | |
246 | ||
247 | // Try comparing nodes to make sure that their order matches the data. | |
248 | for (size_t i = 1; i < ARRAY_SIZE (data); ++i) | |
249 | { | |
250 | int data1 = data[i - 1]; | |
251 | int data2 = data[i]; | |
252 | int comparison = rootless::compare_nodes (nodes[data1], nodes[data2]); | |
253 | if (data1 < data2) | |
254 | ASSERT_TRUE (comparison < 0); | |
255 | else if (data1 > data2) | |
256 | ASSERT_TRUE (comparison > 0); | |
257 | else | |
258 | ASSERT_EQ (comparison, 0); | |
259 | } | |
260 | ||
261 | obstack_free (&ob, nullptr); | |
262 | } | |
263 | } | |
264 | #endif // CHECKING_P |