Add a delta item to the delta view if the value in the container (which must only contain a single leaf) is not shared with any of the values in the subtree below inner.

void gather_all (const nodet &n, delta_viewt &delta_view) const

std::size_t count_unmarked_nodes (bool leafs_only, std::set< const void * > &marked, bool mark=true) const

Protected Attributes

nodet map

size_type num = 0

Static Protected Attributes

static const std::size_t dummy_level = 0xff

static const std::size_t bits = 30

static const std::size_t chunk = 3

static const std::size_t mask = 0xffff >> (16 - chunk)

static const std::size_t levels = bits / chunk

Detailed Description

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
class sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >

A map implemented as a tree where subtrees can be shared between different maps.

The map is implemented as a variable-height n-ary trie.

When inserting a key-value pair into the map, first the hash of its key is computed. The bits number of lower order bits of the hash are deemed significant, and are grouped into bits / chunk chunks. The hash is then treated as a string (with each chunk representing a character) for the purposes of determining the position of the key-value pair in the trie. The actual key-value pairs are stored in the leaf nodes. Collisions (i.e., two different keys yield the same "string"), are handled by chaining the corresponding key-value pairs in a std::forward_list.

The depth at which a key-value pair will be stored (when calling insert()) depends on the shortest unique prefix of its hash code (treated as a string) with respect to the hash codes of the key-value pairs already in the map.

The use of a trie in combination with hashing has the advantage that the tree is unlikely to degenerate (if the number of hash collisions is low). This makes re-balancing operations unnecessary which do not interact well with sharing. A disadvantage is that the height of the tree is likely greater than if the elements had been stored in a balanced tree.

The nodes in the sharing map are objects of type sharing_nodet. A sharing node has a shared pointer (of type small_shared_n_way_ptrt) which can point to objects of type d_internalt, d_leaft, or d_containert (representing internal nodes, leaf nodes, and container nodes, the latter being used for chaining leafs in a linked list on hash collisions).

Sharing is initially generated when a map is assigned to another map or copied via the copy constructor. Then both maps contain a pointer to the root node of the tree that represents the maps. On subsequent modifications to one of the maps, nodes are copied and sharing is lessened as described in the following.

The replace(), update(), insert(), and erase() operations interact with sharing as follows:

When a key-value pair is inserted into the map (or a value of an existing pair is replaced or updated) and its position is in a shared subtree, already existing nodes from the root of the subtree to the position of the key-value pair are copied and integrated with the map, and new nodes are created as needed.
When a key-value pair is erased from the map that is in a shared subtree, nodes from the root of the subtree to the last node that will still exist on the path to the erased element after the element has been removed are copied and integrated with the map, and the remaining nodes are removed.

The replace() and update() operations are the only methods where sharing could unnecessarily be broken. This would happen when replacing an old value with a new equal value, or calling update but making no change. The sharing map provides a debug mode to detect such cases. When the template parameter fail_if_equal is set to true, then the replace() and update() methods yield an invariant violation when the new value is equal to the old value. For this to work, the type of the values stored in the map needs to have a defined equality operator (operator==).

In the descriptions of the methods of the sharing map we also give the complexity of the operations. We use the following symbols:

N: number of key-value pairs in the map
M: maximum number of key-value pairs that are chained in a leaf node
H: maximum height of the tree
S: maximum number of children per internal node

The first two symbols denote dynamic properties of a given map, whereas the last two symbols are static configuration parameters of the map class.

Definition at line 189 of file sharing_map.h.

Member Typedef Documentation

◆ delta_viewt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::vector<delta_view_itemt> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::delta_viewt

Delta view of the key-value pairs in two maps.

A delta view of two maps is a view of the key-value pairs in the maps that are contained in subtrees that are not shared between them (also see get_delta_view()).

Definition at line 439 of file sharing_map.h.

◆ hash

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef hashT sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::hash

Definition at line 199 of file sharing_map.h.

◆ key_equal

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef equalT sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::key_equal

Definition at line 200 of file sharing_map.h.

◆ key_type

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef keyT sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::key_type

