1 /* $NetBSD: prop_rb_impl.h,v 1.7 2008/06/30 20:14:09 matt Exp $ */ 2 3 /*- 4 * Copyright (c) 2001 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Matt Thomas <matt@3am-software.com>. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _PROP_RB_IMPL_H_ 33 #define _PROP_RB_IMPL_H_ 34 35 #ifdef __NetBSD__ 36 #include <sys/rb.h> 37 38 /* 39 * Define local names for common rb_tree functions. 40 */ 41 #define _prop_rb_tree_init rb_tree_init 42 #define _prop_rb_tree_insert_node rb_tree_insert_node 43 #define _prop_rb_tree_find rb_tree_find_node 44 #define _prop_rb_tree_remove_node rb_tree_remove_node 45 #define _prop_rb_tree_iterate rb_tree_iterate 46 47 #else /* __NetBSD__ */ 48 49 #include <sys/types.h> 50 #include <sys/queue.h> 51 #include <machine/endian.h> 52 53 struct rb_node { 54 struct rb_node *rb_nodes[3]; 55 #define RB_NODE_LEFT 0 56 #define RB_NODE_RIGHT 1 57 #define RB_NODE_OTHER 1 58 #define RB_NODE_PARENT 2 59 #define rb_left rb_nodes[RB_NODE_LEFT] 60 #define rb_right rb_nodes[RB_NODE_RIGHT] 61 #define rb_parent rb_nodes[RB_NODE_PARENT] 62 union { 63 struct { 64 #if BYTE_ORDER == LITTLE_ENDIAN 65 unsigned int : 28; 66 unsigned int s_root : 1; 67 unsigned int s_position : 1; 68 unsigned int s_color : 1; 69 unsigned int s_sentinel : 1; 70 #endif 71 #if BYTE_ORDER == BIG_ENDIAN 72 unsigned int s_sentinel : 1; 73 unsigned int s_color : 1; 74 unsigned int s_position : 1; 75 unsigned int s_root : 1; 76 unsigned int : 28; 77 #endif 78 } u_s; 79 unsigned int u_i; 80 } rb_u; 81 #define rb_root rb_u.u_s.s_root 82 #define rb_position rb_u.u_s.s_position 83 #define rb_color rb_u.u_s.s_color 84 #define rb_sentinel rb_u.u_s.s_sentinel 85 #define rb_properties rb_u.u_i 86 #define RB_SENTINEL_P(rb) ((rb)->rb_sentinel + 0) 87 #define RB_LEFT_SENTINEL_P(rb) ((rb)->rb_left->rb_sentinel + 0) 88 #define RB_RIGHT_SENTINEL_P(rb) ((rb)->rb_right->rb_sentinel + 0) 89 #define RB_PARENT_SENTINEL_P(rb) ((rb)->rb_parent->rb_sentinel + 0) 90 #define RB_CHILDLESS_P(rb) (RB_LEFT_SENTINEL_P(rb) \ 91 && RB_RIGHT_SENTINEL_P(rb)) 92 #define RB_TWOCHILDREN_P(rb) (!RB_LEFT_SENTINEL_P(rb) \ 93 && !RB_RIGHT_SENTINEL_P(rb)) 94 #define RB_ROOT_P(rb) ((rb)->rb_root != false) 95 #define RB_RED_P(rb) ((rb)->rb_color + 0) 96 #define RB_BLACK_P(rb) (!(rb)->rb_color) 97 #define RB_MARK_RED(rb) ((void)((rb)->rb_color = 1)) 98 #define RB_MARK_BLACK(rb) ((void)((rb)->rb_color = 0)) 99 #define RB_MARK_ROOT(rb) ((void)((rb)->rb_root = 1)) 100 #ifdef RBDEBUG 101 TAILQ_ENTRY(rb_node) rb_link; 102 #endif 103 }; 104 105 #ifdef RBDEBUG 106 TAILQ_HEAD(rb_node_qh, rb_node); 107 108 #define RB_TAILQ_REMOVE TAILQ_REMOVE 109 #define RB_TAILQ_INIT TAILQ_INIT 110 #define RB_TAILQ_INSERT_HEAD(a, b, c) TAILQ_INSERT_HEAD 111 #define RB_TAILQ_INSERT_BEFORE(a, b, c) TAILQ_INSERT_BEFORE 112 #define RB_TAILQ_INSERT_AFTER(a, b, c, d) TAILQ_INSERT_AFTER 113 #else 114 #define RB_TAILQ_REMOVE(a, b, c) do { } while (/*CONSTCOND*/0) 115 #define RB_TAILQ_INIT(a) do { } while (/*CONSTCOND*/0) 116 #define RB_TAILQ_INSERT_HEAD(a, b, c) do { } while (/*CONSTCOND*/0) 117 #define RB_TAILQ_INSERT_BEFORE(a, b, c) do { } while (/*CONSTCOND*/0) 118 #define RB_TAILQ_INSERT_AFTER(a, b, c, d) do { } while (/*CONSTCOND*/0) 119 #endif 120 121 typedef int (*rb_compare_nodes_fn)(const struct rb_node *, 122 const struct rb_node *); 123 typedef int (*rb_compare_key_fn)(const struct rb_node *, const void *); 124 125 struct rb_tree_ops { 126 rb_compare_nodes_fn rbto_compare_nodes; 127 rb_compare_key_fn rbto_compare_key; 128 }; 129 130 struct rb_tree { 131 struct rb_node *rbt_root; 132 #ifdef RBDEBUG 133 struct rb_node_qh rbt_nodes; 134 #endif 135 const struct rb_tree_ops *rbt_ops; 136 #ifdef RBDEBUG 137 unsigned int rbt_count; 138 #endif 139 }; 140 141 void _prop_rb_tree_init(struct rb_tree *, const struct rb_tree_ops *); 142 bool _prop_rb_tree_insert_node(struct rb_tree *, struct rb_node *); 143 struct rb_node * 144 _prop_rb_tree_find(struct rb_tree *, const void *); 145 void _prop_rb_tree_remove_node(struct rb_tree *, struct rb_node *); 146 #ifdef RBDEBUG 147 void _prop_rb_tree_check(const struct rb_tree *, bool); 148 #endif 149 struct rb_node * 150 _prop_rb_tree_iterate(struct rb_tree *, struct rb_node *, unsigned int); 151 152 #endif /* __NetBSD__ */ 153 154 #endif /* _PROP_RB_IMPL_H_*/ 155