1/* $NetBSD: rb.h,v 1.11 2008/07/03 18:30:39 simonb 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#ifndef _SYS_RB_H_ 32#define _SYS_RB_H_ 33 34#define RBSTATS 1 35 36#if defined(_KERNEL) || defined(_STANDALONE) 37#include <sys/types.h> 38#else 39#include <stdbool.h> 40#include <inttypes.h> 41#endif 42#include <sys/queue.h> 43 44#ifdef __APPLE__ 45#include <machine/endian.h> 46#else 47#include <sys/endian.h> 48#endif 49 50struct rb_node { 51 struct rb_node *rb_nodes[2]; 52#define RB_DIR_LEFT 0 53#define RB_DIR_RIGHT 1 54#define RB_DIR_OTHER 1 55#define rb_left rb_nodes[RB_DIR_LEFT] 56#define rb_right rb_nodes[RB_DIR_RIGHT] 57 58 /* 59 * rb_info contains the two flags and the parent back pointer. 60 * We put the two flags in the low two bits since we know that 61 * rb_node will have an alignment of 4 or 8 bytes. 62 */ 63 uintptr_t rb_info; 64#define RB_FLAG_POSITION 0x2 65#define RB_FLAG_RED 0x1 66#define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED) 67#define RB_FATHER(rb) \ 68 ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK)) 69#define RB_SET_FATHER(rb, father) \ 70 ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK))) 71 72#define RB_SENTINEL_P(rb) ((rb) == NULL) 73#define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left) 74#define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right) 75#define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb))) 76#define RB_CHILDLESS_P(rb) \ 77 (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb))) 78#define RB_TWOCHILDREN_P(rb) \ 79 (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb)) 80 81#define RB_POSITION(rb) \ 82 (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT) 83#define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT) 84#define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT) 85#define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0) 86#define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0) 87#define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED)) 88#define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED)) 89#define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED)) 90#define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb)) 91#define RB_SET_POSITION(rb, position) \ 92 ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \ 93 ((rb)->rb_info &= ~RB_FLAG_POSITION))) 94#define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK)) 95#define RB_COPY_PROPERTIES(dst, src) \ 96 ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK)) 97#define RB_SWAP_PROPERTIES(a, b) do { \ 98 uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \ 99 (a)->rb_info ^= xorinfo; \ 100 (b)->rb_info ^= xorinfo; \ 101 } while (/*CONSTCOND*/ 0) 102#ifdef RBDEBUG 103 TAILQ_ENTRY(rb_node) rb_link; 104#endif 105}; 106 107#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT) 108#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT) 109#define RB_TREE_FOREACH(N, T) \ 110 for ((N) = RB_TREE_MIN(T); (N); \ 111 (N) = rb_tree_iterate((T), (N), RB_DIR_RIGHT)) 112#define RB_TREE_FOREACH_REVERSE(N, T) \ 113 for ((N) = RB_TREE_MAX(T); (N); \ 114 (N) = rb_tree_iterate((T), (N), RB_DIR_LEFT)) 115 116#ifdef RBDEBUG 117TAILQ_HEAD(rb_node_qh, rb_node); 118 119#define RB_TAILQ_REMOVE(a, b, c) TAILQ_REMOVE(a, b, c) 120#define RB_TAILQ_INIT(a) TAILQ_INIT(a) 121#define RB_TAILQ_INSERT_HEAD(a, b, c) TAILQ_INSERT_HEAD(a, b, c) 122#define RB_TAILQ_INSERT_BEFORE(a, b, c) TAILQ_INSERT_BEFORE(a, b, c) 123#define RB_TAILQ_INSERT_AFTER(a, b, c, d) TAILQ_INSERT_AFTER(a, b, c, d) 124#else 125#define RB_TAILQ_REMOVE(a, b, c) do { } while (/*CONSTCOND*/0) 126#define RB_TAILQ_INIT(a) do { } while (/*CONSTCOND*/0) 127#define RB_TAILQ_INSERT_HEAD(a, b, c) do { } while (/*CONSTCOND*/0) 128#define RB_TAILQ_INSERT_BEFORE(a, b, c) do { } while (/*CONSTCOND*/0) 129#define RB_TAILQ_INSERT_AFTER(a, b, c, d) do { } while (/*CONSTCOND*/0) 130#endif /* RBDEBUG */ 131 132typedef signed int (*const rbto_compare_nodes_fn)(const struct rb_node *, 133 const struct rb_node *); 134typedef signed int (*const rbto_compare_key_fn)(const struct rb_node *, 135 const void *); 136 137struct rb_tree_ops { 138 rbto_compare_nodes_fn rbto_compare_nodes; 139 rbto_compare_key_fn rbto_compare_key; 140}; 141 142struct rb_tree { 143 struct rb_node *rbt_root; 144 const struct rb_tree_ops *rbt_ops; 145#ifndef RBSMALL 146 struct rb_node *rbt_minmax[2]; 147#endif 148#ifdef RBDEBUG 149 struct rb_node_qh rbt_nodes; 150#endif 151#ifdef RBSTATS 152 unsigned int rbt_count; 153 unsigned int rbt_insertions; 154 unsigned int rbt_removals; 155 unsigned int rbt_insertion_rebalance_calls; 156 unsigned int rbt_insertion_rebalance_passes; 157 unsigned int rbt_removal_rebalance_calls; 158 unsigned int rbt_removal_rebalance_passes; 159#endif 160}; 161 162#ifdef RBSTATS 163#define RBSTAT_INC(v) ((void)((v)++)) 164#define RBSTAT_DEC(v) ((void)((v)--)) 165#else 166#define RBSTAT_INC(v) do { } while (/*CONSTCOND*/0) 167#define RBSTAT_DEC(v) do { } while (/*CONSTCOND*/0) 168#endif 169 170void rb_tree_init(struct rb_tree *, const struct rb_tree_ops *); 171bool rb_tree_insert_node(struct rb_tree *, struct rb_node *); 172struct rb_node * 173 rb_tree_find_node(struct rb_tree *, const void *); 174struct rb_node * 175 rb_tree_find_node_geq(struct rb_tree *, const void *); 176struct rb_node * 177 rb_tree_find_node_leq(struct rb_tree *, const void *); 178void rb_tree_remove_node(struct rb_tree *, struct rb_node *); 179struct rb_node * 180 rb_tree_iterate(struct rb_tree *, struct rb_node *, const unsigned int); 181#ifdef RBDEBUG 182void rb_tree_check(const struct rb_tree *, bool); 183#endif 184#ifdef RBSTATS 185void rb_tree_depths(const struct rb_tree *, size_t *); 186#endif 187 188#endif /* _SYS_RB_H_*/ 189