rb.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /* $NetBSD: rb.c,v 1.2 2002/10/08 11:58:54 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  * 3. All advertising materials mentioning features or use of this software
   19  *    must display the following acknowledgement:
   20  *        This product includes software developed by the NetBSD
   21  *        Foundation, Inc. and its contributors.
   22  * 4. Neither the name of The NetBSD Foundation nor the names of its
   23  *    contributors may be used to endorse or promote products derived
   24  *    from this software without specific prior written permission.
   25  *
   26  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   27  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   28  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   29  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   30  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   31  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   32  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   33  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   34  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   36  * POSSIBILITY OF SUCH DAMAGE.
   37  */
   38 
   39 #include <sys/types.h>
   40 #include <stddef.h>
   41 #ifndef _KERNEL
   42 #include <assert.h>
   43 #define KASSERT(s)      assert(s)
   44 #endif
   45 #include "rb.h"
   46 
   47 static void rb_tree_rotate(struct rb_tree *, struct rb_node *, int);
   48 static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
   49 static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *);
   50 
   51 /*
   52  * Rather than testing for the NULL everywhere, all terminal leaves are
   53  * pointed to this node.  Note that by setting it to be const, that on
   54  * some architectures trying to write to it will cause a fault.
   55  */
   56 static const struct rb_node sentinel_node = {
   57         NULL, NULL, NULL, { NULL, NULL }, 0, 0, 1
   58 };
   59 
   60 void
   61 rb_tree_init(struct rb_tree *rbt, rb_compare_nodes_fn compare_nodes,
   62         rb_compare_key_fn compare_key, rb_print_node_fn print_node)
   63 {
   64         TAILQ_INIT(&rbt->rbt_nodes);
   65         rbt->rbt_count = 0;
   66         rbt->rbt_compare_nodes = compare_nodes;
   67         rbt->rbt_compare_key = compare_key;
   68         rbt->rbt_print_node = print_node;
   69         *((const struct rb_node **)&rbt->rbt_root) = &sentinel_node;
   70 }
   71 
   72 /*
   73  * Rotate the tree between     Y   and    X
   74  *                           X   c       a   Y
   75  *                          a b             b c
   76  */
   77 void
   78 rb_tree_rotate(struct rb_tree *rbt, struct rb_node *self, int which)
   79 {
   80         const int other = which ^ RB_OTHER;
   81         struct rb_node * const parent = self->rb_parent;
   82         struct rb_node * const child = self->rb_nodes[other];
   83         
   84         assert(!child->rb_sentinel);
   85         assert(child->rb_parent == self);
   86 #if 0
   87         (*rbt->rbt_print_node)(child, which ? "before-l " : "before-r ");
   88 #endif
   89 
   90         if ((child->rb_parent = parent) == NULL) {
   91                 assert(rbt->rbt_root == self);
   92                 rbt->rbt_root = child;
   93         } else {
   94                 parent->rb_nodes[self->rb_position] = child;
   95         }
   96 
   97         self->rb_nodes[other] = child->rb_nodes[which];
   98         if (!self->rb_nodes[other]->rb_sentinel)
   99                 self->rb_nodes[other]->rb_parent = self;
  100         child->rb_nodes[which] = self;
  101         child->rb_position = self->rb_position;
  102         self->rb_parent = child;
  103         self->rb_position = which;
  104 #if 0
  105         (*rbt->rbt_print_node)(self, which ? "after-l " : "after-r ");
  106 #endif
  107 }
  108 
  109 void
  110 rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
  111 {
  112         struct rb_node *prev, *next, *tmp, *parent;
  113         struct rb_node **insert_p;
  114         u_int position;
  115 
  116         prev = NULL;
  117         next = NULL;
  118         parent = NULL;
  119         tmp = rbt->rbt_root;    
  120 
  121         /*
  122          * Find out where to place this new leaf.
  123          */
  124         while (!tmp->rb_sentinel) {
  125                 const int diff = (*rbt->rbt_compare_nodes)(tmp, self);
  126                 parent = tmp;
  127                 assert(diff != 0);
  128                 if (diff < 0) {
  129                         position = RB_LEFT;
  130                         next = parent->rb_left;
  131                         prev = NULL;
  132                 } else {
  133                         position = RB_RIGHT;
  134                         prev = parent->rb_right;
  135                         next = NULL;
  136                 }
  137                 tmp = parent->rb_nodes[position];
  138         }
  139 
  140         /*
  141          * Verify our sequential position
  142          */
  143         if (prev != NULL && next == NULL)
  144                 next = TAILQ_NEXT(prev, rb_link);
  145         if (prev == NULL && next != NULL)
  146                 next = TAILQ_PREV(next, rb_node_qh, rb_link);
  147         assert(prev == NULL || (*rbt->rbt_compare_nodes)(prev, self) > 0);
  148         assert(next == NULL || (*rbt->rbt_compare_nodes)(self, next) < 0);
  149 
  150         /*
  151          * Initialize the node and insert as a leaf into the tree.
  152          */
  153         rbt->rbt_count++;
  154         self->rb_parent = parent;
  155         if (parent == NULL) {
  156                 assert(rbt->rbt_root->rb_sentinel);
  157                 self->rb_position = RB_PARENT;
  158                 self->rb_left = rbt->rbt_root;
  159                 self->rb_right = rbt->rbt_root;
  160                 rbt->rbt_root = self;
  161         } else {
  162                 self->rb_position = position;
  163                 self->rb_left = parent->rb_nodes[position];
  164                 self->rb_right = parent->rb_nodes[position];
  165                 parent->rb_nodes[position] = self;
  166         }
  167         assert(self->rb_left == &sentinel_node &&
  168             self->rb_right == &sentinel_node);
  169 
  170         /*
  171          * Insert the new node into a sorted list for easy sequential access
  172          */
  173         if (next != NULL) {
  174                 TAILQ_INSERT_BEFORE(next, self, rb_link);
  175         } else {
  176                 TAILQ_INSERT_TAIL(&rbt->rbt_nodes, self, rb_link);
  177         }
  178 
  179         /*
  180          * Rebalance tree after insertation
  181          */
  182         rb_tree_insert_rebalance(rbt, self);
  183 }
  184 
  185 void
  186 rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
  187 {
  188         self->rb_red = 1;
  189 
  190         while (self != rbt->rbt_root && self->rb_parent->rb_red) {
  191                 const int which =
  192                      (self->rb_parent == self->rb_parent->rb_parent->rb_left
  193                         ? RB_LEFT
  194                         : RB_RIGHT);
  195                 const int other = which ^ RB_OTHER;
  196                 struct rb_node *uncle;
  197 
  198                 assert(!self->rb_sentinel);
  199                 /*
  200                  * We are red, our are parent is red, and our
  201                  * grandparent is black.
  202                  */
  203                 uncle = self->rb_parent->rb_parent->rb_nodes[other];
  204                 if (uncle->rb_red) {
  205                         /*
  206                          * Case 1: our uncle is red
  207                          *   Simply invert the colors of our parent and
  208                          *   uncle and make our grandparent red.  And
  209                          *   then solve the problem up at his level.
  210                          */
  211                         uncle->rb_red = 0;
  212                         self->rb_parent->rb_red = 0;
  213                         self->rb_parent->rb_parent->rb_red = 1;
  214                         self = self->rb_parent->rb_parent;
  215                 } else {
  216                         /*
  217                          * Case 2&3: our uncle is black.
  218                          */
  219                         if (self == self->rb_parent->rb_nodes[other]) {
  220                                 /*
  221                                  * Case 2: we are on the same side as our uncle
  222                                  *   Rotate parent away from uncle so this
  223                                  *   case becomes case 3
  224                                  */
  225                                 self = self->rb_parent;
  226                                 rb_tree_rotate(rbt, self, which);
  227                         }
  228                         /*
  229                          * Case 3: we are opposite a child of a black uncle.
  230                          *   Change parent to black and grandparent to
  231                          *   red.  Rotate grandparent away from ourself.
  232                          */
  233                         self->rb_parent->rb_red = 0;
  234                         self->rb_parent->rb_parent->rb_red = 1;
  235                         rb_tree_rotate(rbt, self->rb_parent->rb_parent, other);
  236                 }
  237         }
  238 
  239         /*
  240          * Final step: Set the root to black.
  241          */
  242         rbt->rbt_root->rb_red = 0;
  243 }
  244 
  245 struct rb_node *
  246 rb_tree_lookup(struct rb_tree *rbt, void *key)
  247 {
  248         struct rb_node *parent = rbt->rbt_root;
  249 
  250         while (!parent->rb_sentinel) {
  251                 const int diff = (*rbt->rbt_compare_key)(parent, key);
  252                 if (diff == 0)
  253                         return parent;
  254                 parent = parent->rb_nodes[diff > 0];
  255         }
  256 
  257         return NULL;
  258 }
  259 
  260 void
  261 rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
  262 {
  263         struct rb_node *child;
  264         /*
  265          * Easy case, one or more children is NULL (leaf node or parent of
  266          * leaf node).
  267          */
  268         if (self->rb_left->rb_sentinel || self->rb_left->rb_sentinel) {
  269                 const int which = (!self->rb_left->rb_sentinel ? RB_LEFT : RB_RIGHT);
  270                 child = self->rb_nodes[which];
  271                 if (self->rb_parent == NULL) {
  272                         rbt->rbt_root = child;
  273                 } else {
  274                         self->rb_parent->rb_nodes[self->rb_position] = child;
  275                 }
  276                 if (child->rb_sentinel)
  277                         child = self->rb_parent;
  278                 else
  279                         child->rb_parent = self->rb_parent;
  280         } else {
  281                 struct rb_node *new_self;
  282                 child = self->rb_right;
  283                 while (!child->rb_left->rb_sentinel)
  284                         child = child->rb_left;
  285                 new_self = child;
  286                 assert(new_self == TAILQ_NEXT(self, rb_link));
  287                 
  288                 /*
  289                  * Take new_self out of the tree (its only subnode can be on the
  290                  * right since we know the left subnode is NULL).
  291                  */
  292                 child->rb_parent->rb_left = child->rb_right;
  293                 if (!child->rb_right->rb_sentinel) {
  294                         child->rb_right->rb_parent = child->rb_parent;
  295                         child->rb_right->rb_position = RB_LEFT;
  296                 }
  297 
  298                 /*
  299                  * Take self out of the tree and insert new_self into its place.
  300                  */
  301                 new_self->rb_right = self->rb_right;
  302                 new_self->rb_left = self->rb_left;
  303                 if (!new_self->rb_right->rb_sentinel)
  304                         new_self->rb_right->rb_parent = new_self;
  305                 if (!new_self->rb_left->rb_sentinel)
  306                         new_self->rb_left->rb_parent = new_self;
  307                 new_self->rb_red = self->rb_red;
  308                 new_self->rb_parent = self->rb_parent;
  309                 /*
  310                  * Update parent
  311                  */
  312                 if (new_self->rb_parent == NULL) {
  313                         rbt->rbt_root = new_self;
  314                 } else {
  315                         new_self->rb_parent->rb_nodes[self->rb_position] = new_self;
  316                 }
  317         }
  318         TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
  319         rbt->rbt_count--;
  320 
  321         if (child != NULL) {
  322                 assert(!child->rb_sentinel);
  323 #if 0
  324                 (*rbt->rbt_print_node)(child, "before ");
  325 #endif
  326                 rb_tree_removal_rebalance(rbt, child);
  327 #if 0
  328                 (*rbt->rbt_print_node)(child, "after ");
  329 #endif
  330         }
  331 }
  332 
  333 void
  334 rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *self)
  335 {
  336         assert(!self->rb_sentinel);
  337         while (self->rb_parent != NULL && !self->rb_red) {
  338                 struct rb_node *parent = self->rb_parent;
  339                 int which = (self == parent->rb_left) ? RB_LEFT : RB_RIGHT;
  340                 int other = which ^ RB_OTHER;
  341                 struct rb_node *sibling = parent->rb_nodes[other];
  342 
  343                 if (sibling->rb_red) {
  344                         sibling->rb_red = 0;
  345                         parent->rb_red = 1;
  346                         rb_tree_rotate(rbt, parent, which);
  347                         parent = self->rb_parent;
  348                         sibling = parent->rb_nodes[other];
  349                 }
  350 
  351                 if (sibling->rb_sentinel ||
  352                     (!sibling->rb_left->rb_red && !sibling->rb_right->rb_red)) {
  353                         sibling->rb_red = 1;
  354                         self = parent;
  355                         continue;
  356                 }
  357 
  358                 if (!sibling->rb_nodes[other]->rb_red) {
  359                         sibling->rb_nodes[which]->rb_red = 0;
  360                         sibling->rb_red = 1;
  361                         rb_tree_rotate(rbt, sibling, other);
  362                         parent = self->rb_parent;
  363                         sibling = parent->rb_nodes[other];
  364                 }
  365 
  366                 sibling->rb_red = parent->rb_red;
  367                 parent->rb_red = 0;
  368                 sibling->rb_nodes[other]->rb_red = 0;
  369                 rb_tree_rotate(rbt, parent, which);
  370                 break;
  371         }
  372 }
Cache object: fb137ed2c88625b5aa28692539370109
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/lib/libkern/rb.c

FreeBSD/Linux Kernel Cross Reference
sys/lib/libkern/rb.c
