libgomp/splay-tree.c

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