provide an implementation of red black trees using functions

the main goal of this change is to reduce the amount of code that
is generated as a result of using the macro implementation (RB_FOO)
of red black trees. on amd64 we should get a few dozen kilobytes
of code space back, and make red black trees more icache friendly
at the same time.

the new (RBT_FOO) implementation is modelled on the existing one,
but has some minor api variations. generally you can replace RB_
with RBT_ and get most of the way to converting code.

internally the red black tree functions all take an rb_type struct
that describes the layout of the object wired into a tree (ie, the
offset of the RBT_ENTRY inside a node), the comparison function,
and an optional augment function. because the functions are supposed
to be used for all types, they end up taking void * for the node
pointers instead of specific types. the tree is operated on as
pointers between the RBT_ENTRY structs instead of the nodes, which
gave me some type safety when implementing the code (cos casts
to/from void * dont ever fail, and continually calculating the
offset of the rb entry is annoying). RBT_ENTRYs are turned into
node pointers by prepending the offset stored in the rb_type struct
before theyre given to the comparison function or returned to the
caller.

to provide type safety on top of this, RBT_PROTOTYPE generates static
inline function wrappers that only take arguments of the right type,
and implicitly provide the rb_type struct argument to the actual
RBT functions. therefore the actual functions should never be called
directly, all calls should go through the RBT_ wrappers.

RBT_GENERATE is responsible for creating the rb_type struct used
by these wrappers. notably it also generates a wrapper around the
compare function so the user provided one must take the right types
instead of void *.

in terms of speed, this code is comparable to the macro implementation.
eg, insertion is very slightly slower in microbenchmarks, but
deletion appears to be significantly faster. this is possibly because
of the aggressive inlining ive done inside the delete codepaths.

the code is not yet wired into the kernel build.

it also needs to be said that there have been several attempts
before this to provide functions for at least some parts of the
kernels red black trees. that work made this a lot easier.

ok deraadt@ jung@ tedu@

0 files changed, 0 insertions, 0 deletions