tpl_persistent_treap.H File Reference

Immutable path-copying treap set and map. More...

#include <algorithm>
#include <concepts>
#include <cstdint>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <ahFunction.H>
#include <tpl_array.H>

Include dependency graph for tpl_persistent_treap.H:

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

Go to the source code of this file.

Classes
struct	Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >
class	Aleph::PersistentTreapSet< Key, Compare >
	Immutable ordered set backed by a path-copying treap. More...
struct	Aleph::PersistentTreapSet< Key, Compare >::Node
class	Aleph::PersistentTreapMap< Key, T, Compare >
	Immutable ordered map backed by a path-copying treap. More...
struct	Aleph::PersistentTreapMap< Key, T, Compare >::Node

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

Functions
std::uint64_t	Aleph::detail::persistent_treap_priority (const std::uint64_t n) noexcept

Detailed Description

Immutable path-copying treap set and map.

What is a Persistent Treap?

A Treap is a randomized binary search tree that maintains both a BST property (for the keys) and a Min-Heap property (using randomly generated priorities). This guarantees balanced O(log n) tree depth with high probability.

"Persistence" in this context refers to immutability with history (structural sharing or path-copying). It does NOT mean disk storage. When a node is inserted, erased, or when the tree is split/joined, the existing tree is never mutated. Instead, a new root is returned. Only the nodes along the search path (and those affected by rotations) are copied. The rest of the subtrees remain completely untouched and are shared between the old and new versions using smart pointers (std::shared_ptr<const Node>).

Advantages

• Fast Snapshots: Copying the entire collection is an O(1) operation (just copying the root pointer).
• Lock-free Concurrency: Because existing nodes are never mutated, multiple threads can read from past and present versions simultaneously without requiring locks or synchronization.

This is unrelated to Aleph's file-backed B/B+ tree persistence: these containers are volatile in-memory values, not durable storage.

Complexity

Search, insert, erase, split and join are expected O(log n) with O(log n) new nodes allocated per update. Copying a collection value is O(1). keys() and items() flatten a version in sorted order and cost O(n).

Thread safety

Published versions are immutable. Different threads may read distinct collection objects that share the same tree 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_treap.H.