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