1 /*- 2 * Copyright (c) 2001 The NetBSD Foundation, Inc. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to The NetBSD Foundation 6 * by Matt Thomas <matt@3am-software.com>. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 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. 16 * 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. 28 * 29 * Based on NetBSD: rb.h,v 1.13 2009/08/16 10:57:01 yamt Exp 30 */ 31 #ifndef ARCHIVE_RB_H_ 32 #define ARCHIVE_RB_H_ 33 34 struct archive_rb_node { 35 struct archive_rb_node *rb_nodes[2]; 36 /* 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. 40 */ 41 uintptr_t rb_info; 42 }; 43 44 #define ARCHIVE_RB_DIR_LEFT 0 45 #define ARCHIVE_RB_DIR_RIGHT 1 46 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)) 57 58 /* 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. 63 * 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. 68 */ 69 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 *, 73 const void *); 74 75 struct archive_rb_tree_ops { 76 archive_rbto_compare_nodes_fn rbto_compare_nodes; 77 archive_rbto_compare_key_fn rbto_compare_key; 78 }; 79 80 struct archive_rb_tree { 81 struct archive_rb_node *rbt_root; 82 const struct archive_rb_tree_ops *rbt_ops; 83 }; 84 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); 99 100 #endif /* ARCHIVE_RB_H_*/ 101