Immutable unordered map backed by a Hash Array Mapped Trie (HAMT). More...

#include <tpl_persistent_hash_map.H>

Collaboration diagram for Aleph::PersistentHashMap< Key, T, Cmp >:

Classes
struct	BitmapNode

struct	CollisionNode

struct	LeafNode

struct	Node
	Polymorphic base node managed by std::shared_ptr for structural sharing. More...

Public Types
using	Hash_Fct_Ptr = size_t(*)(const Key &)
	Hash function pointer type used by this map.

Public Member Functions
	PersistentHashMap (const Hash_Fct_Ptr hash_fct=dft_hash_ptr_fct< Key >, const Cmp &cmp=Cmp())
	Construct an empty persistent hash map.

size_t	size () const noexcept
	Return the number of bindings stored in this version.

bool	is_empty () const noexcept
	Return true when this version has no bindings.

PersistentHashMap	insert (const Key &key, const T &value) const
	Return a new version with `key` inserted if absent.

PersistentHashMap	insert (const Key &key, T &&value) const
	Return a new version with `key` inserted if absent, moving `value`.

PersistentHashMap	insert_or_assign (const Key &key, const T &value) const
	Return a new version with `key` bound to `value`.

PersistentHashMap	insert_or_assign (const Key &key, T &&value) const
	Return a new version with `key` bound to moved `value`.

PersistentHashMap	erase (const Key &key) const
	Return a new version without `key`.

bool	contains (const Key &key) const
	Test whether `key` is present.

const T *	find (const Key &key) const
	Find a mapped value.

Array< Key >	keys () const
	Return all keys in unspecified order.

Array< std::pair< Key, T > >	items () const
	Return all key/value bindings in unspecified order.

bool	verify () const
	Verify HAMT routing, collision, uniqueness and size invariants.

Private Types
enum class	NodeType { LEAF , BITMAP , COLLISION }
	Types of polymorphic nodes in the HAMT. More...

using	NodePtr = std::shared_ptr< const Node >

Private Member Functions
	PersistentHashMap (NodePtr root, const Hash_Fct_Ptr hash_fct, Cmp cmp, const size_t size)

NodePtr	merge_leaves (const NodePtr &n1, const NodePtr &n2, const size_t shift) const

NodePtr	insert_impl (const NodePtr &node, const Key &key, const T value, T movable_value, const size_t hash, const size_t shift, const bool replace, bool &added, bool &changed) const

NodePtr	erase_impl (const NodePtr &node, const Key &key, const size_t hash, const size_t shift, bool &removed) const

const T *	find_impl (const NodePtr &node, const Key &key, const size_t hash, const size_t shift) const

bool	hashes_match_slot (const NodePtr &node, const size_t shift, const size_t pos) const

bool	collision_keys_are_unique (const CollisionNode &node) const

bool	verify_rec (const NodePtr &node, const size_t shift, size_t &count) const

size_t	size_after_insert (const bool added) const

Static Private Member Functions
static size_t	bitpos (const size_t hash, const size_t shift) noexcept

static std::uint32_t	bit (const size_t pos) noexcept

static size_t	index (const std::uint32_t bitmap, const std::uint32_t bit_value) noexcept

static NodePtr	make_leaf (const Key &key, const T &value, const size_t hash)

static NodePtr	make_leaf (const Key &key, T &&value, const size_t hash)

static NodePtr	make_leaf_from_value (const Key &key, const T value, T movable_value, const size_t hash)

static void	append_entry (Array< std::pair< Key, T > > &entries, const Key &key, const T value, T movable_value)

static void	collect_keys (const NodePtr &node, Array< Key > &out)

static void	collect_items (const NodePtr &node, Array< std::pair< Key, T > > &out)

Private Attributes
NodePtr	root_

Hash_Fct_Ptr	hash_fct_

Cmp	cmp_

size_t	size_ = 0

