jcmoore / c-rrb Goto Github PK

Relaxed Radix Balanced Trees (RRB-trees)

An immutable vector-like data structure with very good performance
characteristics for concatenation and slicing. Also provides transient
(mutable-like) variants which you can convert to and from in constant time.

+-----------+---------------+
| Operation |  Eff. runtime |
+-----------+---------------+
| Lookup    | O(~1)         |
| Last      | O(1)          |
| Count     | O(1)          |
| Update    | O(~1)         |
| Append    | O(~1)         |
| Pop       | O(~1)         |
| Iteration | O(n)*         |
| Concat    | O(log n)      |
| Slice     | O(~1)         |
+-----------+---------------+
* Amortised constant time – O(1) – per element.

For an explanation on how this data structure works in detail, read
http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf and then my thesis:
http://hypirion.com/thesis



This library, unmodified, depends on automake tools and Boehm GC. On
Debian-based distros, you can install the automake tools through:

  sudo apt-get install build-essential automake autoconf gnu-standards\
                       autoconf-doc libtool gettext autoconf-archive

and Boehm GC through:

  sudo apt-get install libgc-dev libgc1c2

To build and install the library, perform the following calls:

  autoreconf --install
  CFLAGS='-Ofast' ./configure
  make
  make check ## but only if you want to
  sudo make install

The `sudo make install` call should return a message which tells you where the
library has been installed (usually `/usr/local/lib`). Now, to check that the
installation went successfully, you try to compile one of the test suite
programs on its own:

  cd test-suite
  gcc -o testy printing_example.c -std=c11 -lrrb -lgc
  ./testy # should work fine, and should create the file "foo.dot"
  dot -Tpng -o foo.png foo.dot # If you have `dot` installed

If this doesn't work by default, then it might be that your linker has a cache
which needs to be updated. Try `sudo ldconfig` and rerun the compilation step.
    
If you want to uninstall the library, do `sudo make uninstall` in the project
root directory. (You have to ./configure it first though.)

Copyright © 2013-2014 Jean Niklas L'orange

Distributed under the MIT License (MIT). You can find a copy in the root of this
project with the name COPYING.