1  /* Partial red-black tree implementation for rs6000-gen-builtins.cc.
       2     Copyright (C) 2020-2023 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 *));