libgomp/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998-2023 Free Software Foundation, Inc.
   3    Contributed by Mark Mitchell (mark@markmitchell.com).
   4
   5    This file is part of the GNU Offloading and Multi Processing Library
   6    (libgomp).
   7
   8    Libgomp is free software; you can redistribute it and/or modify it
   9    under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3, or (at your option)
  11    any later version.
  12
  13    Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
  14    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  16    more details.
  17
  18    Under Section 7 of GPL version 3, you are granted additional
  19    permissions described in the GCC Runtime Library Exception, version
  20    3.1, as published by the Free Software Foundation.
  21
  22    You should have received a copy of the GNU General Public License and
  23    a copy of the GCC Runtime Library Exception along with this program;
  24    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25    <http://www.gnu.org/licenses/>.  */
  26
  27 /* The splay tree code copied from include/splay-tree.h and adjusted,
  28    so that all the data lives directly in splay_tree_node_s structure
  29    and no extra allocations are needed.  */
  30
  31 /* For an easily readable description of splay-trees, see:
  32
  33      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
  34      Algorithms.  Harper-Collins, Inc.  1991.
  35
  36    The major feature of splay trees is that all basic tree operations
  37    are amortized O(log n) time for a tree with n nodes.  */
  38
  39 #include "libgomp.h"
  40
  41 /* Rotate the edge joining the left child N with its parent P.  PP is the
  42    grandparents' pointer to P.  */
  43
  44 static inline void
  45 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  46 {
  47   splay_tree_node tmp;
  48   tmp = n->right;
  49   n->right = p;
  50   p->left = tmp;
  51   *pp = n;
  52 }
  53
  54 /* Rotate the edge joining the right child N with its parent P.  PP is the
  55    grandparents' pointer to P.  */
  56
  57 static inline void
  58 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  59 {
  60   splay_tree_node tmp;
  61   tmp = n->left;
  62   n->left = p;
  63   p->right = tmp;
  64   *pp = n;
  65 }
  66
  67 /* Bottom up splay of KEY.  */
  68
  69 static void
  70 splay_tree_splay (splay_tree sp, splay_tree_key key)
  71 {
  72   if (sp->root == NULL)
  73     return;
  74
  75   do {
  76     int cmp1, cmp2;
  77     splay_tree_node n, c;
  78
  79     n = sp->root;
  80     cmp1 = splay_compare (key, &n->key);
  81
  82     /* Found.  */
  83     if (cmp1 == 0)
  84       return;
  85
  86     /* Left or right?  If no child, then we're done.  */
  87     if (cmp1 < 0)
  88       c = n->left;
  89     else
  90       c = n->right;
  91     if (!c)
  92       return;
  93
  94     /* Next one left or right?  If found or no child, we're done
  95        after one rotation.  */
  96     cmp2 = splay_compare (key, &c->key);
  97     if (cmp2 == 0
  98         || (cmp2 < 0 && !c->left)
  99         || (cmp2 > 0 && !c->right))
 100       {
 101         if (cmp1 < 0)
 102           rotate_left (&sp->root, n, c);
 103         else
 104           rotate_right (&sp->root, n, c);
 105         return;
 106       }
 107
 108     /* Now we have the four cases of double-rotation.  */
 109     if (cmp1 < 0 && cmp2 < 0)
 110       {
 111         rotate_left (&n->left, c, c->left);
 112         rotate_left (&sp->root, n, n->left);
 113       }
 114     else if (cmp1 > 0 && cmp2 > 0)
 115       {
 116         rotate_right (&n->right, c, c->right);
 117         rotate_right (&sp->root, n, n->right);
 118       }
 119     else if (cmp1 < 0 && cmp2 > 0)
 120       {
 121         rotate_right (&n->left, c, c->right);
 122         rotate_left (&sp->root, n, n->left);
 123       }
 124     else if (cmp1 > 0 && cmp2 < 0)
 125       {
 126         rotate_left (&n->right, c, c->left);
 127         rotate_right (&sp->root, n, n->right);
 128       }
 129   } while (1);
 130 }
 131
 132 /* Insert a new NODE into SP.  The NODE shouldn't exist in the tree.  */
 133
 134 #ifdef splay_tree_static
 135 __attribute__((unused)) static void
 136 #else
 137 attribute_hidden void
 138 #endif
 139 splay_tree_insert (splay_tree sp, splay_tree_node node)
 140 {
 141   int comparison = 0;
 142
 143   splay_tree_splay (sp, &node->key);
 144
 145   if (sp->root)
 146     comparison = splay_compare (&sp->root->key, &node->key);
 147
 148   if (sp->root && comparison == 0)
 149     gomp_fatal ("Duplicate node");
 150   else
 151     {
 152       /* Insert it at the root.  */
 153       if (sp->root == NULL)
 154         node->left = node->right = NULL;
 155       else if (comparison < 0)
 156         {
 157           node->left = sp->root;
 158           node->right = node->left->right;
 159           node->left->right = NULL;
 160         }
 161       else
 162         {
 163           node->right = sp->root;
 164           node->left = node->right->left;
 165           node->right->left = NULL;
 166         }
 167
 168       sp->root = node;
 169     }
 170 }
 171
 172 /* Remove node with KEY from SP.  It is not an error if it did not exist.  */
 173
 174 #ifdef splay_tree_static
 175 __attribute__((unused)) static void
 176 #else
 177 attribute_hidden void
 178 #endif
 179 splay_tree_remove (splay_tree sp, splay_tree_key key)
 180 {
 181   splay_tree_splay (sp, key);
 182
 183   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 184     {
 185       splay_tree_node left, right;
 186
 187       left = sp->root->left;
 188       right = sp->root->right;
 189
 190       /* One of the children is now the root.  Doesn't matter much
 191          which, so long as we preserve the properties of the tree.  */
 192       if (left)
 193         {
 194           sp->root = left;
 195
 196           /* If there was a right child as well, hang it off the
 197              right-most leaf of the left child.  */
 198           if (right)
 199             {
 200               while (left->right)
 201                 left = left->right;
 202               left->right = right;
 203             }
 204         }
 205       else
 206         sp->root = right;
 207     }
 208 }
 209
 210 /* Lookup KEY in SP, returning NODE if present, and NULL
 211    otherwise.  */
 212
 213 #ifdef splay_tree_static
 214 __attribute__((unused)) static splay_tree_node
 215 #else
 216 attribute_hidden splay_tree_node
 217 #endif
 218 splay_tree_lookup_node (splay_tree sp, splay_tree_key key)
 219 {
 220   splay_tree_splay (sp, key);
 221
 222   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 223     return sp->root;
 224   else
 225     return NULL;
 226 }
 227
 228 /* Likewise but return the key.  */
 229
 230 #ifdef splay_tree_static
 231 __attribute__((unused)) static splay_tree_key
 232 #else
 233 attribute_hidden splay_tree_key
 234 #endif
 235 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 236 {
 237   splay_tree_splay (sp, key);
 238
 239   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 240     return &sp->root->key;
 241   else
 242     return NULL;
 243 }
 244
 245 /* Helper function for splay_tree_foreach.
 246
 247    Run FUNC on every node in KEY.  */
 248
 249 static void
 250 splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func,
 251                              void *data)
 252 {
 253   if (!node)
 254     return;
 255   func (&node->key, data);
 256   splay_tree_foreach_internal (node->left, func, data);
 257   /* Yeah, whatever.  GCC can fix my tail recursion.  */
 258   splay_tree_foreach_internal (node->right, func, data);
 259 }
 260
 261 /* Run FUNC on each of the nodes in SP.  */
 262
 263 #ifdef splay_tree_static
 264 __attribute__((unused)) static void
 265 #else
 266 attribute_hidden void
 267 #endif
 268 splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data)
 269 {
 270   splay_tree_foreach_internal (sp->root, func, data);
 271 }
 272
 273 /* Like above, except when func returns != 0, stop early.  */
 274
 275 static int
 276 splay_tree_foreach_internal_lazy (splay_tree_node node,
 277                                   splay_tree_callback_stop func, void *data)
 278 {
 279   if (!node)
 280     return 0;
 281   if (func (&node->key, data))
 282     return 1;
 283   if (splay_tree_foreach_internal_lazy (node->left, func, data))
 284     return 1;
 285   /* Yeah, whatever.  GCC can fix my tail recursion.  */
 286   return splay_tree_foreach_internal_lazy (node->right, func, data);
 287 }
 288
 289 #ifdef splay_tree_static
 290 __attribute__((unused)) static void
 291 #else
 292 attribute_hidden void
 293 #endif
 294 splay_tree_foreach_lazy (splay_tree sp, splay_tree_callback_stop func,
 295                          void *data)
 296 {
 297   splay_tree_foreach_internal_lazy (sp->root, func, data);
 298 }