LXR linux/tools/include/linux/rbtree

   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  tools/linux/include/linux/rbtree_augmented.h
  22
  23  Copied from:
  24  linux/include/linux/rbtree_augmented.h
  25*/
  26
  27#ifndef _TOOLS_LINUX_RBTREE_AUGMENTED_H
  28#define _TOOLS_LINUX_RBTREE_AUGMENTED_H
  29
  30#include <linux/compiler.h>
  31#include <linux/rbtree.h>
  32
  33/*
  34 * Please note - only struct rb_augment_callbacks and the prototypes for
  35 * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
  36 * The rest are implementation details you are not expected to depend on.
  37 *
  38 * See Documentation/rbtree.txt for documentation and samples.
  39 */
  40
  41struct rb_augment_callbacks {
  42        void (*propagate)(struct rb_node *node, struct rb_node *stop);
  43        void (*copy)(struct rb_node *old, struct rb_node *new);
  44        void (*rotate)(struct rb_node *old, struct rb_node *new);
  45};
  46
  47extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  48        void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
  49
  50/*
  51 * Fixup the rbtree and update the augmented information when rebalancing.
  52 *
  53 * On insertion, the user must update the augmented information on the path
  54 * leading to the inserted node, then call rb_link_node() as usual and
  55 * rb_insert_augmented() instead of the usual rb_insert_color() call.
  56 * If rb_insert_augmented() rebalances the rbtree, it will callback into
  57 * a user provided function to update the augmented information on the
  58 * affected subtrees.
  59 */
  60static inline void
  61rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  62                    const struct rb_augment_callbacks *augment)
  63{
  64        __rb_insert_augmented(node, root, augment->rotate);
  65}
  66
  67static inline void
  68rb_insert_augmented_cached(struct rb_node *node,
  69                           struct rb_root_cached *root, bool newleft,
  70                           const struct rb_augment_callbacks *augment)
  71{
  72        if (newleft)
  73                root->rb_leftmost = node;
  74        rb_insert_augmented(node, &root->rb_root, augment);
  75}
  76
  77/*
  78 * Template for declaring augmented rbtree callbacks (generic case)
  79 *
  80 * RBSTATIC:    'static' or empty
  81 * RBNAME:      name of the rb_augment_callbacks structure
  82 * RBSTRUCT:    struct type of the tree nodes
  83 * RBFIELD:     name of struct rb_node field within RBSTRUCT
  84 * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
  85 * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
  86 */
  87
  88#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                          \
  89                             RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE) \
  90static inline void                                                      \
  91RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)          \
  92{                                                                       \
  93        while (rb != stop) {                                            \
  94                RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);       \
  95                if (RBCOMPUTE(node, true))                              \
  96                        break;                                          \
  97                rb = rb_parent(&node->RBFIELD);                         \
  98        }                                                               \
  99}                                                                       \
 100static inline void                                                      \
 101RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)         \
 102{                                                                       \
 103        RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);            \
 104        RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);            \
 105        new->RBAUGMENTED = old->RBAUGMENTED;                            \
 106}                                                                       \
 107static void                                                             \
 108RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)       \
 109{                                                                       \
 110        RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);            \
 111        RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);            \
 112        new->RBAUGMENTED = old->RBAUGMENTED;                            \
 113        RBCOMPUTE(old, false);                                          \
 114}                                                                       \
 115RBSTATIC const struct rb_augment_callbacks RBNAME = {                   \
 116        .propagate = RBNAME ## _propagate,                              \
 117        .copy = RBNAME ## _copy,                                        \
 118        .rotate = RBNAME ## _rotate                                     \
 119};
 120
 121/*
 122 * Template for declaring augmented rbtree callbacks,
 123 * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
 124 *
 125 * RBSTATIC:    'static' or empty
 126 * RBNAME:      name of the rb_augment_callbacks structure
 127 * RBSTRUCT:    struct type of the tree nodes
 128 * RBFIELD:     name of struct rb_node field within RBSTRUCT
 129 * RBTYPE:      type of the RBAUGMENTED field
 130 * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
 131 * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
 132 */
 133
 134#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,         \
 135                                 RBTYPE, RBAUGMENTED, RBCOMPUTE)              \
 136static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)          \
 137{                                                                             \
 138        RBSTRUCT *child;                                                      \
 139        RBTYPE max = RBCOMPUTE(node);                                         \
 140        if (node->RBFIELD.rb_left) {                                          \
 141                child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
 142                if (child->RBAUGMENTED > max)                                 \
 143                        max = child->RBAUGMENTED;                             \
 144        }                                                                     \
 145        if (node->RBFIELD.rb_right) {                                         \
 146                child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
 147                if (child->RBAUGMENTED > max)                                 \
 148                        max = child->RBAUGMENTED;                             \
 149        }                                                                     \
 150        if (exit && node->RBAUGMENTED == max)                                 \
 151                return true;                                                  \
 152        node->RBAUGMENTED = max;                                              \
 153        return false;                                                         \
 154}                                                                             \
 155RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                                        \
 156                     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
 157
 158
 159#define RB_RED          0
 160#define RB_BLACK        1
 161
 162#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
 163
 164#define __rb_color(pc)     ((pc) & 1)
 165#define __rb_is_black(pc)  __rb_color(pc)
 166#define __rb_is_red(pc)    (!__rb_color(pc))
 167#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
 168#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
 169#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
 170
 171static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
 172{
 173        rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
 174}
 175
 176static inline void rb_set_parent_color(struct rb_node *rb,
 177                                       struct rb_node *p, int color)
 178{
 179        rb->__rb_parent_color = (unsigned long)p | color;
 180}
 181
 182static inline void
 183__rb_change_child(struct rb_node *old, struct rb_node *new,
 184                  struct rb_node *parent, struct rb_root *root)
 185{
 186        if (parent) {
 187                if (parent->rb_left == old)
 188                        WRITE_ONCE(parent->rb_left, new);
 189                else
 190                        WRITE_ONCE(parent->rb_right, new);
 191        } else
 192                WRITE_ONCE(root->rb_node, new);
 193}
 194
 195extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
 196        void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
 197
 198static __always_inline struct rb_node *
 199__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 200                     const struct rb_augment_callbacks *augment)
 201{
 202        struct rb_node *child = node->rb_right;
 203        struct rb_node *tmp = node->rb_left;
 204        struct rb_node *parent, *rebalance;
 205        unsigned long pc;
 206
 207        if (!tmp) {
 208                /*
 209                 * Case 1: node to erase has no more than 1 child (easy!)
 210                 *
 211                 * Note that if there is one child it must be red due to 5)
 212                 * and node must be black due to 4). We adjust colors locally
 213                 * so as to bypass __rb_erase_color() later on.
 214                 */
 215                pc = node->__rb_parent_color;
 216                parent = __rb_parent(pc);
 217                __rb_change_child(node, child, parent, root);
 218                if (child) {
 219                        child->__rb_parent_color = pc;
 220                        rebalance = NULL;
 221                } else
 222                        rebalance = __rb_is_black(pc) ? parent : NULL;
 223                tmp = parent;
 224        } else if (!child) {
 225                /* Still case 1, but this time the child is node->rb_left */
 226                tmp->__rb_parent_color = pc = node->__rb_parent_color;
 227                parent = __rb_parent(pc);
 228                __rb_change_child(node, tmp, parent, root);
 229                rebalance = NULL;
 230                tmp = parent;
 231        } else {
 232                struct rb_node *successor = child, *child2;
 233
 234                tmp = child->rb_left;
 235                if (!tmp) {
 236                        /*
 237                         * Case 2: node's successor is its right child
 238                         *
 239                         *    (n)          (s)
 240                         *    / \          / \
 241                         *  (x) (s)  ->  (x) (c)
 242                         *        \
 243                         *        (c)
 244                         */
 245                        parent = successor;
 246                        child2 = successor->rb_right;
 247
 248                        augment->copy(node, successor);
 249                } else {
 250                        /*
 251                         * Case 3: node's successor is leftmost under
 252                         * node's right child subtree
 253                         *
 254                         *    (n)          (s)
 255                         *    / \          / \
 256                         *  (x) (y)  ->  (x) (y)
 257                         *      /            /
 258                         *    (p)          (p)
 259                         *    /            /
 260                         *  (s)          (c)
 261                         *    \
 262                         *    (c)
 263                         */
 264                        do {
 265                                parent = successor;
 266                                successor = tmp;
 267                                tmp = tmp->rb_left;
 268                        } while (tmp);
 269                        child2 = successor->rb_right;
 270                        WRITE_ONCE(parent->rb_left, child2);
 271                        WRITE_ONCE(successor->rb_right, child);
 272                        rb_set_parent(child, successor);
 273
 274                        augment->copy(node, successor);
 275                        augment->propagate(parent, successor);
 276                }
 277
 278                tmp = node->rb_left;
 279                WRITE_ONCE(successor->rb_left, tmp);
 280                rb_set_parent(tmp, successor);
 281
 282                pc = node->__rb_parent_color;
 283                tmp = __rb_parent(pc);
 284                __rb_change_child(node, successor, tmp, root);
 285
 286                if (child2) {
 287                        successor->__rb_parent_color = pc;
 288                        rb_set_parent_color(child2, parent, RB_BLACK);
 289                        rebalance = NULL;
 290                } else {
 291                        unsigned long pc2 = successor->__rb_parent_color;
 292                        successor->__rb_parent_color = pc;
 293                        rebalance = __rb_is_black(pc2) ? parent : NULL;
 294                }
 295                tmp = successor;
 296        }
 297
 298        augment->propagate(tmp, NULL);
 299        return rebalance;
 300}
 301
 302static __always_inline void
 303rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 304                   const struct rb_augment_callbacks *augment)
 305{
 306        struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
 307        if (rebalance)
 308                __rb_erase_color(rebalance, root, augment->rotate);
 309}
 310
 311static __always_inline void
 312rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
 313                          const struct rb_augment_callbacks *augment)
 314{
 315        if (root->rb_leftmost == node)
 316                root->rb_leftmost = rb_next(node);
 317        rb_erase_augmented(node, &root->rb_root, augment);
 318}
 319
 320#endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */
 321