Definition at line 196 of file sharing_map.h.

◆ keyst

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::vector<key_type> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::keyst

Definition at line 204 of file sharing_map.h.

◆ leaf_listt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef nodet::leaf_listt sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::leaf_listt

protected

Definition at line 210 of file sharing_map.h.

◆ mapped_type

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef valueT sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::mapped_type

Definition at line 197 of file sharing_map.h.

◆ nodet

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef sharing_nodet<key_type, mapped_type> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::nodet

protected

Definition at line 207 of file sharing_map.h.

◆ size_type

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::size_type

Definition at line 202 of file sharing_map.h.

◆ sorted_viewt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::set<view_itemt> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::sorted_viewt

Definition at line 389 of file sharing_map.h.

◆ to_mapt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef nodet::to_mapt sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::to_mapt

protected

Definition at line 209 of file sharing_map.h.

◆ value_comparatort

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::conditional<fail_if_equal,real_value_comparatort,noop_value_comparatort>::type sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::value_comparatort

protected

Definition at line 253 of file sharing_map.h.

◆ value_equalt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::conditional<fail_if_equal,std::equal_to<valueT>,falset>::type sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::value_equalt

protected

Definition at line 222 of file sharing_map.h.

◆ view_itemt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::pair<const key_type &, const mapped_type &> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::view_itemt

Definition at line 384 of file sharing_map.h.

◆ viewt

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

typedef std::vector<view_itemt> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::viewt

View of the key-value pairs in the map.

A view is a list of pairs with the components being const references to the keys and values in the map.

Definition at line 388 of file sharing_map.h.

Constructor & Destructor Documentation

◆ ~sharing_mapt()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::~sharing_mapt ( )

inline

Definition at line 192 of file sharing_map.h.

Member Function Documentation

◆ add_item_if_not_shared()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::add_item_if_not_shared ( const nodet & leaf,

const nodet & inner,

const std::size_t level,

delta_viewt & delta_view,

const bool only_common

) const

protected

Add a delta item to the delta view if the value in the container (which must only contain a single leaf) is not shared with any of the values in the subtree below inner.

This method is called by get_delta_view() when a container containing a single leaf is encountered in the first map, and the corresponding node in the second map is an inner node.

Parameters: leaf leaf node which is part of the first map in a call map1.get_delta_view(map2, ...)

inner inner node which is part of the second map

level depth of the nodes in the maps (both leaf and inner must be at the same depth in their respective maps)

delta_view delta view to add delta items to

only_common flag indicating if only items are added to the delta view for which the keys are in both maps

Definition at line 860 of file sharing_map.h.

◆ clear()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::clear ( )

inline

Clear map.

Definition at line 366 of file sharing_map.h.

◆ count_unmarked_nodes()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::count_unmarked_nodes ( bool leafs_only,

std::set< const void * > & marked,

bool mark = true

) const

protected

Definition at line 702 of file sharing_map.h.

◆ empty()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

bool sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::empty ( ) const

inline

Check if map is empty.

Definition at line 360 of file sharing_map.h.

◆ erase()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::erase ( const key_type & k )

Erase element, element must exist in map.

Complexity:

Worst case: O(H * S + M)
Best case: O(1)

Parameters: k The key of the element to erase

Definition at line 1203 of file sharing_map.h.

◆ erase_if_exists()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::erase_if_exists ( const key_type & k )

inline

Erase element if it exists.

Complexity:

Worst case: O(H * S + M)
Best case: O(1)

Parameters: k The key of the element to erase

Definition at line 274 of file sharing_map.h.

◆ find()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

std::optional< std::reference_wrapper< const typename sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::mapped_type > > sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::find ( const key_type & k ) const

Find element.

Complexity:

Worst case: O(H * log(S) + M)
Best case: O(1)

Parameters: k The key of the element to search

Returns: std::optional containing a const reference to the value if found

Definition at line 1451 of file sharing_map.h.

◆ gather_all()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::gather_all ( const nodet & n,

delta_viewt & delta_view

) const

protected

