rbtree: optimize fetching of sibling node
authorMichel Lespinasse <[email protected]>
Mon, 8 Oct 2012 23:31:02 +0000 (16:31 -0700)
committerLinus Torvalds <[email protected]>
Tue, 9 Oct 2012 07:22:35 +0000 (16:22 +0900)
commit59633abf34e2f44b8e772a2c12a92132aa7c2220
tree3a260a6100ae2c3e2dbade989c3692234081f1c7
parent7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0
rbtree: optimize fetching of sibling node

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 <[email protected]>
Cc: Andrea Arcangeli <[email protected]>
Cc: David Woodhouse <[email protected]>
Acked-by: Rik van Riel <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Daniel Santos <[email protected]>
Cc: Jens Axboe <[email protected]>
Cc: "Eric W. Biederman" <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
Signed-off-by: Linus Torvalds <[email protected]>
lib/rbtree.c