armon's libart is a "complete" project as far as it doesn't receive any new updates or feature additions.
I've taken libart and tried to modernize the coding style and interfaces to better fit my own projects. Also I've improved the space efficiency of certain data layouts inside the internal data structures somewhat.
This library provides a C99 implementation of the Adaptive Radix Tree or ART. The ART operates similar to a traditional radix tree but avoids the wasted space of internal nodes by changing the node size. It makes use of 4 node sizes (4, 16, 48, 256), and can guarantee that the overhead is no more than 52 bytes per key, though in practice it is much lower.
As a radix tree, it provides the following:
- O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
- Minimum / Maximum value lookups
- Prefix compression
- Ordered iteration
- Prefix based iteration
Build using CMake:
$ mkdir build && cd build
$ cmake -DLIBART_BUILD_TESTS=ON -DLIBART_BUILD_BENCH=ON ..
$ make
Run tests with CTest:
$ ctest --output-on-failure
Or run the test runner directly:
$ ./art_test_runner
Run benchmarks:
$ ./art_bench
The test suite includes 59 tests covering:
- Basic operations (insert, search, delete, replace)
- Key edge cases (binary, null bytes, very long keys)
- Node transitions (NODE4 -> NODE16 -> NODE48 -> NODE256)
- Node shrinking on delete
- Prefix handling (common prefixes, prefix as key)
- Iteration (full, prefix-based, early stop)
- Increment/Decrement counters
- Memory tracking
- Stress tests (100k sequential, 50k random ops)
- Fuzzing tests (random keys, binary patterns)
- File-based tests (235k words, 100k UUIDs)
Related works: