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.
An example illustration of a trie representing a routing table containing
172.16.0.0/12 (baz) and
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:
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.
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.