gcc/splay-tree-utils.cc

   1 // Splay tree utilities                                             -*- C++ -*-
   2 // Copyright (C) 2020-2021 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 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