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://docs.rs/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:

| bit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-------|---|----|----|-----|-----|-----|-----|------| | match | * | 0* | 1* | 00* | 01* | 10* | 11* | 000* |

| bit | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |-------|------|------|------|------|------|------|------|-------------| | 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.

| bit | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | |-------|-------|-------|-------|-------|-------|-------|-------|-------| | match | 0000* | 0001* | 0010* | 0011* | 0100* | 0101* | 0110* | 0111* |

| bit | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | |-------|-------|-------|-------|-------|-------|-------|-------|-------| | 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.