rb_tree: pass parent to RB_INSERT_COLOR

[dougm]

Summary

Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it.

Test Plan

This change makes iommu_gas.o 32 bytes larger.

I tested this with a binary that repeatedly inserts 64k items into a tree, nulls the root and repeats. The allocation and initialization and randomization happens untimed, and only the inserts are timed. On lip3 there appears to be a small benefit:

x old.res
+ new.res
+------------------------------------------------------------------------------+
|                       +                                                      |
|                       +      +*           x                                  |
|                 +    ++     *+*     x     x      xxx       x                x|
|+    ++  +   ++  ++ + +++   ****+ xx x     x+ +xx***x  x   xx  x     x    x  x|
|             |__________M_A______|_____|________A_____________|               |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     29.542046     30.475461      29.93764     29.922804    0.27414741
+  32     29.022955     29.984536     29.471963     29.508554    0.24104074
Difference at 95.0% confidence
        -0.41425 +/- 0.128998
        -1.38439% +/- 0.431103%
        (Student's t, pooled s = 0.258125)

[dougm]

Apply changes to rebalancing functions, fix linux problems.

[• hselasky]

sys/sys/tree.h

359

Are you sure RB_RED_LEFT is expanded properly in RB_COLOR using different C-code pre-processors?

[dougm]

Stop defining RB_RED. Modify the DIAGNOSTIC code in subr_stats.c to compute 'red' on its own.

Reduce code duplication by combining the left-leaning an right-leaning RB_COLOR codes into one.

[dougm]

sys/sys/tree.h

359

I have solved the problem, if any, by rewriting code elsewhere.

[dougm]

Since the last revision, almost everything this change would have done has been checked in separately. Only this little piece remains. I haven't determined that it merits further consideration.

[• hselasky]

Refactoring looks OK to me, to check parent != NULL once instead of twice.