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

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 *));