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