src/prop_rb_impl.h

   1 /*      $NetBSD: prop_rb_impl.h,v 1.8 2010/09/25 01:42:38 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 #if 1
  36 #include <rbtree.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_*/