Static Private Attributes
static constexpr size_t	BITS_PER_LEVEL = 5

static constexpr size_t	BRANCHING_FACTOR = 1ULL << BITS_PER_LEVEL

static constexpr size_t	LEVEL_MASK = BRANCHING_FACTOR - 1

Detailed Description

template<typename Key, typename T, class Cmp = Aleph::equal_to<Key>>
class Aleph::PersistentHashMap< Key, T, Cmp >

Immutable unordered map backed by a Hash Array Mapped Trie (HAMT).

What is a Persistent HAMT?

A HAMT (Hash Array Mapped Trie) is a search trie where keys are not used directly for the search path; instead, they are routed using fragments of their hash value. At each level of the tree, 5 bits of the hash are consumed (allowing 32 possible branches per level).

"Persistence" in this context means immutability with history (structural sharing / path-copying), not disk storage. When an element is inserted or erased, the original container does not mutate; instead, a new map containing the modification is returned. Nodes that were not affected by the operation are recycled and shared between the old and new versions using smart pointers (std::shared_ptr). This makes copying the container an immediate O(1) operation and allows multiple threads to read different versions without using locks.

How does compression work (BitmapNode)?

To avoid wasting memory with arrays of 32 pointers filled with nulls, a 32-bit bitmap is used. If an internal node has only 3 children, its bitmap will have exactly 3 bits set, and it will store an array of exactly 3 pointers. The real position of the pointer is calculated super-efficiently using the hardware instruction std::popcount.

Collisions

If two distinct keys produce exactly the same 64-bit hash, they are stored in a special collision node (CollisionNode), which acts as a small linear array.

Template Parameters

Key	Key type. It must be copy-constructible and copy-assignable.
T	Mapped value type. It must be copy-constructible and copy-assignable so path-copying updates can rebuild shared collision nodes without moving from old versions.
Cmp	Equality predicate. If `cmp(a, b)` is true, the hash function supplied to the constructor must return the same hash for `a` and `b`.

Definition at line 112 of file tpl_persistent_hash_map.H.

Member Typedef Documentation

◆ Hash_Fct_Ptr

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

using Aleph::PersistentHashMap< Key, T, Cmp >::Hash_Fct_Ptr = size_t (*)(const Key &)

Hash function pointer type used by this map.

Definition at line 127 of file tpl_persistent_hash_map.H.

◆ NodePtr

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

using Aleph::PersistentHashMap< Key, T, Cmp >::NodePtr = std::shared_ptr<const Node>

private

Definition at line 156 of file tpl_persistent_hash_map.H.

Member Enumeration Documentation

◆ NodeType

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

enum class Aleph::PersistentHashMap::NodeType

strongprivate

Types of polymorphic nodes in the HAMT.

Enumerator
LEAF	Terminal leaf node that stores exactly one (key, value) pair.
BITMAP	Compressed internal node that uses a 32-bit bitmap for routing.
COLLISION	Terminal node that stores multiple (key, value) pairs with the exact same hash.

Definition at line 135 of file tpl_persistent_hash_map.H.

Constructor & Destructor Documentation

◆ PersistentHashMap() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

Aleph::PersistentHashMap< Key, T, Cmp >::PersistentHashMap	(	NodePtr	root,
		const Hash_Fct_Ptr	hash_fct,
		Cmp	cmp,
		const size_t	size
	)

inlineexplicitprivate

Definition at line 200 of file tpl_persistent_hash_map.H.

◆ PersistentHashMap() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

Aleph::PersistentHashMap< Key, T, Cmp >::PersistentHashMap	(	const Hash_Fct_Ptr	hash_fct = `dft_hash_ptr_fct<Key>`,
		const Cmp &	cmp = `Cmp()`
	)

inlineexplicit

Construct an empty persistent hash map.

Parameters

hash_fct	Hash function used to route keys through the HAMT.
cmp	Equality predicate used to compare keys.

Exceptions

