cprover
small_map.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Small map
4 
5 Author: Daniel Poetzl
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_UTIL_SMALL_MAP_H
13 #define CPROVER_UTIL_SMALL_MAP_H
14 
15 #include <bitset>
16 #include <cstdint>
17 #include <cstring>
18 #include <limits>
19 #include <memory>
20 #include <new>
21 #include <type_traits>
22 #include <utility>
23 
24 #include "invariant.h"
25 
26 //#define _SMALL_MAP_REALLOC_STATS
27 
28 // The following templates are used by the class below to compute parameters at
29 // compilation time. When having a compiler that supports constexpr, the
30 // parameters are computed via static methods defined within the class.
31 #if !defined(__GNUC__) && _MSC_VER < 1900
32 
33 template <std::size_t N>
34 struct num_bitst
35 {
36  static const std::size_t value = 1 + num_bitst<(N >> 1)>::value;
37 };
38 
39 template <>
40 struct num_bitst<1>
41 {
42  static const std::size_t value = 1;
43 };
44 
45 template <>
46 struct num_bitst<0>
47 {
48  static const std::size_t value = 1;
49 };
50 
51 template <typename T, std::size_t B, typename U = std::integral_constant<T, 1>>
53 {
54  static const T value =
55  U::value |
56  indicator_maskt<T, B, std::integral_constant<T, (U::value << B)>>::value;
57 };
58 
59 template <typename T, std::size_t B>
60 struct indicator_maskt<T, B, std::integral_constant<T, 0>>
61 {
62  static const T value = 0;
63 };
64 
65 #endif
66 
106 template <typename T, typename Ind = uint32_t, std::size_t Num = 8>
108 {
109 public:
110  small_mapt() : ind(0), p(nullptr)
111  {
112  }
113 
114 private:
115  static_assert(std::is_unsigned<Ind>::value, "");
116 
117  typedef Ind index_fieldt;
118 
119  friend void small_map_test();
120 
121  // Memory
122 
123  void copy(T *dest, const T *src, std::size_t n) const
124  {
125  for(std::size_t i = 0; i < n; i++)
126  {
127  new(dest + i) T(*(src + i));
128  }
129  }
130 
131  T *allocate(std::size_t n) const
132  {
133  if(n == 0)
134  return nullptr;
135 
136  T *mem = (T *)malloc(sizeof(T) * n);
137 
138  if(!mem)
139  throw std::bad_alloc();
140 
141  return mem;
142  }
143 
144  T *allocate(T *ptr, std::size_t n) const
145  {
146  if(n == 0)
147  return nullptr;
148 
149  // explicitly cast to char * as GCC 8 warns about not using new/delete for
150  // class sharing_node_innert<dstringt, std::basic_string<char>,
151  // std::equal_to<dstringt> >
152  T *mem = (T *)realloc((char *)ptr, sizeof(T) * n);
153 
154  if(!mem)
155  throw std::bad_alloc();
156 
157 #ifdef _SMALL_MAP_REALLOC_STATS
158  if(ptr == mem)
159  {
160  realloc_success++;
161  }
162  else if(ptr != nullptr)
163  {
164  realloc_failure++;
165  }
166 #endif
167 
168  return mem;
169  }
170 
171 public:
172  small_mapt(const small_mapt &m) : ind(m.ind), p(m.p)
173  {
174  if(m.p == nullptr)
175  {
176  return;
177  }
178 
179  const std::size_t n = m.size();
180  INVARIANT(n > 0, "size is > 0 if data pointer is non-null");
181 
182  p = allocate(n);
183 
184  copy(p, m.p, n);
185  }
186 
188  {
189  if(p)
190  {
191  std::size_t n = size();
192 
193  for(std::size_t i = 0; i < n; i++)
194  {
195  (p + i)->~T();
196  }
197 
198  free(p);
199  }
200  }
201 
202 private:
203  // Derived config
204 
205  static const std::size_t N_BITS = std::numeric_limits<index_fieldt>::digits;
206 
207  static const std::size_t NUM = Num;
208 
209  static_assert(NUM >= 2, "");
210 
211 // When we don't have constexpr
212 #if !defined(__GNUC__) && _MSC_VER < 1900
213 
214  static const std::size_t S_BITS = NUM * num_bitst<NUM - 1>::value + NUM;
215 
216  static const std::size_t BITS = num_bitst<NUM - 1>::value + 1;
217 
219 
220 #else
221 
222  static constexpr std::size_t num_bits(const std::size_t n)
223  {
224  return n < 2 ? 1 : 1 + num_bits(n >> 1);
225  }
226 
227  static constexpr std::size_t S_BITS = NUM * num_bits(NUM - 1) + NUM;
228 
229  static const std::size_t BITS = num_bits(NUM - 1) + 1;
230 
231  static constexpr index_fieldt indicator_mask(const index_fieldt digit = 1)
232  {
233  return !digit ? 0 : digit | indicator_mask(digit << BITS);
234  }
235 
236  static const index_fieldt IND = indicator_mask();
237 
238 #endif
239 
240  static const index_fieldt MASK = ((index_fieldt)1 << BITS) - 1;
241 
242  static_assert(S_BITS <= N_BITS, "");
243 
244  static_assert(std::numeric_limits<unsigned>::digits >= BITS, "");
245 
246  // Internal
247 
248  unsigned get_field(std::size_t field) const
249  {
250  PRECONDITION(field < NUM);
251 
252  unsigned shift = field * BITS;
253  return (ind & (MASK << shift)) >> shift;
254  }
255 
256  void set_field(std::size_t field, unsigned v)
257  {
258  PRECONDITION(field < NUM);
259  PRECONDITION((std::size_t)(v >> 1) < NUM);
260 
261  unsigned shift = field * BITS;
262 
263  ind &= ~((index_fieldt)MASK << shift);
264  ind |= v << shift;
265  }
266 
267  void shift_indices(std::size_t ii)
268  {
269  for(std::size_t idx = 0; idx < S_BITS / BITS; idx++)
270  {
271  unsigned v = get_field(idx);
272  if(v & 1)
273  {
274  v >>= 1;
275  if(v > ii)
276  {
277  v = ((v - 1) << 1) | 1;
278  set_field(idx, v);
279  }
280  }
281  }
282  }
283 
284 public:
285  // Standard const iterator
286 
287  typedef std::pair<const unsigned, const T &> value_type;
288 
293  {
294  public:
295  explicit const_iterator(const small_mapt &m) : m(m), idx(0), ii(0)
296  {
297  find_next();
298  }
299 
301  const small_mapt &m,
302  const std::size_t idx,
303  const std::size_t ii)
304  : m(m), idx(idx), ii(ii)
305  {
306  }
307 
308  const value_type operator*() const
309  {
310  return value_type(idx, *(m.p + ii));
311  }
312 
313  const std::shared_ptr<value_type> operator->() const
314  {
315  return std::make_shared<value_type>(idx, *(m.p + ii));
316  }
317 
319  {
320  idx++;
321  find_next();
322 
323  return *this;
324  }
325 
327  {
328  std::size_t old_idx = idx;
329  std::size_t old_ii = ii;
330 
331  idx++;
332  find_next();
333 
334  return const_iterator(m, old_idx, old_ii);
335  }
336 
337  bool operator==(const const_iterator &other) const
338  {
339  return idx == other.idx;
340  }
341 
342  bool operator!=(const const_iterator &other) const
343  {
344  return idx != other.idx;
345  }
346 
347  private:
348  void find_next()
349  {
350  while(idx < NUM)
351  {
352  unsigned v = m.get_field(idx);
353  if(v & 1)
354  {
355  ii = v >> 1;
356  break;
357  }
358 
359  idx++;
360  }
361  }
362 
363  const small_mapt &m;
364  std::size_t idx;
365  std::size_t ii;
366  };
367 
368  const_iterator begin() const
369  {
370  return const_iterator(*this);
371  }
372 
373  const_iterator end() const
374  {
375  return const_iterator(*this, NUM, 0);
376  }
377 
384  {
385  public:
386  const_value_iterator(const small_mapt &m, const int ii) : m(m), ii(ii)
387  {
388  }
389 
390  const T &operator*() const
391  {
392  return *(m.p + ii);
393  }
394 
395  const T *operator->() const
396  {
397  return m.p + ii;
398  }
399 
401  {
402  ii--;
403 
404  return *this;
405  }
406 
408  {
409  int old_ii = ii;
410 
411  ii--;
412 
413  return const_value_iterator(m, old_ii);
414  }
415 
416  bool operator==(const const_value_iterator &other) const
417  {
418  return ii == other.ii;
419  }
420 
421  bool operator!=(const const_value_iterator &other) const
422  {
423  return ii != other.ii;
424  }
425 
426  private:
427  const small_mapt &m;
428  int ii;
429  };
430 
431  const_value_iterator value_begin() const
432  {
433  return const_value_iterator(*this, size() - 1);
434  }
435 
436  const_value_iterator value_end() const
437  {
438  return const_value_iterator(*this, -1);
439  }
440 
441  // Interface
442 
443  T &operator[](std::size_t idx)
444  {
445  PRECONDITION(idx < NUM);
446 
447  unsigned v = get_field(idx);
448  if(v & 1)
449  {
450  std::size_t ii = v >> 1;
451  return *(p + ii);
452  }
453 
454  std::size_t ii = size();
455  p = allocate(p, ii + 1);
456  new(p + ii) T();
457 
458  v = (ii << 1) | 1;
459  set_field(idx, v);
460 
461  return *(p + ii);
462  }
463 
464  const_iterator find(std::size_t idx) const
465  {
466  PRECONDITION(idx < NUM);
467 
468  unsigned v = get_field(idx);
469  if(v & 1)
470  {
471  std::size_t ii = v >> 1;
472  return const_iterator(*this, idx, ii);
473  }
474 
475  return end();
476  }
477 
478  std::size_t erase(std::size_t idx)
479  {
480  PRECONDITION(idx < NUM);
481 
482  unsigned v = get_field(idx);
483 
484  if(v & 1)
485  {
486  std::size_t ii = v >> 1;
487 
488  (p + ii)->~T();
489  std::size_t n = size();
490  if(ii < n - 1)
491  {
492  // explicitly cast to char * as GCC 8 warns about not using new/delete
493  // for
494  // class sharing_node_innert<dstringt, std::basic_string<char>,
495  // std::equal_to<dstringt> >
496  memmove((char *)(p + ii), p + ii + 1, sizeof(T) * (n - ii - 1));
497  }
498 
499  p = allocate(p, n - 1);
500 
501  if(n == 1)
502  {
503  p = nullptr;
504  }
505 
506  set_field(idx, 0);
507  shift_indices(ii);
508 
509  return 1;
510  }
511 
512  return 0;
513  }
514 
515  small_mapt *copy_and_erase(std::size_t idx) const
516  {
517  PRECONDITION(idx < NUM);
518 
519  unsigned v = get_field(idx);
520  INVARIANT(v & 1, "element must be in map");
521 
522  std::size_t ii = v >> 1;
523  std::size_t n = size();
524 
525  // new map
526 
527  small_mapt *m = new small_mapt();
528 
529  if(n == 1)
530  {
531  return m;
532  }
533 
534  m->p = allocate(n - 1);
535 
536  // copy part before erased element
537  copy(m->p, p, ii);
538 
539  // copy part after erased element
540  copy(m->p + ii, p + ii + 1, n - ii - 1);
541 
542  m->ind = ind;
543  m->set_field(idx, 0);
544  m->shift_indices(ii);
545 
546  return m;
547  }
548 
549  small_mapt *copy_and_insert(std::size_t idx, const T &value) const
550  {
551  PRECONDITION(idx < NUM);
552 
553  unsigned v = get_field(idx);
554  INVARIANT(!(v & 1), "element must not be in map");
555 
556  std::size_t n = size();
557  std::size_t ii = n;
558 
559  small_mapt *m = new small_mapt();
560 
561  m->p = allocate(n + 1);
562 
563  // copy old elements
564  copy(m->p, p, n);
565 
566  // new element
567  new(m->p + ii) T(value);
568 
569  m->ind = ind;
570  v = (ii << 1) | 1;
571  m->set_field(idx, v);
572 
573  return m;
574  }
575 
576  std::size_t size() const
577  {
578  std::bitset<N_BITS> bs(ind & IND);
579  return bs.count();
580  }
581 
582  bool empty() const
583  {
584  return !ind;
585  }
586 
587 #ifdef _SMALL_MAP_REALLOC_STATS
588  mutable std::size_t realloc_failure = 0;
589  mutable std::size_t realloc_success = 0;
590 #endif
591 
592 private:
594  T *p;
595 };
596 
597 #endif
small_mapt::allocate
T * allocate(T *ptr, std::size_t n) const
Definition: small_map.h:144
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:438
small_mapt::const_value_iterator::ii
int ii
Definition: small_map.h:428
small_mapt::IND
static const index_fieldt IND
Definition: small_map.h:218
small_mapt::shift_indices
void shift_indices(std::size_t ii)
Definition: small_map.h:267
small_mapt::const_iterator::const_iterator
const_iterator(const small_mapt &m, const std::size_t idx, const std::size_t ii)
Definition: small_map.h:300
small_mapt::ind
index_fieldt ind
Definition: small_map.h:593
small_mapt::const_value_iterator::operator++
const_value_iterator operator++()
Definition: small_map.h:400
small_mapt::const_value_iterator::operator->
const T * operator->() const
Definition: small_map.h:395
small_mapt::NUM
static const std::size_t NUM
Definition: small_map.h:207
small_mapt::end
const_iterator end() const
Definition: small_map.h:373
small_mapt::erase
std::size_t erase(std::size_t idx)
Definition: small_map.h:478
small_mapt::const_value_iterator
Const value iterator.
Definition: small_map.h:383
small_mapt::const_value_iterator::operator*
const T & operator*() const
Definition: small_map.h:390
invariant.h
small_mapt::S_BITS
static const std::size_t S_BITS
Definition: small_map.h:214
indicator_maskt::value
static const T value
Definition: small_map.h:54
small_mapt::small_mapt
small_mapt(const small_mapt &m)
Definition: small_map.h:172
small_mapt::const_iterator::operator->
const std::shared_ptr< value_type > operator->() const
Definition: small_map.h:313
small_mapt::BITS
static const std::size_t BITS
Definition: small_map.h:216
small_mapt::const_iterator::ii
std::size_t ii
Definition: small_map.h:365
small_mapt::const_value_iterator::operator==
bool operator==(const const_value_iterator &other) const
Definition: small_map.h:416
small_mapt::copy_and_erase
small_mapt * copy_and_erase(std::size_t idx) const
Definition: small_map.h:515
small_mapt::const_iterator::idx
std::size_t idx
Definition: small_map.h:364
small_mapt::const_iterator::operator!=
bool operator!=(const const_iterator &other) const
Definition: small_map.h:342
small_mapt::empty
bool empty() const
Definition: small_map.h:582
small_mapt::const_iterator::operator*
const value_type operator*() const
Definition: small_map.h:308
small_mapt::get_field
unsigned get_field(std::size_t field) const
Definition: small_map.h:248
small_mapt::copy_and_insert
small_mapt * copy_and_insert(std::size_t idx, const T &value) const
Definition: small_map.h:549
small_mapt::value_end
const_value_iterator value_end() const
Definition: small_map.h:436
small_mapt::value_type
std::pair< const unsigned, const T & > value_type
Definition: small_map.h:287
small_mapt::operator[]
T & operator[](std::size_t idx)
Definition: small_map.h:443
malloc
void * malloc(size_t)
small_mapt
Map from small integers to values.
Definition: small_map.h:107
small_mapt::const_iterator::operator==
bool operator==(const const_iterator &other) const
Definition: small_map.h:337
small_mapt::set_field
void set_field(std::size_t field, unsigned v)
Definition: small_map.h:256
small_mapt::MASK
static const index_fieldt MASK
Definition: small_map.h:240
small_mapt::N_BITS
static const std::size_t N_BITS
Definition: small_map.h:205
small_mapt::const_value_iterator::operator++
const_value_iterator operator++(int)
Definition: small_map.h:407
small_mapt::allocate
T * allocate(std::size_t n) const
Definition: small_map.h:131
small_mapt::const_value_iterator::const_value_iterator
const_value_iterator(const small_mapt &m, const int ii)
Definition: small_map.h:386
small_mapt::copy
void copy(T *dest, const T *src, std::size_t n) const
Definition: small_map.h:123
small_mapt::size
std::size_t size() const
Definition: small_map.h:576
num_bitst
Definition: small_map.h:34
small_mapt::const_iterator::operator++
const_iterator operator++(int)
Definition: small_map.h:326
small_mapt::value_begin
const_value_iterator value_begin() const
Definition: small_map.h:431
small_mapt::const_iterator
Const iterator.
Definition: small_map.h:292
small_mapt::small_mapt
small_mapt()
Definition: small_map.h:110
small_mapt::begin
const_iterator begin() const
Definition: small_map.h:368
small_mapt::const_value_iterator::operator!=
bool operator!=(const const_value_iterator &other) const
Definition: small_map.h:421
small_mapt::~small_mapt
~small_mapt()
Definition: small_map.h:187
small_mapt::const_value_iterator::m
const small_mapt & m
Definition: small_map.h:427
small_mapt::small_map_test
friend void small_map_test()
small_mapt::index_fieldt
Ind index_fieldt
Definition: small_map.h:115
small_mapt::const_iterator::const_iterator
const_iterator(const small_mapt &m)
Definition: small_map.h:295
small_mapt::const_iterator::operator++
const_iterator operator++()
Definition: small_map.h:318
small_mapt::const_iterator::m
const small_mapt & m
Definition: small_map.h:363
num_bitst::value
static const std::size_t value
Definition: small_map.h:36
small_mapt::p
T * p
Definition: small_map.h:594
free
void free(void *)
small_mapt::const_iterator::find_next
void find_next()
Definition: small_map.h:348
indicator_maskt
Definition: small_map.h:52
validation_modet::INVARIANT
small_mapt::find
const_iterator find(std::size_t idx) const
Definition: small_map.h:464