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 
67 template <typename T, typename Ind = uint32_t, std::size_t Num = 8>
69 {
70 public:
71  small_mapt() : ind(0), p(nullptr)
72  {
73  }
74 
75 private:
76  static_assert(std::is_unsigned<Ind>::value, "Ind should be an unsigned type");
77 
78  typedef Ind index_fieldt;
79 
80  friend void small_map_test();
81 
82  // Memory
83 
84  void copy(T *dest, const T *src, std::size_t n) const
85  {
86  for(std::size_t i = 0; i < n; i++)
87  {
88  new(dest + i) T(*(src + i));
89  }
90  }
91 
92  T *allocate(std::size_t n) const
93  {
94  if(n == 0)
95  return nullptr;
96 
97  T *mem = (T *)malloc(sizeof(T) * n);
98 
99  if(!mem)
100  throw std::bad_alloc();
101 
102  return mem;
103  }
104 
105  T *allocate(T *ptr, std::size_t n) const
106  {
107  if(n == 0)
108  return nullptr;
109 
110  // explicitly cast to char * as GCC 8 warns about not using new/delete for
111  // class sharing_node_innert<dstringt, std::basic_string<char>,
112  // std::equal_to<dstringt> >
113  T *mem = (T *)realloc((char *)ptr, sizeof(T) * n);
114 
115  if(!mem)
116  throw std::bad_alloc();
117 
118 #ifdef _SMALL_MAP_REALLOC_STATS
119  if(ptr == mem)
120  {
121  realloc_success++;
122  }
123  else if(ptr != nullptr)
124  {
125  realloc_failure++;
126  }
127 #endif
128 
129  return mem;
130  }
131 
132 public:
133  small_mapt(const small_mapt &m) : ind(m.ind), p(m.p)
134  {
135  if(m.p == nullptr)
136  {
137  return;
138  }
139 
140  const std::size_t n = m.size();
141  INVARIANT(n > 0, "size is > 0 if data pointer is non-null");
142 
143  p = allocate(n);
144 
145  copy(p, m.p, n);
146  }
147 
149  {
150  if(p)
151  {
152  std::size_t n = size();
153 
154  for(std::size_t i = 0; i < n; i++)
155  {
156  (p + i)->~T();
157  }
158 
159  free(p);
160  }
161  }
162 
163 private:
164  // Derived config
165 
166  static const std::size_t N_BITS = std::numeric_limits<index_fieldt>::digits;
167 
168  static const std::size_t NUM = Num;
169 
170  static_assert(NUM >= 2, "NUM should be at least 2");
171 
172  static constexpr std::size_t num_bits(const std::size_t n)
173  {
174  return n < 2 ? 1 : 1 + num_bits(n >> 1);
175  }
176 
177  static constexpr std::size_t S_BITS = NUM * num_bits(NUM - 1) + NUM;
178 
179  static const std::size_t BITS = num_bits(NUM - 1) + 1;
180 
181  static constexpr index_fieldt indicator_mask(const index_fieldt digit = 1)
182  {
183  return !digit ? 0 : digit | indicator_mask(digit << BITS);
184  }
185 
186  static const index_fieldt IND = indicator_mask();
187 
188  static const index_fieldt MASK = ((index_fieldt)1 << BITS) - 1;
189 
190  static_assert(S_BITS <= N_BITS, "S_BITS should be no larger than N_BITS");
191 
192  static_assert(
193  std::numeric_limits<std::size_t>::digits >= BITS,
194  "BITS must fit into an unsigned");
195 
196  // Internal
197 
198  std::size_t get_field(std::size_t field) const
199  {
200  PRECONDITION(field < NUM);
201 
202  std::size_t shift = field * BITS;
203  return (ind & (MASK << shift)) >> shift;
204  }
205 
206  void set_field(std::size_t field, std::size_t v)
207  {
208  PRECONDITION(field < NUM);
209  PRECONDITION((std::size_t)(v >> 1) < NUM);
210 
211  std::size_t shift = field * BITS;
212 
213  ind &= ~((index_fieldt)MASK << shift);
214  ind |= (index_fieldt)v << shift;
215  }
216 
217  void shift_indices(std::size_t ii)
218  {
219  for(std::size_t idx = 0; idx < S_BITS / BITS; idx++)
220  {
221  std::size_t v = get_field(idx);
222  if(v & 1)
223  {
224  v >>= 1;
225  if(v > ii)
226  {
227  v = ((v - 1) << 1) | 1;
228  set_field(idx, v);
229  }
230  }
231  }
232  }
233 
234 public:
235  // Standard const iterator
236 
237  typedef std::pair<const std::size_t, const T &> valuet;
238 
243  {
244  public:
245  explicit const_iterator(const small_mapt &m) : m(m), idx(0), ii(0)
246  {
247  find_next();
248  }
249 
251  const small_mapt &m,
252  const std::size_t idx,
253  const std::size_t ii)
254  : m(m), idx(idx), ii(ii)
255  {
256  }
257 
258  const valuet operator*() const
259  {
260  return valuet(idx, *(m.p + ii));
261  }
262 
263  const std::shared_ptr<valuet> operator->() const
264  {
265  return std::make_shared<valuet>(idx, *(m.p + ii));
266  }
267 
269  {
270  idx++;
271  find_next();
272 
273  return *this;
274  }
275 
277  {
278  std::size_t old_idx = idx;
279  std::size_t old_ii = ii;
280 
281  idx++;
282  find_next();
283 
284  return const_iterator(m, old_idx, old_ii);
285  }
286 
287  bool operator==(const const_iterator &other) const
288  {
289  return idx == other.idx;
290  }
291 
292  bool operator!=(const const_iterator &other) const
293  {
294  return idx != other.idx;
295  }
296 
297  private:
298  void find_next()
299  {
300  while(idx < NUM)
301  {
302  std::size_t v = m.get_field(idx);
303  if(v & 1)
304  {
305  ii = v >> 1;
306  break;
307  }
308 
309  idx++;
310  }
311  }
312 
313  const small_mapt &m;
314  std::size_t idx;
315  std::size_t ii;
316  };
317 
318  const_iterator begin() const
319  {
320  return const_iterator(*this);
321  }
322 
323  const_iterator end() const
324  {
325  return const_iterator(*this, NUM, 0);
326  }
327 
334  {
335  public:
336  const_value_iterator(const small_mapt &m, const int ii) : m(m), ii(ii)
337  {
338  }
339 
340  const T &operator*() const
341  {
342  return *(m.p + ii);
343  }
344 
345  const T *operator->() const
346  {
347  return m.p + ii;
348  }
349 
351  {
352  ii--;
353 
354  return *this;
355  }
356 
358  {
359  int old_ii = ii;
360 
361  ii--;
362 
363  return const_value_iterator(m, old_ii);
364  }
365 
366  bool operator==(const const_value_iterator &other) const
367  {
368  return ii == other.ii;
369  }
370 
371  bool operator!=(const const_value_iterator &other) const
372  {
373  return ii != other.ii;
374  }
375 
376  private:
377  const small_mapt &m;
378  int ii;
379  };
380 
381  const_value_iterator value_begin() const
382  {
383  return const_value_iterator(*this, size() - 1);
384  }
385 
386  const_value_iterator value_end() const
387  {
388  return const_value_iterator(*this, -1);
389  }
390 
391  // Interface
392 
393  T &operator[](std::size_t idx)
394  {
395  PRECONDITION(idx < NUM);
396 
397  std::size_t v = get_field(idx);
398  if(v & 1)
399  {
400  std::size_t ii = v >> 1;
401  return *(p + ii);
402  }
403 
404  std::size_t ii = size();
405  p = allocate(p, ii + 1);
406  new(p + ii) T();
407 
408  v = (ii << 1) | 1;
409  set_field(idx, v);
410 
411  return *(p + ii);
412  }
413 
414  const_iterator find(std::size_t idx) const
415  {
416  PRECONDITION(idx < NUM);
417 
418  std::size_t v = get_field(idx);
419  if(v & 1)
420  {
421  std::size_t ii = v >> 1;
422  return const_iterator(*this, idx, ii);
423  }
424 
425  return end();
426  }
427 
428  std::size_t erase(std::size_t idx)
429  {
430  PRECONDITION(idx < NUM);
431 
432  std::size_t v = get_field(idx);
433 
434  if(v & 1)
435  {
436  std::size_t ii = v >> 1;
437 
438  (p + ii)->~T();
439  std::size_t n = size();
440  if(ii < n - 1)
441  {
442  // explicitly cast to char * as GCC 8 warns about not using new/delete
443  // for
444  // class sharing_node_innert<dstringt, std::basic_string<char>,
445  // std::equal_to<dstringt> >
446  memmove((char *)(p + ii), p + ii + 1, sizeof(T) * (n - ii - 1));
447  }
448 
449  p = allocate(p, n - 1);
450 
451  if(n == 1)
452  {
453  p = nullptr;
454  }
455 
456  set_field(idx, 0);
457  shift_indices(ii);
458 
459  return 1;
460  }
461 
462  return 0;
463  }
464 
465  small_mapt *copy_and_erase(std::size_t idx) const
466  {
467  PRECONDITION(idx < NUM);
468 
469  std::size_t v = get_field(idx);
470  INVARIANT(v & 1, "element must be in map");
471 
472  std::size_t ii = v >> 1;
473  std::size_t n = size();
474 
475  // new map
476 
477  small_mapt *m = new small_mapt();
478 
479  if(n == 1)
480  {
481  return m;
482  }
483 
484  m->p = allocate(n - 1);
485 
486  // copy part before erased element
487  copy(m->p, p, ii);
488 
489  // copy part after erased element
490  copy(m->p + ii, p + ii + 1, n - ii - 1);
491 
492  m->ind = ind;
493  m->set_field(idx, 0);
494  m->shift_indices(ii);
495 
496  return m;
497  }
498 
499  small_mapt *copy_and_insert(std::size_t idx, const T &value) const
500  {
501  PRECONDITION(idx < NUM);
502 
503  std::size_t v = get_field(idx);
504  INVARIANT(!(v & 1), "element must not be in map");
505 
506  std::size_t n = size();
507  std::size_t ii = n;
508 
509  small_mapt *m = new small_mapt();
510 
511  m->p = allocate(n + 1);
512 
513  // copy old elements
514  copy(m->p, p, n);
515 
516  // new element
517  new(m->p + ii) T(value);
518 
519  m->ind = ind;
520  v = (ii << 1) | 1;
521  m->set_field(idx, v);
522 
523  return m;
524  }
525 
526  std::size_t size() const
527  {
528  std::bitset<N_BITS> bs(ind & IND);
529  return bs.count();
530  }
531 
532  bool empty() const
533  {
534  return !ind;
535  }
536 
537 #ifdef _SMALL_MAP_REALLOC_STATS
538  mutable std::size_t realloc_failure = 0;
539  mutable std::size_t realloc_success = 0;
540 #endif
541 
542 private:
544  T *p;
545 };
546 
547 #endif
small_mapt::allocate
T * allocate(T *ptr, std::size_t n) const
Definition: small_map.h:105
small_mapt::set_field
void set_field(std::size_t field, std::size_t v)
Definition: small_map.h:206
small_mapt::const_value_iterator::ii
int ii
Definition: small_map.h:378
small_mapt::IND
static const index_fieldt IND
Definition: small_map.h:186
small_mapt::const_iterator::operator*
const valuet operator*() const
Definition: small_map.h:258
small_mapt::shift_indices
void shift_indices(std::size_t ii)
Definition: small_map.h:217
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:250
small_mapt::ind
index_fieldt ind
Definition: small_map.h:543
small_mapt::const_value_iterator::operator++
const_value_iterator operator++()
Definition: small_map.h:350
small_mapt::const_value_iterator::operator->
const T * operator->() const
Definition: small_map.h:345
small_mapt::NUM
static const std::size_t NUM
Definition: small_map.h:168
small_mapt::end
const_iterator end() const
Definition: small_map.h:323
small_mapt::erase
std::size_t erase(std::size_t idx)
Definition: small_map.h:428
small_mapt::const_value_iterator
Const value iterator.
Definition: small_map.h:334
small_mapt::const_value_iterator::operator*
const T & operator*() const
Definition: small_map.h:340
small_mapt::valuet
std::pair< const std::size_t, const T & > valuet
Definition: small_map.h:237
small_mapt::num_bits
static constexpr std::size_t num_bits(const std::size_t n)
Definition: small_map.h:172
small_mapt::small_mapt
small_mapt(const small_mapt &m)
Definition: small_map.h:133
small_mapt::BITS
static const std::size_t BITS
Definition: small_map.h:179
small_mapt::const_iterator::ii
std::size_t ii
Definition: small_map.h:315
small_mapt::const_value_iterator::operator==
bool operator==(const const_value_iterator &other) const
Definition: small_map.h:366
small_mapt::indicator_mask
static constexpr index_fieldt indicator_mask(const index_fieldt digit=1)
Definition: small_map.h:181
small_mapt::copy_and_erase
small_mapt * copy_and_erase(std::size_t idx) const
Definition: small_map.h:465
small_mapt::const_iterator::idx
std::size_t idx
Definition: small_map.h:314
small_mapt::const_iterator::operator!=
bool operator!=(const const_iterator &other) const
Definition: small_map.h:292
small_mapt::empty
bool empty() const
Definition: small_map.h:532
small_mapt::get_field
std::size_t get_field(std::size_t field) const
Definition: small_map.h:198
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
small_mapt::copy_and_insert
small_mapt * copy_and_insert(std::size_t idx, const T &value) const
Definition: small_map.h:499
small_mapt::value_end
const_value_iterator value_end() const
Definition: small_map.h:386
small_mapt::operator[]
T & operator[](std::size_t idx)
Definition: small_map.h:393
small_mapt
Map from small integers to values.
Definition: small_map.h:69
small_mapt::const_iterator::operator==
bool operator==(const const_iterator &other) const
Definition: small_map.h:287
small_mapt::MASK
static const index_fieldt MASK
Definition: small_map.h:188
small_mapt::N_BITS
static const std::size_t N_BITS
Definition: small_map.h:166
small_mapt::const_value_iterator::operator++
const_value_iterator operator++(int)
Definition: small_map.h:357
small_mapt::allocate
T * allocate(std::size_t n) const
Definition: small_map.h:92
small_mapt::const_value_iterator::const_value_iterator
const_value_iterator(const small_mapt &m, const int ii)
Definition: small_map.h:336
small_mapt::copy
void copy(T *dest, const T *src, std::size_t n) const
Definition: small_map.h:84
small_mapt::size
std::size_t size() const
Definition: small_map.h:526
small_mapt::const_iterator::operator++
const_iterator operator++(int)
Definition: small_map.h:276
small_mapt::value_begin
const_value_iterator value_begin() const
Definition: small_map.h:381
small_mapt::const_iterator
Const iterator.
Definition: small_map.h:243
small_mapt::small_mapt
small_mapt()
Definition: small_map.h:71
small_mapt::begin
const_iterator begin() const
Definition: small_map.h:318
small_mapt::const_iterator::operator->
const std::shared_ptr< valuet > operator->() const
Definition: small_map.h:263
invariant.h
small_mapt::const_value_iterator::operator!=
bool operator!=(const const_value_iterator &other) const
Definition: small_map.h:371
small_mapt::~small_mapt
~small_mapt()
Definition: small_map.h:148
small_mapt::const_value_iterator::m
const small_mapt & m
Definition: small_map.h:377
small_mapt::small_map_test
friend void small_map_test()
small_mapt::index_fieldt
Ind index_fieldt
Definition: small_map.h:76
small_mapt::S_BITS
static constexpr std::size_t S_BITS
Definition: small_map.h:177
small_mapt::const_iterator::const_iterator
const_iterator(const small_mapt &m)
Definition: small_map.h:245
small_mapt::const_iterator::operator++
const_iterator operator++()
Definition: small_map.h:268
small_mapt::const_iterator::m
const small_mapt & m
Definition: small_map.h:313
small_mapt::p
T * p
Definition: small_map.h:544
small_mapt::const_iterator::find_next
void find_next()
Definition: small_map.h:298
validation_modet::INVARIANT
@ INVARIANT
small_mapt::find
const_iterator find(std::size_t idx) const
Definition: small_map.h:414