12 #ifndef CPROVER_UTIL_SMALL_MAP_H 13 #define CPROVER_UTIL_SMALL_MAP_H 21 #include <type_traits> 31 #if !defined(__GNUC__) && _MSC_VER < 1900 33 template <std::
size_t N>
42 static const std::size_t
value = 1;
48 static const std::size_t
value = 1;
51 template <
typename T, std::
size_t B,
typename U = std::
integral_constant<T, 1>>
59 template <
typename T, std::
size_t B>
106 template <
typename T,
typename Ind = u
int32_t, std::
size_t Num = 8>
115 static_assert(std::is_unsigned<Ind>::value,
"");
123 void copy(T *dest,
const T *src, std::size_t n)
const 125 for(std::size_t i = 0; i < n; i++)
127 new(dest + i) T(*(src + i));
136 T *mem = (T *)
malloc(
sizeof(T) * n);
139 throw std::bad_alloc();
152 T *mem = (T *)realloc((
char *)ptr,
sizeof(T) * n);
155 throw std::bad_alloc();
157 #ifdef _SMALL_MAP_REALLOC_STATS 162 else if(ptr !=
nullptr)
179 const std::size_t n = m.
size();
180 INVARIANT(n > 0,
"size is > 0 if data pointer is non-null");
191 std::size_t n =
size();
193 for(std::size_t i = 0; i < n; i++)
205 static const std::size_t
N_BITS = std::numeric_limits<index_fieldt>::digits;
207 static const std::size_t
NUM = Num;
209 static_assert(
NUM >= 2,
"");
212 #if !defined(__GNUC__) && _MSC_VER < 1900 222 static constexpr std::size_t num_bits(
const std::size_t n)
224 return n < 2 ? 1 : 1 + num_bits(n >> 1);
229 static const std::size_t
BITS = num_bits(
NUM - 1) + 1;
233 return !digit ? 0 : digit | indicator_mask(digit <<
BITS);
244 static_assert(std::numeric_limits<unsigned>::digits >=
BITS,
"");
252 unsigned shift = field *
BITS;
253 return (
ind & (
MASK << shift)) >> shift;
261 unsigned shift = field *
BITS;
269 for(std::size_t idx = 0; idx <
S_BITS /
BITS; idx++)
277 v = ((v - 1) << 1) | 1;
302 const std::size_t
idx,
303 const std::size_t
ii)
315 return std::make_shared<value_type>(
idx, *(
m.
p +
ii));
328 std::size_t old_idx =
idx;
329 std::size_t old_ii =
ii;
370 return const_iterator(*
this);
373 const_iterator
end()
const 375 return const_iterator(*
this,
NUM, 0);
418 return ii == other.
ii;
423 return ii != other.
ii;
433 return const_value_iterator(*
this,
size() - 1);
438 return const_value_iterator(*
this, -1);
450 std::size_t ii = v >> 1;
454 std::size_t ii =
size();
464 const_iterator
find(std::size_t idx)
const 471 std::size_t ii = v >> 1;
472 return const_iterator(*
this, idx, ii);
486 std::size_t ii = v >> 1;
489 std::size_t n =
size();
496 memmove((
char *)(
p + ii),
p + ii + 1,
sizeof(T) * (n - ii - 1));
520 INVARIANT(v & 1,
"element must be in map");
522 std::size_t ii = v >> 1;
523 std::size_t n =
size();
540 copy(m->
p + ii,
p + ii + 1, n - ii - 1);
554 INVARIANT(!(v & 1),
"element must not be in map");
556 std::size_t n =
size();
567 new(m->
p + ii) T(value);
578 std::bitset<N_BITS> bs(
ind &
IND);
587 #ifdef _SMALL_MAP_REALLOC_STATS 588 mutable std::size_t realloc_failure = 0;
589 mutable std::size_t realloc_success = 0;
const_value_iterator operator++(int)
bool operator==(const const_value_iterator &other) const
static const index_fieldt IND
const T & operator*() const
void shift_indices(std::size_t ii)
static const std::size_t N_BITS
bool operator==(const const_iterator &other) const
const value_type operator*() const
T * allocate(std::size_t n) const
friend void small_map_test()
const_iterator begin() const
T * allocate(T *ptr, std::size_t n) const
const_iterator end() const
const_iterator find(std::size_t idx) const
const std::shared_ptr< value_type > operator->() const
std::size_t erase(std::size_t idx)
static const std::size_t S_BITS
const_value_iterator operator++()
const T * operator->() const
#define PRECONDITION(CONDITION)
static const std::size_t NUM
static const index_fieldt MASK
bool operator!=(const const_iterator &other) const
small_mapt * copy_and_erase(std::size_t idx) const
void set_field(std::size_t field, unsigned v)
const_value_iterator value_begin() const
const_iterator(const small_mapt &m, const std::size_t idx, const std::size_t ii)
void copy(T *dest, const T *src, std::size_t n) const
const_iterator(const small_mapt &m)
bool operator!=(const const_value_iterator &other) const
unsigned get_field(std::size_t field) const
static const std::size_t value
const_iterator operator++(int)
static const std::size_t BITS
small_mapt(const small_mapt &m)
small_mapt * copy_and_insert(std::size_t idx, const T &value) const
std::pair< const unsigned, const T & > value_type
const_iterator operator++()
T & operator[](std::size_t idx)
const_value_iterator value_end() const
const_value_iterator(const small_mapt &m, const int ii)
Map from small integers to values.