On 07/23/2012 09:54 PM, Michel Lespinasse wrote:
Add an augmented tree rotation callback to __rb_erase_color(), so that
augmented tree information can be maintained while rebalancing.
Also introduce rb_erase_augmented(), which is a version of rb_erase()
with augmented tree callbacks. We need three callbacks here: one to
copy the subtree's augmented value after stitching in a new node as
the subtree root (rb_erase_augmented cases 2 and 3), one to propagate
the augmented values up after removing a node, and one to pass up to
__rb_erase_color() to handle rebalancing.
Things are set up so that rb_erase() uses dummy do-nothing callbacks,
which get inlined and eliminated by the compiler, and also inlines the
__rb_erase_color() call so as to generate similar code than before
(once again, the compiler somehow generates smaller code than before
with all that inlining, but the speed seems to be on par). For the
augmented version rb_erase_augmented(), however, we use partial
inlining: we want rb_erase_augmented() and its augmented copy and
propagation callbacks to get inlined together, but we still call into
a generic __rb_erase_color() (passing a non-inlined callback function)
for the rebalancing work. This is intended to strike a reasonable
compromise between speed and compiled code size.
I guess moving the inlined function to the include file
takes care of my concerns for patch 4/6...
Signed-off-by: Michel Lespinasse <wal...@google.com>
Acked-by: Rik van Riel <r...@redhat.com>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