Definition at line 851 of file sharing_map.h.

◆ get_delta_view() [1/2]

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::delta_viewt sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_delta_view ( const sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > & other,

const bool only_common = true

) const

Definition at line 1122 of file sharing_map.h.

◆ get_delta_view() [2/2]

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_delta_view ( const sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > & other,

delta_viewt & delta_view,

const bool only_common = true

) const

Get a delta view of the elements in the map.

Informally, a delta view of two maps is a view of the key-value pairs in the maps that are contained in subtrees that are not shared between them.

A delta view is represented as a list of structs, with each struct having three members (key, value1, value2). The elements key, value1, and value2 are const references to the corresponding elements in the map, with the third being absent if the key only existed in the queried map. The first element is the key, the second element is the mapped value of the first map, and the third element is the mapped value of the second map if present.

Calling A.delta_view(B, ...) yields a view such that for each element in the view one of two things holds:

the key is contained in both A and B, and in the maps the corresponding key-value pairs are not contained in a subtree that is shared between them
the key is only contained in A

When only_common=true, the first case above holds for every element in the view.

Complexity:

Worst case: O(max(N1, N2) * H * log(S) * M1 * M2) (no sharing)
Best case: O(1) (maximum sharing)

The symbols N1, M1 refer to map A, and symbols N2, M2 refer to map B.

Parameters: other other map

[out] delta_view Empty delta view

only_common Indicates if the returned delta view should only contain key-value pairs for keys that exist in both maps

Definition at line 939 of file sharing_map.h.

◆ get_leaf_node() [1/2]

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::nodet & sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_leaf_node ( const key_type & k )

protected

Definition at line 1131 of file sharing_map.h.

◆ get_leaf_node() [2/2]

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::nodet * sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_leaf_node ( const key_type & k ) const

protected

Definition at line 1163 of file sharing_map.h.

◆ get_sharing_stats()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

template<class Iterator >

sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::sharing_map_statst sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_sharing_stats ( Iterator begin,

Iterator end,

std::function< sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > &(const Iterator)> f = [](const Iterator it) -> sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > & { return *it; }

)

static

Get sharing stats.

Complexity:

Worst case: O(N * H * log(S))
Best case: O(N + H)

Parameters: begin begin iterator

end end iterator

f function applied to the iterator to get a sharing map

Returns: sharing stats

Definition at line 784 of file sharing_map.h.

◆ get_sharing_stats_map()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

template<class Iterator >

sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::sharing_map_statst sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_sharing_stats_map ( Iterator begin,

Iterator end

)

static

Get sharing stats.

Complexity:

Worst case: O(N * H * log(S))
Best case: O(N + H)

Parameters: begin begin iterator of a map

end end iterator of a map

Returns: sharing stats

Definition at line 829 of file sharing_map.h.

◆ get_sorted_view()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

sorted_viewt sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_sorted_view ( ) const

inline

Convenience function to get a sorted view of the map elements.

A view is a list of pairs with the components being const references to the keys and values in the map.

Definition at line 462 of file sharing_map.h.

◆ get_view() [1/3]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

viewt sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_view ( ) const

inline

Definition at line 452 of file sharing_map.h.

◆ get_view() [2/3]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

template<class V >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_view ( V & view ) const

Get a view of the elements in the map A view is a list of pairs with the components being const references to the keys and values in the map.

Complexity:

Worst case: O(N * H * log(S))
Best case: O(N + H)

Parameters: [out] view Empty view

◆ get_view() [3/3]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

template<class view_type >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_view ( view_type & view ) const

Definition at line 836 of file sharing_map.h.

◆ has_key()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

bool sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::has_key ( const key_type & k ) const

inline

Check if key is in map.

Complexity:

Worst case: O(H * log(S) + M)
Best case: O(1)

Definition at line 377 of file sharing_map.h.

◆ insert()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

template<class valueU >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::insert ( const key_type & k,

valueU && m

)

Insert element, element must not exist in map.

Complexity:

Worst case: O(H * S + M)
Best case: O(1)

Parameters: k The key of the element to insert

m The mapped value to insert

