summaryrefslogtreecommitdiffstats
path: root/scripts
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:30:47 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:34 +0900
commit5bc9188aa207dafd47eab57df7c4fe5b3d3f636a (patch)
tree09bce40b0253f38250dd180315d7b3fa22999988 /scripts
parent6d58452dc066db61acdff7b84671db1b11a3de1c (diff)
downloadlinux-5bc9188aa207dafd47eab57df7c4fe5b3d3f636a.tar.bz2
rbtree: low level optimizations in rb_insert_color()
- Use the newly introduced rb_set_parent_color() function to flip the color of nodes whose parent is already known. - Optimize rb_parent() when the node is known to be red - there is no need to mask out the color in that case. - Flipping gparent's color to red requires us to fetch its rb_parent_color field, so we can reuse it as the parent value for the next loop iteration. - Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree rotations: we already have pointers to all relevant nodes, and know their colors (either because we want to adjust it, or because we've tested it, or we can deduce it as black due to the node proximity to a known red node). So we can generate more efficient code by making use of the node pointers we already have, and setting both the parent and color attributes for nodes all at once. Also in Case 2, some node attributes don't have to be set because we know another tree rotation (Case 3) will always follow and override them. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Acked-by: David Woodhouse <David.Woodhouse@intel.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Daniel Santos <daniel.santos@pobox.com> Cc: Jens Axboe <axboe@kernel.dk> Cc: "Eric W. Biederman" <ebiederm@xmission.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'scripts')
0 files changed, 0 insertions, 0 deletions