std::domain_error	if `hash_fct` is null.
Whatever	copying `cmp` throws.

Precondition: If cmp(a, b) is true, hash_fct(a) == hash_fct(b) must also be true.

Note: Exception safety: strong guarantee; if an exception is thrown, no map is constructed.

Definition at line 712 of file tpl_persistent_hash_map.H.

References ah_domain_error_unless, and Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_.

Member Function Documentation

◆ append_entry()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static void Aleph::PersistentHashMap< Key, T, Cmp >::append_entry	(	Array< std::pair< Key, T > > &	entries,
		const Key &	key,
		const T *	value,
		T *	movable_value
	)

inlinestaticprivate

Definition at line 245 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and value.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl().

◆ bit()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static std::uint32_t Aleph::PersistentHashMap< Key, T, Cmp >::bit ( const size_t pos )

inlinestaticprivatenoexcept

Definition at line 214 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::find_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ bitpos()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static size_t Aleph::PersistentHashMap< Key, T, Cmp >::bitpos	(	const size_t	hash,
		const size_t	shift
	)

inlinestaticprivatenoexcept

Definition at line 209 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::LEVEL_MASK.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::find_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::hashes_match_slot(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), and Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves().

◆ collect_items()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static void Aleph::PersistentHashMap< Key, T, Cmp >::collect_items	(	const NodePtr &	node,
		Array< std::pair< Key, T > > &	out
	)

inlinestaticprivate

Definition at line 670 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::collect_items(), Aleph::PersistentHashMap< Key, T, Cmp >::COLLISION, Aleph::PersistentHashMap< Key, T, Cmp >::LEAF, and out.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::collect_items(), and Aleph::PersistentHashMap< Key, T, Cmp >::items().

◆ collect_keys()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static void Aleph::PersistentHashMap< Key, T, Cmp >::collect_keys	(	const NodePtr &	node,
		Array< Key > &	out
	)

inlinestaticprivate

Definition at line 648 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::collect_keys(), Aleph::PersistentHashMap< Key, T, Cmp >::COLLISION, Aleph::PersistentHashMap< Key, T, Cmp >::LeafNode::key, Aleph::PersistentHashMap< Key, T, Cmp >::LEAF, and out.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::collect_keys(), and Aleph::PersistentHashMap< Key, T, Cmp >::keys().

◆ collision_keys_are_unique()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::collision_keys_are_unique ( const CollisionNode & node ) const

inlineprivate

Definition at line 570 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::CollisionNode::entries, and Aleph::Array< T >::size().

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ contains()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::contains ( const Key & key ) const

inline

Test whether key is present.

Parameters

key	Key to search.

Returns: true if an equivalent key is stored.

Exceptions

Whatever comparison or hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 832 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::find().

◆ erase()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

PersistentHashMap Aleph::PersistentHashMap< Key, T, Cmp >::erase ( const Key & key ) const

inline

Return a new version without key.

Parameters

key	Key to erase.

Returns: New map version. If the key is absent, returns an unchanged version sharing the same root.

Exceptions

std::bad_alloc or whatever comparison/hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 816 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, Aleph::PersistentHashMap< Key, T, Cmp >::root_, and Aleph::PersistentHashMap< Key, T, Cmp >::size_.

Referenced by TEST().

◆ erase_impl()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl	(	const NodePtr &	node,
		const Key &	key,
		const size_t	hash,
		const size_t	shift,
		bool &	removed
	)		const

inlineprivate

Definition at line 423 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase(), and Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl().

◆ find()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

const T * Aleph::PersistentHashMap< Key, T, Cmp >::find ( const Key & key ) const

inline

Find a mapped value.

Parameters

key	Key to search.

Returns: Pointer to the stored mapped value, or nullptr when absent. The pointer remains valid while this map version is alive.

Exceptions

Whatever comparison or hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 845 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::find_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, and Aleph::PersistentHashMap< Key, T, Cmp >::root_.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::contains(), and TEST().

◆ find_impl()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

const T * Aleph::PersistentHashMap< Key, T, Cmp >::find_impl	(	const NodePtr &	node,
		const Key &	key,
		const size_t	hash,
		const size_t	shift
	)		const

inlineprivate

Definition at line 514 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::find(), and Aleph::PersistentHashMap< Key, T, Cmp >::find_impl().

◆ hashes_match_slot()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::hashes_match_slot	(	const NodePtr &	node,
		const size_t	shift,
		const size_t	pos
	)		const

inlineprivate

Definition at line 552 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::bitpos(), Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::COLLISION, Aleph::PersistentHashMap< Key, T, Cmp >::LeafNode::hash, Aleph::PersistentHashMap< Key, T, Cmp >::CollisionNode::hash, Aleph::PersistentHashMap< Key, T, Cmp >::hashes_match_slot(), and Aleph::PersistentHashMap< Key, T, Cmp >::LEAF.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::hashes_match_slot(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ index()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static size_t Aleph::PersistentHashMap< Key, T, Cmp >::index	(	const std::uint32_t	bitmap,
		const std::uint32_t	bit_value
	)

inlinestaticprivatenoexcept

Definition at line 219 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::find_impl(), and Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl().

◆ insert() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

PersistentHashMap Aleph::PersistentHashMap< Key, T, Cmp >::insert	(	const Key &	key,
		const T &	value
	)		const

inline

Return a new version with key inserted if absent.

Parameters

key	Key to insert.
value	Mapped value to copy into the new version when `key` is absent.

Returns: New map version. If an equivalent key already exists, returns an unchanged version sharing the same root.

Exceptions

std::bad_alloc or whatever copying/comparison/hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 743 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert(), and value.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

PersistentHashMap Aleph::PersistentHashMap< Key, T, Cmp >::insert	(	const Key &	key,
		T &&	value
	)		const

inline

Return a new version with key inserted if absent, moving value.

Parameters

key	Key to insert.
value	Mapped value to move into the new version when `key` is absent.

Returns: New map version. If an equivalent key already exists, returns an unchanged version and does not move from value.

Exceptions

std::bad_alloc or whatever copying/moving/comparison/hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 763 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert(), and value.

◆ insert_impl()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl	(	const NodePtr &	node,
		const Key &	key,
		const T *	value,
		T *	movable_value,
		const size_t	hash,
		const size_t	shift,
		const bool	replace,
		bool &	added,
		bool &	changed
	)		const

inlineprivate

Definition at line 292 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), and Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign().

◆ insert_or_assign() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

PersistentHashMap Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign	(	const Key &	key,
		const T &	value
	)		const

inline

Return a new version with key bound to value.

Parameters

key	Key to insert or update.
value	Mapped value to copy into the returned version.

Returns: New map version with an equivalent key present.

Exceptions

std::bad_alloc or whatever copying/comparison/hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 782 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert(), and value.

Referenced by TEST().

◆ insert_or_assign() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

PersistentHashMap Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign	(	const Key &	key,
		T &&	value
	)		const

inline

Return a new version with key bound to moved value.

Parameters

key	Key to insert or update.
value	Mapped value to move into the returned version.

Returns: New map version with an equivalent key present.

Exceptions

std::bad_alloc or whatever copying/moving/comparison/hashing throws.

Note: Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 799 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::cmp_, Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_, Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert(), and value.

◆ is_empty()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::is_empty ( ) const

inlinenoexcept

Return true when this version has no bindings.

Returns: true iff size() == 0.

Exceptions

Nothing.

Note: Exception safety: no-throw.

Definition at line 732 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::size_.

Referenced by TEST(), and TEST().

◆ items()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

Array< std::pair< Key, T > > Aleph::PersistentHashMap< Key, T, Cmp >::items ( ) const

inline

Return all key/value bindings in unspecified order.

