summaryrefslogtreecommitdiffstats
path: root/lib/parser.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:13 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:37 +0900
commit4f035ad67f4633c233cb3642711d49b4efc9c82d (patch)
tree151fd5ff00a07da479805a01cb8b1d370db72d8f /lib/parser.c
parent46b6135a7402ac23c5b25f2bd79b03bab8f98278 (diff)
downloadop-kernel-dev-4f035ad67f4633c233cb3642711d49b4efc9c82d.zip
op-kernel-dev-4f035ad67f4633c233cb3642711d49b4efc9c82d.tar.gz
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/parser.c')
0 files changed, 0 insertions, 0 deletions
OpenPOWER on IntegriCloud