libdict

libdict is a C library that provides the following data structures with efficient insert, lookup, and delete routines:

• height-balanced (AVL) tree
• red-black tree
• splay tree
• weight-balanced tree
• path-reduction tree
• treap
• hashtable using separate chaining
• hashtable using open addressing with linear probing
• skip list

All data structures in this library support insert, search, and remove, and have bidirectional iterators. The sorted data structures (everything but hash tables) support near-search operations: searching for the key greater or equal to, strictly greater than, lesser or equal to, or strictly less than, a given key. The tree data structures also support selecting the nth element; this takes linear time, except in path-reduction and weight-balanced trees, where it only takes logarithmic time.

The API and code are written with efficiency as a primary concern. For example, an insert call returns a boolean (dict_insert_result.inserted) that is true if the key was inserted, i.e. was not already present, and false if an existing entry was found, together with a pointer to the location of the associated data. Thus, an insert-or-update operation can be supported with a single traversal of the data structure. In addition, almost all recursive algorithms have been rewritten to use iteration instead.

Documentation is generated by Doxygen on every commit to master and is available here. Changes between releases are listed in CHANGELOG.md.

Usage notes

• Iterators support remove on every container. Iterator compare is not available on the hash tables, where dict_itor_compare() evaluates to 0.
• Iterator invalidation (full rules in dict.h, "Iterator invalidation" in the generated documentation):
  • Trees and the skip list: inserting never invalidates an iterator; removing an element invalidates iterators positioned on it. In every tree except the treap, removing a key whose node has two children also moves an in-order neighbour into that node, invalidating iterators on the neighbour.
  • Hash tables: an insert that grows the table, an explicit resize, and dict_clear() invalidate every iterator. In hashtable2 (open addressing) any removal does too. Hash table iterators detect this: dict_itor_valid() returns false and dict_itor_next() stops. Reposition them with dict_itor_first() or dict_itor_search().
• String keys: dict_str_cmp orders bytes as unsigned char, exactly as strcmp() does, so string keys sort the same on every platform. dict_str_hash gives the same hash on every platform.
• Selection: dict_select() accepts NULL for either out-parameter.
• Treap priorities: the treap is a max-heap; a dict_prio_func should return a larger value for a key that should sit closer to the root. Pass NULL for random priorities.

Installing

On every release, Debian packages are automatically built. You can download the latest packages from here.

To install, run this:

wget https://github.com/rtbrick/libdict/releases/latest/download/libdict-debian.zip
unzip libdict-debian.zip
sudo apt install -y ./*.deb

This will install the library, along with headers and tools.

Building

Both GNU Make and CMake are supported. To use the CMake build system, ensure that you have a recent version of CMake installed (version 3.10 or greater). Then, from within this repository, run:

mkdir build
cd build
cmake ..
make -j16

If you want to run unit tests, you can run:

make test

A few slow, memory-hungry tests (e.g. a 6-million-element tree) only run when LIBDICT_SLOW_TESTS=1 is set:

LIBDICT_SLOW_TESTS=1 ./libdict-tests

If you want to generate Debian packages, you can run:

cpack -G DEB

To build with the included GNU Makefile, simply run make in the repository, and make test to run the unit tests.

License

libdict is released under the simplified BSD license.