public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-07-17 17:22 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-07-17 17:22 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:68128e0d0a60630b78983f6e7c75d783753fc262
commit 68128e0d0a60630b78983f6e7c75d783753fc262
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-06-17 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-10-29 19:50 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-10-29 19:50 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:59e371743a67dec675c1a85bf58761d21eeb1b1f
commit 59e371743a67dec675c1a85bf58761d21eeb1b1f
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-10-27 16:27 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-10-27 16:27 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:41f07b764a87a42c7b8ee9e2c60952f3c2de7da7
commit 41f07b764a87a42c7b8ee9e2c60952f3c2de7da7
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-09-16 21:29 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-09-16 21:29 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:43e9299393b03269c333d794535e7a0bb1710321
commit 43e9299393b03269c333d794535e7a0bb1710321
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-09-14 13:57 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-09-14 13:57 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:f48cf25046dc088cad9988597c3f278aec1afc1d
commit f48cf25046dc088cad9988597c3f278aec1afc1d
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-08-28 20:07 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-08-28 20:07 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:b880c409048cbdaddb7a2133ae8a9b3e464df77d
commit b880c409048cbdaddb7a2133ae8a9b3e464df77d
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-08-20 16:38 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-08-20 16:38 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:ce87fe43e15523166e8bc154fe79b10ee02a3251
commit ce87fe43e15523166e8bc154fe79b10ee02a3251
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-08-18 18:44 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-08-18 18:44 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:1a783b0d46180365d7041ec3973d7064cf871edf
commit 1a783b0d46180365d7041ec3973d7064cf871edf
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-07-27 18:47 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-07-27 18:47 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:5707fc9fa429d6667a39261b843cf90cb4b7bf6d
commit 5707fc9fa429d6667a39261b843cf90cb4b7bf6d
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-07-26 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
* [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search
@ 2020-06-17 20:04 William Schmidt
0 siblings, 0 replies; 10+ messages in thread
From: William Schmidt @ 2020-06-17 20:04 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:ca48da36df9796205b11bac99223e68d14189be2
commit ca48da36df9796205b11bac99223e68d14189be2
Author: Bill Schmidt <wschmidt@linux.ibm.com>
Date: Wed Jun 17 10:50:42 2020 -0500
rs6000: Red-black tree implementation for balanced tree search
2020-06-17 Bill Schmidt <wschmidt@linux.ibm.com>
* config/rs6000/rbtree.c: New file.
* config/rs6000/rbtree.h: New file.
Diff:
---
gcc/config/rs6000/rbtree.c | 233 +++++++++++++++++++++++++++++++++++++++++++++
gcc/config/rs6000/rbtree.h | 51 ++++++++++
2 files changed, 284 insertions(+)
diff --git a/gcc/config/rs6000/rbtree.c b/gcc/config/rs6000/rbtree.c
new file mode 100644
index 00000000000..50e5f57a50c
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.c
@@ -0,0 +1,233 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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..f20f94028e4
--- /dev/null
+++ b/gcc/config/rs6000/rbtree.h
@@ -0,0 +1,51 @@
+/* Partial red-black tree implementation for rs6000-gen-builtins.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 *));
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2020-10-29 19:50 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-07-17 17:22 [gcc(refs/users/wschmidt/heads/builtins3)] rs6000: Red-black tree implementation for balanced tree search William Schmidt
-- strict thread matches above, loose matches on Subject: below --
2020-10-29 19:50 William Schmidt
2020-10-27 16:27 William Schmidt
2020-09-16 21:29 William Schmidt
2020-09-14 13:57 William Schmidt
2020-08-28 20:07 William Schmidt
2020-08-20 16:38 William Schmidt
2020-08-18 18:44 William Schmidt
2020-07-27 18:47 William Schmidt
2020-06-17 20:04 William Schmidt
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).