From 984f0e42665e9fa09467145976183bf88f8f3da8 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 3 Sep 2013 19:54:38 +0200 Subject: erts: Optimize rb-tree operations by "caching" parent ptr --- erts/emulator/sys/common/erl_mmap.c | 152 +++++++++++++++++++----------------- 1 file changed, 81 insertions(+), 71 deletions(-) (limited to 'erts/emulator/sys') diff --git a/erts/emulator/sys/common/erl_mmap.c b/erts/emulator/sys/common/erl_mmap.c index 2d749b2402..ede7c66fdc 100644 --- a/erts/emulator/sys/common/erl_mmap.c +++ b/erts/emulator/sys/common/erl_mmap.c @@ -419,13 +419,14 @@ replace(RBTNode **root, RBTNode *x, RBTNode *y) static void tree_insert_fixup(RBTNode** root, RBTNode *blk) { - RBTNode *x = blk, *y; + RBTNode *x = blk, *y, *papa_x, *granpa_x; /* * Rearrange the tree so that it satisfies the Red-Black Tree properties */ - RBT_ASSERT(x != *root && IS_RED(parent(x))); + papa_x = parent(x); + RBT_ASSERT(x != *root && IS_RED(papa_x)); do { /* @@ -433,35 +434,36 @@ tree_insert_fixup(RBTNode** root, RBTNode *blk) * until we get to the root or until we can separate them. */ + granpa_x = parent(papa_x); RBT_ASSERT(IS_RED(x)); - RBT_ASSERT(IS_BLACK(parent(parent(x)))); - RBT_ASSERT(parent(parent(x))); + RBT_ASSERT(IS_BLACK(granpa_x)); + RBT_ASSERT(granpa_x); - if (parent(x) == parent(parent(x))->left) { - y = parent(parent(x))->right; + if (papa_x == granpa_x->left) { + y = granpa_x->right; if (IS_RED(y)) { SET_BLACK(y); - x = parent(x); - SET_BLACK(x); - x = parent(x); - SET_RED(x); + SET_BLACK(papa_x); + SET_RED(granpa_x); + x = granpa_x; } else { - if (x == parent(x)->right) { - x = parent(x); - left_rotate(root, x); + if (x == papa_x->right) { + left_rotate(root, papa_x); + papa_x = x; + x = papa_x->left; } - RBT_ASSERT(x == parent(parent(x))->left->left); + RBT_ASSERT(x == granpa_x->left->left); RBT_ASSERT(IS_RED(x)); - RBT_ASSERT(IS_RED(parent(x))); - RBT_ASSERT(IS_BLACK(parent(parent(x)))); + RBT_ASSERT(IS_RED(papa_x)); + RBT_ASSERT(IS_BLACK(granpa_x)); RBT_ASSERT(IS_BLACK(y)); - SET_BLACK(parent(x)); - SET_RED(parent(parent(x))); - right_rotate(root, parent(parent(x))); + SET_BLACK(papa_x); + SET_RED(granpa_x); + right_rotate(root, granpa_x); RBT_ASSERT(x == parent(x)->left); RBT_ASSERT(IS_RED(x)); @@ -471,31 +473,31 @@ tree_insert_fixup(RBTNode** root, RBTNode *blk) } } else { - RBT_ASSERT(parent(x) == parent(parent(x))->right); - y = parent(parent(x))->left; + RBT_ASSERT(papa_x == granpa_x->right); + y = granpa_x->left; if (IS_RED(y)) { SET_BLACK(y); - x = parent(x); - SET_BLACK(x); - x = parent(x); - SET_RED(x); + SET_BLACK(papa_x); + SET_RED(granpa_x); + x = granpa_x; } else { - if (x == parent(x)->left) { - x = parent(x); - right_rotate(root, x); + if (x == papa_x->left) { + right_rotate(root, papa_x); + papa_x = x; + x = papa_x->right; } - RBT_ASSERT(x == parent(parent(x))->right->right); + RBT_ASSERT(x == granpa_x->right->right); RBT_ASSERT(IS_RED(x)); - RBT_ASSERT(IS_RED(parent(x))); - RBT_ASSERT(IS_BLACK(parent(parent(x)))); + RBT_ASSERT(IS_RED(papa_x)); + RBT_ASSERT(IS_BLACK(granpa_x)); RBT_ASSERT(IS_BLACK(y)); - SET_BLACK(parent(x)); - SET_RED(parent(parent(x))); - left_rotate(root, parent(parent(x))); + SET_BLACK(papa_x); + SET_RED(granpa_x); + left_rotate(root, granpa_x); RBT_ASSERT(x == parent(x)->right); RBT_ASSERT(IS_RED(x)); @@ -504,7 +506,7 @@ tree_insert_fixup(RBTNode** root, RBTNode *blk) break; } } - } while (x != *root && IS_RED(parent(x))); + } while (x != *root && (papa_x=parent(x), IS_RED(papa_x))); SET_BLACK(*root); } @@ -513,7 +515,7 @@ static void rbt_delete(RBTNode** root, RBTNode* del) { Uint spliced_is_black; - RBTNode *x, *y, *z = del; + RBTNode *x, *y, *z = del, *papa_y; RBTNode null_x; /* null_x is used to get the fixup started when we splice out a node without children. */ @@ -532,8 +534,9 @@ rbt_delete(RBTNode** root, RBTNode* del) /* splice out y */ x = y->left ? y->left : y->right; spliced_is_black = IS_BLACK(y); + papa_y = parent(y); if (x) { - set_parent(x, parent(y)); + set_parent(x, papa_y); } else if (spliced_is_black) { x = &null_x; @@ -541,21 +544,21 @@ rbt_delete(RBTNode** root, RBTNode* del) SET_BLACK(x);*/ x->right = x->left = NULL; /*SVERK x->max_sz = 0;*/ - x->parent_and_color = parent_and_color(parent(y), !RED_FLG); + x->parent_and_color = parent_and_color(papa_y, !RED_FLG); y->left = x; } - if (!parent(y)) { + if (!papa_y) { RBT_ASSERT(*root == y); *root = x; } else { - if (y == parent(y)->left) { - parent(y)->left = x; + if (y == papa_y->left) { + papa_y->left = x; } else { - RBT_ASSERT(y == parent(y)->right); - parent(y)->right = x; + RBT_ASSERT(y == papa_y->right); + papa_y->right = x; } /*SVERK if (y->parent != z) { lower_max_size(y->parent, (y==z ? NULL : z)); @@ -569,10 +572,12 @@ rbt_delete(RBTNode** root, RBTNode* del) } if (spliced_is_black) { + RBTNode* papa_x; /* We removed a black node which makes the resulting tree violate the Red-Black Tree properties. Fixup tree... */ - while (IS_BLACK(x) && parent(x)) { + papa_x = parent(x); + while (IS_BLACK(x) && papa_x) { /* * x has an "extra black" which we move up the tree @@ -581,91 +586,96 @@ rbt_delete(RBTNode** root, RBTNode* del) * y is the sibbling of x */ - if (x == parent(x)->left) { - y = parent(x)->right; + if (x == papa_x->left) { + y = papa_x->right; RBT_ASSERT(y); if (IS_RED(y)) { RBT_ASSERT(y->right); RBT_ASSERT(y->left); SET_BLACK(y); - RBT_ASSERT(IS_BLACK(parent(x))); - SET_RED(parent(x)); - left_rotate(root, parent(x)); - y = parent(x)->right; + RBT_ASSERT(IS_BLACK(papa_x)); + SET_RED(papa_x); + left_rotate(root, papa_x); + RBT_ASSERT(papa_x == parent(x)); + y = papa_x->right; } RBT_ASSERT(y); RBT_ASSERT(IS_BLACK(y)); if (IS_BLACK(y->left) && IS_BLACK(y->right)) { SET_RED(y); - x = parent(x); } else { if (IS_BLACK(y->right)) { SET_BLACK(y->left); SET_RED(y); right_rotate(root, y); - y = parent(x)->right; + RBT_ASSERT(papa_x == parent(x)); + y = papa_x->right; } RBT_ASSERT(y); - if (IS_RED(parent(x))) { + if (IS_RED(papa_x)) { - SET_BLACK(parent(x)); + SET_BLACK(papa_x); SET_RED(y); } RBT_ASSERT(y->right); SET_BLACK(y->right); - left_rotate(root, parent(x)); + left_rotate(root, papa_x); x = *root; break; } } else { - RBT_ASSERT(x == parent(x)->right); - y = parent(x)->left; + RBT_ASSERT(x == papa_x->right); + y = papa_x->left; RBT_ASSERT(y); if (IS_RED(y)) { RBT_ASSERT(y->right); RBT_ASSERT(y->left); SET_BLACK(y); - RBT_ASSERT(IS_BLACK(parent(x))); - SET_RED(parent(x)); - right_rotate(root, parent(x)); - y = parent(x)->left; + RBT_ASSERT(IS_BLACK(papa_x)); + SET_RED(papa_x); + right_rotate(root, papa_x); + RBT_ASSERT(papa_x == parent(x)); + y = papa_x->left; } RBT_ASSERT(y); RBT_ASSERT(IS_BLACK(y)); if (IS_BLACK(y->right) && IS_BLACK(y->left)) { SET_RED(y); - x = parent(x); } else { if (IS_BLACK(y->left)) { SET_BLACK(y->right); SET_RED(y); left_rotate(root, y); - y = parent(x)->left; + RBT_ASSERT(papa_x == parent(x)); + y = papa_x->left; } RBT_ASSERT(y); - if (IS_RED(parent(x))) { - SET_BLACK(parent(x)); + if (IS_RED(papa_x)) { + SET_BLACK(papa_x); SET_RED(y); } RBT_ASSERT(y->left); SET_BLACK(y->left); - right_rotate(root, parent(x)); + right_rotate(root, papa_x); x = *root; break; } } + x = papa_x; + papa_x = parent(x); } SET_BLACK(x); - if (parent(&null_x)) { - if (parent(&null_x)->left == &null_x) - parent(&null_x)->left = NULL; + papa_x = parent(&null_x); + if (papa_x) { + if (papa_x->left == &null_x) + papa_x->left = NULL; else { - RBT_ASSERT(parent(&null_x)->right == &null_x); - parent(&null_x)->right = NULL; + RBT_ASSERT(papa_x->right == &null_x); + papa_x->right = NULL; } RBT_ASSERT(!null_x.left); RBT_ASSERT(!null_x.right); -- cgit v1.2.3