xref: /netbsd-src/external/gpl3/gcc/dist/gcc/config/rs6000/rbtree.h (revision b1e838363e3c6fc78a55519254d99869742dd33c)
1 /* Partial red-black tree implementation for rs6000-gen-builtins.cc.
2    Copyright (C) 2020-2022 Free Software Foundation, Inc.
3    Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20 
21 /* Red-black binary search tree on strings.  Presently we don't support
22    deletes; only insert/find operations are implemented.  */
23 enum rbt_color
24   {
25     RBT_BLACK,
26     RBT_RED
27   };
28 
29 struct rbt_string_node {
30   char *str;
31   struct rbt_string_node *left;
32   struct rbt_string_node *right;
33   struct rbt_string_node *par;
34   enum rbt_color color;
35 };
36 
37 /* Root and sentinel nodes of a red-black tree.
38    rbt_nil points to a sentinel node, which is the parent of root
39    and the child of every node without a "real" left or right child.
40    rbt_root points to the root of the tree, if it exists yet.  The
41    root and sentinel nodes are always black.  */
42 struct rbt_strings {
43   struct rbt_string_node *rbt_nil;
44   struct rbt_string_node *rbt_root;
45 };
46 
47 void rbt_new (struct rbt_strings *);
48 int rbt_insert (struct rbt_strings *, char *);
49 int rbt_find (struct rbt_strings *, char *);
50 void rbt_dump (struct rbt_strings *, struct rbt_string_node *);
51 void rbt_inorder_callback (struct rbt_strings *, struct rbt_string_node *,
52 			   void (*) (char *));
53