tpl_persistent_hash_map.H File Reference

Immutable path-copying hash map backed by a HAMT. More...

#include <bit>
#include <cstdint>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <ahFunction.H>
#include <hash-fct.H>
#include <tpl_array.H>

Include dependency graph for tpl_persistent_hash_map.H:

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

Go to the source code of this file.

Classes
class	Aleph::PersistentHashMap< Key, T, Cmp >
	Immutable unordered map backed by a Hash Array Mapped Trie (HAMT). More...
struct	Aleph::PersistentHashMap< Key, T, Cmp >::Node
	Polymorphic base node managed by std::shared_ptr for structural sharing. More...
struct	Aleph::PersistentHashMap< Key, T, Cmp >::LeafNode
struct	Aleph::PersistentHashMap< Key, T, Cmp >::BitmapNode
struct	Aleph::PersistentHashMap< Key, T, Cmp >::CollisionNode

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

Detailed Description

Immutable path-copying hash map backed by a HAMT.

PersistentHashMap is an in-memory persistent collection: operations that look like updates return a new collection version and never mutate the old one. Unchanged trie nodes are shared through std::shared_ptr<const Node>.

This is unrelated to Aleph's file-backed persistence. Values are volatile in-memory objects and are not durable storage.

Complexity

Lookup, insertion and erasure are expected O(1) for well-distributed hashes because the trie depth is bounded by the width of size_t. Keys with the same full hash are stored in a collision node and cost O(k) inside that collision group.

Thread safety

Published versions are immutable. Different threads may read distinct collection objects that share the same trie without synchronization. The publication of a new version into a shared variable is still the user's responsibility and must be synchronized externally.

Definition in file tpl_persistent_hash_map.H.