Improved Red-black tree implementation

[Jens Stimpfle]

On Mon, May 15, 2017 at 10:34:10AM -0600, Alan Somers wrote:
> Nice work, Jens.  This certainly sounds like an improvement.  A few questions:
> 1) Are there any automated tests?  I would definitely want robust
> coverage for something this complicated.

So far there is only the benchmark code, one directory level up. If
there's use for it that would be motivation for me to work on packaging,
also including automated tests and documentation.

> 2) FreeBSD can't rely on any Python code during the build.  Does
> gen-macros.py need to be run on every build?  Or is it more like
> autoreconf, something that gets run when a developer modifies the RB
> code, and then checks in its output?

More like autoreconf. The output of gen-macros.py is something like
tree.h.

> 3) Do you know of any examples of programs that use multiple instances
> of RB trees?

Tmux has 14 instances.

I have no idea if the saved code matters in any practical application.
It could be rare that more than two instances or so are active at the
same time *and* the size of the client code is not dominating. But if
anything, code sharing is "the right thing".

Digression: I figure most algorithmic implementations could be generic.
Even if many data structures need a "stride" parameter. Are there case
where it's clearly better to duplicate code for some data structure
whose instances are only differing by integer parameters?

For functions parameters, there is the famous example of std::sort being
faster than qsort, but that must be about the most extreme one: On flat
arrays function call overhead dominates cache miss overhead to the point
where it sometimes makes sense to inline the function call.

Jens