1c09f92d2SPeter Avalos /*- 2c09f92d2SPeter Avalos * Copyright (c) 2001 The NetBSD Foundation, Inc. 3c09f92d2SPeter Avalos * All rights reserved. 4c09f92d2SPeter Avalos * 5c09f92d2SPeter Avalos * This code is derived from software contributed to The NetBSD Foundation 6c09f92d2SPeter Avalos * by Matt Thomas <matt@3am-software.com>. 7c09f92d2SPeter Avalos * 8c09f92d2SPeter Avalos * Redistribution and use in source and binary forms, with or without 9c09f92d2SPeter Avalos * modification, are permitted provided that the following conditions 10c09f92d2SPeter Avalos * are met: 11c09f92d2SPeter Avalos * 1. Redistributions of source code must retain the above copyright 12c09f92d2SPeter Avalos * notice, this list of conditions and the following disclaimer. 13c09f92d2SPeter Avalos * 2. Redistributions in binary form must reproduce the above copyright 14c09f92d2SPeter Avalos * notice, this list of conditions and the following disclaimer in the 15c09f92d2SPeter Avalos * documentation and/or other materials provided with the distribution. 16c09f92d2SPeter Avalos * 17c09f92d2SPeter Avalos * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 18c09f92d2SPeter Avalos * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 19c09f92d2SPeter Avalos * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20c09f92d2SPeter Avalos * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 21c09f92d2SPeter Avalos * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22c09f92d2SPeter Avalos * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23c09f92d2SPeter Avalos * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24c09f92d2SPeter Avalos * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25c09f92d2SPeter Avalos * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26c09f92d2SPeter Avalos * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27c09f92d2SPeter Avalos * POSSIBILITY OF SUCH DAMAGE. 28c09f92d2SPeter Avalos * 29c09f92d2SPeter Avalos * Based on NetBSD: rb.h,v 1.13 2009/08/16 10:57:01 yamt Exp 30c09f92d2SPeter Avalos */ 31085658deSDaniel Fojt 32085658deSDaniel Fojt #ifndef ARCHIVE_RB_H_INCLUDED 33085658deSDaniel Fojt #define ARCHIVE_RB_H_INCLUDED 34c09f92d2SPeter Avalos 35c09f92d2SPeter Avalos struct archive_rb_node { 36c09f92d2SPeter Avalos struct archive_rb_node *rb_nodes[2]; 37c09f92d2SPeter Avalos /* 38c09f92d2SPeter Avalos * rb_info contains the two flags and the parent back pointer. 39c09f92d2SPeter Avalos * We put the two flags in the low two bits since we know that 40c09f92d2SPeter Avalos * rb_node will have an alignment of 4 or 8 bytes. 41c09f92d2SPeter Avalos */ 42c09f92d2SPeter Avalos uintptr_t rb_info; 43c09f92d2SPeter Avalos }; 44c09f92d2SPeter Avalos 45c09f92d2SPeter Avalos #define ARCHIVE_RB_DIR_LEFT 0 46c09f92d2SPeter Avalos #define ARCHIVE_RB_DIR_RIGHT 1 47c09f92d2SPeter Avalos 48c09f92d2SPeter Avalos #define ARCHIVE_RB_TREE_MIN(T) \ 49c09f92d2SPeter Avalos __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_LEFT) 50c09f92d2SPeter Avalos #define ARCHIVE_RB_TREE_MAX(T) \ 51c09f92d2SPeter Avalos __archive_rb_tree_iterate((T), NULL, ARCHIVE_RB_DIR_RIGHT) 52085658deSDaniel Fojt #define ARCHIVE_RB_TREE_NEXT(T, N) \ 53085658deSDaniel Fojt __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_RIGHT) 54085658deSDaniel Fojt #define ARCHIVE_RB_TREE_PREV(T, N) \ 55085658deSDaniel Fojt __archive_rb_tree_iterate((T), (N), ARCHIVE_RB_DIR_LEFT) 56c09f92d2SPeter Avalos #define ARCHIVE_RB_TREE_FOREACH(N, T) \ 57c09f92d2SPeter Avalos for ((N) = ARCHIVE_RB_TREE_MIN(T); (N); \ 58085658deSDaniel Fojt (N) = ARCHIVE_RB_TREE_NEXT((T), (N))) 59c09f92d2SPeter Avalos #define ARCHIVE_RB_TREE_FOREACH_REVERSE(N, T) \ 60c09f92d2SPeter Avalos for ((N) = ARCHIVE_RB_TREE_MAX(T); (N); \ 61085658deSDaniel Fojt (N) = ARCHIVE_RB_TREE_PREV((T), (N))) 62085658deSDaniel Fojt #define ARCHIVE_RB_TREE_FOREACH_SAFE(N, T, S) \ 63085658deSDaniel Fojt for ((N) = ARCHIVE_RB_TREE_MIN(T); \ 64085658deSDaniel Fojt (N) && ((S) = ARCHIVE_RB_TREE_NEXT((T), (N)), 1); \ 65085658deSDaniel Fojt (N) = (S)) 66085658deSDaniel Fojt #define ARCHIVE_RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \ 67085658deSDaniel Fojt for ((N) = ARCHIVE_RB_TREE_MAX(T); \ 68085658deSDaniel Fojt (N) && ((S) = ARCHIVE_RB_TREE_PREV((T), (N)), 1); \ 69085658deSDaniel Fojt (N) = (S)) 70c09f92d2SPeter Avalos 71c09f92d2SPeter Avalos /* 72c09f92d2SPeter Avalos * archive_rbto_compare_nodes_fn: 73c09f92d2SPeter Avalos * return a positive value if the first node < the second node. 74c09f92d2SPeter Avalos * return a negative value if the first node > the second node. 75c09f92d2SPeter Avalos * return 0 if they are considered same. 76c09f92d2SPeter Avalos * 77c09f92d2SPeter Avalos * archive_rbto_compare_key_fn: 78c09f92d2SPeter Avalos * return a positive value if the node < the key. 79c09f92d2SPeter Avalos * return a negative value if the node > the key. 80c09f92d2SPeter Avalos * return 0 if they are considered same. 81c09f92d2SPeter Avalos */ 82c09f92d2SPeter Avalos 83c09f92d2SPeter Avalos typedef signed int (*const archive_rbto_compare_nodes_fn)(const struct archive_rb_node *, 84c09f92d2SPeter Avalos const struct archive_rb_node *); 85c09f92d2SPeter Avalos typedef signed int (*const archive_rbto_compare_key_fn)(const struct archive_rb_node *, 86c09f92d2SPeter Avalos const void *); 87c09f92d2SPeter Avalos 88c09f92d2SPeter Avalos struct archive_rb_tree_ops { 89c09f92d2SPeter Avalos archive_rbto_compare_nodes_fn rbto_compare_nodes; 90c09f92d2SPeter Avalos archive_rbto_compare_key_fn rbto_compare_key; 91c09f92d2SPeter Avalos }; 92c09f92d2SPeter Avalos 93c09f92d2SPeter Avalos struct archive_rb_tree { 94c09f92d2SPeter Avalos struct archive_rb_node *rbt_root; 95c09f92d2SPeter Avalos const struct archive_rb_tree_ops *rbt_ops; 96c09f92d2SPeter Avalos }; 97c09f92d2SPeter Avalos 98c09f92d2SPeter Avalos void __archive_rb_tree_init(struct archive_rb_tree *, 99c09f92d2SPeter Avalos const struct archive_rb_tree_ops *); 100c09f92d2SPeter Avalos int __archive_rb_tree_insert_node(struct archive_rb_tree *, 101c09f92d2SPeter Avalos struct archive_rb_node *); 102c09f92d2SPeter Avalos struct archive_rb_node * 103c09f92d2SPeter Avalos __archive_rb_tree_find_node(struct archive_rb_tree *, const void *); 104c09f92d2SPeter Avalos struct archive_rb_node * 105c09f92d2SPeter Avalos __archive_rb_tree_find_node_geq(struct archive_rb_tree *, const void *); 106c09f92d2SPeter Avalos struct archive_rb_node * 107c09f92d2SPeter Avalos __archive_rb_tree_find_node_leq(struct archive_rb_tree *, const void *); 108c09f92d2SPeter Avalos void __archive_rb_tree_remove_node(struct archive_rb_tree *, struct archive_rb_node *); 109c09f92d2SPeter Avalos struct archive_rb_node * 110c09f92d2SPeter Avalos __archive_rb_tree_iterate(struct archive_rb_tree *, 111c09f92d2SPeter Avalos struct archive_rb_node *, const unsigned int); 112c09f92d2SPeter Avalos 113c09f92d2SPeter Avalos #endif /* ARCHIVE_RB_H_*/ 114