Shared fixed-width bit-trie algorithms for Patricia containers. More...

#include <tpl_patricia_trie.H>

Collaboration diagram for Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >:

Static Public Member Functions
static bool	bit_at (const UInt key, const size_t bit_index) noexcept
	Return the bit at a most-significant-bit-first index.

static size_t	first_differing_bit (const UInt lhs, const UInt rhs) noexcept
	Find the first bit where two keys differ.

template<typename Node >
static const Node *	leaf_for (const Node *node, const UInt key) noexcept
	Find the leaf reached by routing a key through a Patricia tree.

template<typename Node >
static Node *	leaf_for (Node *node, const UInt key) noexcept
	Mutable overload of leaf_for().

template<typename Node >
static void	collect_keys (const Node *node, Array< UInt > &out)
	Append all leaf keys in a Patricia subtree.

template<typename Node >
static bool	erase_key (std::unique_ptr< Node > &root, size_t &size, const UInt key) noexcept
	Remove a key using the shared Patricia deletion algorithm.

template<typename Node >
static bool	subtree_matches (const Node *node, const size_t bit_index, const bool expected) noexcept
	Check that every leaf in a subtree matches a routing bit.

template<typename Node >
static bool	check_invariants_rec (const Node *node, const size_t parent_bit, const bool has_parent, size_t &counted) noexcept
	Recursively verify Patricia structural invariants.

Static Public Attributes
static constexpr size_t	bit_width = std::numeric_limits<UInt>::digits
	Number of significant bits in `UInt`.

Detailed Description

template<typename UInt>
struct Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >

Shared fixed-width bit-trie algorithms for Patricia containers.

The node type is supplied by PatriciaSet or PatriciaMap; both node shapes expose leaf, key, bit_index, and child. Map nodes also expose an optional value, which check_invariants_rec() validates when present.

Template Parameters

UInt	Unsigned integral key type used by the owning Patricia type.

Definition at line 99 of file tpl_patricia_trie.H.

Member Function Documentation

◆ bit_at()

template<typename UInt >

static bool Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at	(	const UInt	key,
		const size_t	bit_index
	)

inlinestaticnoexcept

Return the bit at a most-significant-bit-first index.

Parameters

[in]	key	Key whose bit is queried.
[in]	bit_index	Zero-based bit index from the most significant bit.

Returns: true when the indexed bit is one.

Precondition: bit_index < bit_width.

Exceptions

Nothing.

Definition at line 113 of file tpl_patricia_trie.H.

References Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_width, and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::erase_key(), Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::first_differing_bit(), Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::leaf_for(), and Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::subtree_matches().

◆ check_invariants_rec()

template<typename UInt >

template<typename Node >

static bool Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::check_invariants_rec	(	const Node *	node,
		const size_t	parent_bit,
		const bool	has_parent,
		size_t &	counted
	)

inlinestaticnoexcept

Recursively verify Patricia structural invariants.

Template Parameters

Node	Patricia node type.

Parameters

[in]	node	Subtree root.
[in]	parent_bit	Parent internal-node bit index.
[in]	has_parent	Whether `parent_bit` is meaningful.
[in,out]	counted	Number of leaves seen so far.

Returns: true if the subtree is structurally valid.

Exceptions

Nothing.

Definition at line 272 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_width, Aleph::blossom_maximum_cardinality_matching(), Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::check_invariants_rec(), and Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::subtree_matches().

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::check_invariants_rec().

◆ collect_keys()

template<typename UInt >

template<typename Node >

static void Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::collect_keys	(	const Node *	node,
		Array< UInt > &	out
	)

inlinestatic

Append all leaf keys in a Patricia subtree.

Template Parameters

Node	Patricia node type.

Parameters

[in]	node	Subtree root, possibly `nullptr`.
[out]	out	Destination array.

Exceptions

std::bad_alloc if appending grows out and allocation fails.

