Guest User

Untitled

a guest
Jun 26th, 2016
332
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <unistd.h>
  2. #include <stdbool.h>
  3.  
  4. struct rb_node {
  5.     unsigned long  __rb_parent_color;
  6.     struct rb_node *rb_right;
  7.     struct rb_node *rb_left;
  8. } __attribute__((aligned(sizeof(long))));
  9.  
  10. struct rb_root {
  11.     struct rb_node *rb_node;
  12. };
  13.  
  14.  
  15. #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
  16.  
  17. #define RB_ROOT (struct rb_root) { NULL, }
  18. #define rb_entry(ptr, type, member) container_of(ptr, type, member)
  19.  
  20. #define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
  21.  
  22. #define RB_EMPTY_NODE(node)  \
  23.     ((node)->__rb_parent_color == (unsigned long)(node))
  24. #define RB_CLEAR_NODE(node)  \
  25.     ((node)->__rb_parent_color = (unsigned long)(node))
  26.  
  27.  
  28. extern void rb_insert_color(struct rb_node *, struct rb_root *);
  29. extern void rb_erase(struct rb_node *, struct rb_root *);
  30. extern struct rb_node *rb_next(const struct rb_node *);
  31. extern struct rb_node *rb_prev(const struct rb_node *);
  32. extern struct rb_node *rb_first(const struct rb_root *);
  33. extern struct rb_node *rb_last(const struct rb_root *);
  34.  
  35. extern struct rb_node *rb_first_postorder(const struct rb_root *);
  36. extern struct rb_node *rb_next_postorder(const struct rb_node *);
  37.  
  38. extern void rb_replace_node(struct rb_node *victim, struct rb_node *nw, struct rb_root *root);
  39.  
  40. static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link)
  41. {
  42.     node->__rb_parent_color = (unsigned long)parent;
  43.     node->rb_left = node->rb_right = NULL;
  44.  
  45.     *rb_link = node;
  46. }
  47.  
  48. #define rb_entry_safe(ptr, type, member) ({ typeof(ptr) ____ptr = (ptr); ____ptr ? rb_entry(____ptr, type, member) : NULL; })
  49.  
  50. #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), typeof(*pos), field); 1; });
  51.  
  52. struct rb_augment_callbacks {
  53.     void (*propagate)(struct rb_node *node, struct rb_node *stop);
  54.     void (*copy)(struct rb_node *old, struct rb_node *nw);
  55.     void (*rotate)(struct rb_node *old, struct rb_node *nw);
  56. };
  57.  
  58. extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  59.     void (*augment_rotate)(struct rb_node *old, struct rb_node *nw));
  60.  
  61. static inline void
  62. rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  63.             const struct rb_augment_callbacks *augment)
  64. {
  65.     __rb_insert_augmented(node, root, augment->rotate);
  66. }
  67.  
  68.  
  69. #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, rbtype, rbaugmented, rbcompute) \
  70. static inline void \
  71. rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
  72. { \
  73.     while (rb != stop) { \
  74.         rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
  75.         rbtype augmented = rbcompute(node);         \
  76.         if (node->rbaugmented == augmented)         \
  77.             break;                      \
  78.         node->rbaugmented = augmented;              \
  79.         rb = rb_parent(&node->rbfield);             \
  80.     }                               \
  81. }                                   \
  82. static inline void                          \
  83. rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)     \
  84. {                                   \
  85.     rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);        \
  86.     rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);        \
  87.     new->rbaugmented = old->rbaugmented;                \
  88. }                                   \
  89. static void                             \
  90. rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)   \
  91. {                                   \
  92.     rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);        \
  93.     rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);        \
  94.     new->rbaugmented = old->rbaugmented;                \
  95.     old->rbaugmented = rbcompute(old);              \
  96. }                                   \
  97. rbstatic const struct rb_augment_callbacks rbname = {           \
  98.     rbname ## _propagate, rbname ## _copy, rbname ## _rotate    \
  99. };
  100.  
  101. #define RB_RED      0
  102. #define RB_BLACK    1
  103.  
  104. #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
  105.  
  106. #define __rb_color(pc)     ((pc) & 1)
  107. #define __rb_is_black(pc)  __rb_color(pc)
  108. #define __rb_is_red(pc)    (!__rb_color(pc))
  109. #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
  110. #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
  111. #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
  112.  
  113. static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
  114. {
  115.     rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
  116. }
  117.  
  118. static inline void rb_set_parent_color(struct rb_node *rb,
  119.                        struct rb_node *p, int color)
  120. {
  121.     rb->__rb_parent_color = (unsigned long)p | color;
  122. }
  123.  
  124. static inline void
  125. __rb_change_child(struct rb_node *old, struct rb_node *nw,
  126.           struct rb_node *parent, struct rb_root *root)
  127. {
  128.     if (parent) {
  129.         if (parent->rb_left == old)
  130.             parent->rb_left = nw;
  131.         else
  132.             parent->rb_right = nw;
  133.     } else
  134.         root->rb_node = nw;
  135. }
  136.  
  137. extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
  138.     void (*augment_rotate)(struct rb_node *old, struct rb_node *nw));
  139.  
  140. static __always_inline struct rb_node *
  141. __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
  142.              const struct rb_augment_callbacks *augment)
  143. {
  144.     struct rb_node *child = node->rb_right, *tmp = node->rb_left;
  145.     struct rb_node *parent, *rebalance;
  146.     unsigned long pc;
  147.  
  148.     if (!tmp) {
  149.         /*
  150.          * Case 1: node to erase has no more than 1 child (easy!)
  151.          *
  152.          * Note that if there is one child it must be red due to 5)
  153.          * and node must be black due to 4). We adjust colors locally
  154.          * so as to bypass __rb_erase_color() later on.
  155.          */
  156.         pc = node->__rb_parent_color;
  157.         parent = __rb_parent(pc);
  158.         __rb_change_child(node, child, parent, root);
  159.         if (child) {
  160.             child->__rb_parent_color = pc;
  161.             rebalance = NULL;
  162.         } else
  163.             rebalance = __rb_is_black(pc) ? parent : NULL;
  164.         tmp = parent;
  165.     } else if (!child) {
  166.         /* Still case 1, but this time the child is node->rb_left */
  167.         tmp->__rb_parent_color = pc = node->__rb_parent_color;
  168.         parent = __rb_parent(pc);
  169.         __rb_change_child(node, tmp, parent, root);
  170.         rebalance = NULL;
  171.         tmp = parent;
  172.     } else {
  173.         struct rb_node *successor = child, *child2;
  174.         tmp = child->rb_left;
  175.         if (!tmp) {
  176.             /*
  177.              * Case 2: node's successor is its right child
  178.              *
  179.              *    (n)          (s)
  180.              *    / \          / \
  181.              *  (x) (s)  ->  (x) (c)
  182.              *        \
  183.              *        (c)
  184.              */
  185.             parent = successor;
  186.             child2 = successor->rb_right;
  187.             augment->copy(node, successor);
  188.         } else {
  189.             /*
  190.              * Case 3: node's successor is leftmost under
  191.              * node's right child subtree
  192.              *
  193.              *    (n)          (s)
  194.              *    / \          / \
  195.              *  (x) (y)  ->  (x) (y)
  196.              *      /            /
  197.              *    (p)          (p)
  198.              *    /            /
  199.              *  (s)          (c)
  200.              *    \
  201.              *    (c)
  202.              */
  203.             do {
  204.                 parent = successor;
  205.                 successor = tmp;
  206.                 tmp = tmp->rb_left;
  207.             } while (tmp);
  208.             parent->rb_left = child2 = successor->rb_right;
  209.             successor->rb_right = child;
  210.             rb_set_parent(child, successor);
  211.             augment->copy(node, successor);
  212.             augment->propagate(parent, successor);
  213.         }
  214.  
  215.         successor->rb_left = tmp = node->rb_left;
  216.         rb_set_parent(tmp, successor);
  217.  
  218.         pc = node->__rb_parent_color;
  219.         tmp = __rb_parent(pc);
  220.         __rb_change_child(node, successor, tmp, root);
  221.         if (child2) {
  222.             successor->__rb_parent_color = pc;
  223.             rb_set_parent_color(child2, parent, RB_BLACK);
  224.             rebalance = NULL;
  225.         } else {
  226.             unsigned long pc2 = successor->__rb_parent_color;
  227.             successor->__rb_parent_color = pc;
  228.             rebalance = __rb_is_black(pc2) ? parent : NULL;
  229.         }
  230.         tmp = successor;
  231.     }
  232.  
  233.     augment->propagate(tmp, NULL);
  234.     return rebalance;
  235. }
  236.  
  237.  
  238. #define RB_RED    0
  239. #define RB_BLACK  1
  240.  
  241. static inline void rb_set_black(struct rb_node *rb)
  242. {
  243.     rb->__rb_parent_color |= RB_BLACK;
  244. }
  245.  
  246. static inline struct rb_node *rb_red_parent(struct rb_node *red)
  247. {
  248.     return (struct rb_node *)red->__rb_parent_color;
  249. }
  250.  
  251. static inline void
  252. __rb_rotate_set_parents(struct rb_node *old, struct rb_node *nw,
  253.                         struct rb_root *root, int color)
  254. {
  255.     struct rb_node *parent = rb_parent(old);
  256.     nw->__rb_parent_color = old->__rb_parent_color;
  257.     rb_set_parent_color(old, nw, color);
  258.     __rb_change_child(old, nw, parent, root);
  259. }
  260.  
  261. static __always_inline void
  262. __rb_insert(struct rb_node *node, struct rb_root *root,
  263.             void (*augment_rotate)(struct rb_node *old, struct rb_node *nw))
  264. {
  265.     struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
  266.  
  267.     while (true) {
  268.     /*
  269.     * Loop invariant: node is red
  270.     *
  271.     * If there is a black parent, we are done.
  272.     * Otherwise, take some corrective action as we don't
  273.     * want a red root or two consecutive red nodes.
  274.     */
  275.         if (!parent) {
  276.             rb_set_parent_color(node, NULL, RB_BLACK);
  277.             break;
  278.         } else if (rb_is_black(parent))
  279.             break;
  280.  
  281.         gparent = rb_red_parent(parent);
  282.  
  283.         tmp = gparent->rb_right;
  284.         if (parent != tmp) {    /* parent == gparent->rb_left */
  285.             if (tmp && rb_is_red(tmp)) {
  286.                 /*
  287.                  * Case 1 - color flips
  288.                  *
  289.                  *       G            g
  290.                  *      / \          / \
  291.                  *     p   u  -->   P   U
  292.                  *    /            /
  293.                  *   n            n
  294.                  *
  295.                  * However, since g's parent might be red, and
  296.                  * 4) does not allow this, we need to recurse
  297.                  * at g.
  298.                  */
  299.                 rb_set_parent_color(tmp, gparent, RB_BLACK);
  300.                 rb_set_parent_color(parent, gparent, RB_BLACK);
  301.                 node = gparent;
  302.                 parent = rb_parent(node);
  303.                 rb_set_parent_color(node, parent, RB_RED);
  304.                 continue;
  305.             }
  306.  
  307.             tmp = parent->rb_right;
  308.             if (node == tmp) {
  309.                 /*
  310.                  * Case 2 - left rotate at parent
  311.                  *
  312.                  *      G             G
  313.                  *     / \           / \
  314.                  *    p   U  -->    n   U
  315.                  *     \           /
  316.                  *      n         p
  317.                  *
  318.                  * This still leaves us in violation of 4), the
  319.                  * continuation into Case 3 will fix that.
  320.                  */
  321.                 parent->rb_right = tmp = node->rb_left;
  322.                 node->rb_left = parent;
  323.                 if (tmp)
  324.                     rb_set_parent_color(tmp, parent,
  325.                                 RB_BLACK);
  326.                 rb_set_parent_color(parent, node, RB_RED);
  327.                 augment_rotate(parent, node);
  328.                 parent = node;
  329.                 tmp = node->rb_right;
  330.             }
  331.  
  332.             /*
  333.              * Case 3 - right rotate at gparent
  334.              *
  335.              *        G           P
  336.              *       / \         / \
  337.              *      p   U  -->  n   g
  338.              *     /                 \
  339.              *    n                   U
  340.              */
  341.             gparent->rb_left = tmp;  /* == parent->rb_right */
  342.             parent->rb_right = gparent;
  343.             if (tmp)
  344.                 rb_set_parent_color(tmp, gparent, RB_BLACK);
  345.             __rb_rotate_set_parents(gparent, parent, root, RB_RED);
  346.             augment_rotate(gparent, parent);
  347.             break;
  348.         } else {
  349.             tmp = gparent->rb_left;
  350.             if (tmp && rb_is_red(tmp)) {
  351.                 /* Case 1 - color flips */
  352.                 rb_set_parent_color(tmp, gparent, RB_BLACK);
  353.                 rb_set_parent_color(parent, gparent, RB_BLACK);
  354.                 node = gparent;
  355.                 parent = rb_parent(node);
  356.                 rb_set_parent_color(node, parent, RB_RED);
  357.                 continue;
  358.             }
  359.  
  360.             tmp = parent->rb_left;
  361.             if (node == tmp) {
  362.                 /* Case 2 - right rotate at parent */
  363.                 parent->rb_left = tmp = node->rb_right;
  364.                 node->rb_right = parent;
  365.                 if (tmp)
  366.                     rb_set_parent_color(tmp, parent,
  367.                                 RB_BLACK);
  368.                 rb_set_parent_color(parent, node, RB_RED);
  369.                 augment_rotate(parent, node);
  370.                 parent = node;
  371.                 tmp = node->rb_left;
  372.             }
  373.  
  374.             /* Case 3 - left rotate at gparent */
  375.             gparent->rb_right = tmp;  /* == parent->rb_left */
  376.             parent->rb_left = gparent;
  377.             if (tmp)
  378.                 rb_set_parent_color(tmp, gparent, RB_BLACK);
  379.             __rb_rotate_set_parents(gparent, parent, root, RB_RED);
  380.             augment_rotate(gparent, parent);
  381.             break;
  382.         }
  383.     }
  384. }
  385.  
  386. static __always_inline void
  387. ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
  388.                    void (*augment_rotate)(struct rb_node *old,
  389.                                           struct rb_node *nw))
  390. {
  391.     struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
  392.  
  393.     while (true) {
  394.         /*
  395.          * Loop invariants:
  396.          * - node is black (or NULL on first iteration)
  397.          * - node is not the root (parent is not NULL)
  398.          * - All leaf paths going through parent and node have a
  399.          *   black node count that is 1 lower than other leaf paths.
  400.          */
  401.         sibling = parent->rb_right;
  402.         if (node != sibling) {    /* node == parent->rb_left */
  403.             if (rb_is_red(sibling)) {
  404.                 /*
  405.                  * Case 1 - left rotate at parent
  406.                  *
  407.                  *     P               S
  408.                  *    / \             / \
  409.                  *   N   s    -->    p   Sr
  410.                  *      / \         / \
  411.                  *     Sl  Sr      N   Sl
  412.                  */
  413.                 parent->rb_right = tmp1 = sibling->rb_left;
  414.                 sibling->rb_left = parent;
  415.                 rb_set_parent_color(tmp1, parent, RB_BLACK);
  416.                 __rb_rotate_set_parents(parent, sibling, root,
  417.                             RB_RED);
  418.                 augment_rotate(parent, sibling);
  419.                 sibling = tmp1;
  420.             }
  421.             tmp1 = sibling->rb_right;
  422.             if (!tmp1 || rb_is_black(tmp1)) {
  423.                 tmp2 = sibling->rb_left;
  424.                 if (!tmp2 || rb_is_black(tmp2)) {
  425.                     /*
  426.                      * Case 2 - sibling color flip
  427.                      * (p could be either color here)
  428.                      *
  429.                      *    (p)           (p)
  430.                      *    / \           / \
  431.                      *   N   S    -->  N   s
  432.                      *      / \           / \
  433.                      *     Sl  Sr        Sl  Sr
  434.                      *
  435.                      * This leaves us violating 5) which
  436.                      * can be fixed by flipping p to black
  437.                      * if it was red, or by recursing at p.
  438.                      * p is red when coming from Case 1.
  439.                      */
  440.                     rb_set_parent_color(sibling, parent,
  441.                                 RB_RED);
  442.                     if (rb_is_red(parent))
  443.                         rb_set_black(parent);
  444.                     else {
  445.                         node = parent;
  446.                         parent = rb_parent(node);
  447.                         if (parent)
  448.                             continue;
  449.                     }
  450.                     break;
  451.                 }
  452.                 /*
  453.                  * Case 3 - right rotate at sibling
  454.                  * (p could be either color here)
  455.                  *
  456.                  *   (p)           (p)
  457.                  *   / \           / \
  458.                  *  N   S    -->  N   Sl
  459.                  *     / \             \
  460.                  *    sl  Sr            s
  461.                  *                       \
  462.                  *                        Sr
  463.                  */
  464.                 sibling->rb_left = tmp1 = tmp2->rb_right;
  465.                 tmp2->rb_right = sibling;
  466.                 parent->rb_right = tmp2;
  467.                 if (tmp1)
  468.                     rb_set_parent_color(tmp1, sibling,
  469.                                 RB_BLACK);
  470.                 augment_rotate(sibling, tmp2);
  471.                 tmp1 = sibling;
  472.                 sibling = tmp2;
  473.             }
  474.             /*
  475.              * Case 4 - left rotate at parent + color flips
  476.              * (p and sl could be either color here.
  477.              *  After rotation, p becomes black, s acquires
  478.              *  p's color, and sl keeps its color)
  479.              *
  480.              *      (p)             (s)
  481.              *      / \             / \
  482.              *     N   S     -->   P   Sr
  483.              *        / \         / \
  484.              *      (sl) sr      N  (sl)
  485.              */
  486.             parent->rb_right = tmp2 = sibling->rb_left;
  487.             sibling->rb_left = parent;
  488.             rb_set_parent_color(tmp1, sibling, RB_BLACK);
  489.             if (tmp2)
  490.                 rb_set_parent(tmp2, parent);
  491.             __rb_rotate_set_parents(parent, sibling, root,
  492.                         RB_BLACK);
  493.             augment_rotate(parent, sibling);
  494.             break;
  495.         } else {
  496.             sibling = parent->rb_left;
  497.             if (rb_is_red(sibling)) {
  498.                 /* Case 1 - right rotate at parent */
  499.                 parent->rb_left = tmp1 = sibling->rb_right;
  500.                 sibling->rb_right = parent;
  501.                 rb_set_parent_color(tmp1, parent, RB_BLACK);
  502.                 __rb_rotate_set_parents(parent, sibling, root,
  503.                             RB_RED);
  504.                 augment_rotate(parent, sibling);
  505.                 sibling = tmp1;
  506.             }
  507.             tmp1 = sibling->rb_left;
  508.             if (!tmp1 || rb_is_black(tmp1)) {
  509.                 tmp2 = sibling->rb_right;
  510.                 if (!tmp2 || rb_is_black(tmp2)) {
  511.                     /* Case 2 - sibling color flip */
  512.                     rb_set_parent_color(sibling, parent,
  513.                                 RB_RED);
  514.                     if (rb_is_red(parent))
  515.                         rb_set_black(parent);
  516.                     else {
  517.                         node = parent;
  518.                         parent = rb_parent(node);
  519.                         if (parent)
  520.                             continue;
  521.                     }
  522.                     break;
  523.                 }
  524.                 /* Case 3 - right rotate at sibling */
  525.                 sibling->rb_right = tmp1 = tmp2->rb_left;
  526.                 tmp2->rb_left = sibling;
  527.                 parent->rb_left = tmp2;
  528.                 if (tmp1)
  529.                     rb_set_parent_color(tmp1, sibling,
  530.                                 RB_BLACK);
  531.                 augment_rotate(sibling, tmp2);
  532.                 tmp1 = sibling;
  533.                 sibling = tmp2;
  534.             }
  535.             /* Case 4 - left rotate at parent + color flips */
  536.             parent->rb_left = tmp2 = sibling->rb_right;
  537.             sibling->rb_right = parent;
  538.             rb_set_parent_color(tmp1, sibling, RB_BLACK);
  539.             if (tmp2)
  540.                 rb_set_parent(tmp2, parent);
  541.             __rb_rotate_set_parents(parent, sibling, root,
  542.                         RB_BLACK);
  543.             augment_rotate(parent, sibling);
  544.             break;
  545.         }
  546.     }
  547. }
  548.  
  549. void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
  550.                       void (*augment_rotate)(struct rb_node *old, struct rb_node *nw))
  551. {
  552.     ____rb_erase_color(parent, root, augment_rotate);
  553. }
  554.  
  555. static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
  556. static inline void dummy_copy(struct rb_node *old, struct rb_node *nw) {}
  557. static inline void dummy_rotate(struct rb_node *old, struct rb_node *nw) {}
  558.  
  559. static const struct rb_augment_callbacks dummy_callbacks = {
  560.     dummy_propagate, dummy_copy, dummy_rotate
  561. };
  562.  
  563. void rb_insert_color(struct rb_node *node, struct rb_root *root)
  564. {
  565.     __rb_insert(node, root, dummy_rotate);
  566. }
  567.  
  568. void rb_erase(struct rb_node *node, struct rb_root *root)
  569. {
  570.     struct rb_node *rebalance;
  571.     rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
  572.     if (rebalance)
  573.         ____rb_erase_color(rebalance, root, dummy_rotate);
  574. }
  575.  
  576. void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  577.                            void (*augment_rotate)(struct rb_node *old,
  578.                                                   struct rb_node *nw))
  579. {
  580.     __rb_insert(node, root, augment_rotate);
  581. }
  582.  
  583. struct rb_node *rb_first(const struct rb_root *root)
  584. {
  585.     struct rb_node    *n;
  586.  
  587.     n = root->rb_node;
  588.     if (!n)
  589.         return NULL;
  590.     while (n->rb_left)
  591.         n = n->rb_left;
  592.     return n;
  593. }
  594.  
  595. struct rb_node *rb_last(const struct rb_root *root)
  596. {
  597.     struct rb_node    *n;
  598.  
  599.     n = root->rb_node;
  600.     if (!n)
  601.         return NULL;
  602.     while (n->rb_right)
  603.         n = n->rb_right;
  604.     return n;
  605. }
  606.  
  607. struct rb_node *rb_next(const struct rb_node *node)
  608. {
  609.     struct rb_node *parent;
  610.  
  611.     if (RB_EMPTY_NODE(node))
  612.         return NULL;
  613.  
  614.     /*
  615.      * If we have a right-hand child, go down and then left as far
  616.      * as we can.
  617.      */
  618.     if (node->rb_right) {
  619.         node = node->rb_right;
  620.         while (node->rb_left)
  621.             node=node->rb_left;
  622.         return (struct rb_node *)node;
  623.     }
  624.  
  625.     /*
  626.      * No right-hand children. Everything down and left is smaller than us,
  627.      * so any 'next' node must be in the general direction of our parent.
  628.      * Go up the tree; any time the ancestor is a right-hand child of its
  629.      * parent, keep going up. First time it's a left-hand child of its
  630.      * parent, said parent is our 'next' node.
  631.      */
  632.     while ((parent = rb_parent(node)) && node == parent->rb_right)
  633.         node = parent;
  634.  
  635.     return parent;
  636. }
  637.  
  638. struct rb_node *rb_prev(const struct rb_node *node)
  639. {
  640.     struct rb_node *parent;
  641.  
  642.     if (RB_EMPTY_NODE(node))
  643.         return NULL;
  644.  
  645.     /*
  646.      * If we have a left-hand child, go down and then right as far
  647.      * as we can.
  648.      */
  649.     if (node->rb_left) {
  650.         node = node->rb_left;
  651.         while (node->rb_right)
  652.             node=node->rb_right;
  653.         return (struct rb_node *)node;
  654.     }
  655.  
  656.     /*
  657.      * No left-hand children. Go up till we find an ancestor which
  658.      * is a right-hand child of its parent.
  659.      */
  660.     while ((parent = rb_parent(node)) && node == parent->rb_left)
  661.         node = parent;
  662.  
  663.     return parent;
  664. }
  665.  
  666. void rb_replace_node(struct rb_node *victim, struct rb_node *nw,
  667.              struct rb_root *root)
  668. {
  669.     struct rb_node *parent = rb_parent(victim);
  670.  
  671.     /* Set the surrounding nodes to point to the replacement */
  672.     __rb_change_child(victim, nw, parent, root);
  673.     if (victim->rb_left)
  674.         rb_set_parent(victim->rb_left, nw);
  675.     if (victim->rb_right)
  676.         rb_set_parent(victim->rb_right, nw);
  677.  
  678.     /* Copy the pointers/colour from the victim to the replacement */
  679.     *nw = *victim;
  680. }
  681.  
  682. static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
  683. {
  684.     for (;;) {
  685.         if (node->rb_left)
  686.             node = node->rb_left;
  687.         else if (node->rb_right)
  688.             node = node->rb_right;
  689.         else
  690.             return (struct rb_node *)node;
  691.     }
  692. }
  693.  
  694. struct rb_node *rb_next_postorder(const struct rb_node *node)
  695. {
  696.     const struct rb_node *parent;
  697.     if (!node)
  698.         return NULL;
  699.     parent = rb_parent(node);
  700.  
  701.     /* If we're sitting on node, we've already seen our children */
  702.     if (parent && node == parent->rb_left && parent->rb_right) {
  703.         /* If we are the parent's left node, go to the parent's right
  704.          * node then all the way down to the left */
  705.         return rb_left_deepest_node(parent->rb_right);
  706.     } else
  707.         /* Otherwise we are the parent's right node, and the parent
  708.          * should be next */
  709.         return (struct rb_node *)parent;
  710. }
  711.  
  712. struct rb_node *rb_first_postorder(const struct rb_root *root)
  713. {
  714.     if (!root->rb_node)
  715.         return NULL;
  716.  
  717.     return rb_left_deepest_node(root->rb_node);
  718. }
RAW Paste Data