librtree

Implementation of the R-tree algorithm by A. Guttman, updated by Melinda Green. Retrieved from (1), July 2019. This rather old code (Green reports updating it to ANSI C) has been rewritten in C11 with an extensive test-suite to make a small, reasonably portable self-contained library. For use in smaller projects.

For documentation and stable releases, see the project homepage.

See (2), (3) for a similar developments in C++.

Features

The same underlying algorithms are implemented, and we have some features which seem desirable for a modern library:

• Re-entrant, no global variables at all
• Dimension set at run-time rather than compile-time
• Extensive test-suite (with CUnit), used for CI (4)
• Serialisation to/from custom binary format or JSON
• Output to PostScript in the dimension-two case
• Builds a 100,000 rectangle tree in around a third of a second

Status

This code is beta and the features planned for version 1.0 have been implemented.

Building

Quite standard:

./configure
make
sudo make install

If you do not have the Jansson library (or do not want JSON support) add the --disable-json option to the configure. Similarly, if you do not have libcsv (or do not want CSV support) pass the --disable-csv option.

To run the test-suite (which requires the CUnit library)

./configure --enable-unit-tests
make
make test

See ./configure --help for additional features.

OS-specific dependencies

Debian and derivatives (Ubuntu, Mint, ...)

• build: libjansson-dev, libcsv-dev
• test: libcunit1-dev, valgrind, ghostscript
• develop: clang-tools, cppcheck, gengetopt, xsltproc, jq, cloc

Licence

The licence of the original files, according to (1), is that

You're completely free to use them for any purpose whatsoever. All I ask is that if you find one to be particularly valuable, then consider sending feedback.

Given this, I have released the rewrite under the MIT licence (see the file LICENCE).