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 32 #ifndef ARCHIVE_RB_H_INCLUDED 33 #define ARCHIVE_RB_H_INCLUDED 34 35 struct archive_rb_node { 36 struct archive_rb_node *rb_nodes[2]; 37 /* 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. 41 */ 42 uintptr_t rb_info; 43 }; 44 45 #define ARCHIVE_RB_DIR_LEFT 0 46 #define ARCHIVE_RB_DIR_RIGHT 1 47 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); \ 65 (N) = (S)) 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); \ 69 (N) = (S)) 70 71 /* 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. 76 * 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. 81 */ 82 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 *, 86 const void *); 87 88 struct archive_rb_tree_ops { 89 archive_rbto_compare_nodes_fn rbto_compare_nodes; 90 archive_rbto_compare_key_fn rbto_compare_key; 91 }; 92 93 struct archive_rb_tree { 94 struct archive_rb_node *rbt_root; 95 const struct archive_rb_tree_ops *rbt_ops; 96 }; 97 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); 112 113 #endif /* ARCHIVE_RB_H_*/ 114