Returns: Aleph array with a copy of every binding.

Exceptions

std::bad_alloc or whatever copying Key or T throws.

Note: Complexity: O(n) time for a full-trie collection operation.; Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 872 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::collect_items(), out, Aleph::Array< T >::reserve(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, and Aleph::PersistentHashMap< Key, T, Cmp >::size().

Referenced by TEST(), TEST(), and TEST().

◆ keys()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

Array< Key > Aleph::PersistentHashMap< Key, T, Cmp >::keys ( ) const

inline

Return all keys in unspecified order.

Returns: Aleph array with a copy of every key.

Exceptions

std::bad_alloc or whatever copying Key throws.

Note: Complexity: O(n) time for a full-trie collection operation.; Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 857 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::collect_keys(), out, Aleph::Array< T >::reserve(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, and Aleph::PersistentHashMap< Key, T, Cmp >::size().

Referenced by TEST(), TEST(), and TEST().

◆ make_leaf() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::make_leaf	(	const Key &	key,
		const T &	value,
		const size_t	hash
	)

inlinestaticprivate

Definition at line 225 of file tpl_persistent_hash_map.H.

References value.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::make_leaf_from_value().

◆ make_leaf() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::make_leaf	(	const Key &	key,
		T &&	value,
		const size_t	hash
	)

inlinestaticprivate

Definition at line 230 of file tpl_persistent_hash_map.H.

References value.

◆ make_leaf_from_value()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

static NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::make_leaf_from_value	(	const Key &	key,
		const T *	value,
		T *	movable_value,
		const size_t	hash
	)

inlinestaticprivate

Definition at line 235 of file tpl_persistent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::make_leaf(), and value.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl().

◆ merge_leaves()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves	(	const NodePtr &	n1,
		const NodePtr &	n2,
		const size_t	shift
	)		const

inlineprivate

Definition at line 256 of file tpl_persistent_hash_map.H.

References Aleph::Array< T >::append(), Aleph::PersistentHashMap< Key, T, Cmp >::bit(), Aleph::PersistentHashMap< Key, T, Cmp >::bitpos(), Aleph::PersistentHashMap< Key, T, Cmp >::BITS_PER_LEVEL, Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentHashMap< Key, T, Cmp >::LEAF, Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves(), Aleph::Array< T >::reserve(), and Aleph::PersistentHashMap< Key, T, Cmp >::Node::type.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), and Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves().

◆ size()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

size_t Aleph::PersistentHashMap< Key, T, Cmp >::size ( ) const

inlinenoexcept

Return the number of bindings stored in this version.

Returns: Number of bindings.

Exceptions

Nothing.

Note: Exception safety: no-throw.

Definition at line 725 of file tpl_persistent_hash_map.H.

References Aleph::PersistentHashMap< Key, T, Cmp >::size_.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::items(), Aleph::PersistentHashMap< Key, T, Cmp >::keys(), main(), TEST(), and TEST().

◆ size_after_insert()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

size_t Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert ( const bool added ) const

inlineprivate

Definition at line 693 of file tpl_persistent_hash_map.H.

References ah_overflow_error_if, Aleph::blossom_maximum_cardinality_matching(), and Aleph::PersistentHashMap< Key, T, Cmp >::size_.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), and Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign().

◆ verify()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::verify ( ) const

inline

Verify HAMT routing, collision, uniqueness and size invariants.

Returns: true if the internal structure is consistent.

Exceptions

std::overflow_error	if a diagnostic node count overflows.
Whatever	`hash_fct_` or `Cmp` throws.

Note: Intended for tests and diagnostics; it is O(n) plus O(k^2) inside each full-hash collision node.; Exception safety: strong guarantee; this map version remains unchanged if an exception is thrown.

Definition at line 889 of file tpl_persistent_hash_map.H.

