persistent_map< K, V, Hash > Class Template Reference

Persistent (structurally shared) map with O(1) copy. More...

#include <persistent_map.h>

Public Types
using	const_iterator = typename map_t::iterator

Public Member Functions
	persistent_map ()=default
std::size_t	size () const
bool	empty () const
const V *	find (const K &k) const
const V &	at (const K &k) const
void	set (const K &k, const V &v)
void	set (const K &k, V &&v)
template<class Fn>
void	update (const K &k, Fn &&fn)
bool	erase (const K &k)
void	clear ()
const_iterator	begin () const
const_iterator	end () const
template<class Added, class Removed, class Changed>
void	diff (const persistent_map &other, Added &&added, Removed &&removed, Changed &&changed) const

Detailed Description

template<typename K, typename V, typename Hash>
class persistent_map< K, V, Hash >

Persistent (structurally shared) map with O(1) copy.

Symex state that is snapshotted whenever the call stack is copied — the level1/level2 renaming maps and the value set — lives in one of these. A std::unordered_map copies O(N) at every per-branch merge_statet and state fork; immer's HAMT makes that copy O(1) structural sharing, the same win guard_seq's immer::vector gives the conjunct list. Two shared snapshots then compare in O(divergence) via diff(), which is what turns a control-flow merge from O(state) into O(paths' divergence).

Ownership: non-atomic refcount, no lock — symex runs single-threaded (the only parallelism, –parallel-solving, solves an already-built equation and never touches a live state). See guard_seq.h for the same reasoning.

Lookup returns const V* (immer's find), nullptr when absent — a pointer into shared storage, valid until the next mutating call; callers must not stash it across a set()/erase().

Member Typedef Documentation

const_iterator

template<typename K, typename V, typename Hash>

using persistent_map< K, V, Hash >::const_iterator = typename map_t::iterator

Constructor & Destructor Documentation

persistent_map()

template<typename K, typename V, typename Hash>

persistent_map< K, V, Hash >::persistent_map ( )

default

Member Function Documentation

at()

template<typename K, typename V, typename Hash>

const V & persistent_map< K, V, Hash >::at ( const K & k ) const

inline

begin()

template<typename K, typename V, typename Hash>

const_iterator persistent_map< K, V, Hash >::begin ( ) const

inline

clear()

template<typename K, typename V, typename Hash>

void persistent_map< K, V, Hash >::clear ( )

inline

diff()

template<typename K, typename V, typename Hash>

template<class Added, class Removed, class Changed>

void persistent_map< K, V, Hash >::diff ( const persistent_map< K, V, Hash > & other, Added && added, Removed && removed, Changed && changed ) const

inline

empty()

template<typename K, typename V, typename Hash>

bool persistent_map< K, V, Hash >::empty ( ) const

inline

end()

template<typename K, typename V, typename Hash>

const_iterator persistent_map< K, V, Hash >::end ( ) const

inline

erase()

template<typename K, typename V, typename Hash>

bool persistent_map< K, V, Hash >::erase ( const K & k )

inline

find()

template<typename K, typename V, typename Hash>

const V * persistent_map< K, V, Hash >::find ( const K & k ) const

inline

set() [1/2]

template<typename K, typename V, typename Hash>

void persistent_map< K, V, Hash >::set ( const K & k, const V & v )

inline

set() [2/2]

template<typename K, typename V, typename Hash>

void persistent_map< K, V, Hash >::set ( const K & k, V && v )

inline

size()

template<typename K, typename V, typename Hash>

std::size_t persistent_map< K, V, Hash >::size ( ) const

inline

update()

template<typename K, typename V, typename Hash>

template<class Fn>

void persistent_map< K, V, Hash >::update ( const K & k, Fn && fn )

inline

---

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

• src/util/persistent_map.h