lkml.org 
[lkml]   [2012]   [Jul]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 2/6] rbtree: optimize fetching of sibling node
    Date
    When looking to fetch a node's sibling, we went through a sequence of:
    - check if node is the parent's left child
    - if it is, then fetch the parent's right child

    This can be replaced with:
    - fetch the parent's right child as an assumed sibling
    - check that node is NOT the fetched child

    This avoids fetching the parent's left child when node is actually
    that child. Saves a bit on code size, though it doesn't seem to make
    a large difference in speed.

    Signed-off-by: Michel Lespinasse <walken@google.com>
    ---
    lib/rbtree.c | 21 +++++++++++++--------
    1 files changed, 13 insertions(+), 8 deletions(-)

    diff --git a/lib/rbtree.c b/lib/rbtree.c
    index 3b6ec98..8b111cc 100644
    --- a/lib/rbtree.c
    +++ b/lib/rbtree.c
    @@ -108,8 +108,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)

    gparent = rb_red_parent(parent);

    - if (parent == gparent->rb_left) {
    - tmp = gparent->rb_right;
    + tmp = gparent->rb_right;
    + if (parent != tmp) { /* parent == gparent->rb_left */
    if (tmp && rb_is_red(tmp)) {
    /*
    * Case 1 - color flips
    @@ -132,7 +132,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
    continue;
    }

    - if (parent->rb_right == node) {
    + tmp = parent->rb_right;
    + if (node == tmp) {
    /*
    * Case 2 - left rotate at parent
    *
    @@ -152,6 +153,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
    RB_BLACK);
    rb_set_parent_color(parent, node, RB_RED);
    parent = node;
    + tmp = node->rb_right;
    }

    /*
    @@ -163,7 +165,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
    * / \
    * n U
    */
    - gparent->rb_left = tmp = parent->rb_right;
    + gparent->rb_left = tmp; /* == parent->rb_right */
    parent->rb_right = gparent;
    if (tmp)
    rb_set_parent_color(tmp, gparent, RB_BLACK);
    @@ -181,7 +183,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
    continue;
    }

    - if (parent->rb_left == node) {
    + tmp = parent->rb_left;
    + if (node == tmp) {
    /* Case 2 - right rotate at parent */
    parent->rb_left = tmp = node->rb_right;
    node->rb_right = parent;
    @@ -190,10 +193,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
    RB_BLACK);
    rb_set_parent_color(parent, node, RB_RED);
    parent = node;
    + tmp = node->rb_left;
    }

    /* Case 3 - left rotate at gparent */
    - gparent->rb_right = tmp = parent->rb_left;
    + gparent->rb_right = tmp; /* == parent->rb_left */
    parent->rb_left = gparent;
    if (tmp)
    rb_set_parent_color(tmp, gparent, RB_BLACK);
    @@ -224,8 +228,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
    break;
    } else if (!parent) {
    break;
    - } else if (parent->rb_left == node) {
    - sibling = parent->rb_right;
    + }
    + sibling = parent->rb_right;
    + if (node != sibling) { /* node == parent->rb_left */
    if (rb_is_red(sibling)) {
    /*
    * Case 1 - left rotate at parent
    --
    1.7.7.3


    \
     
     \ /
      Last update: 2012-07-20 16:21    [W:0.027 / U:0.228 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site