Crate poptrie 

poptrie

A pure Rust implementation of Poptrie, a data structure for efficient longest-prefix matching (LPM) lookups.

Poptrie uses bitmaps combined with the popcount instruction to achieve fast IP routing table lookups with high cache locality. During lookup, the key is consumed in the biggest step that can be represented in a bitmap for which the native popcount instruction exists (i.e. 6-bit steps in a 64-bit bitmap), similarly to how a tree-bitmap works, but with a more contiguous use of memory, trading insertion speed for cache locality.

This is particularly useful for IP forwarding tables, where the longest-prefix matching is a common operation and insertions are comparatively rare.

Reference

Asai, Hirochika, and Yasuhiro Ohara. Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup ACM SIGCOMM Computer Communication Review 45.4 (2015): 57-70.

Structs

IntoIter

An owning iterator over the entries of a Poptrie, in lexicographic order of (prefix_length, key).

Iter

A borrowing iterator over the entries of a Poptrie, in lexicographic order of (prefix_length, key).

IterMut

A mutable borrowing iterator over the entries of a Poptrie, in lexicographic order of (prefix_length, key).

Keys

An iterator over the keys of a Poptrie, in lexicographic order of (prefix_length, key).

Poptrie

A compressed prefix tree optimized for fast longest prefix match (LPM) lookups.

Values

An iterator over the values of a Poptrie, in lexicographic order of (prefix_length, key).

ValuesMut

A mutable iterator over the values of a Poptrie, in lexicographic order of (prefix_length, key).

Traits

Address

A trait for types that can be used as addresses in the Prefix.

Prefix

A prefix is a pattern to match the beginning of a sequence, in this case called an ADDRESS. The prefix is represented by an ADDRESS and a prefix_length that defines the number of bits in the prefix (counted from the most significant bits).