References Aleph::and, Aleph::count(), Aleph::PersistentHashMap< Key, T, Cmp >::root_, Aleph::PersistentHashMap< Key, T, Cmp >::size_, and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

Referenced by TEST(), and TEST().

◆ verify_rec()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

bool Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec	(	const NodePtr &	node,
		const size_t	shift,
		size_t &	count
	)		const

inlineprivate

Definition at line 579 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::verify(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

Member Data Documentation

◆ BITS_PER_LEVEL

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

constexpr size_t Aleph::PersistentHashMap< Key, T, Cmp >::BITS_PER_LEVEL = 5

staticconstexprprivate

Definition at line 130 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::find_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_impl(), Aleph::PersistentHashMap< Key, T, Cmp >::merge_leaves(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ BRANCHING_FACTOR

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

constexpr size_t Aleph::PersistentHashMap< Key, T, Cmp >::BRANCHING_FACTOR = 1ULL << BITS_PER_LEVEL

staticconstexprprivate

Definition at line 131 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ cmp_

◆ hash_fct_

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

Hash_Fct_Ptr Aleph::PersistentHashMap< Key, T, Cmp >::hash_fct_

private

Definition at line 196 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::PersistentHashMap(), Aleph::PersistentHashMap< Key, T, Cmp >::erase(), Aleph::PersistentHashMap< Key, T, Cmp >::find(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify_rec().

◆ LEVEL_MASK

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

constexpr size_t Aleph::PersistentHashMap< Key, T, Cmp >::LEVEL_MASK = BRANCHING_FACTOR - 1

staticconstexprprivate

Definition at line 132 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::bitpos().

◆ root_

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

NodePtr Aleph::PersistentHashMap< Key, T, Cmp >::root_

private

Definition at line 195 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase(), Aleph::PersistentHashMap< Key, T, Cmp >::find(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), Aleph::PersistentHashMap< Key, T, Cmp >::insert_or_assign(), Aleph::PersistentHashMap< Key, T, Cmp >::items(), Aleph::PersistentHashMap< Key, T, Cmp >::keys(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify().

◆ size_

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>>

size_t Aleph::PersistentHashMap< Key, T, Cmp >::size_ = 0

private

Definition at line 198 of file tpl_persistent_hash_map.H.

Referenced by Aleph::PersistentHashMap< Key, T, Cmp >::erase(), Aleph::PersistentHashMap< Key, T, Cmp >::is_empty(), Aleph::PersistentHashMap< Key, T, Cmp >::size(), Aleph::PersistentHashMap< Key, T, Cmp >::size_after_insert(), and Aleph::PersistentHashMap< Key, T, Cmp >::verify().

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

tpl_persistent_hash_map.H

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

What is a Persistent HAMT?

How does compression work (BitmapNode)?

Collisions

Member Typedef Documentation

◆ Hash_Fct_Ptr

◆ NodePtr

Member Enumeration Documentation

◆ NodeType

Constructor & Destructor Documentation

◆ PersistentHashMap() [1/2]

◆ PersistentHashMap() [2/2]

Member Function Documentation

◆ append_entry()

◆ bit()

◆ bitpos()

◆ collect_items()

◆ collect_keys()

◆ collision_keys_are_unique()

◆ contains()

◆ erase()

◆ erase_impl()

◆ find()

◆ find_impl()

◆ hashes_match_slot()

◆ index()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_impl()

◆ insert_or_assign() [1/2]

◆ insert_or_assign() [2/2]

◆ is_empty()

◆ items()

◆ keys()

◆ make_leaf() [1/2]

◆ make_leaf() [2/2]

◆ make_leaf_from_value()

◆ merge_leaves()

◆ size()

◆ size_after_insert()

◆ verify()

◆ verify_rec()

Member Data Documentation

◆ BITS_PER_LEVEL

◆ BRANCHING_FACTOR

◆ cmp_

◆ hash_fct_

◆ LEVEL_MASK

◆ root_

◆ size_