Skip to content
master
Go to file
Code

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
src
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README.md

libart Build Status

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

Usage

Building the test code will generate errors if libcheck is not available. To build the test code successfully, do the following::

$ cd deps/check-0.9.8/
$ ./configure
$ make
# make install
# ldconfig (necessary on some Linux distros)
$ cd ../../
$ scons
$ ./test_runner

Or, if you prefer, you can skip the installation of libcheck and the test will adapt to it being in the tree (leave out make install):

 $ LD_LIBRARY_PATH=deps/check-0.9.8/src/.libs:. ./test_runner

This build will produce a test_runner executable for testing and a shared_object (libart.so on *NIX systems) for linking with.

References

Related works:

About

Adaptive Radix Trees implemented in C

Resources

License

Releases

No releases published

Packages

No packages published
You can’t perform that action at this time.