Rabbit Tree: radix bit tries for implementing maps and sets in C

Xyne · 2012-09-04 04:45:39

Project Page and Documentation

Introduction

Rabbit Tree is an implementation of radix trees in C with bit keys instead of character keys. The library is implemented with a set of very flexible macros that can be used to create maps (a.k.a. dictionaries or association lists) of any data type to any other that can be represented as a contiguous sequence of bytes.

For example, you can map strings to strings, ints to ints, strings to structs, structs to unions, strings to file handles, etc.

The code supports both fixed length and variable key and value sizes. Worst-case lookup times are limited by key length, not the number of items in the map.

It can also be used to create sets, which are internally implemented as maps to boolean values.

Functions are provided for insertions, deletions, updates, replacements and all of the other expected actions. Functions are also provide for visualizing the tree structure (see the project page and the documentation for examples).

Last edited by Xyne (2013-09-01 22:17:16)

Xyne · 2013-09-01 22:19:45

I have added a walkthrough to the project page for creating a map of strings to strings. Please let me know if anything is unclear.

Arch Linux

#1 2012-09-04 04:45:39