cprover
small_mapt< T, Ind, Num > Class Template Reference

Map from small integers to values. More...

#include <small_map.h>

Inheritance diagram for small_mapt< T, Ind, Num >:
[legend]
Collaboration diagram for small_mapt< T, Ind, Num >:
[legend]

Classes

class  const_iterator
 Const iterator. More...
 
class  const_value_iterator
 Const value iterator. More...
 

Public Types

typedef std::pair< const unsigned, const T & > value_type
 

Public Member Functions

 small_mapt ()
 
 small_mapt (const small_mapt &m)
 
 ~small_mapt ()
 
const_iterator begin () const
 
const_iterator end () const
 
const_value_iterator value_begin () const
 
const_value_iterator value_end () const
 
T & operator[] (std::size_t idx)
 
const_iterator find (std::size_t idx) const
 
std::size_t erase (std::size_t idx)
 
small_maptcopy_and_erase (std::size_t idx) const
 
small_maptcopy_and_insert (std::size_t idx, const T &value) const
 
std::size_t size () const
 
bool empty () const
 

Private Types

typedef Ind index_fieldt
 

Private Member Functions

void copy (T *dest, const T *src, std::size_t n) const
 
T * allocate (std::size_t n) const
 
T * allocate (T *ptr, std::size_t n) const
 
unsigned get_field (std::size_t field) const
 
void set_field (std::size_t field, unsigned v)
 
void shift_indices (std::size_t ii)
 

Private Attributes

index_fieldt ind
 
T * p
 

Static Private Attributes

static const std::size_t N_BITS = std::numeric_limits<index_fieldt>::digits
 
static const std::size_t NUM = Num
 
static const std::size_t S_BITS = NUM * num_bitst<NUM - 1>::value + NUM
 
static const std::size_t BITS = num_bitst<NUM - 1>::value + 1
 
static const index_fieldt IND = indicator_maskt<index_fieldt, BITS>::value
 
static const index_fieldt MASK = ((index_fieldt)1 << BITS) - 1
 

Friends

void small_map_test ()
 

Detailed Description

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
class small_mapt< T, Ind, Num >

Map from small integers to values.

A data structure that maps small integers (in {0, ..., Num-1}) to values. It is designed to be more memory-efficient than std::map for this use case.

In the following we give some data about the memory consumption of small_mapt compared to std::map, on a 64-bit Linux system with GNU STL. It was determined with valgrind/massif. We configured the maps as small_mapt<uint64_t, uint32_t, Num=8> and std::map<uint8_t, uint64_t>. Thus, indices to small_mapt can be in {0, ..., 7} for this configuration.

Below we give the memory consumption (in bytes) of small_mapt and std::map, both for when containing 8 elements, and when being empty. The value for "useful" indicates the number of bytes requested, the value for "total" also includes padding bytes.

small_mapt:

  • 8 elements:
    • useful: 80 B
    • total: 120 B
  • empty:
    • useful: 16 B
    • total: 32 B

std::map:

  • 8 elements:
    • useful: 432 B
    • total: 512 B
  • empty:
    • useful: 48 B
    • total: 64 B
Template Parameters
Tmapped type
Indunsigned integer type, used to map integer indices to internal indices that index into the memory block that stores the mapped values
Numgives range of valid indices, i.e., the valid indices are {0, ..., Num-1}, must satisfy Num * num_bits(Num-1) + Num < sizeof(Ind) * 8, with num_bits(n) denoting the minimum number of bits required to represent integer n

Definition at line 107 of file small_map.h.

Member Typedef Documentation

◆ index_fieldt

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
typedef Ind small_mapt< T, Ind, Num >::index_fieldt
private

Definition at line 115 of file small_map.h.

◆ value_type

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
typedef std::pair<const unsigned, const T &> small_mapt< T, Ind, Num >::value_type

Definition at line 287 of file small_map.h.

Constructor & Destructor Documentation

◆ small_mapt() [1/2]

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
small_mapt< T, Ind, Num >::small_mapt ( )
inline

