libgomp/splay-tree.c

   1 /* A splay-tree datatype.
   2    Copyright (C) 1998-2015 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 #include "splay-tree.h"
  41
  42 extern int splay_compare (splay_tree_key, splay_tree_key);
  43
  44 /* Rotate the edge joining the left child N with its parent P.  PP is the
  45    grandparents' pointer to P.  */
  46
  47 static inline void
  48 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  49 {
  50   splay_tree_node tmp;
  51   tmp = n->right;
  52   n->right = p;
  53   p->left = tmp;
  54   *pp = n;
  55 }
  56
  57 /* Rotate the edge joining the right child N with its parent P.  PP is the
  58    grandparents' pointer to P.  */
  59
  60 static inline void
  61 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  62 {
  63   splay_tree_node tmp;
  64   tmp = n->left;
  65   n->left = p;
  66   p->right = tmp;
  67   *pp = n;
  68 }
  69
  70 /* Bottom up splay of KEY.  */
  71
  72 static void
  73 splay_tree_splay (splay_tree sp, splay_tree_key key)
  74 {
  75   if (sp->root == NULL)
  76     return;
  77
  78   do {
  79     int cmp1, cmp2;
  80     splay_tree_node n, c;
  81
  82     n = sp->root;
  83     cmp1 = splay_compare (key, &n->key);
  84
  85     /* Found.  */
  86     if (cmp1 == 0)
  87       return;
  88
  89     /* Left or right?  If no child, then we're done.  */
  90     if (cmp1 < 0)
  91       c = n->left;
  92     else
  93       c = n->right;
  94     if (!c)
  95       return;
  96
  97     /* Next one left or right?  If found or no child, we're done
  98        after one rotation.  */
  99     cmp2 = splay_compare (key, &c->key);
 100     if (cmp2 == 0
 101         || (cmp2 < 0 && !c->left)
 102         || (cmp2 > 0 && !c->right))
 103       {
 104         if (cmp1 < 0)
 105           rotate_left (&sp->root, n, c);
 106         else
 107           rotate_right (&sp->root, n, c);
 108         return;
 109       }
 110
 111     /* Now we have the four cases of double-rotation.  */
 112     if (cmp1 < 0 && cmp2 < 0)
 113       {
 114         rotate_left (&n->left, c, c->left);
 115         rotate_left (&sp->root, n, n->left);
 116       }
 117     else if (cmp1 > 0 && cmp2 > 0)
 118       {
 119         rotate_right (&n->right, c, c->right);
 120         rotate_right (&sp->root, n, n->right);
 121       }
 122     else if (cmp1 < 0 && cmp2 > 0)
 123       {
 124         rotate_right (&n->left, c, c->right);
 125         rotate_left (&sp->root, n, n->left);
 126       }
 127     else if (cmp1 > 0 && cmp2 < 0)
 128       {
 129         rotate_left (&n->right, c, c->left);
 130         rotate_right (&sp->root, n, n->right);
 131       }
 132   } while (1);
 133 }
 134
 135 /* Insert a new NODE into SP.  The NODE shouldn't exist in the tree.  */
 136
 137 attribute_hidden void
 138 splay_tree_insert (splay_tree sp, splay_tree_node node)
 139 {
 140   int comparison = 0;
 141
 142   splay_tree_splay (sp, &node->key);
 143
 144   if (sp->root)
 145     comparison = splay_compare (&sp->root->key, &node->key);
 146
 147   if (sp->root && comparison == 0)
 148     gomp_fatal ("Duplicate node");
 149   else
 150     {
 151       /* Insert it at the root.  */
 152       if (sp->root == NULL)
 153         node->left = node->right = NULL;
 154       else if (comparison < 0)
 155         {
 156           node->left = sp->root;
 157           node->right = node->left->right;
 158           node->left->right = NULL;
 159         }
 160       else
 161         {
 162           node->right = sp->root;
 163           node->left = node->right->left;
 164           node->right->left = NULL;
 165         }
 166
 167       sp->root = node;
 168     }
 169 }
 170
 171 /* Remove node with KEY from SP.  It is not an error if it did not exist.  */
 172
 173 attribute_hidden void
 174 splay_tree_remove (splay_tree sp, splay_tree_key key)
 175 {
 176   splay_tree_splay (sp, key);
 177
 178   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 179     {
 180       splay_tree_node left, right;
 181
 182       left = sp->root->left;
 183       right = sp->root->right;
 184
 185       /* One of the children is now the root.  Doesn't matter much
 186          which, so long as we preserve the properties of the tree.  */
 187       if (left)
 188         {
 189           sp->root = left;
 190
 191           /* If there was a right child as well, hang it off the
 192              right-most leaf of the left child.  */
 193           if (right)
 194             {
 195               while (left->right)
 196                 left = left->right;
 197               left->right = right;
 198             }
 199         }
 200       else
 201         sp->root = right;
 202     }
 203 }
 204
 205 /* Lookup KEY in SP, returning NODE if present, and NULL
 206    otherwise.  */
 207
 208 attribute_hidden splay_tree_key
 209 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 210 {
 211   splay_tree_splay (sp, key);
 212
 213   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 214     return &sp->root->key;
 215   else
 216     return NULL;
 217 }