cprover
Classes | Public Types | Public Member Functions | Public Attributes | Static Public Attributes | Protected Member Functions | Friends | List of all members
sharing_mapt< keyT, valueT, hashT, predT > Class Template Reference

#include <sharing_map.h>

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

Classes

class  delta_view_itemt
 

Public Types

typedef keyT key_type
 
typedef valueT mapped_type
 
typedef std::pair< const key_type, mapped_type > value_type
 
typedef hashT hash
 
typedef predT key_equal
 
typedef sharing_mapt< key_type, mapped_type, hash, key_equal > self_type
 
typedef sharing_nodet< key_type, mapped_type, key_equal > node_type
 
typedef size_t size_type
 
typedef const std::pair< const mapped_type &, const bool > const_find_type
 
typedef const std::pair< mapped_type &, const bool > find_type
 
typedef std::vector< key_type > keyst
 
typedef node_type::subt subt
 
typedef node_type::containert containert
 
typedef std::pair< const key_type &, const mapped_type & > view_itemt
 
typedef std::vector< view_itemt > viewt
 
typedef std::vector< delta_view_itemt > delta_viewt
 

Public Member Functions

 ~sharing_mapt ()
 
size_type erase (const key_type &k, const tvt &key_exists=tvt::unknown())
 
size_type erase_all (const keyst &ks, const tvt &key_exists=tvt::unknown())
 
const_find_type insert (const key_type &k, const mapped_type &v, const tvt &key_exists=tvt::unknown())
 
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)
 
find_type place (const value_type &p)
 
find_type find (const key_type &k, const tvt &key_exists=tvt::unknown())
 
const_find_type find (const key_type &k) const
 
mapped_type & at (const key_type &k, const tvt &key_exists=tvt::unknown())
 
const mapped_type & at (const key_type &k) const
 
mapped_type & operator[] (const key_type &k)
 
void swap (self_type &other)
 
size_type size () const
 
bool empty () const
 
void clear ()
 
bool has_key (const key_type &k) const
 
void get_view (viewt &view) const
 
void get_delta_view (const self_type &other, delta_viewt &delta_view, const bool only_common=true) const
 

Public Attributes

node_type map
 
size_type num =0
 

Static Public Attributes

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

Protected Member Functions

node_type * get_container_node (const key_type &k)
 
const node_type * get_container_node (const key_type &k) const
 
const node_type * get_leaf_node (const key_type &k) const
 
void gather_all (const node_type &n, delta_viewt &delta_view) const
 

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 predT = std::equal_to<keyT>>
class sharing_mapt< keyT, valueT, hashT, predT >

Definition at line 47 of file sharing_map.h.

Member Typedef Documentation

◆ const_find_type

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

Definition at line 71 of file sharing_map.h.

◆ containert

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef node_type::containert sharing_mapt< keyT, valueT, hashT, predT >::containert

Definition at line 77 of file sharing_map.h.

◆ delta_viewt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef std::vector<delta_view_itemt> sharing_mapt< keyT, valueT, hashT, predT >::delta_viewt

Definition at line 197 of file sharing_map.h.

◆ find_type

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

Definition at line 72 of file sharing_map.h.

◆ hash

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

Definition at line 63 of file sharing_map.h.

◆ key_equal

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

Definition at line 64 of file sharing_map.h.

◆ key_type

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

Definition at line 59 of file sharing_map.h.

◆ keyst

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

Definition at line 74 of file sharing_map.h.

◆ mapped_type

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

Definition at line 60 of file sharing_map.h.

◆ node_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef sharing_nodet<key_type, mapped_type, key_equal> sharing_mapt< keyT, valueT, hashT, predT >::node_type

Definition at line 67 of file sharing_map.h.

◆ self_type

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef sharing_mapt<key_type, mapped_type, hash, key_equal> sharing_mapt< keyT, valueT, hashT, predT >::self_type

Definition at line 66 of file sharing_map.h.

◆ size_type

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

Definition at line 69 of file sharing_map.h.

◆ subt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef node_type::subt sharing_mapt< keyT, valueT, hashT, predT >::subt

Definition at line 76 of file sharing_map.h.

◆ value_type

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

Definition at line 61 of file sharing_map.h.

◆ view_itemt

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

Definition at line 171 of file sharing_map.h.

◆ viewt

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
typedef std::vector<view_itemt> sharing_mapt< keyT, valueT, hashT, predT >::viewt

Definition at line 172 of file sharing_map.h.

Constructor & Destructor Documentation

◆ ~sharing_mapt()

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

Definition at line 55 of file sharing_map.h.

Member Function Documentation

◆ at() [1/2]

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

Definition at line 591 of file sharing_map.h.

References r.

◆ at() [2/2]

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

Definition at line 603 of file sharing_map.h.

References r.

◆ clear()

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

Definition at line 158 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::clear(), sharing_mapt< keyT, valueT, hashT, predT >::map, and sharing_mapt< keyT, valueT, hashT, predT >::num.

◆ empty()

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

Definition at line 153 of file sharing_map.h.

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

◆ erase()

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

Definition at line 442 of file sharing_map.h.