◆ small_mapt() [2/2]

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
small_mapt< T, Ind, Num >::small_mapt ( const small_mapt< T, Ind, Num > &  m)
inline

Definition at line 172 of file small_map.h.

◆ ~small_mapt()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
small_mapt< T, Ind, Num >::~small_mapt ( )
inline

Definition at line 187 of file small_map.h.

Member Function Documentation

◆ allocate() [1/2]

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
T* small_mapt< T, Ind, Num >::allocate ( std::size_t  n) const
inlineprivate

◆ allocate() [2/2]

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
T* small_mapt< T, Ind, Num >::allocate ( T *  ptr,
std::size_t  n 
) const
inlineprivate

Definition at line 144 of file small_map.h.

◆ begin()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const_iterator small_mapt< T, Ind, Num >::begin ( ) const
inline

Definition at line 368 of file small_map.h.

◆ copy()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
void small_mapt< T, Ind, Num >::copy ( T *  dest,
const T *  src,
std::size_t  n 
) const
inlineprivate

◆ copy_and_erase()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
small_mapt* small_mapt< T, Ind, Num >::copy_and_erase ( std::size_t  idx) const
inline

Definition at line 515 of file small_map.h.

◆ copy_and_insert()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
small_mapt* small_mapt< T, Ind, Num >::copy_and_insert ( std::size_t  idx,
const T &  value 
) const
inline

Definition at line 549 of file small_map.h.

◆ empty()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
bool small_mapt< T, Ind, Num >::empty ( ) const
inline

◆ end()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const_iterator small_mapt< T, Ind, Num >::end ( ) const
inline

◆ erase()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
std::size_t small_mapt< T, Ind, Num >::erase ( std::size_t  idx)
inline

◆ find()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const_iterator small_mapt< T, Ind, Num >::find ( std::size_t  idx) const
inline

◆ get_field()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
unsigned small_mapt< T, Ind, Num >::get_field ( std::size_t  field) const
inlineprivate

◆ operator[]()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
T& small_mapt< T, Ind, Num >::operator[] ( std::size_t  idx)
inline

Definition at line 443 of file small_map.h.

◆ set_field()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
void small_mapt< T, Ind, Num >::set_field ( std::size_t  field,
unsigned  v 
)
inlineprivate

◆ shift_indices()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
void small_mapt< T, Ind, Num >::shift_indices ( std::size_t  ii)
inlineprivate

◆ size()

◆ value_begin()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const_value_iterator small_mapt< T, Ind, Num >::value_begin ( ) const
inline

Definition at line 431 of file small_map.h.

◆ value_end()

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const_value_iterator small_mapt< T, Ind, Num >::value_end ( ) const
inline

Definition at line 436 of file small_map.h.

Friends And Related Function Documentation

◆ small_map_test

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
void small_map_test ( )
friend

Member Data Documentation

◆ BITS

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const std::size_t small_mapt< T, Ind, Num >::BITS = num_bitst<NUM - 1>::value + 1
staticprivate

◆ IND

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const index_fieldt small_mapt< T, Ind, Num >::IND = indicator_maskt<index_fieldt, BITS>::value
staticprivate

Definition at line 218 of file small_map.h.

Referenced by small_mapt< innert >::size().

◆ ind

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
index_fieldt small_mapt< T, Ind, Num >::ind
private

◆ MASK

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const index_fieldt small_mapt< T, Ind, Num >::MASK = ((index_fieldt)1 << BITS) - 1
staticprivate

◆ N_BITS

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const std::size_t small_mapt< T, Ind, Num >::N_BITS = std::numeric_limits<index_fieldt>::digits
staticprivate

Definition at line 205 of file small_map.h.

◆ NUM

◆ p

◆ S_BITS

template<typename T, typename Ind = uint32_t, std::size_t Num = 8>
const std::size_t small_mapt< T, Ind, Num >::S_BITS = NUM * num_bitst<NUM - 1>::value + NUM
staticprivate

Definition at line 214 of file small_map.h.

Referenced by small_mapt< innert >::shift_indices().


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