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