Definition at line 179 of file tpl_patricia_trie.H.

References Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::collect_keys(), and out.

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::collect_keys().

◆ erase_key()

template<typename UInt >

template<typename Node >

static bool Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::erase_key	(	std::unique_ptr< Node > &	root,
		size_t &	size,
		const UInt	key
	)

inlinestaticnoexcept

Remove a key using the shared Patricia deletion algorithm.

Template Parameters

Node	Patricia node type.

Parameters

[in,out]	root	Owning root pointer.
[in,out]	size	Stored-key count.
[in]	key	Key to erase.

Returns: true if a leaf was removed, false if the key was absent.

Exceptions

Nothing.

Definition at line 203 of file tpl_patricia_trie.H.

References Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at(), Aleph::blossom_maximum_cardinality_matching(), root(), and Aleph::size().

◆ first_differing_bit()

template<typename UInt >

static size_t Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::first_differing_bit	(	const UInt	lhs,
		const UInt	rhs
	)

inlinestaticnoexcept

Find the first bit where two keys differ.

Parameters

[in]	lhs	First key.
[in]	rhs	Second key.

Returns: First differing bit index, or bit_width if keys are equal.

Exceptions

Nothing.

Definition at line 127 of file tpl_patricia_trie.H.

References Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at(), Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_width, Aleph::blossom_maximum_cardinality_matching(), and Aleph::diff().

◆ leaf_for() [1/2]

template<typename UInt >

template<typename Node >

static const Node * Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::leaf_for	(	const Node *	node,
		const UInt	key
	)

inlinestaticnoexcept

Find the leaf reached by routing a key through a Patricia tree.

Template Parameters

Node	Patricia node type.

Parameters

[in]	node	Root node to start from.
[in]	key	Key used for branch decisions.

Returns: Reached leaf, or nullptr for an empty tree.

Exceptions

Nothing.

Definition at line 147 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at(), and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::leaf_for().

◆ leaf_for() [2/2]

template<typename UInt >

template<typename Node >

static Node * Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::leaf_for	(	Node *	node,
		const UInt	key
	)

inlinestaticnoexcept

Mutable overload of leaf_for().

Template Parameters

Node	Patricia node type.

Parameters

[in,out]	node	Root node to start from.
[in]	key	Key used for branch decisions.

Returns: Reached mutable leaf, or nullptr for an empty tree.

Exceptions

Nothing.

Definition at line 165 of file tpl_patricia_trie.H.

References Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::leaf_for().

◆ subtree_matches()

template<typename UInt >

template<typename Node >

static bool Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::subtree_matches	(	const Node *	node,
		const size_t	bit_index,
		const bool	expected
	)

inlinestaticnoexcept

Check that every leaf in a subtree matches a routing bit.

Template Parameters

Node	Patricia node type.

Parameters

[in]	node	Subtree root.
[in]	bit_index	Routing bit to verify.
[in]	expected	Required bit value.

Returns: true if all leaves match the expected branch bit.

Exceptions

Nothing.

Definition at line 248 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at(), and Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::subtree_matches().

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::check_invariants_rec(), and Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::subtree_matches().

Member Data Documentation

◆ bit_width

template<typename UInt >

constexpr size_t Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_width = std::numeric_limits<UInt>::digits

staticconstexpr

Number of significant bits in UInt.

Definition at line 102 of file tpl_patricia_trie.H.

Referenced by Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::bit_at(), Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::check_invariants_rec(), and Aleph::patricia_trie_detail::Bitwise_Trie_Utils< UInt >::first_differing_bit().

The documentation for this struct was generated from the following file:

tpl_patricia_trie.H

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Function Documentation

◆ bit_at()

◆ check_invariants_rec()

◆ collect_keys()

◆ erase_key()

◆ first_differing_bit()

◆ leaf_for() [1/2]

◆ leaf_for() [2/2]

◆ subtree_matches()

Member Data Documentation

◆ bit_width