• Michel Lespinasse's avatar
    rbtree: low level optimizations in rb_insert_color() · 5bc9188a
    Michel Lespinasse authored
    - 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: default avatarMichel Lespinasse <walken@google.com>
    Cc: Andrea Arcangeli <aarcange@redhat.com>
    Acked-by: default avatarDavid 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: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    5bc9188a
rbtree.c 13.8 KB