libgomp/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998-2017 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 attribute_hidden void
 135 splay_tree_insert (splay_tree sp, splay_tree_node node)
 136 {
 137   int comparison = 0;
 138
 139   splay_tree_splay (sp, &node->key);
 140
 141   if (sp->root)
 142     comparison = splay_compare (&sp->root->key, &node->key);
 143
 144   if (sp->root && comparison == 0)
 145     gomp_fatal ("Duplicate node");
 146   else
 147     {
 148       /* Insert it at the root.  */
 149       if (sp->root == NULL)
 150         node->left = node->right = NULL;
 151       else if (comparison < 0)
 152         {
 153           node->left = sp->root;
 154           node->right = node->left->right;
 155           node->left->right = NULL;
 156         }
 157       else
 158         {
 159           node->right = sp->root;
 160           node->left = node->right->left;
 161           node->right->left = NULL;
 162         }
 163
 164       sp->root = node;
 165     }
 166 }
 167
 168 /* Remove node with KEY from SP.  It is not an error if it did not exist.  */
 169
 170 attribute_hidden void
 171 splay_tree_remove (splay_tree sp, splay_tree_key key)
 172 {
 173   splay_tree_splay (sp, key);
 174
 175   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 176     {
 177       splay_tree_node left, right;
 178
 179       left = sp->root->left;
 180       right = sp->root->right;
 181
 182       /* One of the children is now the root.  Doesn't matter much
 183          which, so long as we preserve the properties of the tree.  */
 184       if (left)
 185         {
 186           sp->root = left;
 187
 188           /* If there was a right child as well, hang it off the
 189              right-most leaf of the left child.  */
 190           if (right)
 191             {
 192               while (left->right)
 193                 left = left->right;
 194               left->right = right;
 195             }
 196         }
 197       else
 198         sp->root = right;
 199     }
 200 }
 201
 202 /* Lookup KEY in SP, returning NODE if present, and NULL
 203    otherwise.  */
 204
 205 attribute_hidden splay_tree_key
 206 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 207 {
 208   splay_tree_splay (sp, key);
 209
 210   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 211     return &sp->root->key;
 212   else
 213     return NULL;
 214 }
 215
 216 /* Helper function for splay_tree_foreach.
 217
 218    Run FUNC on every node in KEY.  */
 219
 220 static void
 221 splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func,
 222                              void *data)
 223 {
 224   if (!node)
 225     return;
 226   func (&node->key, data);
 227   splay_tree_foreach_internal (node->left, func, data);
 228   /* Yeah, whatever.  GCC can fix my tail recursion.  */
 229   splay_tree_foreach_internal (node->right, func, data);
 230 }
 231
 232 /* Run FUNC on each of the nodes in SP.  */
 233
 234 attribute_hidden void
 235 splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data)
 236 {
 237   splay_tree_foreach_internal (sp->root, func, data);
 238 }