diff options
author | Michel Lespinasse <walken@google.com> | 2012-10-08 16:31:13 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2012-10-09 16:22:37 +0900 |
commit | 4f035ad67f4633c233cb3642711d49b4efc9c82d (patch) | |
tree | 151fd5ff00a07da479805a01cb8b1d370db72d8f /lib/mpi | |
parent | 46b6135a7402ac23c5b25f2bd79b03bab8f98278 (diff) | |
download | linux-4f035ad67f4633c233cb3642711d49b4efc9c82d.tar.bz2 |
rbtree: low level optimizations in rb_erase()
Various minor optimizations in rb_erase():
- Avoid multiple loading of node->__rb_parent_color when computing parent
and color information (possibly not in close sequence, as there might
be further branches in the algorithm)
- In the 1-child subcase of case 1, copy the __rb_parent_color field from
the erased node to the child instead of recomputing it from the desired
parent and color
- When searching for the erased node's successor, differentiate between
cases 2 and 3 based on whether any left links were followed. This avoids
a condition later down.
- In case 3, keep a pointer to the erased node's right child so we don't
have to refetch it later to adjust its parent.
- In the no-childs subcase of cases 2 and 3, place the rebalance assigment
last so that the compiler can remove the following if(rebalance) test.
Also, added some comments to illustrate cases 2 and 3.
Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/mpi')
0 files changed, 0 insertions, 0 deletions