gcc/config/rs6000/rbtree.cc

   1 /* Partial red-black tree implementation for rs6000-gen-builtins.cc.
   2    Copyright (C) 2020-2023 Free Software Foundation, Inc.
   3    Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <assert.h>
  25 #include "rbtree.h"
  26
  27 /* Initialize a red-black tree.  */
  28 void
  29 rbt_new (struct rbt_strings *t)
  30 {
  31   t->rbt_nil = (rbt_string_node *) malloc (sizeof (rbt_string_node));
  32   t->rbt_nil->color = RBT_BLACK;
  33   t->rbt_root = t->rbt_nil;
  34 }
  35
  36 /* Create a new node to be inserted into the red-black tree.  An inserted
  37    node starts out red.  */
  38 static struct rbt_string_node *
  39 rbt_create_node (struct rbt_strings *t, char *str)
  40 {
  41   struct rbt_string_node *nodeptr
  42     = (struct rbt_string_node *) malloc (sizeof (rbt_string_node));
  43   nodeptr->str = str;
  44   nodeptr->left = t->rbt_nil;
  45   nodeptr->right = t->rbt_nil;
  46   nodeptr->par = NULL;
  47   nodeptr->color = RBT_RED;
  48   return nodeptr;
  49 }
  50
  51 /* Perform a left-rotate operation on NODE in the red-black tree.  */
  52 static void
  53 rbt_left_rotate (struct rbt_strings *t, struct rbt_string_node *node)
  54 {
  55   struct rbt_string_node *right = node->right;
  56   assert (right);
  57
  58   /* Turn RIGHT's left subtree into NODE's right subtree.  */
  59   node->right = right->left;
  60   if (right->left != t->rbt_nil)
  61     right->left->par = node;
  62
  63   /* Link NODE's parent to RIGHT.  */
  64   right->par = node->par;
  65
  66   if (node->par == t->rbt_nil)
  67     t->rbt_root = right;
  68   else if (node == node->par->left)
  69     node->par->left = right;
  70   else
  71     node->par->right = right;
  72
  73   /* Put NODE on RIGHT's left.  */
  74   right->left = node;
  75   node->par = right;
  76 }
  77
  78 /* Perform a right-rotate operation on NODE in the red-black tree.  */
  79 static void
  80 rbt_right_rotate (struct rbt_strings *t, struct rbt_string_node *node)
  81 {
  82   struct rbt_string_node *left = node->left;
  83   assert (left);
  84
  85   /* Turn LEFT's right subtree into NODE's left subtree.  */
  86   node->left = left->right;
  87   if (left->right != t->rbt_nil)
  88     left->right->par = node;
  89
  90   /* Link NODE's parent to LEFT.  */
  91   left->par = node->par;
  92
  93   if (node->par == t->rbt_nil)
  94     t->rbt_root = left;
  95   else if (node == node->par->right)
  96     node->par->right = left;
  97   else
  98     node->par->left = left;
  99
 100   /* Put NODE on LEFT's right.  */
 101   left->right = node;
 102   node->par = left;
 103 }
 104
 105 /* Insert STR into the tree, returning 1 for success and 0 if STR already
 106    appears in the tree.  */
 107 int
 108 rbt_insert (struct rbt_strings *t, char *str)
 109 {
 110   struct rbt_string_node *curr = t->rbt_root;
 111   struct rbt_string_node *trail = t->rbt_nil;
 112
 113   while (curr != t->rbt_nil)
 114     {
 115       trail = curr;
 116       int cmp = strcmp (str, curr->str);
 117       if (cmp < 0)
 118         curr = curr->left;
 119       else if (cmp > 0)
 120         curr = curr->right;
 121       else
 122         return 0;
 123     }
 124
 125   struct rbt_string_node *fresh = rbt_create_node (t, str);
 126   fresh->par = trail;
 127
 128   if (trail == t->rbt_nil)
 129     t->rbt_root = fresh;
 130   else if (strcmp (fresh->str, trail->str) < 0)
 131     trail->left = fresh;
 132   else
 133     trail->right = fresh;
 134
 135   fresh->left = t->rbt_nil;
 136   fresh->right = t->rbt_nil;
 137
 138   /* FRESH has now been inserted as a red leaf.  If we have invalidated
 139      one of the following preconditions, we must fix things up:
 140       (a) If a node is red, both of its children are black.
 141       (b) The root must be black.
 142      Note that only (a) or (b) applies at any given time during the
 143      process.  This algorithm works up the tree from NEW looking
 144      for a red child with a red parent, and cleaning that up.  If the
 145      root ends up red, it gets turned black at the end.  */
 146   curr = fresh;
 147   while (curr->par->color == RBT_RED)
 148     if (curr->par == curr->par->par->left)
 149       {
 150         struct rbt_string_node *uncle = curr->par->par->right;
 151         if (uncle->color == RBT_RED)
 152           {
 153             curr->par->color = RBT_BLACK;
 154             uncle->color = RBT_BLACK;
 155             curr->par->par->color = RBT_RED;
 156             curr = curr->par->par;
 157           }
 158         else if (curr == curr->par->right)
 159           {
 160             curr = curr->par;
 161             rbt_left_rotate (t, curr);
 162           }
 163         else
 164           {
 165             curr->par->color = RBT_BLACK;
 166             curr->par->par->color = RBT_RED;
 167             rbt_right_rotate (t, curr->par->par);
 168           }
 169       }
 170     else /* curr->par == curr->par->par->right  */
 171       {
 172         /* Gender-neutral formations are awkward, so let's be fair. ;-)
 173            ("Parent-sibling" is just awful.)  */
 174         struct rbt_string_node *aunt = curr->par->par->left;
 175         if (aunt->color == RBT_RED)
 176           {
 177             curr->par->color = RBT_BLACK;
 178             aunt->color = RBT_BLACK;
 179             curr->par->par->color = RBT_RED;
 180             curr = curr->par->par;
 181           }
 182         else if (curr == curr->par->left)
 183           {
 184             curr = curr->par;
 185             rbt_right_rotate (t, curr);
 186           }
 187         else
 188           {
 189             curr->par->color = RBT_BLACK;
 190             curr->par->par->color = RBT_RED;
 191             rbt_left_rotate (t, curr->par->par);
 192           }
 193       }
 194
 195   t->rbt_root->color = RBT_BLACK;
 196   return 1;
 197 }
 198
 199 /* Return 1 if STR is in the red-black tree, else 0.  */
 200 int
 201 rbt_find (struct rbt_strings *t, char *str)
 202 {
 203   struct rbt_string_node *curr = t->rbt_root;
 204
 205   while (curr != t->rbt_nil)
 206     {
 207       int cmp = strcmp (str, curr->str);
 208       if (cmp < 0)
 209         curr = curr->left;
 210       else if (cmp > 0)
 211         curr = curr->right;
 212       else
 213         return 1;
 214     }
 215
 216   return 0;
 217 }
 218
 219 /* Inorder dump of the binary search tree.  */
 220 void
 221 rbt_dump (struct rbt_strings *t, struct rbt_string_node *subtree)
 222 {
 223   if (subtree != t->rbt_nil)
 224     {
 225       rbt_dump (t, subtree->left);
 226       fprintf (stderr, "%s\n", subtree->str);
 227       rbt_dump (t, subtree->right);
 228     }
 229 }
 230
 231 /* Inorder call-back for iteration over the tree.  */
 232 void
 233 rbt_inorder_callback (struct rbt_strings *t, struct rbt_string_node *subtree,
 234                       void (*fn) (char *))
 235 {
 236   if (subtree != t->rbt_nil)
 237     {
 238       rbt_inorder_callback (t, subtree->left, fn);
 239       (*fn) (subtree->str);
 240       rbt_inorder_callback (t, subtree->right, fn);
 241     }
 242 }