Improved Red-black tree implementation

[Jens Stimpfle]

Hello,

the BSD tree.h Red-black tree implementation has a design issue in that
it doesn't share code between generated instances. Each instanciated
tree costs about 3K of machine code (on amd64). Making multiple
instances means increased pressure on the instruction cache (often 64K
these days).

In the last weeks I've designed a very efficient implementation that
shares most of the machine code between all instances. There are macros
for type safety equivalent to tree.h's, but they are only thin wrappers
around the generic code. The implementation is about 15% faster than
tree.h on my benchmark.

It is quite similar in overall design (e.g. intrusively linked, no
memory allocation). A notable difference is that color information is
stored in the low child pointer bits, which might trouble some people,
but it saves memory. It includes a shim for the tree.h API. A few
touches are still missing, but it can probably work as drop-in
replacement for most client code.

Furthermore it allows for more flexible usage, for example search
functions that receive additional context besides a search key.

The code is currently at
https://github.com/jstimpfle/sil/tree/master/rb3ptr

Could FreeBSD profit from this improved implementation? I can adapt
future development to simplify integration into the tree.

Jens Stimpfle