tpl_patricia_trie.H File Reference

PATRICIA/crit-bit set and map for fixed-width unsigned integer keys. More...

#include <array>
#include <cstddef>
#include <limits>
#include <memory>
#include <optional>
#include <type_traits>
#include <utility>
#include <tpl_array.H>

Include dependency graph for tpl_patricia_trie.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >
	Shared fixed-width bit-trie algorithms for Patricia containers. More...
class	Aleph::PatriciaSet< UInt >
	Compressed bitwise set for unsigned integral keys. More...
struct	Aleph::PatriciaSet< UInt >::Node
class	Aleph::PatriciaMap< UInt, T >
	Compressed bitwise map for unsigned integral keys. More...
struct	Aleph::PatriciaMap< UInt, T >::Node

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::patricia_trie_detail

Detailed Description

PATRICIA/crit-bit set and map for fixed-width unsigned integer keys.

PatriciaSet<UInt> stores unsigned integral keys in a compressed binary trie. Internal nodes keep only the first bit where keys in their two subtrees differ; leaves store the complete key. This is the fixed-width integer variant requested by the missing-data-structures plan as the first PATRICIA deliverable after RadixTree.

PatriciaMap<UInt, T> uses the same bitwise structure and attaches a mapped value to each stored key, making it the fixed-width integer-key dictionary counterpart to RadixTree.

Relationship with RadixTree

RadixTree<T, Char> compresses string edges and maps keys to values. PatriciaSet<UInt> is a set-only structure over machine integers, and PatriciaMap<UInt, T> is the analogous integer-key map. Both Patricia variants use individual bits rather than characters. They are a good fit for dense routing tables, bit prefixes, integer identifiers, and other fixed-width key workloads.

Complexity

Let w = std::numeric_limits<UInt>::digits. Exact lookup, insertion, and erasure are O(w). The depth is bounded by w, independent of the number of stored keys. Enumerating keys() is O(n), where n == size().

Ownership and invalidation

Nodes are owned by std::unique_ptr. PatriciaMap::find() returns a raw pointer into the map; it is invalidated by the next non-const operation on that map. Copying performs a deep clone; moving transfers ownership and leaves the source empty.

Thread-safety

None. This is an ordinary sequential container; concurrent callers must provide external synchronization.

Author

Leandro Rabindranath Leon

Definition in file tpl_patricia_trie.H.