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

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

#include <sharing_map.h>

Collaboration diagram for sharing_mapt< keyT, valueT, hashT, equalT >:
[legend]

Classes

class  delta_view_itemt
 

Public Types

typedef keyT key_type
 
typedef valueT mapped_type
 
typedef std::pair< const key_type, mapped_typevalue_type
 
typedef hashT hash
 
typedef equalT key_equal
 
typedef std::size_t size_type
 
typedef const std::pair< const mapped_type &, const bool > const_find_type
 Return type of methods that retrieve a const reference to a value. More...
 
typedef const std::pair< mapped_type &, const bool > find_type
 Return type of methods that retrieve a reference to a value. More...
 
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 ()
 
size_type erase (const key_type &k, const tvt &key_exists=tvt::unknown())
 Erase element. More...
 
size_type erase_all (const keyst &ks, const tvt &key_exists=tvt::unknown())
 Erase all elements. More...
 
const_find_type insert (const key_type &k, const mapped_type &v, const tvt &key_exists=tvt::unknown())
 Insert element, return const reference. More...
 
const_find_type insert (const value_type &p, const tvt &key_exists=tvt::unknown())
 
find_type place (const key_type &k, const mapped_type &v)
 Insert element, return non-const reference. More...
 
find_type place (const value_type &p)
 Insert element, return non-const reference. More...
 
find_type find (const key_type &k, const tvt &key_exists=tvt::unknown())
 Find element. More...
 
const_find_type find (const key_type &k) const
 Find element. More...
 
mapped_typeat (const key_type &k, const tvt &key_exists=tvt::unknown())
 Get element at key. More...
 
const mapped_typeat (const key_type &k) const
 Get element at key. More...
 
mapped_typeoperator[] (const key_type &k)
 Get element at key, insert new if non-existent. 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...
 

Protected Types

typedef sharing_node_innert< key_type, mapped_typeinnert
 
typedef sharing_node_leaft< key_type, mapped_typeleaft
 
typedef sharing_node_baset baset
 
typedef innert::to_mapt to_mapt
 
typedef innert::leaf_listt leaf_listt
 

Protected Member Functions

innertget_container_node (const key_type &k)
 
const innertget_container_node (const key_type &k) const
 
const leaftget_leaf_node (const key_type &k) const
 
void iterate (const baset &n, const unsigned depth, std::function< void(const key_type &k, const mapped_type &m)> f) const
 
void gather_all (const baset &n, const unsigned depth, delta_viewt &delta_view) const
 

Protected Attributes

innert map
 
size_type num = 0
 

Static Protected Attributes

static mapped_type dummy
 
static const std::string not_found_msg ="key not found"
 
static const std::size_t bits = 18
 
static const std::size_t chunk = 3
 
static const std::size_t mask = 0xffff >> (16 - chunk)
 
static const std::size_t steps = bits / chunk
 

Friends

void sharing_map_interface_test ()
 
void sharing_map_copy_test ()
 
void sharing_map_collision_test ()
 
void sharing_map_view_test ()
 

Detailed Description

template<class keyT, class valueT, class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
class sharing_mapt< keyT, valueT, hashT, equalT >

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

The map is implemented as a fixed-height n-ary trie. The height H and the maximum number of children per inner node S are determined by the two configuration parameters bits and chunks in sharing_map.h. It holds that H = bits / chunks and S = 2 ^ chunks.

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::list.

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 (with greater differences for sparser maps).

The nodes in the sharing map are objects of type sharing_nodet. Each sharing node has a shared_ptr to an object of type dt which can be shared between nodes.

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.

Retrieval, insertion, and removal operations interact with sharing as follows:

  • When a non-const reference to a value in the map that is contained in a shared subtree is retrieved, the nodes on the path from the root of the subtree to the corresponding key-value pair (and the key-value pair itself) are copied and integrated with the map.
  • When a key-value pair is inserted into the map 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.

Several methods take a hint indicating whether the element is known not to be in the map (false), known to be in the map (true), or it is unknown whether the element is in the map (unknown). The value unknown is always valid. When true or false are given they need to be accurate, otherwise the behavior is undefined. A correct hint can prevent the need to follow a path from the root to a key-value pair twice (e.g., once for checking that it exists, and second for copying nodes).

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: 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 124 of file sharing_map.h.

Member Typedef Documentation

◆ baset

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef sharing_node_baset sharing_mapt< keyT, valueT, hashT, equalT >::baset
protected

Definition at line 163 of file sharing_map.h.

◆ const_find_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef const std::pair<const mapped_type &, const bool> sharing_mapt< keyT, valueT, hashT, equalT >::const_find_type

