2 * Copyright (c) 2001 The NetBSD Foundation, Inc.
5 * This code is derived from software contributed to The NetBSD Foundation
6 * by Matt Thomas <matt@3am-software.com>.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
18 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
21 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
29 * Based on NetBSD: rb.h,v 1.13 2009/08/16 10:57:01 yamt Exp
34 struct archive_rb_node {
35 struct archive_rb_node *rb_nodes[2];
37 * rb_info contains the two flags and the parent back pointer.
38 * We put the two flags in the low two bits since we know that
39 * rb_node will have an alignment of 4 or 8 bytes.
44 #define ARCHIVE_RB_DIR_LEFT 0
45 #define ARCHIVE_RB_DIR_RIGHT 1
47 #define ARCHIVE_RB_TREE_MIN(T) \
48 __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_LEFT)
49 #define ARCHIVE_RB_TREE_MAX(T) \
50 __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_RIGHT)
51 #define ARCHIVE_RB_TREE_FOREACH(N, T) \
52 for ((N) = ARCHIVE_RB_TREE_MIN(T); (N); \
53 (N) = __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_RIGHT))
54 #define ARCHIVE_RB_TREE_FOREACH_REVERSE(N, T) \
55 for ((N) = ARCHIVE_RB_TREE_MAX(T); (N); \
56 (N) = __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_LEFT))
59 * archive_rbto_compare_nodes_fn:
60 * return a positive value if the first node < the second node.
61 * return a negative value if the first node > the second node.
62 * return 0 if they are considered same.
64 * archive_rbto_compare_key_fn:
65 * return a positive value if the node < the key.
66 * return a negative value if the node > the key.
67 * return 0 if they are considered same.
70 typedef signed int (*const archive_rbto_compare_nodes_fn)(const struct archive_rb_node *,
71 const struct archive_rb_node *);
72 typedef signed int (*const archive_rbto_compare_key_fn)(const struct archive_rb_node *,
75 struct archive_rb_tree_ops {
76 archive_rbto_compare_nodes_fn rbto_compare_nodes;
77 archive_rbto_compare_key_fn rbto_compare_key;
80 struct archive_rb_tree {
81 struct archive_rb_node *rbt_root;
82 const struct archive_rb_tree_ops *rbt_ops;
85 void __archive_rb_tree_init(struct archive_rb_tree *,
86 const struct archive_rb_tree_ops *);
87 int __archive_rb_tree_insert_node(struct archive_rb_tree *,
88 struct archive_rb_node *);
89 struct archive_rb_node *
90 __archive_rb_tree_find_node(struct archive_rb_tree *, const void *);
91 struct archive_rb_node *
92 __archive_rb_tree_find_node_geq(struct archive_rb_tree *, const void *);
93 struct archive_rb_node *
94 __archive_rb_tree_find_node_leq(struct archive_rb_tree *, const void *);
95 void __archive_rb_tree_remove_node(struct archive_rb_tree *, struct archive_rb_node *);
96 struct archive_rb_node *
97 __archive_rb_tree_iterate(struct archive_rb_tree *,
98 struct archive_rb_node *, const unsigned int);
100 #endif /* ARCHIVE_RB_H_*/