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
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
rbt_new(struct rbt_strings * t)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 *
rbt_create_node(struct rbt_strings * t,char * str)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
rbt_left_rotate(struct rbt_strings * t,struct rbt_string_node * node)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
rbt_right_rotate(struct rbt_strings * t,struct rbt_string_node * node)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
rbt_insert(struct rbt_strings * t,char * str)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
rbt_find(struct rbt_strings * t,char * str)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
rbt_dump(struct rbt_strings * t,struct rbt_string_node * subtree)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
rbt_inorder_callback(struct rbt_strings * t,struct rbt_string_node * subtree,void (* fn)(char *))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 }
243