Subversion Repositories Kolibri OS

Rev

Rev 4103 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.   Red Black Trees
  3.   (C) 1999  Andrea Arcangeli <andrea@suse.de>
  4.   (C) 2002  David Woodhouse <dwmw2@infradead.org>
  5.   (C) 2012  Michel Lespinasse <walken@google.com>
  6.  
  7.   This program is free software; you can redistribute it and/or modify
  8.   it under the terms of the GNU General Public License as published by
  9.   the Free Software Foundation; either version 2 of the License, or
  10.   (at your option) any later version.
  11.  
  12.   This program is distributed in the hope that it will be useful,
  13.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.   GNU General Public License for more details.
  16.  
  17.   You should have received a copy of the GNU General Public License
  18.   along with this program; if not, write to the Free Software
  19.   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20.  
  21.   linux/include/linux/rbtree_augmented.h
  22. */
  23.  
  24. #ifndef _LINUX_RBTREE_AUGMENTED_H
  25. #define _LINUX_RBTREE_AUGMENTED_H
  26.  
  27. #include <linux/compiler.h>
  28. #include <linux/rbtree.h>
  29.  
  30. /*
  31.  * Please note - only struct rb_augment_callbacks and the prototypes for
  32.  * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
  33.  * The rest are implementation details you are not expected to depend on.
  34.  *
  35.  * See Documentation/rbtree.txt for documentation and samples.
  36.  */
  37.  
  38. struct rb_augment_callbacks {
  39.         void (*propagate)(struct rb_node *node, struct rb_node *stop);
  40.         void (*copy)(struct rb_node *old, struct rb_node *new);
  41.         void (*rotate)(struct rb_node *old, struct rb_node *new);
  42. };
  43.  
  44. extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  45.         void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
  46. /*
  47.  * Fixup the rbtree and update the augmented information when rebalancing.
  48.  *
  49.  * On insertion, the user must update the augmented information on the path
  50.  * leading to the inserted node, then call rb_link_node() as usual and
  51.  * rb_augment_inserted() instead of the usual rb_insert_color() call.
  52.  * If rb_augment_inserted() rebalances the rbtree, it will callback into
  53.  * a user provided function to update the augmented information on the
  54.  * affected subtrees.
  55.  */
  56. static inline void
  57. rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  58.                     const struct rb_augment_callbacks *augment)
  59. {
  60.         __rb_insert_augmented(node, root, augment->rotate);
  61. }
  62.  
  63. #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,       \
  64.                              rbtype, rbaugmented, rbcompute)            \
  65. static inline void                                                      \
  66. rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)          \
  67. {                                                                       \
  68.         while (rb != stop) {                                            \
  69.                 rbstruct *node = rb_entry(rb, rbstruct, rbfield);       \
  70.                 rbtype augmented = rbcompute(node);                     \
  71.                 if (node->rbaugmented == augmented)                     \
  72.                         break;                                          \
  73.                 node->rbaugmented = augmented;                          \
  74.                 rb = rb_parent(&node->rbfield);                         \
  75.         }                                                               \
  76. }                                                                       \
  77. static inline void                                                      \
  78. rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)         \
  79. {                                                                       \
  80.         rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);            \
  81.         rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);            \
  82.         new->rbaugmented = old->rbaugmented;                            \
  83. }                                                                       \
  84. static void                                                             \
  85. rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)       \
  86. {                                                                       \
  87.         rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);            \
  88.         rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);            \
  89.         new->rbaugmented = old->rbaugmented;                            \
  90.         old->rbaugmented = rbcompute(old);                              \
  91. }                                                                       \
  92. rbstatic const struct rb_augment_callbacks rbname = {                   \
  93.         rbname ## _propagate, rbname ## _copy, rbname ## _rotate        \
  94. };
  95.  
  96.  
  97. #define RB_RED          0
  98. #define RB_BLACK        1
  99.  
  100. #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
  101.  
  102. #define __rb_color(pc)     ((pc) & 1)
  103. #define __rb_is_black(pc)  __rb_color(pc)
  104. #define __rb_is_red(pc)    (!__rb_color(pc))
  105. #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
  106. #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
  107. #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
  108.  
  109. static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
  110. {
  111.         rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
  112. }
  113.  
  114. static inline void rb_set_parent_color(struct rb_node *rb,
  115.                                        struct rb_node *p, int color)
  116. {
  117.         rb->__rb_parent_color = (unsigned long)p | color;
  118. }
  119.  
  120. static inline void
  121. __rb_change_child(struct rb_node *old, struct rb_node *new,
  122.                   struct rb_node *parent, struct rb_root *root)
  123. {
  124.         if (parent) {
  125.                 if (parent->rb_left == old)
  126.                         parent->rb_left = new;
  127.                 else
  128.                         parent->rb_right = new;
  129.         } else
  130.                 root->rb_node = new;
  131. }
  132.  
  133. extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
  134.         void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
  135.  
  136. static __always_inline struct rb_node *
  137. __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
  138.                      const struct rb_augment_callbacks *augment)
  139. {
  140.         struct rb_node *child = node->rb_right, *tmp = node->rb_left;
  141.         struct rb_node *parent, *rebalance;
  142.         unsigned long pc;
  143.  
  144.         if (!tmp) {
  145.                 /*
  146.                  * Case 1: node to erase has no more than 1 child (easy!)
  147.                  *
  148.                  * Note that if there is one child it must be red due to 5)
  149.                  * and node must be black due to 4). We adjust colors locally
  150.                  * so as to bypass __rb_erase_color() later on.
  151.                  */
  152.                 pc = node->__rb_parent_color;
  153.                 parent = __rb_parent(pc);
  154.                 __rb_change_child(node, child, parent, root);
  155.                 if (child) {
  156.                         child->__rb_parent_color = pc;
  157.                         rebalance = NULL;
  158.                 } else
  159.                         rebalance = __rb_is_black(pc) ? parent : NULL;
  160.                 tmp = parent;
  161.         } else if (!child) {
  162.                 /* Still case 1, but this time the child is node->rb_left */
  163.                 tmp->__rb_parent_color = pc = node->__rb_parent_color;
  164.                 parent = __rb_parent(pc);
  165.                 __rb_change_child(node, tmp, parent, root);
  166.                 rebalance = NULL;
  167.                 tmp = parent;
  168.         } else {
  169.                 struct rb_node *successor = child, *child2;
  170.                 tmp = child->rb_left;
  171.                 if (!tmp) {
  172.                         /*
  173.                          * Case 2: node's successor is its right child
  174.                          *
  175.                          *    (n)          (s)
  176.                          *    / \          / \
  177.                          *  (x) (s)  ->  (x) (c)
  178.                          *        \
  179.                          *        (c)
  180.                          */
  181.                         parent = successor;
  182.                         child2 = successor->rb_right;
  183.                         augment->copy(node, successor);
  184.                 } else {
  185.                         /*
  186.                          * Case 3: node's successor is leftmost under
  187.                          * node's right child subtree
  188.                          *
  189.                          *    (n)          (s)
  190.                          *    / \          / \
  191.                          *  (x) (y)  ->  (x) (y)
  192.                          *      /            /
  193.                          *    (p)          (p)
  194.                          *    /            /
  195.                          *  (s)          (c)
  196.                          *    \
  197.                          *    (c)
  198.                          */
  199.                         do {
  200.                                 parent = successor;
  201.                                 successor = tmp;
  202.                                 tmp = tmp->rb_left;
  203.                         } while (tmp);
  204.                         parent->rb_left = child2 = successor->rb_right;
  205.                         successor->rb_right = child;
  206.                         rb_set_parent(child, successor);
  207.                         augment->copy(node, successor);
  208.                         augment->propagate(parent, successor);
  209.                 }
  210.  
  211.                 successor->rb_left = tmp = node->rb_left;
  212.                 rb_set_parent(tmp, successor);
  213.  
  214.                 pc = node->__rb_parent_color;
  215.                 tmp = __rb_parent(pc);
  216.                 __rb_change_child(node, successor, tmp, root);
  217.                 if (child2) {
  218.                         successor->__rb_parent_color = pc;
  219.                         rb_set_parent_color(child2, parent, RB_BLACK);
  220.                         rebalance = NULL;
  221.                 } else {
  222.                         unsigned long pc2 = successor->__rb_parent_color;
  223.                         successor->__rb_parent_color = pc;
  224.                         rebalance = __rb_is_black(pc2) ? parent : NULL;
  225.                 }
  226.                 tmp = successor;
  227.         }
  228.  
  229.         augment->propagate(tmp, NULL);
  230.         return rebalance;
  231. }
  232.  
  233. static __always_inline void
  234. rb_erase_augmented(struct rb_node *node, struct rb_root *root,
  235.                    const struct rb_augment_callbacks *augment)
  236. {
  237.         struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
  238.         if (rebalance)
  239.                 __rb_erase_color(rebalance, root, augment->rotate);
  240. }
  241.  
  242. #endif  /* _LINUX_RBTREE_AUGMENTED_H */
  243.