From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id B6F6D3951883 for ; Thu, 17 Jun 2021 15:20:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B6F6D3951883 Received: from pps.filterd (m0098410.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 15HF3dWw107363; Thu, 17 Jun 2021 11:20:56 -0400 Received: from ppma04wdc.us.ibm.com (1a.90.2fa9.ip4.static.sl-reverse.com [169.47.144.26]) by mx0a-001b2d01.pphosted.com with ESMTP id 3987hrknk5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Jun 2021 11:20:55 -0400 Received: from pps.filterd (ppma04wdc.us.ibm.com [127.0.0.1]) by ppma04wdc.us.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 15HFAlYX004007; Thu, 17 Jun 2021 15:20:54 GMT Received: from b03cxnp07027.gho.boulder.ibm.com (b03cxnp07027.gho.boulder.ibm.com [9.17.130.14]) by ppma04wdc.us.ibm.com with ESMTP id 394mja20r7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 17 Jun 2021 15:20:54 +0000 Received: from b03ledav001.gho.boulder.ibm.com (b03ledav001.gho.boulder.ibm.com [9.17.130.232]) by b03cxnp07027.gho.boulder.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 15HFKrQL12976604 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 17 Jun 2021 15:20:53 GMT Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id A202B6E04E; Thu, 17 Jun 2021 15:20:53 +0000 (GMT) Received: from b03ledav001.gho.boulder.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 816E26E054; Thu, 17 Jun 2021 15:20:53 +0000 (GMT) Received: from localhost (unknown [9.40.194.84]) by b03ledav001.gho.boulder.ibm.com (Postfix) with ESMTP; Thu, 17 Jun 2021 15:20:53 +0000 (GMT) From: Bill Schmidt To: gcc-patches@gcc.gnu.org Cc: segher@kernel.crashing.org Subject: [PATCH 09/55] rs6000: Red-black tree implementation for balanced tree search Date: Thu, 17 Jun 2021 10:18:53 -0500 Message-Id: <84213d566e6ce0f25de703c6aed8e9fd2a8207d7.1623941441.git.wschmidt@linux.ibm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: References: In-Reply-To: References: X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 5oJb62zX51N3dtXQDZh0BkvoBHAQ60om X-Proofpoint-ORIG-GUID: 5oJb62zX51N3dtXQDZh0BkvoBHAQ60om X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-06-17_13:2021-06-15, 2021-06-17 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 malwarescore=0 phishscore=0 spamscore=0 impostorscore=0 mlxlogscore=999 clxscore=1015 priorityscore=1501 lowpriorityscore=0 bulkscore=0 mlxscore=0 adultscore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2106170096 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 17 Jun 2021 15:20:58 -0000 2021-06-08 Bill Schmidt gcc/ * config/rs6000/rbtree.c: New file. * config/rs6000/rbtree.h: New file. --- gcc/config/rs6000/rbtree.c | 242 +++++++++++++++++++++++++++++++++++++ gcc/config/rs6000/rbtree.h | 52 ++++++++ 2 files changed, 294 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..37a559c1fbc --- /dev/null +++ b/gcc/config/rs6000/rbtree.c @@ -0,0 +1,242 @@ +/* Partial red-black tree implementation for rs6000-gen-builtins.c. + Copyright (C) 2020-21 Free Software Foundation, Inc. + Contributed by Bill Schmidt, IBM + +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 +. */ + +#include +#include +#include +#include +#include "rbtree.h" + +/* Initialize a red-black tree. */ +void +rbt_new (struct rbt_strings *t) +{ + t->rbt_nil = (rbt_string_node *) malloc (sizeof (rbt_string_node)); + t->rbt_nil->color = RBT_BLACK; + t->rbt_root = t->rbt_nil; +} + +/* 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 (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..fab0001ffde --- /dev/null +++ b/gcc/config/rs6000/rbtree.h @@ -0,0 +1,52 @@ +/* Partial red-black tree implementation for rs6000-gen-builtins.c. + Copyright (C) 2020-21 Free Software Foundation, Inc. + Contributed by Bill Schmidt, IBM + +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 +. */ + +/* 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; +}; + +void rbt_new (struct rbt_strings *); +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.27.0