blob: 4ba88a0f4d3c63f9538661bb607dcc262fe39c82 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
/* Partial red-black tree implementation for rs6000-gen-builtins.c.
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 *));
|