Return type of methods that retrieve a const reference to a value.

First component is a reference to the value (or a dummy value if the given key does not exist), and the second component indicates if the value with the given key was found.

Definition at line 149 of file sharing_map.h.

◆ delta_viewt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::vector<delta_view_itemt> sharing_mapt< keyT, valueT, 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 285 of file sharing_map.h.

◆ find_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef const std::pair<mapped_type &, const bool> sharing_mapt< keyT, valueT, hashT, equalT >::find_type

Return type of methods that retrieve a reference to a value.

First component is a reference to the value (or a dummy value if the given key does not exist), and the second component indicates if the value with the given key was found.

Definition at line 155 of file sharing_map.h.

◆ hash

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef hashT sharing_mapt< keyT, valueT, hashT, equalT >::hash

Definition at line 140 of file sharing_map.h.

◆ innert

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef sharing_node_innert<key_type, mapped_type> sharing_mapt< keyT, valueT, hashT, equalT >::innert
protected

Definition at line 160 of file sharing_map.h.

◆ key_equal

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef equalT sharing_mapt< keyT, valueT, hashT, equalT >::key_equal

Definition at line 141 of file sharing_map.h.

◆ key_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef keyT sharing_mapt< keyT, valueT, hashT, equalT >::key_type

Definition at line 136 of file sharing_map.h.

◆ keyst

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::vector<key_type> sharing_mapt< keyT, valueT, hashT, equalT >::keyst

Definition at line 157 of file sharing_map.h.

◆ leaf_listt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef innert::leaf_listt sharing_mapt< keyT, valueT, hashT, equalT >::leaf_listt
protected

Definition at line 166 of file sharing_map.h.

◆ leaft

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef sharing_node_leaft<key_type, mapped_type> sharing_mapt< keyT, valueT, hashT, equalT >::leaft
protected

Definition at line 161 of file sharing_map.h.

◆ mapped_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef valueT sharing_mapt< keyT, valueT, hashT, equalT >::mapped_type

Definition at line 137 of file sharing_map.h.

◆ size_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::size_t sharing_mapt< keyT, valueT, hashT, equalT >::size_type

Definition at line 143 of file sharing_map.h.

◆ to_mapt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef innert::to_mapt sharing_mapt< keyT, valueT, hashT, equalT >::to_mapt
protected

Definition at line 165 of file sharing_map.h.

◆ value_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::pair<const key_type, mapped_type> sharing_mapt< keyT, valueT, hashT, equalT >::value_type

Definition at line 138 of file sharing_map.h.

◆ view_itemt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::pair<const key_type &, const mapped_type &> sharing_mapt< keyT, valueT, hashT, equalT >::view_itemt

Definition at line 253 of file sharing_map.h.

◆ viewt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
typedef std::vector<view_itemt> sharing_mapt< keyT, valueT, 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 257 of file sharing_map.h.

Constructor & Destructor Documentation

◆ ~sharing_mapt()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
sharing_mapt< keyT, valueT, hashT, equalT >::~sharing_mapt ( )
inline

Definition at line 132 of file sharing_map.h.

Member Function Documentation

◆ at() [1/2]

template<class keyT , class valueT , class hashT , class equalT >
sharing_mapt< keyT, valueT, hashT, equalT >::mapped_type & sharing_mapt< keyT, valueT, hashT, equalT >::at ( const key_type k,
const tvt key_exists = tvt::unknown() 
)

Get element at key.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element
key_existsHint to indicate whether the element is known to exist (possible values unknown or true)
Exceptions
<tt>std::out_of_range</tt>if key not found
Returns
The mapped value

Definition at line 820 of file sharing_map.h.

References r.