References _sm_assert, sharing_nodet< keyT, valueT, predT, no_sharing >::add_child(), as_const(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::remove_child(), and sharing_nodet< keyT, valueT, predT, no_sharing >::remove_leaf().

◆ erase_all()

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

Definition at line 494 of file sharing_map.h.

◆ find() [1/2]

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

Definition at line 562 of file sharing_map.h.

References _sm_assert, sharing_nodet< keyT, valueT, predT, no_sharing >::find_leaf(), and sharing_nodet< keyT, valueT, predT, no_sharing >::get_value().

◆ find() [2/2]

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

Definition at line 581 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::get_value().

◆ gather_all()

template<class keyT , class valueT , class hashT , class predT >
void sharing_mapt< keyT, valueT, hashT, predT >::gather_all ( const node_type &  n,
delta_viewt &  delta_view 
) const
protected

Definition at line 253 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::get_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_sub(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_internal(), and stack.

◆ get_container_node() [1/2]

template<class keyT , class valueT , class hashT , class predT >
sharing_mapt< keyT, valueT, hashT, predT >::node_type * sharing_mapt< keyT, valueT, hashT, predT >::get_container_node ( const key_type &  k)
protected

Definition at line 395 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::add_child().

◆ get_container_node() [2/2]

template<class keyT , class valueT , class hashT , class predT >
const sharing_mapt< keyT, valueT, hashT, predT >::node_type * sharing_mapt< keyT, valueT, hashT, predT >::get_container_node ( const key_type &  k) const
protected

Definition at line 411 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::find_child(), and sharing_nodet< keyT, valueT, predT, no_sharing >::is_container().

◆ get_delta_view()

template<class keyT , class valueT , class hashT , class predT >
void sharing_mapt< keyT, valueT, hashT, predT >::get_delta_view ( const self_type &  other,
delta_viewt &  delta_view,
const bool  only_common = true 
) const

Definition at line 289 of file sharing_map.h.

References _sn_assert, sharing_nodet< keyT, valueT, predT, no_sharing >::find_child(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_sub(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_internal(), and stack.

◆ get_leaf_node()

template<class keyT , class valueT , class hashT , class predT >
const sharing_mapt< keyT, valueT, hashT, predT >::node_type * sharing_mapt< keyT, valueT, hashT, predT >::get_leaf_node ( const key_type &  k) const
protected

Definition at line 431 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::find_leaf().

Referenced by sharing_mapt< keyT, valueT, hashT, predT >::has_key().

◆ get_view()

template<class keyT , class valueT , class hashT , class predT >
void sharing_mapt< keyT, valueT, hashT, predT >::get_view ( viewt &  view) const

Definition at line 217 of file sharing_map.h.

References sharing_nodet< keyT, valueT, predT, no_sharing >::get_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_sub(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_container(), sharing_nodet< keyT, valueT, predT, no_sharing >::is_internal(), and stack.

◆ has_key()

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
bool sharing_mapt< keyT, valueT, hashT, predT >::has_key ( const key_type &  k) const
inline

Definition at line 164 of file sharing_map.h.

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

◆ insert() [1/2]

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

Definition at line 508 of file sharing_map.h.

References _sn_assert, as_const(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_value(), and sharing_nodet< keyT, valueT, predT, no_sharing >::place_leaf().

◆ insert() [2/2]

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

Definition at line 531 of file sharing_map.h.

◆ operator[]()

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

Definition at line 612 of file sharing_map.h.

◆ place() [1/2]

template<class keyT , class valueT , class hashT , class predT >
sharing_mapt< keyT, valueT, hashT, predT >::find_type sharing_mapt< keyT, valueT, hashT, predT >::place ( const key_type &  k,
const mapped_type &  v 
)

Definition at line 538 of file sharing_map.h.

References _sm_assert, sharing_nodet< keyT, valueT, predT, no_sharing >::find_leaf(), sharing_nodet< keyT, valueT, predT, no_sharing >::get_value(), and sharing_nodet< keyT, valueT, predT, no_sharing >::place_leaf().

◆ place() [2/2]

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

Definition at line 556 of file sharing_map.h.

◆ size()

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

Definition at line 148 of file sharing_map.h.

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

◆ swap()

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

Definition at line 139 of file sharing_map.h.

References sharing_mapt< keyT, valueT, hashT, predT >::map, sharing_mapt< keyT, valueT, hashT, predT >::num, and sharing_nodet< keyT, valueT, predT, no_sharing >::swap().

Friends And Related Function Documentation

◆ sharing_map_collision_test

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = 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 predT = 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 predT = 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 predT = 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 predT = std::equal_to<keyT>>
const size_t sharing_mapt< keyT, valueT, hashT, predT >::bits =18
static

Definition at line 92 of file sharing_map.h.

◆ chunk

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

Definition at line 93 of file sharing_map.h.

◆ dummy

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

Definition at line 86 of file sharing_map.h.

◆ map

template<class keyT , class valueT , class hashT = std::hash<keyT>, class predT = std::equal_to<keyT>>
node_type sharing_mapt< keyT, valueT, hashT, predT >::map

Definition at line 80 of file sharing_map.h.

Referenced by sharing_mapt< keyT, valueT, hashT, predT >::clear(), and sharing_mapt< keyT, valueT, hashT, predT >::swap().

◆ mask

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

Definition at line 95 of file sharing_map.h.

◆ not_found_msg

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

Definition at line 90 of file sharing_map.h.

◆ num

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

Definition at line 83 of file sharing_map.h.

Referenced by sharing_mapt< keyT, valueT, hashT, predT >::clear(), sharing_mapt< keyT, valueT, hashT, predT >::empty(), sharing_mapt< keyT, valueT, hashT, predT >::size(), and sharing_mapt< keyT, valueT, hashT, predT >::swap().

◆ steps

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

Definition at line 96 of file sharing_map.h.

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