cprover
sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT > Class Template Reference

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

#include <sharing_map.h>

+ Inheritance diagram for sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >:
+ Collaboration diagram for sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >:

Classes

class  delta_view_itemt
 
struct  falset
 
struct  noop_value_comparatort
 
struct  real_value_comparatort
 
struct  sharing_map_statst
 Stats about sharing between several sharing map instances. More...
 

Public Types

typedef keyT key_type
 
typedef valueT mapped_type
 
typedef hashT hash
 
typedef equalT key_equal
 
typedef std::size_t size_type
 
typedef std::vector< key_typekeyst
 
typedef std::pair< const key_type &, const mapped_type & > view_itemt
 
typedef std::vector< view_itemtviewt
 View of the key-value pairs in the map. More...
 
typedef std::vector< delta_view_itemtdelta_viewt
 Delta view of the key-value pairs in two maps. More...
 

Public Member Functions

 ~sharing_mapt ()
 
void erase (const key_type &k)
 Erase element, element must exist in map. More...
 
void erase_if_exists (const key_type &k)
 Erase element if it exists. More...
 
template<class valueU >
void insert (const key_type &k, valueU &&m)
 Insert element, element must not exist in map. More...
 
template<class valueU >
void replace (const key_type &k, valueU &&m)
 Replace element, element must exist in map. More...
 
void update (const key_type &k, std::function< void(mapped_type &)> mutator)
 Update an element in place; element must exist in map. More...
 
optionalt< std::reference_wrapper< const mapped_type > > find (const key_type &k) const
 Find element. More...
 
void swap (sharing_mapt &other)
 Swap with other map. More...
 
size_type size () const
 Get number of elements in map. More...
 
bool empty () const
 Check if map is empty. More...
 
void clear ()
 Clear map. More...
 
bool has_key (const key_type &k) const
 Check if key is in map. More...
 
void get_view (viewt &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. More...
 
void get_delta_view (const sharing_mapt &other, delta_viewt &delta_view, const bool only_common=true) const
 Get a delta view of the elements in the map. More...
 
void iterate (std::function< void(const key_type &k, const mapped_type &m)> f) const
 Call a function for every key-value pair in the map. More...
 

Static Public Member Functions

template<class Iterator >
static sharing_map_statst get_sharing_stats (Iterator begin, Iterator end, std::function< sharing_mapt &(const Iterator)> f=[](const Iterator it) -> sharing_mapt &{ return *it;})
 Get sharing stats. More...
 
template<class Iterator >
static sharing_map_statst get_sharing_stats_map (Iterator begin, Iterator end)
 Get sharing stats. More...
 

Protected Types

typedef sharing_nodet< key_type, mapped_typenodet
 
typedef nodet::to_mapt to_mapt
 
typedef nodet::leaf_listt leaf_listt
 
typedef std::conditional< fail_if_equal, std::equal_to< valueT >, falset >::type value_equalt
 
typedef std::conditional< fail_if_equal, real_value_comparatort, noop_value_comparatort >::type value_comparatort
 

Protected Member Functions

nodetget_leaf_node (const key_type &k)
 
const nodetget_leaf_node (const key_type &k) const
 
template<class valueU >
void 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)
 Move a leaf node further down the tree such as to resolve a collision with another key-value pair. More...
 
void iterate (const nodet &n, std::function< void(const key_type &k, const mapped_type &m)> f) const
 
void 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
 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. More...
 
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 179 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 405 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 189 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 190 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 186 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 194 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 200 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 187 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 197 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 192 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 199 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 243 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 212 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 361 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 365 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 182 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
leafleaf node which is part of the first map in a call map1.get_delta_view(map2, ...)
innerinner node which is part of the second map
leveldepth of the nodes in the maps (both leaf and inner must be at the same depth in their respective maps)
delta_viewdelta view to add delta items to
only_commonflag indicating if only items are added to the delta view for which the keys are in both maps

Definition at line 806 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 ( void  )
inline

Clear map.

Definition at line 343 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 648 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 337 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
kThe key of the element to erase

Definition at line 1137 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
kThe key of the element to erase

Definition at line 264 of file sharing_map.h.

◆ find()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >
optionalt< 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
kThe key of the element to search
Returns
optionalt containing a const reference to the value if found

Definition at line 1385 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 797 of file sharing_map.h.

◆ get_delta_view()

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
otherother map
[out]delta_viewEmpty delta view
only_commonIndicates if the returned delta view should only contain key-value pairs for keys that exist in both maps

Definition at line 881 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 1065 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 1097 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
beginbegin iterator
endend iterator
ffunction applied to the iterator to get a sharing map
Returns
sharing stats

Definition at line 730 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
beginbegin iterator of a map
endend iterator of a map
Returns
sharing stats

Definition at line 775 of file sharing_map.h.

◆ get_view()

template<typename keyT , typename valueT , bool fail_if_equal, typename hashT , typename equalT >
void sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::get_view ( viewt 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]viewEmpty view

Definition at line 782 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 354 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
kThe key of the element to insert
mThe mapped value to insert

Definition at line 1282 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 601 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 460 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_levelthe depth of the inner node pointing to the leaf existing in the map
key_suffixhash 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_lastlast 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)
innerinner node of which the child inner[bit_last] is the leaf node to move further down the tree
kkey of the element to be newly inserted
mvalue of the element to be newly inserted

Definition at line 1204 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
kThe key of the element to insert
mThe mapped value to replace the old value with

Definition at line 1359 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 331 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 319 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
kThe key of the element to update
mutatorfunction 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 1371 of file sharing_map.h.

Member Data Documentation

◆ bits

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::bits = 30
staticprotected

Definition at line 586 of file sharing_map.h.

◆ chunk

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::chunk = 3
staticprotected

Definition at line 587 of file sharing_map.h.

◆ dummy_level

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::dummy_level = 0xff
staticprotected

Definition at line 583 of file sharing_map.h.

◆ levels

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::levels = bits / chunk
staticprotected

Definition at line 591 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 594 of file sharing_map.h.

◆ mask

template<typename keyT, typename valueT, bool fail_if_equal = false, typename hashT = std::hash<keyT>, typename equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, fail_if_equal, hashT, equalT >::mask = 0xffff >> (16 - chunk)
staticprotected

Definition at line 590 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 597 of file sharing_map.h.


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