◆ at() [2/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::mapped_type & sharing_mapt< keyT, valueT, hashT, equalT >::at ( const key_type k) const

Get element at key.

Complexity:

  • Worst case: O(H * log(S) + M)
  • Best case: O(H)
Parameters
kThe key of the element
Exceptions
std::out_of_rangeif key not found
Returns
The mapped value

Definition at line 841 of file sharing_map.h.

References r.

◆ clear()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_mapt< keyT, valueT, hashT, equalT >::clear ( void  )
inline

◆ empty()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
bool sharing_mapt< keyT, valueT, hashT, equalT >::empty ( ) const
inline

Check if map is empty.

Definition at line 229 of file sharing_map.h.

References sharing_mapt< keyT, valueT, hashT, equalT >::num.

◆ erase()

template<class keyT , class valueT , class hashT , class equalT >
sharing_mapt< keyT, valueT, hashT, equalT >::size_type sharing_mapt< keyT, valueT, hashT, equalT >::erase ( const key_type k,
const tvt key_exists = tvt::unknown() 
)

Erase element.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element to erase
key_existsHint to indicate whether the element is known to exist (possible values unknown ortrue)

Definition at line 604 of file sharing_map.h.

References sharing_node_innert< keyT, valueT, equalT >::add_child(), as_const(), sharing_node_innert< keyT, valueT, equalT >::remove_child(), sharing_node_innert< keyT, valueT, equalT >::remove_leaf(), small_mapt< T, Ind, Num >::size(), and SM_ASSERT.

◆ erase_all()

template<class keyT , class valueT , class hashT , class equalT >
sharing_mapt< keyT, valueT, hashT, equalT >::size_type sharing_mapt< keyT, valueT, hashT, equalT >::erase_all ( const keyst ks,
const tvt key_exists = tvt::unknown() 
)

Erase all elements.

Complexity:

  • Worst case: O(K * (H * S + M))
  • Best case: O(K * H)
Parameters
ksThe keys of the element to erase
key_existsHint to indicate whether the elements are known to exist (possible values unknown or true). Applies to all elements (i.e., have to use unknown if for at least one element it is not known whether it exists)

Definition at line 677 of file sharing_map.h.

◆ find() [1/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::find_type sharing_mapt< keyT, valueT, hashT, equalT >::find ( const key_type k,
const tvt key_exists = tvt::unknown() 
)

Find element.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element to search for
key_existsHint to indicate whether the element is known to exist (possible values unknown or true)
Returns
Pair of reference to found value (or dummy value if not found), and boolean indicating if element was found.

Definition at line 773 of file sharing_map.h.

References sharing_node_innert< keyT, valueT, equalT >::find_leaf(), sharing_node_leaft< keyT, valueT, equalT >::get_value(), and SM_ASSERT.

◆ find() [2/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::const_find_type sharing_mapt< keyT, valueT, hashT, equalT >::find ( const key_type k) const

Find element.

Complexity:

  • Worst case: O(H * log(S) + M)
  • Best case: O(H)
Parameters
kThe key of the element to search
Returns
Pair of const reference to found value (or dummy value if not found), and boolean indicating if element was found.

Definition at line 799 of file sharing_map.h.

References sharing_node_leaft< keyT, valueT, equalT >::get_value().

◆ gather_all()

template<class keyT , class valueT , class hashT , class equalT >
void sharing_mapt< keyT, valueT, hashT, equalT >::gather_all ( const baset n,
const unsigned  depth,
delta_viewt delta_view 
) const
protected

Definition at line 413 of file sharing_map.h.

◆ get_container_node() [1/2]

template<class keyT , class valueT , class hashT , class equalT >
sharing_mapt< keyT, valueT, hashT, equalT >::innert * sharing_mapt< keyT, valueT, hashT, equalT >::get_container_node ( const key_type k)
protected

◆ get_container_node() [2/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::innert * sharing_mapt< keyT, valueT, hashT, equalT >::get_container_node ( const key_type k) const
protected

◆ get_delta_view()

template<class keyT , class valueT , class hashT , class equalT >
void sharing_mapt< keyT, valueT, hashT, equalT >::get_delta_view ( const sharing_mapt< keyT, valueT, 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 four members (in_both, key, value1, value2). The elements key, value1, and value2 are const references to the corresponding elements in the map. The first element indicates whether the key exists in both maps, the second element is the key, the third element is the mapped value of the first map, and the fourth element is the mapped value of the second map, or a dummy element if the key exists only in the first map (in which case in_both is false).

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 456 of file sharing_map.h.

References sharing_node_innert< keyT, valueT, equalT >::find_child(), sharing_node_innert< keyT, valueT, equalT >::find_leaf(), sharing_node_innert< keyT, valueT, equalT >::get_container(), sharing_node_innert< keyT, valueT, equalT >::get_to_map(), sharing_node_leaft< keyT, valueT, equalT >::get_value(), SM_ASSERT, and stack.

◆ get_leaf_node()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
const leaft* sharing_mapt< keyT, valueT, hashT, equalT >::get_leaf_node ( const key_type k) const
inlineprotected

◆ get_view()

template<class keyT , class valueT , class hashT , class equalT >
void sharing_mapt< keyT, valueT, 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 398 of file sharing_map.h.

References SM_ASSERT.

◆ has_key()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
bool sharing_mapt< keyT, valueT, 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(H)

Definition at line 246 of file sharing_map.h.

References sharing_mapt< keyT, valueT, hashT, equalT >::get_leaf_node().

◆ insert() [1/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::const_find_type sharing_mapt< keyT, valueT, hashT, equalT >::insert ( const key_type k,
const mapped_type m,
const tvt key_exists = tvt::unknown() 
)

Insert element, return const reference.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element to insert
mThe mapped value to insert
key_existsHint to indicate whether the element is known to exist (possible values false or unknown)
Returns
Pair of const reference to existing or newly inserted element, and boolean indicating if new element was inserted

Definition at line 702 of file sharing_map.h.

References as_const(), sharing_node_leaft< keyT, valueT, equalT >::get_value(), sharing_node_innert< keyT, valueT, equalT >::place_leaf(), and SM_ASSERT.

◆ insert() [2/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::const_find_type sharing_mapt< keyT, valueT, hashT, equalT >::insert ( const value_type p,
const tvt key_exists = tvt::unknown() 
)

Definition at line 725 of file sharing_map.h.

◆ iterate()

template<class keyT , class valueT , class hashT , class equalT >
void sharing_mapt< keyT, valueT, hashT, equalT >::iterate ( const baset n,
const unsigned  depth,
std::function< void(const key_type &k, const mapped_type &m)>  f 
) const
protected

◆ operator[]()

template<class keyT , class valueT , class hashT , class equalT >
sharing_mapt< keyT, valueT, hashT, equalT >::mapped_type & sharing_mapt< keyT, valueT, hashT, equalT >::operator[] ( const key_type k)

Get element at key, insert new if non-existent.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element
Returns
The mapped value

Definition at line 858 of file sharing_map.h.

◆ place() [1/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::find_type sharing_mapt< keyT, valueT, hashT, equalT >::place ( const key_type k,
const mapped_type m 
)

Insert element, return non-const reference.

Complexity:

  • Worst case: O(H * S + M)
  • Best case: O(H)
Parameters
kThe key of the element to insert
mThe mapped value to insert
Returns
Pair of reference to existing or newly inserted element, and boolean indicating if new element was inserted

Definition at line 740 of file sharing_map.h.

References sharing_node_innert< keyT, valueT, equalT >::find_leaf(), sharing_node_leaft< keyT, valueT, equalT >::get_value(), sharing_node_innert< keyT, valueT, equalT >::place_leaf(), and SM_ASSERT.

◆ place() [2/2]

template<class keyT , class valueT , class hashT , class equalT >
const sharing_mapt< keyT, valueT, hashT, equalT >::find_type sharing_mapt< keyT, valueT, hashT, equalT >::place ( const value_type p)

Insert element, return non-const reference.

Definition at line 757 of file sharing_map.h.

◆ size()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
size_type sharing_mapt< keyT, valueT, hashT, equalT >::size ( ) const
inline

Get number of elements in map.

Complexity: O(1)

Definition at line 223 of file sharing_map.h.

References sharing_mapt< keyT, valueT, hashT, equalT >::num.

◆ swap()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_mapt< keyT, valueT, hashT, equalT >::swap ( sharing_mapt< keyT, valueT, hashT, equalT > &  other)
inline

Friends And Related Function Documentation

◆ sharing_map_collision_test

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_map_collision_test ( )
friend

◆ sharing_map_copy_test

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_map_copy_test ( )
friend

◆ sharing_map_interface_test

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_map_interface_test ( )
friend

◆ sharing_map_view_test

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
void sharing_map_view_test ( )
friend

Member Data Documentation

◆ bits

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, hashT, equalT >::bits = 18
staticprotected

Definition at line 326 of file sharing_map.h.

◆ chunk

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, hashT, equalT >::chunk = 3
staticprotected

Definition at line 327 of file sharing_map.h.

◆ dummy

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
sharing_mapt< keyT, valueT, hashT, equalT >::mapped_type sharing_mapt< keyT, valueT, hashT, equalT >::dummy
staticprotected

Definition at line 321 of file sharing_map.h.

◆ map

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
innert sharing_mapt< keyT, valueT, hashT, equalT >::map
protected

◆ mask

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

Definition at line 330 of file sharing_map.h.

◆ not_found_msg

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
const std::string sharing_mapt< keyT, valueT, hashT, equalT >::not_found_msg ="key not found"
staticprotected

Definition at line 323 of file sharing_map.h.

◆ num

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
size_type sharing_mapt< keyT, valueT, hashT, equalT >::num = 0
protected

◆ steps

template<class keyT , class valueT , class hashT = std::hash<keyT>, class equalT = std::equal_to<keyT>>
const std::size_t sharing_mapt< keyT, valueT, hashT, equalT >::steps = bits / chunk
staticprotected

Definition at line 331 of file sharing_map.h.


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