Definition at line 1348 of file sharing_map.h.

◆ insert_or_replace()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

template<class valueU >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::insert_or_replace ( const key_type & k,

valueU && m

)

inline

Definition at line 292 of file sharing_map.h.

◆ insert_view_item() [1/2]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

static void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::insert_view_item ( sorted_viewt & v,

view_itemt && vi

)

inlinestatic

Definition at line 396 of file sharing_map.h.

◆ insert_view_item() [2/2]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

static void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::insert_view_item ( viewt & v,

view_itemt && vi

)

inlinestatic

Definition at line 391 of file sharing_map.h.

◆ iterate() [1/2]

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::iterate ( const nodet & n,

std::function< void(const key_type &k, const mapped_type &m)> f

) const

protected

Definition at line 656 of file sharing_map.h.

◆ iterate() [2/2]

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::iterate ( std::function< void(const key_type &k, const mapped_type &m)> f ) const

inline

Call a function for every key-value pair in the map.

Complexity: as sharing_mapt::get_view

Definition at line 515 of file sharing_map.h.

◆ migrate()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

template<class valueU >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::migrate ( const std::size_t starting_level,

const std::size_t key_suffix,

const std::size_t bit_last,

nodet & inner,

const key_type & k,

valueU && m

)

protected

Move a leaf node further down the tree such as to resolve a collision with another key-value pair.

This method is called by insert() to resolve a collision between a key-value pair to be newly inserted, and a key-value pair existing in the map.

Parameters: starting_level the depth of the inner node pointing to the leaf existing in the map

key_suffix hash code of the existing key in the map, shifted to the right by chunk * starting_level bits (i.e., key_suffix is the rest of the hash code used to determine the position of the key-value pair below level starting_level

bit_last last portion of the hash code of the key existing in the map (inner[bit_last] points to the leaf node to move further down the tree)

inner inner node of which the child inner[bit_last] is the leaf node to move further down the tree

k key of the element to be newly inserted

m value of the element to be newly inserted

Definition at line 1270 of file sharing_map.h.

◆ replace()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

template<class valueU >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::replace ( const key_type & k,

valueU && m

)

Replace element, element must exist in map.

Complexity:

Worst case: O(H * S + M)
Best case: O(1)

Parameters: k The key of the element to insert

m The mapped value to replace the old value with

Definition at line 1425 of file sharing_map.h.

◆ size()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

size_type sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::size ( ) const

inline

Get number of elements in map.

Complexity: O(1)

Definition at line 354 of file sharing_map.h.

◆ swap()

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::swap ( sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > & other )

inline

Swap with other map.

Complexity: O(1)

Definition at line 342 of file sharing_map.h.

◆ update()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::update ( const key_type & k,

std::function< void(mapped_type &)> mutator

)

Update an element in place; element must exist in map.

Rationale: this avoids copy-out / edit / replace sequences without leaking a non-const reference

Complexity: as sharing_mapt::replace

Parameters: k The key of the element to update

mutator function to apply to the existing value. Must not store the reference; should make some change to the stored value (if you are unsure if you need to make a change, use find beforehand)

Definition at line 1437 of file sharing_map.h.

Member Data Documentation

◆ bits

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::bits = 30

staticprotected

Definition at line 641 of file sharing_map.h.

◆ chunk

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::chunk = 3

staticprotected

Definition at line 642 of file sharing_map.h.

◆ dummy_level

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::dummy_level = 0xff

staticprotected

Definition at line 638 of file sharing_map.h.

◆ levels

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::levels = bits / chunk

staticprotected

Definition at line 646 of file sharing_map.h.

◆ map

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

nodet sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::map

protected

Definition at line 649 of file sharing_map.h.

◆ mask

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >

const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::mask = 0xffff >> (16 - chunk)

staticprotected

Definition at line 645 of file sharing_map.h.

◆ num

template<typename keyT , typename valueT , bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>

size_type sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::num = 0

protected

Definition at line 652 of file sharing_map.h.

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

/home/runner/work/cbmc/cbmc/src/util/sharing_map.h