API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 26th, 2016
387
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 23.52 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!