description
llrb.h implements Robert Sedgewick's
2-3 variant left-leaning red-black tree, but using
iteration rather than recursion. The code relies
on C preprocessor macros and is intended to be a
drop-in replacement for Niels Provos' excellent
<sys/tree.h>.
Why use llrb.h? There's not much reason
to over <sys/tree.h>. Performance
is on par. llrb.h is implemented in
roughly 40% fewer SLoC, however. And the algorithm
is considerably simpler thanks to Sedgewick's
insights. So it may be more convenient to embed or
modify.
Why use parent pointers? Because without parent pointers iteration through the tree by user code requires callbacks or a dynamically allocated stack structure. Callbacks are ugly and confusing in languages which don't support closures; they obsfuscate the flow of logic. Allocating a separate stack would mean that the conceptually simple operation of iterating over a tree could possibly fail due to resource constraints. For those of us who bother to check the return value of malloc(3), being able to rely on a primitive data structure guaranteed to succeed (as long the logic is correct) is quite useful.
For the intrepid I can provide a Git repo I used to write, test, and benchmark the code. It implements a simple command language, taken on stdin, for insertions, deletions, invariant checks, etc, and outputs colored PDFs of the tree using Graphviz. Four versions are included: (1) a transliteration of Sedgewick's recursive Java implementation to C; (2) an iterative version of the C implementation; (3) the preprocessor variant of the iterative version; and (4) one which uses Provos' implementation for comparing performance, but without the invariant checks.
news
2013-09-25
Add LLRB_PROTOTYPE_STATIC and LLRB_GENERATE_STATIC, like OpenBSD's
<sys/tree.h>. Almost committed code to overload LLRB_GENERATE to take four or five arguments, allowing one to specify a function qualifier as the first argument of a five-argument invocation. But backed out that code because it created too much macro noise in the implementation compared to the slight usage benefit.
2012-03-15
NULL intialize child pointers on insert. Never caught before because of calloc() and memset() usage in regression and application code.
2011-11-02
Use macro type name in DELETEMIN, and make LLRB_PROTOTYPE and LLRB_GENERATE agree on storage class of INSERT.
2011-10-22
Public release.
usage
The interface is almost identical to the *BSD tree(3) API.
license
Copyright (c) 2011, 2013 William Ahern
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
download
The code resides in a single header file: llrb.h.