src/prop_rb_impl.h

   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 #include <sys/types.h>
  36 #include "queue.h"
  37
  38 struct rb_node {
  39         struct rb_node *rb_nodes[3];
  40 #define RB_NODE_LEFT            0
  41 #define RB_NODE_RIGHT           1
  42 #define RB_NODE_OTHER           1
  43 #define RB_NODE_PARENT          2
  44 #define rb_left         rb_nodes[RB_NODE_LEFT]
  45 #define rb_right        rb_nodes[RB_NODE_RIGHT]
  46 #define rb_parent       rb_nodes[RB_NODE_PARENT]
  47         union {
  48                 struct {
  49 #if BYTE_ORDER == LITTLE_ENDIAN
  50                         unsigned int : 28;
  51                         unsigned int s_root : 1;
  52                         unsigned int s_position : 1;
  53                         unsigned int s_color : 1;
  54                         unsigned int s_sentinel : 1;
  55 #endif
  56 #if BYTE_ORDER == BIG_ENDIAN
  57                         unsigned int s_sentinel : 1;
  58                         unsigned int s_color : 1;
  59                         unsigned int s_position : 1;
  60                         unsigned int s_root : 1;
  61                         unsigned int : 28;
  62 #endif
  63                 } u_s;
  64                 unsigned int u_i;
  65         } rb_u;
  66 #define rb_root                         rb_u.u_s.s_root
  67 #define rb_position                     rb_u.u_s.s_position
  68 #define rb_color                        rb_u.u_s.s_color
  69 #define rb_sentinel                     rb_u.u_s.s_sentinel
  70 #define rb_properties                   rb_u.u_i
  71 #define RB_SENTINEL_P(rb)               ((rb)->rb_sentinel + 0)
  72 #define RB_LEFT_SENTINEL_P(rb)          ((rb)->rb_left->rb_sentinel + 0)
  73 #define RB_RIGHT_SENTINEL_P(rb)         ((rb)->rb_right->rb_sentinel + 0)
  74 #define RB_PARENT_SENTINEL_P(rb)        ((rb)->rb_parent->rb_sentinel + 0)
  75 #define RB_CHILDLESS_P(rb)              (RB_LEFT_SENTINEL_P(rb) \
  76                                          && RB_RIGHT_SENTINEL_P(rb))
  77 #define RB_TWOCHILDREN_P(rb)            (!RB_LEFT_SENTINEL_P(rb) \
  78                                          && !RB_RIGHT_SENTINEL_P(rb))
  79 #define RB_ROOT_P(rb)                   ((rb)->rb_root != false)
  80 #define RB_RED_P(rb)                    ((rb)->rb_color + 0)
  81 #define RB_BLACK_P(rb)                  (!(rb)->rb_color)
  82 #define RB_MARK_RED(rb)                 ((void)((rb)->rb_color = 1))
  83 #define RB_MARK_BLACK(rb)               ((void)((rb)->rb_color = 0))
  84 #define RB_MARK_ROOT(rb)                ((void)((rb)->rb_root = 1))
  85 #ifdef RBDEBUG
  86         TAILQ_ENTRY(rb_node) rb_link;
  87 #endif
  88 };
  89
  90 #ifdef RBDEBUG
  91 TAILQ_HEAD(rb_node_qh, rb_node);
  92
  93 #define RB_TAILQ_REMOVE                         TAILQ_REMOVE
  94 #define RB_TAILQ_INIT                           TAILQ_INIT
  95 #define RB_TAILQ_INSERT_HEAD(a, b, c)           TAILQ_INSERT_HEAD
  96 #define RB_TAILQ_INSERT_BEFORE(a, b, c)         TAILQ_INSERT_BEFORE
  97 #define RB_TAILQ_INSERT_AFTER(a, b, c, d)       TAILQ_INSERT_AFTER
  98 #else
  99 #define RB_TAILQ_REMOVE(a, b, c)                do { } while (/*CONSTCOND*/0)
 100 #define RB_TAILQ_INIT(a)                        do { } while (/*CONSTCOND*/0)
 101 #define RB_TAILQ_INSERT_HEAD(a, b, c)           do { } while (/*CONSTCOND*/0)
 102 #define RB_TAILQ_INSERT_BEFORE(a, b, c)         do { } while (/*CONSTCOND*/0)
 103 #define RB_TAILQ_INSERT_AFTER(a, b, c, d)       do { } while (/*CONSTCOND*/0)
 104 #endif
 105
 106 typedef int (*rb_compare_nodes_fn)(const struct rb_node *,
 107     const struct rb_node *);
 108 typedef int (*rb_compare_key_fn)(const struct rb_node *, const void *);
 109
 110 struct rb_tree_ops {
 111         rb_compare_nodes_fn     rbto_compare_nodes;
 112         rb_compare_key_fn       rbto_compare_key;
 113 };
 114
 115 struct rb_tree {
 116         struct rb_node *rbt_root;
 117 #ifdef RBDEBUG
 118         struct rb_node_qh rbt_nodes;
 119 #endif
 120         const struct rb_tree_ops *rbt_ops;
 121 #ifdef RBDEBUG
 122         unsigned int rbt_count;
 123 #endif
 124 };
 125
 126 void    _prop_rb_tree_init(struct rb_tree *, const struct rb_tree_ops *);
 127 bool    _prop_rb_tree_insert_node(struct rb_tree *, struct rb_node *);
 128 struct rb_node  *
 129         _prop_rb_tree_find(struct rb_tree *, const void *);
 130 void    _prop_rb_tree_remove_node(struct rb_tree *, struct rb_node *);
 131 #ifdef RBDEBUG
 132 void    _prop_rb_tree_check(const struct rb_tree *, bool);
 133 #endif
 134 struct rb_node *
 135         _prop_rb_tree_iterate(struct rb_tree *, struct rb_node *, unsigned int);
 136
 137 #endif  /* _PROP_RB_IMPL_H_*/