libgomp/splay-tree.h

   1 /* A splay-tree datatype.
   2    Copyright 1998-2014
   3    Free Software Foundation, Inc.
   4    Contributed by Mark Mitchell (mark@markmitchell.com).
   5
   6    This file is part of the GNU OpenMP Library (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    Files including this header should before including it add:
  32 typedef struct splay_tree_node_s *splay_tree_node;
  33 typedef struct splay_tree_s *splay_tree;
  34 typedef struct splay_tree_key_s *splay_tree_key;
  35    define splay_tree_key_s structure, and define
  36    splay_compare inline function.  */
  37
  38 /* For an easily readable description of splay-trees, see:
  39
  40      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
  41      Algorithms.  Harper-Collins, Inc.  1991.
  42
  43    The major feature of splay trees is that all basic tree operations
  44    are amortized O(log n) time for a tree with n nodes.  */
  45
  46 /* The nodes in the splay tree.  */
  47 struct splay_tree_node_s {
  48   struct splay_tree_key_s key;
  49   /* The left and right children, respectively.  */
  50   splay_tree_node left;
  51   splay_tree_node right;
  52 };
  53
  54 /* The splay tree.  */
  55 struct splay_tree_s {
  56   splay_tree_node root;
  57 };
  58
  59 /* Rotate the edge joining the left child N with its parent P.  PP is the
  60    grandparents' pointer to P.  */
  61
  62 static inline void
  63 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  64 {
  65   splay_tree_node tmp;
  66   tmp = n->right;
  67   n->right = p;
  68   p->left = tmp;
  69   *pp = n;
  70 }
  71
  72 /* Rotate the edge joining the right child N with its parent P.  PP is the
  73    grandparents' pointer to P.  */
  74
  75 static inline void
  76 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
  77 {
  78   splay_tree_node tmp;
  79   tmp = n->left;
  80   n->left = p;
  81   p->right = tmp;
  82   *pp = n;
  83 }
  84
  85 /* Bottom up splay of KEY.  */
  86
  87 static void
  88 splay_tree_splay (splay_tree sp, splay_tree_key key)
  89 {
  90   if (sp->root == NULL)
  91     return;
  92
  93   do {
  94     int cmp1, cmp2;
  95     splay_tree_node n, c;
  96
  97     n = sp->root;
  98     cmp1 = splay_compare (key, &n->key);
  99
 100     /* Found.  */
 101     if (cmp1 == 0)
 102       return;
 103
 104     /* Left or right?  If no child, then we're done.  */
 105     if (cmp1 < 0)
 106       c = n->left;
 107     else
 108       c = n->right;
 109     if (!c)
 110       return;
 111
 112     /* Next one left or right?  If found or no child, we're done
 113        after one rotation.  */
 114     cmp2 = splay_compare (key, &c->key);
 115     if (cmp2 == 0
 116         || (cmp2 < 0 && !c->left)
 117         || (cmp2 > 0 && !c->right))
 118       {
 119         if (cmp1 < 0)
 120           rotate_left (&sp->root, n, c);
 121         else
 122           rotate_right (&sp->root, n, c);
 123         return;
 124       }
 125
 126     /* Now we have the four cases of double-rotation.  */
 127     if (cmp1 < 0 && cmp2 < 0)
 128       {
 129         rotate_left (&n->left, c, c->left);
 130         rotate_left (&sp->root, n, n->left);
 131       }
 132     else if (cmp1 > 0 && cmp2 > 0)
 133       {
 134         rotate_right (&n->right, c, c->right);
 135         rotate_right (&sp->root, n, n->right);
 136       }
 137     else if (cmp1 < 0 && cmp2 > 0)
 138       {
 139         rotate_right (&n->left, c, c->right);
 140         rotate_left (&sp->root, n, n->left);
 141       }
 142     else if (cmp1 > 0 && cmp2 < 0)
 143       {
 144         rotate_left (&n->right, c, c->left);
 145         rotate_right (&sp->root, n, n->right);
 146       }
 147   } while (1);
 148 }
 149
 150 /* Insert a new NODE into SP.  The NODE shouldn't exist in the tree.  */
 151
 152 static void
 153 splay_tree_insert (splay_tree sp, splay_tree_node node)
 154 {
 155   int comparison = 0;
 156
 157   splay_tree_splay (sp, &node->key);
 158
 159   if (sp->root)
 160     comparison = splay_compare (&sp->root->key, &node->key);
 161
 162   if (sp->root && comparison == 0)
 163     abort ();
 164   else
 165     {
 166       /* Insert it at the root.  */
 167       if (sp->root == NULL)
 168         node->left = node->right = NULL;
 169       else if (comparison < 0)
 170         {
 171           node->left = sp->root;
 172           node->right = node->left->right;
 173           node->left->right = NULL;
 174         }
 175       else
 176         {
 177           node->right = sp->root;
 178           node->left = node->right->left;
 179           node->right->left = NULL;
 180         }
 181
 182       sp->root = node;
 183     }
 184 }
 185
 186 /* Remove node with KEY from SP.  It is not an error if it did not exist.  */
 187
 188 static void
 189 splay_tree_remove (splay_tree sp, splay_tree_key key)
 190 {
 191   splay_tree_splay (sp, key);
 192
 193   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 194     {
 195       splay_tree_node left, right;
 196
 197       left = sp->root->left;
 198       right = sp->root->right;
 199
 200       /* One of the children is now the root.  Doesn't matter much
 201          which, so long as we preserve the properties of the tree.  */
 202       if (left)
 203         {
 204           sp->root = left;
 205
 206           /* If there was a right child as well, hang it off the
 207              right-most leaf of the left child.  */
 208           if (right)
 209             {
 210               while (left->right)
 211                 left = left->right;
 212               left->right = right;
 213             }
 214         }
 215       else
 216         sp->root = right;
 217     }
 218 }
 219
 220 /* Lookup KEY in SP, returning NODE if present, and NULL
 221    otherwise.  */
 222
 223 static splay_tree_key
 224 splay_tree_lookup (splay_tree sp, splay_tree_key key)
 225 {
 226   splay_tree_splay (sp, key);
 227
 228   if (sp->root && splay_compare (&sp->root->key, key) == 0)
 229     return &sp->root->key;
 230   else
 231     return NULL;
 232 }