1// Splay tree utilities -*- C++ -*- 2// Copyright (C) 2020-2022 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 30namespace { 31// A simple test node for rootless_splay_tree. 32struct rootless_test_node 33{ 34 int data; 35 rootless_test_node *m_parent; 36 rootless_test_node *m_children[2]; 37}; 38} 39 40namespace selftest { 41 42// Random input data. 43static const size_t MAX_DATA = 32768; 44static 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. 68static int 69lookup1 (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. 79static int 80lookup2 (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. 95static void 96test_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. 108static void 109test_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. 153void 154splay_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 265