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
32 #ifndef ARCHIVE_RB_H_INCLUDED
33 #define ARCHIVE_RB_H_INCLUDED
35 struct archive_rb_node {
36 struct archive_rb_node *rb_nodes[2];
38 * rb_info contains the two flags and the parent back pointer.
39 * We put the two flags in the low two bits since we know that
40 * rb_node will have an alignment of 4 or 8 bytes.
45 #define ARCHIVE_RB_DIR_LEFT 0
46 #define ARCHIVE_RB_DIR_RIGHT 1
48 #define ARCHIVE_RB_TREE_MIN(T) \
49 __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_LEFT)
50 #define ARCHIVE_RB_TREE_MAX(T) \
51 __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_RIGHT)
52 #define ARCHIVE_RB_TREE_NEXT(T, N) \
53 __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_RIGHT)
54 #define ARCHIVE_RB_TREE_PREV(T, N) \
55 __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_LEFT)
56 #define ARCHIVE_RB_TREE_FOREACH(N, T) \
57 for ((N) = ARCHIVE_RB_TREE_MIN(T); (N); \
58 (N) = ARCHIVE_RB_TREE_NEXT((T), (N)))
59 #define ARCHIVE_RB_TREE_FOREACH_REVERSE(N, T) \
60 for ((N) = ARCHIVE_RB_TREE_MAX(T); (N); \
61 (N) = ARCHIVE_RB_TREE_PREV((T), (N)))
62 #define ARCHIVE_RB_TREE_FOREACH_SAFE(N, T, S) \
63 for ((N) = ARCHIVE_RB_TREE_MIN(T); \
64 (N) && ((S) = ARCHIVE_RB_TREE_NEXT((T), (N)), 1); \
66 #define ARCHIVE_RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \
67 for ((N) = ARCHIVE_RB_TREE_MAX(T); \
68 (N) && ((S) = ARCHIVE_RB_TREE_PREV((T), (N)), 1); \
72 * archive_rbto_compare_nodes_fn:
73 * return a positive value if the first node < the second node.
74 * return a negative value if the first node > the second node.
75 * return 0 if they are considered same.
77 * archive_rbto_compare_key_fn:
78 * return a positive value if the node < the key.
79 * return a negative value if the node > the key.
80 * return 0 if they are considered same.
83 typedef signed int (*const archive_rbto_compare_nodes_fn)(const struct archive_rb_node *,
84 const struct archive_rb_node *);
85 typedef signed int (*const archive_rbto_compare_key_fn)(const struct archive_rb_node *,
88 struct archive_rb_tree_ops {
89 archive_rbto_compare_nodes_fn rbto_compare_nodes;
90 archive_rbto_compare_key_fn rbto_compare_key;
93 struct archive_rb_tree {
94 struct archive_rb_node *rbt_root;
95 const struct archive_rb_tree_ops *rbt_ops;
98 void __archive_rb_tree_init(struct archive_rb_tree *,
99 const struct archive_rb_tree_ops *);
100 int __archive_rb_tree_insert_node(struct archive_rb_tree *,
101 struct archive_rb_node *);
102 struct archive_rb_node *
103 __archive_rb_tree_find_node(struct archive_rb_tree *, const void *);
104 struct archive_rb_node *
105 __archive_rb_tree_find_node_geq(struct archive_rb_tree *, const void *);
106 struct archive_rb_node *
107 __archive_rb_tree_find_node_leq(struct archive_rb_tree *, const void *);
108 void __archive_rb_tree_remove_node(struct archive_rb_tree *, struct archive_rb_node *);
109 struct archive_rb_node *
110 __archive_rb_tree_iterate(struct archive_rb_tree *,
111 struct archive_rb_node *, const unsigned int);
113 #endif /* ARCHIVE_RB_H_*/