# Tree-Bitmap: Fast lookup table for IPv4/IPv6 prefixes
This crate provides a datastructure for fast IP address lookups.
It aims at fast lookup times, and a reasonable memory footprint.
The internal datastructure is based on the Tree-bitmap algorithm described by
W. Eatherton, Z. Dittia, G. Varghes.
## Documentation
Rustdoc: https://hroi.github.io/treebitmap/
## Illustration
An example illustration of a trie representing a routing table containing
```0.0.0.0/0``` (foo), ```10.0.0.0/8``` (bar), ```172.16.0.0/12``` (baz) and
```192.168.0.0/16``` (quux).
## Internal trie datastructure basics
```Node ``` encodes result and child node pointers in a bitmap.
A trie node can encode up to 31 results when acting as an "end node", or 15
results and 16 children/subtrees when acting as a normal/internal node.
Each bit in the bitmap indicates a bit matching pattern:
| match | * | 0* | 1* | 00* | 01* | 10* | 11* | 000* |
| match | 001* | 010* | 011* | 100* | 101* | 110* | 111* | endnode-bit |
The last bit here does not indicate a pattern. It instead indicates if this
node is an "end node". End nodes carry double the amount of results but can't
encode any child pointers.
| match | 0000* | 0001* | 0010* | 0011* | 0100* | 0101* | 0110* | 0111* |
| match | 1000* | 1001* | 1010* | 1011* | 1100* | 1101* | 1110* | 1111* |
The location of the result value is computed by adding the ```result_ptr``` base
pointer and its position among set bits.
If the endnode bit is not set, the last 16 bits encodes pointers to child
nodes.
If bit N is set it means that a child node with segment value N is present.
The pointer to the child node is then computed by adding the ```child_ptr``` base
pointer and its position among set bits.