1/* Partial red-black tree implementation for rs6000-gen-builtins.cc.
2   Copyright (C) 2020-2022 Free Software Foundation, Inc.
3   Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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.  */
28void
29rbt_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.  */
38static struct rbt_string_node *
39rbt_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.  */
52static void
53rbt_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.  */
79static void
80rbt_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.  */
107int
108rbt_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.  */
200int
201rbt_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.  */
220void
221rbt_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.  */
232void
233rbt_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}
243