1*f14fb602SLionel Sambuc /* $NetBSD: prop_rb_impl.h,v 1.9 2012/07/27 09:11:00 pooka Exp $ */ 26b6d114aSBen Gras 36b6d114aSBen Gras /*- 46b6d114aSBen Gras * Copyright (c) 2001 The NetBSD Foundation, Inc. 56b6d114aSBen Gras * All rights reserved. 66b6d114aSBen Gras * 76b6d114aSBen Gras * This code is derived from software contributed to The NetBSD Foundation 86b6d114aSBen Gras * by Matt Thomas <matt@3am-software.com>. 96b6d114aSBen Gras * 106b6d114aSBen Gras * Redistribution and use in source and binary forms, with or without 116b6d114aSBen Gras * modification, are permitted provided that the following conditions 126b6d114aSBen Gras * are met: 136b6d114aSBen Gras * 1. Redistributions of source code must retain the above copyright 146b6d114aSBen Gras * notice, this list of conditions and the following disclaimer. 156b6d114aSBen Gras * 2. Redistributions in binary form must reproduce the above copyright 166b6d114aSBen Gras * notice, this list of conditions and the following disclaimer in the 176b6d114aSBen Gras * documentation and/or other materials provided with the distribution. 186b6d114aSBen Gras * 196b6d114aSBen Gras * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 206b6d114aSBen Gras * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 216b6d114aSBen Gras * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 226b6d114aSBen Gras * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 236b6d114aSBen Gras * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 246b6d114aSBen Gras * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 256b6d114aSBen Gras * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 266b6d114aSBen Gras * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 276b6d114aSBen Gras * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 286b6d114aSBen Gras * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 296b6d114aSBen Gras * POSSIBILITY OF SUCH DAMAGE. 306b6d114aSBen Gras */ 316b6d114aSBen Gras 326b6d114aSBen Gras #ifndef _PROP_RB_IMPL_H_ 336b6d114aSBen Gras #define _PROP_RB_IMPL_H_ 346b6d114aSBen Gras 356b6d114aSBen Gras #if defined(__NetBSD__) || defined(__minix) 366b6d114aSBen Gras #include <sys/rbtree.h> 376b6d114aSBen Gras 386b6d114aSBen Gras /* 396b6d114aSBen Gras * Define local names for common rb_tree functions. 406b6d114aSBen Gras */ 416b6d114aSBen Gras #define _prop_rb_tree_init rb_tree_init 426b6d114aSBen Gras #define _prop_rb_tree_insert_node rb_tree_insert_node 436b6d114aSBen Gras #define _prop_rb_tree_find rb_tree_find_node 446b6d114aSBen Gras #define _prop_rb_tree_remove_node rb_tree_remove_node 456b6d114aSBen Gras #define _prop_rb_tree_iterate rb_tree_iterate 466b6d114aSBen Gras 476b6d114aSBen Gras #else /* __NetBSD__ */ 486b6d114aSBen Gras 496b6d114aSBen Gras #include <sys/types.h> 50*f14fb602SLionel Sambuc #ifdef RBDEBUG 516b6d114aSBen Gras #include <sys/queue.h> 52*f14fb602SLionel Sambuc #endif 536b6d114aSBen Gras 54*f14fb602SLionel Sambuc typedef struct rb_node { 55*f14fb602SLionel Sambuc struct rb_node *rb_nodes[2]; 56*f14fb602SLionel Sambuc #define RB_DIR_LEFT 0 57*f14fb602SLionel Sambuc #define RB_DIR_RIGHT 1 58*f14fb602SLionel Sambuc #define RB_DIR_OTHER 1 59*f14fb602SLionel Sambuc #define rb_left rb_nodes[RB_DIR_LEFT] 60*f14fb602SLionel Sambuc #define rb_right rb_nodes[RB_DIR_RIGHT] 61*f14fb602SLionel Sambuc 62*f14fb602SLionel Sambuc /* 63*f14fb602SLionel Sambuc * rb_info contains the two flags and the parent back pointer. 64*f14fb602SLionel Sambuc * We put the two flags in the low two bits since we know that 65*f14fb602SLionel Sambuc * rb_node will have an alignment of 4 or 8 bytes. 66*f14fb602SLionel Sambuc */ 67*f14fb602SLionel Sambuc uintptr_t rb_info; 68*f14fb602SLionel Sambuc #define RB_FLAG_POSITION 0x2 69*f14fb602SLionel Sambuc #define RB_FLAG_RED 0x1 70*f14fb602SLionel Sambuc #define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED) 71*f14fb602SLionel Sambuc #define RB_FATHER(rb) \ 72*f14fb602SLionel Sambuc ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK)) 73*f14fb602SLionel Sambuc #define RB_SET_FATHER(rb, father) \ 74*f14fb602SLionel Sambuc ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK))) 75*f14fb602SLionel Sambuc 76*f14fb602SLionel Sambuc #define RB_SENTINEL_P(rb) ((rb) == NULL) 77*f14fb602SLionel Sambuc #define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left) 78*f14fb602SLionel Sambuc #define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right) 79*f14fb602SLionel Sambuc #define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb))) 80*f14fb602SLionel Sambuc #define RB_CHILDLESS_P(rb) \ 81*f14fb602SLionel Sambuc (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb))) 82*f14fb602SLionel Sambuc #define RB_TWOCHILDREN_P(rb) \ 83*f14fb602SLionel Sambuc (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb)) 84*f14fb602SLionel Sambuc 85*f14fb602SLionel Sambuc #define RB_POSITION(rb) \ 86*f14fb602SLionel Sambuc (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT) 87*f14fb602SLionel Sambuc #define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT) 88*f14fb602SLionel Sambuc #define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT) 89*f14fb602SLionel Sambuc #define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0) 90*f14fb602SLionel Sambuc #define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0) 91*f14fb602SLionel Sambuc #define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED)) 92*f14fb602SLionel Sambuc #define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED)) 93*f14fb602SLionel Sambuc #define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED)) 94*f14fb602SLionel Sambuc #define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb)) 95*f14fb602SLionel Sambuc #define RB_SET_POSITION(rb, position) \ 96*f14fb602SLionel Sambuc ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \ 97*f14fb602SLionel Sambuc ((rb)->rb_info &= ~RB_FLAG_POSITION))) 98*f14fb602SLionel Sambuc #define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK)) 99*f14fb602SLionel Sambuc #define RB_COPY_PROPERTIES(dst, src) \ 100*f14fb602SLionel Sambuc ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK)) 101*f14fb602SLionel Sambuc #define RB_SWAP_PROPERTIES(a, b) do { \ 102*f14fb602SLionel Sambuc uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \ 103*f14fb602SLionel Sambuc (a)->rb_info ^= xorinfo; \ 104*f14fb602SLionel Sambuc (b)->rb_info ^= xorinfo; \ 105*f14fb602SLionel Sambuc } while (/*CONSTCOND*/ 0) 1066b6d114aSBen Gras #ifdef RBDEBUG 1076b6d114aSBen Gras TAILQ_ENTRY(rb_node) rb_link; 1086b6d114aSBen Gras #endif 109*f14fb602SLionel Sambuc } rb_node_t; 110*f14fb602SLionel Sambuc 111*f14fb602SLionel Sambuc #define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT) 112*f14fb602SLionel Sambuc #define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT) 113*f14fb602SLionel Sambuc #define RB_TREE_FOREACH(N, T) \ 114*f14fb602SLionel Sambuc for ((N) = RB_TREE_MIN(T); (N); \ 115*f14fb602SLionel Sambuc (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT)) 116*f14fb602SLionel Sambuc #define RB_TREE_FOREACH_REVERSE(N, T) \ 117*f14fb602SLionel Sambuc for ((N) = RB_TREE_MAX(T); (N); \ 118*f14fb602SLionel Sambuc (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT)) 1196b6d114aSBen Gras 1206b6d114aSBen Gras #ifdef RBDEBUG 1216b6d114aSBen Gras TAILQ_HEAD(rb_node_qh, rb_node); 1226b6d114aSBen Gras 123*f14fb602SLionel Sambuc #define RB_TAILQ_REMOVE(a, b, c) TAILQ_REMOVE(a, b, c) 124*f14fb602SLionel Sambuc #define RB_TAILQ_INIT(a) TAILQ_INIT(a) 125*f14fb602SLionel Sambuc #define RB_TAILQ_INSERT_HEAD(a, b, c) TAILQ_INSERT_HEAD(a, b, c) 126*f14fb602SLionel Sambuc #define RB_TAILQ_INSERT_BEFORE(a, b, c) TAILQ_INSERT_BEFORE(a, b, c) 127*f14fb602SLionel Sambuc #define RB_TAILQ_INSERT_AFTER(a, b, c, d) TAILQ_INSERT_AFTER(a, b, c, d) 1286b6d114aSBen Gras #else 1296b6d114aSBen Gras #define RB_TAILQ_REMOVE(a, b, c) do { } while (/*CONSTCOND*/0) 1306b6d114aSBen Gras #define RB_TAILQ_INIT(a) do { } while (/*CONSTCOND*/0) 1316b6d114aSBen Gras #define RB_TAILQ_INSERT_HEAD(a, b, c) do { } while (/*CONSTCOND*/0) 1326b6d114aSBen Gras #define RB_TAILQ_INSERT_BEFORE(a, b, c) do { } while (/*CONSTCOND*/0) 1336b6d114aSBen Gras #define RB_TAILQ_INSERT_AFTER(a, b, c, d) do { } while (/*CONSTCOND*/0) 134*f14fb602SLionel Sambuc #endif /* RBDEBUG */ 1356b6d114aSBen Gras 136*f14fb602SLionel Sambuc /* 137*f14fb602SLionel Sambuc * rbto_compare_nodes_fn: 138*f14fb602SLionel Sambuc * return a positive value if the first node > the second node. 139*f14fb602SLionel Sambuc * return a negative value if the first node < the second node. 140*f14fb602SLionel Sambuc * return 0 if they are considered same. 141*f14fb602SLionel Sambuc * 142*f14fb602SLionel Sambuc * rbto_compare_key_fn: 143*f14fb602SLionel Sambuc * return a positive value if the node > the key. 144*f14fb602SLionel Sambuc * return a negative value if the node < the key. 145*f14fb602SLionel Sambuc * return 0 if they are considered same. 146*f14fb602SLionel Sambuc */ 1476b6d114aSBen Gras 148*f14fb602SLionel Sambuc typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *); 149*f14fb602SLionel Sambuc typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *); 1506b6d114aSBen Gras 151*f14fb602SLionel Sambuc typedef struct { 152*f14fb602SLionel Sambuc rbto_compare_nodes_fn rbto_compare_nodes; 153*f14fb602SLionel Sambuc rbto_compare_key_fn rbto_compare_key; 154*f14fb602SLionel Sambuc size_t rbto_node_offset; 155*f14fb602SLionel Sambuc void *rbto_context; 156*f14fb602SLionel Sambuc } rb_tree_ops_t; 157*f14fb602SLionel Sambuc 158*f14fb602SLionel Sambuc typedef struct rb_tree { 1596b6d114aSBen Gras struct rb_node *rbt_root; 160*f14fb602SLionel Sambuc const rb_tree_ops_t *rbt_ops; 161*f14fb602SLionel Sambuc struct rb_node *rbt_minmax[2]; 1626b6d114aSBen Gras #ifdef RBDEBUG 1636b6d114aSBen Gras struct rb_node_qh rbt_nodes; 1646b6d114aSBen Gras #endif 165*f14fb602SLionel Sambuc #ifdef RBSTATS 1666b6d114aSBen Gras unsigned int rbt_count; 167*f14fb602SLionel Sambuc unsigned int rbt_insertions; 168*f14fb602SLionel Sambuc unsigned int rbt_removals; 169*f14fb602SLionel Sambuc unsigned int rbt_insertion_rebalance_calls; 170*f14fb602SLionel Sambuc unsigned int rbt_insertion_rebalance_passes; 171*f14fb602SLionel Sambuc unsigned int rbt_removal_rebalance_calls; 172*f14fb602SLionel Sambuc unsigned int rbt_removal_rebalance_passes; 1736b6d114aSBen Gras #endif 174*f14fb602SLionel Sambuc } rb_tree_t; 1756b6d114aSBen Gras 176*f14fb602SLionel Sambuc #ifdef RBSTATS 177*f14fb602SLionel Sambuc #define RBSTAT_INC(v) ((void)((v)++)) 178*f14fb602SLionel Sambuc #define RBSTAT_DEC(v) ((void)((v)--)) 179*f14fb602SLionel Sambuc #else 180*f14fb602SLionel Sambuc #define RBSTAT_INC(v) do { } while (/*CONSTCOND*/0) 181*f14fb602SLionel Sambuc #define RBSTAT_DEC(v) do { } while (/*CONSTCOND*/0) 182*f14fb602SLionel Sambuc #endif 183*f14fb602SLionel Sambuc 184*f14fb602SLionel Sambuc void _prop_rb_tree_init(rb_tree_t *, const rb_tree_ops_t *); 185*f14fb602SLionel Sambuc void * _prop_rb_tree_insert_node(rb_tree_t *, void *); 186*f14fb602SLionel Sambuc void * _prop_rb_tree_find(rb_tree_t *, const void *); 187*f14fb602SLionel Sambuc void * _prop_rb_tree_find_node(rb_tree_t *, const void *); 188*f14fb602SLionel Sambuc void _prop_rb_tree_remove_node(rb_tree_t *, void *); 189*f14fb602SLionel Sambuc void * _prop_rb_tree_iterate(rb_tree_t *, void *, const unsigned int); 1906b6d114aSBen Gras #ifdef RBDEBUG 1916b6d114aSBen Gras void _prop_rb_tree_check(const struct rb_tree *, bool); 1926b6d114aSBen Gras #endif 1936b6d114aSBen Gras 1946b6d114aSBen Gras #endif /* __NetBSD__ */ 1956b6d114aSBen Gras 1966b6d114aSBen Gras #endif /* _PROP_RB_IMPL_H_*/ 197