[PATCH 06/14] Red-black tree implementation for balanced tree search.
Bill Schmidt
wschmidt@linux.ibm.com
Tue Feb 4 02:27:00 GMT 2020
2020-02-03 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++
2 files changed, 284 insertions(+)
create mode 100644 gcc/config/rs6000/rbtree.c
create mode 100644 gcc/config/rs6000/rbtree.h
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..f6a8cdefaae
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-genbif.c.
+ Copyright (C) 2020 Free Software Foundation, Inc.
+ Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "rbtree.h"
+
+/* Create a new node to be inserted into the red-black tree. An inserted
+ node starts out red. */
+static struct rbt_string_node *
+rbt_create_node (struct rbt_strings *t, char *str)
+{
+ struct rbt_string_node *nodeptr
+ = (struct rbt_string_node *) malloc (sizeof (struct rbt_string_node));
+ nodeptr->str = str;
+ nodeptr->left = t->rbt_nil;
+ nodeptr->right = t->rbt_nil;
+ nodeptr->par = NULL;
+ nodeptr->color = RBT_RED;
+ return nodeptr;
+}
+
+/* Perform a left-rotate operation on NODE in the red-black tree. */
+static void
+rbt_left_rotate (struct rbt_strings *t, struct rbt_string_node *node)
+{
+ struct rbt_string_node *right = node->right;
+ assert (right);
+
+ /* Turn RIGHT's left subtree into NODE's right subtree. */
+ node->right = right->left;
+ if (right->left != t->rbt_nil)
+ right->left->par = node;
+
+ /* Link NODE's parent to RIGHT. */
+ right->par = node->par;
+
+ if (node->par == t->rbt_nil)
+ t->rbt_root = right;
+ else if (node == node->par->left)
+ node->par->left = right;
+ else
+ node->par->right = right;
+
+ /* Put NODE on RIGHT's left. */
+ right->left = node;
+ node->par = right;
+}
+
+/* Perform a right-rotate operation on NODE in the red-black tree. */
+static void
+rbt_right_rotate (struct rbt_strings *t, struct rbt_string_node *node)
+{
+ struct rbt_string_node *left = node->left;
+ assert (left);
+
+ /* Turn LEFT's right subtree into NODE's left subtree. */
+ node->left = left->right;
+ if (left->right != t->rbt_nil)
+ left->right->par = node;
+
+ /* Link NODE's parent to LEFT. */
+ left->par = node->par;
+
+ if (node->par == t->rbt_nil)
+ t->rbt_root = left;
+ else if (node == node->par->right)
+ node->par->right = left;
+ else
+ node->par->left = left;
+
+ /* Put NODE on LEFT's right. */
+ left->right = node;
+ node->par = left;
+}
+
+/* Insert STR into the tree, returning 1 for success and 0 if STR already
+ appears in the tree. */
+int
+rbt_insert (struct rbt_strings *t, char *str)
+{
+ struct rbt_string_node *curr = t->rbt_root;
+ struct rbt_string_node *trail = t->rbt_nil;
+
+ while (curr != t->rbt_nil)
+ {
+ trail = curr;
+ int cmp = strcmp (str, curr->str);
+ if (cmp < 0)
+ curr = curr->left;
+ else if (cmp > 0)
+ curr = curr->right;
+ else
+ return 0;
+ }
+
+ struct rbt_string_node *fresh = rbt_create_node (t, str);
+ fresh->par = trail;
+
+ if (trail == t->rbt_nil)
+ t->rbt_root = fresh;
+ else if (strcmp (fresh->str, trail->str) < 0)
+ trail->left = fresh;
+ else
+ trail->right = fresh;
+
+ fresh->left = t->rbt_nil;
+ fresh->right = t->rbt_nil;
+
+ /* FRESH has now been inserted as a red leaf. If we have invalidated
+ one of the following preconditions, we must fix things up:
+ (a) If a node is red, both of its children are black.
+ (b) The root must be black.
+ Note that only (a) or (b) applies at any given time during the
+ process. This algorithm works up the tree from NEW looking
+ for a red child with a red parent, and cleaning that up. If the
+ root ends up red, it gets turned black at the end. */
+ curr = fresh;
+ while (curr->par->color == RBT_RED)
+ if (curr->par == curr->par->par->left)
+ {
+ struct rbt_string_node *uncle = curr->par->par->right;
+ if (uncle->color == RBT_RED)
+ {
+ curr->par->color = RBT_BLACK;
+ uncle->color = RBT_BLACK;
+ curr->par->par->color = RBT_RED;
+ curr = curr->par->par;
+ }
+ else if (curr == curr->par->right)
+ {
+ curr = curr->par;
+ rbt_left_rotate (t, curr);
+ }
+ else
+ {
+ curr->par->color = RBT_BLACK;
+ curr->par->par->color = RBT_RED;
+ rbt_right_rotate (t, curr->par->par);
+ }
+ }
+ else /* curr->par == curr->par->par->right */
+ {
+ /* Gender-neutral formations are awkward, so let's be fair. ;-)
+ ("Parent-sibling" is just awful.) */
+ struct rbt_string_node *aunt = curr->par->par->left;
+ if (aunt->color == RBT_RED)
+ {
+ curr->par->color = RBT_BLACK;
+ aunt->color = RBT_BLACK;
+ curr->par->par->color = RBT_RED;
+ curr = curr->par->par;
+ }
+ else if (curr == curr->par->left)
+ {
+ curr = curr->par;
+ rbt_right_rotate (t, curr);
+ }
+ else
+ {
+ curr->par->color = RBT_BLACK;
+ curr->par->par->color = RBT_RED;
+ rbt_left_rotate (t, curr->par->par);
+ }
+ }
+
+ t->rbt_root->color = RBT_BLACK;
+ return 1;
+}
+
+/* Return 1 if STR is in the red-black tree, else 0. */
+int
+rbt_find (struct rbt_strings *t, char *str)
+{
+ struct rbt_string_node *curr = t->rbt_root;
+
+ while (curr != t->rbt_nil)
+ {
+ int cmp = strcmp (str, curr->str);
+ if (cmp < 0)
+ curr = curr->left;
+ else if (cmp > 0)
+ curr = curr->right;
+ else
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Inorder dump of the binary search tree. */
+void
+rbt_dump (struct rbt_strings *t, struct rbt_string_node *subtree)
+{
+ if (subtree != t->rbt_nil)
+ {
+ rbt_dump (t, subtree->left);
+ fprintf (stderr, "%s\n", subtree->str);
+ rbt_dump (t, subtree->right);
+ }
+}
+
+/* Inorder call-back for iteration over the tree. */
+void
+rbt_inorder_callback (struct rbt_strings *t, struct rbt_string_node *subtree,
+ void (*fn) (char *))
+{
+ if (subtree != t->rbt_nil)
+ {
+ rbt_inorder_callback (t, subtree->left, fn);
+ (*fn) (subtree->str);
+ rbt_inorder_callback (t, subtree->right, fn);
+ }
+}
diff --git a/gcc/config/rs6000/rbtree.h b/gcc/config/rs6000/rbtree.h
new file mode 100644
index 00000000000..49fa98596a6
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-genbif.c.
+ Copyright (C) 2020 Free Software Foundation, Inc.
+ Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* Red-black binary search tree on strings. Presently we don't support
+ deletes; only insert/find operations are implemented. */
+enum rbt_color
+ {
+ RBT_BLACK,
+ RBT_RED
+ };
+
+struct rbt_string_node {
+ char *str;
+ struct rbt_string_node *left;
+ struct rbt_string_node *right;
+ struct rbt_string_node *par;
+ enum rbt_color color;
+};
+
+/* Root and sentinel nodes of a red-black tree.
+ rbt_nil points to a sentinel node, which is the parent of root
+ and the child of every node without a "real" left or right child.
+ rbt_root points to the root of the tree, if it exists yet. The
+ root and sentinel nodes are always black. */
+struct rbt_strings {
+ struct rbt_string_node *rbt_nil;
+ struct rbt_string_node *rbt_root;
+};
+
+int rbt_insert (struct rbt_strings *, char *);
+int rbt_find (struct rbt_strings *, char *);
+void rbt_dump (struct rbt_strings *, struct rbt_string_node *);
+void rbt_inorder_callback (struct rbt_strings *, struct rbt_string_node *,
+ void (*) (char *));
--
2.17.1
More information about the Gcc-patches
mailing list