fe::Patricia< D, KT, K, N > Class Template Reference

Hash-consed, immutable sets of D*, ordered by an unsigned id the elements carry themselves. More...

#include <fe/patricia.h>

Classes
class	Set
	An immutable set - really just a tagged pointer, so copy it around freely. More...

Public Member Functions
Construction
Patricia &	operator= (const Patricia &)=delete
	Patricia (size_t page_size=Arena::Default_Page_Size)
	Patricia (const Patricia &)=delete
	Patricia (Patricia &&other)
Set Operations
Note These operations do not modify their input; they yield a new Set.
template<std::ranges::input_range R> requires std::convertible_to<std::ranges::range_reference_t<R>, D*>
Set	create (R &&r)
	Creates a Set with all elements in r.
Set	create (std::initializer_list< D * > list)
Set	insert (Set s, D *d)
	Yields \(s \cup \{d\}\).
Set	erase (Set s, D *d)
	Yields \(s \setminus \{d\}\).
Set	merge (Set s1, Set s2)
	Yields \(s_1 \cup s_2\).
Set	intersect (Set s1, Set s2)
	Yields \(s_1 \cap s_2\).
Set	diff (Set s1, Set s2)
	Yields \(s_1 \setminus s_2\).

Friends
void	swap (Patricia &p1, Patricia &p2) noexcept

Detailed Description

template<class D, class KT, class K = uint32_t, size_t N = 8>
class fe::Patricia< D, KT, K, N >

Hash-consed, immutable sets of D*, ordered by an unsigned id the elements carry themselves.

A Patricia tree - a prefix trie over the big-endian bits of the id, as in Okasaki and Gill's Fast Mergeable Integer Maps

• in the four flavours below, picked by size alone; equal sets are therefore pointer-equal.

Flavour	Holds
empty	nothing; a Set that converts to false
Uniq	exactly one D* - inline in the Set itself, so a singleton costs no node at all
Arr	2 to N elements, sorted by id
Br	more than N elements: a prefix, its branching bit, and two non-empty children

The flavour is picked for every subtree, so a branch's children are again single elements, arrays, or branches - which collapses the bottom \(\log_2 N\) levels of the trie into one array each. Patricia shape is canonical (the branching bit of an id set is just the highest bit its minimum and maximum disagree on), so this keeps one element set mapped to exactly one representation.

Ids are ordered as unsigned, i.e. iteration yields 0 first and K(-1) last. KT is a key trait:

struct Key {
    static K key(const D*) noexcept;                       ///< Unique id; orders the elements.
    static std::ostream& stream(std::ostream&, const D*);  ///< Optional; defaults to Key::key.
};

Attention

Key::key is the identity: two elements sharing an id are the same element to a Set, and which of them survives an operation is unspecified. Every D must be at least 4-byte aligned, since a Set tags the two low bits of its word.

Note

All operations yield a new Set; none of them modify their input. Nothing is ever freed - the Arenas release everything at once when the Patricia dies.

Definition at line 64 of file patricia.h.

Constructor & Destructor Documentation

Patricia() [1/3]

template<class D, class KT, class K = uint32_t, size_t N = 8>

fe::Patricia< D, KT, K, N >::Patricia ( size_t page_size = Arena::Default_Page_Size )

inlineexplicit

Definition at line 465 of file patricia.h.

References fe::Arena::Default_Page_Size.

Referenced by operator=(), Patricia(), Patricia(), and swap.

Patricia() [2/3]

template<class D, class KT, class K = uint32_t, size_t N = 8>

fe::Patricia< D, KT, K, N >::Patricia ( const Patricia< D, KT, K, N > & )

delete

References Patricia().

Patricia() [3/3]

template<class D, class KT, class K = uint32_t, size_t N = 8>

fe::Patricia< D, KT, K, N >::Patricia ( Patricia< D, KT, K, N > && other )

inline

Definition at line 469 of file patricia.h.

References Patricia(), and swap.

Member Function Documentation

create() [1/2]

template<class D, class KT, class K = uint32_t, size_t N = 8>

template<std::ranges::input_range R>
requires std::convertible_to<std::ranges::range_reference_t<R>, D*>

Set fe::Patricia< D, KT, K, N >::create ( R && r )

inlinenodiscard

Creates a Set with all elements in r.

Definition at line 481 of file patricia.h.

References fe::Vector< T, N, A >::Vector().

create() [2/2]

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::create ( std::initializer_list< D * > list )

inlinenodiscard

Definition at line 488 of file patricia.h.

References create().

Referenced by create().

diff()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::diff ( Set s1, Set s2 )

inlinenodiscard

Yields \(s_1 \setminus s_2\).

Definition at line 608 of file patricia.h.

References diff(), fe::Patricia< D, KT, K, N >::Set::empty(), and fe::unreachable().

Referenced by diff().

erase()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::erase ( Set s, D * d )

inlinenodiscard

Yields \(s \setminus \{d\}\).

Definition at line 533 of file patricia.h.

References erase(), and fe::Patricia< D, KT, K, N >::Set::Set().

Referenced by erase().

insert()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::insert ( Set s, D * d )

inlinenodiscard

Yields \(s \cup \{d\}\).

Note

s comes back unchanged if it already holds an element with d's id.

Definition at line 492 of file patricia.h.

References fe::Patricia< D, KT, K, N >::Set::empty(), insert(), and fe::Patricia< D, KT, K, N >::Set::Set().

Referenced by insert().

intersect()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::intersect ( Set s1, Set s2 )

inlinenodiscard

Yields \(s_1 \cap s_2\).

Definition at line 585 of file patricia.h.

References fe::Patricia< D, KT, K, N >::Set::empty(), intersect(), and fe::unreachable().

Referenced by intersect().

merge()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Set fe::Patricia< D, KT, K, N >::merge ( Set s1, Set s2 )

inlinenodiscard

Yields \(s_1 \cup s_2\).

Definition at line 562 of file patricia.h.

References fe::Patricia< D, KT, K, N >::Set::empty(), merge(), and fe::unreachable().

Referenced by merge().

operator=()

template<class D, class KT, class K = uint32_t, size_t N = 8>

Patricia & fe::Patricia< D, KT, K, N >::operator= ( const Patricia< D, KT, K, N > & )

delete

References Patricia().

Friends And Related Symbol Documentation

swap

template<class D, class KT, class K = uint32_t, size_t N = 8>

void swap ( Patricia< D, KT, K, N > & p1, Patricia< D, KT, K, N > & p2 )

friend

Definition at line 630 of file patricia.h.

References Patricia(), and swap.

Referenced by Patricia(), and swap.

---

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

• fe/patricia.h