cprover
sharing_map.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Sharing map
4 
5 Author: Daniel Poetzl
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_UTIL_SHARING_MAP_H
13 #define CPROVER_UTIL_SHARING_MAP_H
14 
15 #ifdef SM_DEBUG
16 #include <iostream>
17 #endif
18 
19 #include <functional>
20 #include <map>
21 #include <memory>
22 #include <stack>
23 #include <stdexcept>
24 #include <string>
25 #include <tuple>
26 #include <vector>
27 
28 #include "irep.h"
29 #include "sharing_node.h"
30 #include "threeval.h"
31 
32 #ifdef SM_INTERNAL_CHECKS
33 #define SM_ASSERT(b) INVARIANT(b, "Sharing map internal invariant")
34 #else
35 #define SM_ASSERT(b)
36 #endif
37 
38 // clang-format off
39 #define SHARING_MAPT(R) \
40  template <class keyT, class valueT, class hashT, class equalT> \
41  R sharing_mapt<keyT, valueT, hashT, equalT>
42 
43 #define SHARING_MAPT2(CV, ST) \
44  template <class keyT, class valueT, class hashT, class equalT> \
45  CV typename sharing_mapt<keyT, valueT, hashT, equalT>::ST \
46  sharing_mapt<keyT, valueT, hashT, equalT>
47 
48 #define SHARING_MAPT3(T, CV, ST) \
49  template <class keyT, class valueT, class hashT, class equalT> \
50  template <class T> \
51  CV typename sharing_mapt<keyT, valueT, hashT, equalT>::ST \
52  sharing_mapt<keyT, valueT, hashT, equalT>
53 // clang-format on
54 
55 // Note: Due to a bug in Visual Studio we need to add an additional "const"
56 // qualifier to the return values of insert(), place(), and find(). The type
57 // defined in sharing_mapt already includes the const qualifier, but it is lost
58 // when accessed from outside the class. This is fixed in Visual Studio 15.6.
59 
126 template <class keyT,
127  class valueT,
128  class hashT = std::hash<keyT>,
129  class equalT = std::equal_to<keyT>>
131 {
132 public:
134  {
135  }
136 
137  typedef keyT key_type;
138  typedef valueT mapped_type;
139  typedef std::pair<const key_type, mapped_type> value_type;
140 
141  typedef hashT hash;
142  typedef equalT key_equal;
143 
144  typedef std::size_t size_type;
145 
150  typedef const std::pair<const mapped_type &, const bool> const_find_type;
151 
156  typedef const std::pair<mapped_type &, const bool> find_type;
157 
158  typedef std::vector<key_type> keyst;
159 
160 protected:
163 
165 
166  typedef typename innert::to_mapt to_mapt;
167  typedef typename innert::leaf_listt leaf_listt;
168 
169 public:
170  // interface
171 
172  size_type erase(const key_type &k, const tvt &key_exists = tvt::unknown());
173 
175  const keyst &ks,
176  const tvt &key_exists = tvt::unknown()); // applies to all keys
177 
178  // return true if element was inserted
180  const key_type &k,
181  const mapped_type &v,
182  const tvt &key_exists=tvt::unknown());
183 
185  const value_type &p,
186  const tvt &key_exists=tvt::unknown());
187 
189  const key_type &k,
190  const mapped_type &v);
191 
193  const value_type &p);
194 
195  find_type find(
196  const key_type &k,
197  const tvt &key_exists=tvt::unknown());
198 
199  const_find_type find(const key_type &k) const;
200 
201  mapped_type &at(
202  const key_type &k,
203  const tvt &key_exists=tvt::unknown());
204 
205  const mapped_type &at(const key_type &k) const;
206 
207  mapped_type &operator[](const key_type &k);
208 
212  void swap(sharing_mapt &other)
213  {
214  map.swap(other.map);
215 
216  std::size_t tmp = num;
217  num=other.num;
218  other.num=tmp;
219  }
220 
224  size_type size() const
225  {
226  return num;
227  }
228 
230  bool empty() const
231  {
232  return num==0;
233  }
234 
236  void clear()
237  {
238  map.clear();
239  num=0;
240  }
241 
247  bool has_key(const key_type &k) const
248  {
249  return get_leaf_node(k)!=nullptr;
250  }
251 
252  // views
253 
254  typedef std::pair<const key_type &, const mapped_type &> view_itemt;
255 
258  typedef std::vector<view_itemt> viewt;
259 
261  {
262  public:
264  const bool in_both,
265  const key_type &k,
266  const mapped_type &m,
267  const mapped_type &other_m) :
268  in_both(in_both),
269  k(k),
270  m(m),
271  other_m(other_m) {}
272 
273  // if true key is in both maps, if false key is only in the map
274  // from which the view was obtained
275  const bool in_both;
276 
277  const key_type &k;
278 
279  const mapped_type &m;
281  };
282 
286  typedef std::vector<delta_view_itemt> delta_viewt;
287 
288  void get_view(viewt &view) const;
289 
290  void get_delta_view(
291  const sharing_mapt &other,
292  delta_viewt &delta_view,
293  const bool only_common = true) const;
294 
307  {
308  std::size_t num_nodes = 0;
309  std::size_t num_unique_nodes = 0;
310  std::size_t num_leafs = 0;
311  std::size_t num_unique_leafs = 0;
312  };
313 
314  template <class Iterator>
316  Iterator begin,
317  Iterator end,
318  std::function<sharing_mapt &(const Iterator)> f =
319  [](const Iterator it) -> sharing_mapt & { return *it; });
320 
321  template <class Iterator>
322  static sharing_map_statst get_sharing_stats_map(Iterator begin, Iterator end);
323 
324 protected:
325  // helpers
326 
328  const innert *get_container_node(const key_type &k) const;
329 
330  const leaft *get_leaf_node(const key_type &k) const
331  {
332  const innert *cp = get_container_node(k);
333  if(cp == nullptr)
334  return nullptr;
335 
336  const leaft *lp;
337  lp = cp->find_leaf(k);
338 
339  return lp;
340  }
341 
342  void iterate(
343  const baset &n,
344  const unsigned start_depth,
345  std::function<void(const key_type &k, const mapped_type &m)> f) const;
346 
347  void gather_all(const baset &n, const unsigned depth, delta_viewt &delta_view)
348  const;
349 
350  std::size_t count_unmarked_nodes(
351  bool leafs_only,
352  std::set<void *> &marked,
353  bool mark = true) const;
354 
355  // dummy element returned when no element was found
357 
358  static const std::string not_found_msg;
359 
360  // config
361  static const std::size_t bits;
362  static const std::size_t chunk;
363 
364  // derived config
365  static const std::size_t mask;
366  static const std::size_t steps;
367 
368  // key-value map
370 
371  // number of elements in the map
373 };
374 
375 SHARING_MAPT(void)
376 ::iterate(
377  const baset &n,
378  unsigned start_depth,
379  std::function<void(const key_type &k, const mapped_type &m)> f) const
380 {
381  typedef std::pair<unsigned, const baset *> stack_itemt;
382 
383  std::stack<stack_itemt> stack;
384  stack.push({start_depth, &n});
385 
386  do
387  {
388  const stack_itemt &si = stack.top();
389 
390  const unsigned depth = si.first;
391  const baset *bp = si.second;
392 
393  stack.pop();
394 
395  if(depth < steps) // internal
396  {
397  const innert *ip = static_cast<const innert *>(bp);
398  const to_mapt &m = ip->get_to_map();
399  SM_ASSERT(!m.empty());
400 
401  for(const auto &item : m)
402  {
403  const innert *i = &item.second;
404  stack.push({depth + 1, i});
405  }
406  }
407  else // container
408  {
409  SM_ASSERT(depth == steps);
410 
411  const innert *cp = static_cast<const innert *>(bp);
412  const leaf_listt &ll = cp->get_container();
413  SM_ASSERT(!ll.empty());
414 
415  for(const auto &l : ll)
416  {
417  f(l.get_key(), l.get_value());
418  }
419  }
420  }
421  while(!stack.empty());
422 }
423 
424 SHARING_MAPT(std::size_t)
425 ::count_unmarked_nodes(bool leafs_only, std::set<void *> &marked, bool mark)
426  const
427 {
428  if(empty())
429  return 0;
430 
431  unsigned count = 0;
432 
433  typedef std::pair<unsigned, const baset *> stack_itemt;
434 
435  std::stack<stack_itemt> stack;
436  stack.push({0, &map});
437 
438  do
439  {
440  const stack_itemt &si = stack.top();
441 
442  const unsigned depth = si.first;
443  const baset *bp = si.second;
444 
445  stack.pop();
446 
447  // internal node or container node
448  const innert *ip = static_cast<const innert *>(bp);
449  const unsigned use_count = ip->data.use_count();
450  void *raw_ptr = ip->data.get();
451 
452  if(use_count >= 2)
453  {
454  if(marked.find(raw_ptr) != marked.end())
455  {
456  continue;
457  }
458 
459  if(mark)
460  {
461  marked.insert(raw_ptr);
462  }
463  }
464 
465  if(!leafs_only)
466  {
467  count++;
468  }
469 
470  if(depth < steps) // internal
471  {
472  const to_mapt &m = ip->get_to_map();
473  SM_ASSERT(!m.empty());
474 
475  for(const auto &item : m)
476  {
477  const innert *i = &item.second;
478  stack.push({depth + 1, i});
479  }
480  }
481  else // container
482  {
483  SM_ASSERT(depth == steps);
484 
485  const leaf_listt &ll = ip->get_container();
486  SM_ASSERT(!ll.empty());
487 
488  for(const auto &l : ll)
489  {
490  const unsigned leaf_use_count = l.data.use_count();
491  void *leaf_raw_ptr = l.data.get();
492 
493  if(leaf_use_count >= 2)
494  {
495  if(marked.find(leaf_raw_ptr) != marked.end())
496  {
497  continue;
498  }
499 
500  if(mark)
501  {
502  marked.insert(leaf_raw_ptr);
503  }
504  }
505 
506  count++;
507  }
508  }
509  } while(!stack.empty());
510 
511  return count;
512 }
513 
524 SHARING_MAPT3(Iterator, , sharing_map_statst)
525 ::get_sharing_stats(
526  Iterator begin,
527  Iterator end,
528  std::function<sharing_mapt &(const Iterator)> f)
529 {
530  std::set<void *> marked;
531  sharing_map_statst sms;
532 
533  // We do a separate pass over the tree for each statistic. This is not very
534  // efficient but the function is intended only for diagnosis purposes anyways.
535 
536  // number of nodes
537  for(Iterator it = begin; it != end; it++)
538  {
539  sms.num_nodes += f(it).count_unmarked_nodes(false, marked, false);
540  }
541 
542  SM_ASSERT(marked.empty());
543 
544  // number of unique nodes
545  for(Iterator it = begin; it != end; it++)
546  {
547  sms.num_unique_nodes += f(it).count_unmarked_nodes(false, marked, true);
548  }
549 
550  marked.clear();
551 
552  // number of leafs
553  for(Iterator it = begin; it != end; it++)
554  {
555  sms.num_leafs += f(it).count_unmarked_nodes(true, marked, false);
556  }
557 
558  SM_ASSERT(marked.empty());
559 
560  // number of unique leafs
561  for(Iterator it = begin; it != end; it++)
562  {
563  sms.num_unique_leafs += f(it).count_unmarked_nodes(true, marked, true);
564  }
565 
566  return sms;
567 }
568 
578 SHARING_MAPT3(Iterator, , sharing_map_statst)
579 ::get_sharing_stats_map(Iterator begin, Iterator end)
580 {
581  return get_sharing_stats<Iterator>(
582  begin, end, [](const Iterator it) -> sharing_mapt & { return it->second; });
583 }
584 
594 SHARING_MAPT(void)::get_view(viewt &view) const
595 {
596  SM_ASSERT(view.empty());
597 
598  if(empty())
599  return;
600 
601  auto f = [&view](const key_type &k, const mapped_type &m) {
602  view.push_back(view_itemt(k, m));
603  };
604 
605  iterate(map, 0, f);
606 }
607 
608 SHARING_MAPT(void)
609 ::gather_all(const baset &n, unsigned depth, delta_viewt &delta_view) const
610 {
611  auto f = [&delta_view](const key_type &k, const mapped_type &m) {
612  delta_view.push_back(delta_view_itemt(false, k, m, dummy));
613  };
614 
615  iterate(n, depth, f);
616 }
617 
651 SHARING_MAPT(void)
652 ::get_delta_view(
653  const sharing_mapt &other,
654  delta_viewt &delta_view,
655  const bool only_common) const
656 {
657  SM_ASSERT(delta_view.empty());
658 
659  if(empty())
660  return;
661 
662  if(other.empty())
663  {
664  if(!only_common)
665  {
666  gather_all(map, 0, delta_view);
667  }
668 
669  return;
670  }
671 
672  typedef std::tuple<unsigned, const baset *, const baset *> stack_itemt;
673  std::stack<stack_itemt> stack;
674 
675  // We do a DFS "in lockstep" simultaneously on both maps. For
676  // corresponding nodes we check whether they are shared between the
677  // maps, and if not, we recurse into the corresponding subtrees.
678 
679  // The stack contains the children of already visited nodes that we
680  // still have to visit during the traversal.
681 
682  stack.push(stack_itemt(0, &map, &other.map));
683 
684  do
685  {
686  const stack_itemt &si = stack.top();
687 
688  const unsigned depth = std::get<0>(si);
689  const baset *bp1 = std::get<1>(si);
690  const baset *bp2 = std::get<2>(si);
691 
692  stack.pop();
693 
694  if(depth < steps) // internal
695  {
696  const innert *ip1 = static_cast<const innert *>(bp1);
697  const innert *ip2 = static_cast<const innert *>(bp2);
698 
699  const to_mapt &m = ip1->get_to_map();
700 
701  for(const auto &item : m)
702  {
703  const innert *p;
704 
705  p = ip2->find_child(item.first);
706  if(p==nullptr)
707  {
708  if(!only_common)
709  {
710  gather_all(item.second, depth + 1, delta_view);
711  }
712  }
713  else if(!item.second.shares_with(*p))
714  {
715  stack.push(stack_itemt(depth + 1, &item.second, p));
716  }
717  }
718  }
719  else // container
720  {
721  SM_ASSERT(depth == steps);
722 
723  const innert *cp1 = static_cast<const innert *>(bp1);
724  const innert *cp2 = static_cast<const innert *>(bp2);
725 
726  const leaf_listt &ll1 = cp1->get_container();
727 
728  for(const auto &l1 : ll1)
729  {
730  const key_type &k1=l1.get_key();
731  const leaft *p;
732 
733  p = cp2->find_leaf(k1);
734 
735  if(p != nullptr)
736  {
737  if(!l1.shares_with(*p))
738  {
739  delta_view.push_back({true, k1, l1.get_value(), p->get_value()});
740  }
741  }
742  else if(!only_common)
743  {
744  delta_view.push_back({false, l1.get_key(), l1.get_value(), dummy});
745  }
746  }
747  }
748  }
749  while(!stack.empty());
750 }
751 
752 SHARING_MAPT2(, innert *)::get_container_node(const key_type &k)
753 {
754  std::size_t key = hash()(k);
755  innert *ip = &map;
756 
757  for(std::size_t i = 0; i < steps; i++)
758  {
759  std::size_t bit = key & mask;
760 
761  ip = ip->add_child(bit);
762 
763  key >>= chunk;
764  }
765 
766  return ip;
767 }
768 
769 SHARING_MAPT2(const, innert *)::get_container_node(const key_type &k) const
770 {
771  if(empty())
772  return nullptr;
773 
774  std::size_t key = hash()(k);
775  const innert *ip = &map;
776 
777  for(std::size_t i = 0; i < steps; i++)
778  {
779  std::size_t bit = key & mask;
780 
781  ip = ip->find_child(bit);
782  if(ip == nullptr)
783  return nullptr;
784 
785  key >>= chunk;
786  }
787 
788  return ip;
789 }
790 
800 SHARING_MAPT2(, size_type)::erase(const key_type &k, const tvt &key_exists)
801 {
802  SM_ASSERT(!key_exists.is_false());
803  SM_ASSERT(!key_exists.is_true() || has_key(k));
804 
805  // check if key exists
806  if(key_exists.is_unknown() && !has_key(k))
807  return 0;
808 
809  innert *del = nullptr;
810  std::size_t del_bit = 0;
811  std::size_t del_level = 0;
812 
813  std::size_t key = hash()(k);
814  innert *ip = &map;
815 
816  for(std::size_t i = 0; i < steps; i++)
817  {
818  std::size_t bit = key & mask;
819 
820  const to_mapt &m = as_const(ip)->get_to_map();
821 
822  if(m.size() > 1 || del == nullptr)
823  {
824  del = ip;
825  del_bit=bit;
826  del_level = i;
827  }
828 
829  ip = ip->add_child(bit);
830 
831  key >>= chunk;
832  }
833 
834  const leaf_listt &ll = as_const(ip)->get_container();
835 
836  // forward list has one element
837  if(!ll.empty() && std::next(ll.begin()) == ll.end())
838  {
839  if(del_level < steps - 1)
840  {
841  del->remove_child(del_bit);
842  }
843  else
844  {
845  SM_ASSERT(del_level == steps - 1);
846  del->remove_child(del_bit);
847  }
848 
849  num--;
850  return 1;
851  }
852 
853  SM_ASSERT(!ll.empty());
854 
855  ip->remove_leaf(k);
856  num--;
857 
858  return 1;
859 }
860 
873 ::erase_all(const keyst &ks, const tvt &key_exists)
874 {
875  size_type cnt = 0;
876 
877  for(const key_type &k : ks)
878  {
879  cnt+=erase(k, key_exists);
880  }
881 
882  return cnt;
883 }
884 
897 SHARING_MAPT2(const, const_find_type)
898 ::insert(const key_type &k, const mapped_type &m, const tvt &key_exists)
899 {
900  SM_ASSERT(!key_exists.is_true());
901  SM_ASSERT(!key_exists.is_false() || !has_key(k));
902 
903  if(key_exists.is_unknown())
904  {
905  const leaft *lp = as_const(this)->get_leaf_node(k);
906  if(lp != nullptr)
907  return const_find_type(lp->get_value(), false);
908  }
909 
910  innert *cp = get_container_node(k);
911  SM_ASSERT(cp != nullptr);
912 
913  const leaft *lp = cp->place_leaf(k, m);
914  num++;
915 
916  return const_find_type(lp->get_value(), true);
917 }
918 
919 // Insert element, return const reference
920 SHARING_MAPT2(const, const_find_type)
921 ::insert(const value_type &p, const tvt &key_exists)
922 {
923  return insert(p.first, p.second, key_exists);
924 }
925 
936 SHARING_MAPT2(const, find_type)::place(const key_type &k, const mapped_type &m)
937 {
938  innert *cp = get_container_node(k);
939  SM_ASSERT(cp != nullptr);
940 
941  leaft *lp = cp->find_leaf(k);
942 
943  if(lp != nullptr)
944  return find_type(lp->get_value(), false);
945 
946  lp = cp->place_leaf(k, m);
947  num++;
948 
949  return find_type(lp->get_value(), true);
950 }
951 
953 SHARING_MAPT2(const, find_type)::place(const value_type &p)
954 {
955  return place(p.first, p.second);
956 }
957 
969 SHARING_MAPT2(const, find_type)::find(const key_type &k, const tvt &key_exists)
970 {
971  SM_ASSERT(!key_exists.is_false());
972  SM_ASSERT(!key_exists.is_true() || has_key(k));
973 
974  if(key_exists.is_unknown() && !has_key(k))
975  return find_type(dummy, false);
976 
977  innert *cp = get_container_node(k);
978  SM_ASSERT(cp != nullptr);
979 
980  leaft *lp = cp->find_leaf(k);
981  SM_ASSERT(lp != nullptr);
982 
983  return find_type(lp->get_value(), true);
984 }
985 
995 SHARING_MAPT2(const, const_find_type)::find(const key_type &k) const
996 {
997  const leaft *lp = get_leaf_node(k);
998 
999  if(lp == nullptr)
1000  return const_find_type(dummy, false);
1001 
1002  return const_find_type(lp->get_value(), true);
1003 }
1004 
1017  const key_type &k,
1018  const tvt &key_exists)
1019 {
1020  find_type r=find(k, key_exists);
1021 
1022  if(!r.second)
1023  throw std::out_of_range(not_found_msg);
1024 
1025  return r.first;
1026 }
1027 
1037 SHARING_MAPT2(const, mapped_type &)::at(const key_type &k) const
1038 {
1039  const_find_type r=find(k);
1040  if(!r.second)
1041  throw std::out_of_range(not_found_msg);
1042 
1043  return r.first;
1044 }
1045 
1054 SHARING_MAPT2(, mapped_type &)::operator[](const key_type &k)
1055 {
1056  return place(k, mapped_type()).first;
1057 }
1058 
1059 // static constants
1060 
1061 SHARING_MAPT(const std::string)::not_found_msg="key not found";
1062 
1063 SHARING_MAPT2(, mapped_type)::dummy;
1064 
1065 SHARING_MAPT(const std::size_t)::bits = 18;
1066 SHARING_MAPT(const std::size_t)::chunk = 3;
1067 
1068 SHARING_MAPT(const std::size_t)::mask = 0xffff >> (16 - chunk);
1069 SHARING_MAPT(const std::size_t)::steps = bits / chunk;
1070 
1071 #endif
sharing_mapt::insert
const_find_type insert(const key_type &k, const mapped_type &v, const tvt &key_exists=tvt::unknown())
Insert element, return const reference.
Definition: sharing_map.h:898
sharing_mapt::delta_view_itemt::in_both
const bool in_both
Definition: sharing_map.h:275
sharing_mapt::sharing_map_statst
Stats about sharing between several sharing map instances.
Definition: sharing_map.h:306
sharing_mapt::keyst
std::vector< key_type > keyst
Definition: sharing_map.h:158
sharing_mapt::viewt
std::vector< view_itemt > viewt
View of the key-value pairs in the map.
Definition: sharing_map.h:258
sharing_mapt::get_view
void get_view(viewt &view) const
Get a view of the elements in the map A view is a list of pairs with the components being const refer...
Definition: sharing_map.h:594
sharing_mapt::clear
void clear()
Clear map.
Definition: sharing_map.h:236
sharing_mapt::value_type
std::pair< const key_type, mapped_type > value_type
Definition: sharing_map.h:139
sharing_mapt::sharing_map_statst::num_unique_leafs
std::size_t num_unique_leafs
Definition: sharing_map.h:311
sharing_node_innert::place_leaf
leaft * place_leaf(const keyT &k, const valueT &v)
Definition: sharing_node.h:257
sharing_mapt
A map implemented as a tree where subtrees can be shared between different maps.
Definition: sharing_map.h:130
sharing_mapt::baset
sharing_node_baset baset
Definition: sharing_map.h:164
sharing_mapt::innert
sharing_node_innert< key_type, mapped_type > innert
Definition: sharing_map.h:161
sharing_mapt::sharing_map_statst::num_unique_nodes
std::size_t num_unique_nodes
Definition: sharing_map.h:309
threeval.h
sharing_mapt::get_sharing_stats_map
static sharing_map_statst get_sharing_stats_map(Iterator begin, Iterator end)
Get sharing stats.
Definition: sharing_map.h:579
sharing_mapt::delta_view_itemt
Definition: sharing_map.h:260
sharing_mapt::leaft
sharing_node_leaft< key_type, mapped_type > leaft
Definition: sharing_map.h:162
sharing_node.h
sharing_mapt::find_type
const typedef std::pair< mapped_type &, const bool > find_type
Return type of methods that retrieve a reference to a value.
Definition: sharing_map.h:156
sharing_mapt::gather_all
void gather_all(const baset &n, const unsigned depth, delta_viewt &delta_view) const
Definition: sharing_map.h:609
sharing_node_innert::remove_child
void remove_child(const std::size_t n)
Definition: sharing_node.h:331
sharing_mapt::const_find_type
const typedef std::pair< const mapped_type &, const bool > const_find_type
Return type of methods that retrieve a const reference to a value.
Definition: sharing_map.h:150
sharing_node_leaft::get_value
const valueT & get_value() const
Definition: sharing_node.h:441
SHARING_MAPT
#define SHARING_MAPT(R)
Definition: sharing_map.h:39
sharing_mapt::has_key
bool has_key(const key_type &k) const
Check if key is in map.
Definition: sharing_map.h:247
sharing_mapt::chunk
static const std::size_t chunk
Definition: sharing_map.h:362
sharing_mapt::operator[]
mapped_type & operator[](const key_type &k)
Get element at key, insert new if non-existent.
Definition: sharing_map.h:1054
sharing_mapt::swap
void swap(sharing_mapt &other)
Swap with other map.
Definition: sharing_map.h:212
sharing_node_innert::remove_leaf
void remove_leaf(const keyT &k)
Definition: sharing_node.h:271
sharing_node_innert::get_to_map
const to_mapt & get_to_map() const
Definition: sharing_node.h:202
sharing_node_innert::clear
void clear()
Definition: sharing_node.h:125
sharing_mapt::mapped_type
valueT mapped_type
Definition: sharing_map.h:138
sharing_mapt::steps
static const std::size_t steps
Definition: sharing_map.h:366
sharing_mapt::bits
static const std::size_t bits
Definition: sharing_map.h:361
as_const
const T * as_const(T *t)
Definition: sharing_node.h:66
sharing_mapt::erase_all
size_type erase_all(const keyst &ks, const tvt &key_exists=tvt::unknown())
Erase all elements.
Definition: sharing_map.h:873
sharing_mapt::delta_view_itemt::delta_view_itemt
delta_view_itemt(const bool in_both, const key_type &k, const mapped_type &m, const mapped_type &other_m)
Definition: sharing_map.h:263
sharing_mapt::map
innert map
Definition: sharing_map.h:369
sharing_node_innert::find_child
const d_it::innert * find_child(const std::size_t n) const
Definition: sharing_node.h:310
sharing_mapt::sharing_map_statst::num_leafs
std::size_t num_leafs
Definition: sharing_map.h:310
sharing_mapt::size_type
std::size_t size_type
Definition: sharing_map.h:144
sharing_mapt::dummy
static mapped_type dummy
Definition: sharing_map.h:356
small_mapt::empty
bool empty() const
Definition: small_map.h:582
sharing_node_innert::add_child
d_it::innert * add_child(const std::size_t n)
Definition: sharing_node.h:323
sharing_mapt::key_type
keyT key_type
Definition: sharing_map.h:137
sharing_node_innert::find_leaf
const leaft * find_leaf(const keyT &k) const
Definition: sharing_node.h:224
sharing_node_innert::swap
void swap(sharing_node_innert &other)
Definition: sharing_node.h:137
sharing_mapt::get_leaf_node
const leaft * get_leaf_node(const key_type &k) const
Definition: sharing_map.h:330
sharing_mapt::place
find_type place(const key_type &k, const mapped_type &v)
Insert element, return non-const reference.
Definition: sharing_map.h:936
sharing_mapt::find
find_type find(const key_type &k, const tvt &key_exists=tvt::unknown())
Find element.
Definition: sharing_map.h:969
sharing_mapt::hash
hashT hash
Definition: sharing_map.h:141
sharing_mapt::iterate
void iterate(const baset &n, const unsigned start_depth, std::function< void(const key_type &k, const mapped_type &m)> f) const
Definition: sharing_map.h:376
small_shared_two_way_ptrt::use_count
use_countt use_count() const
Definition: small_shared_two_way_ptr.h:133
sharing_mapt::leaf_listt
innert::leaf_listt leaf_listt
Definition: sharing_map.h:167
small_mapt< innert >
sharing_mapt::delta_view_itemt::k
const key_type & k
Definition: sharing_map.h:277
tvt::unknown
static tvt unknown()
Definition: threeval.h:33
sharing_mapt::erase
size_type erase(const key_type &k, const tvt &key_exists=tvt::unknown())
Erase element.
Definition: sharing_map.h:800
sharing_node_innert::get_container
const leaf_listt & get_container() const
Definition: sharing_node.h:212
sharing_node_leaft
Definition: sharing_node.h:90
sharing_mapt::view_itemt
std::pair< const key_type &, const mapped_type & > view_itemt
Definition: sharing_map.h:254
sharing_mapt::mask
static const std::size_t mask
Definition: sharing_map.h:365
sharing_node_innert::data
small_shared_two_way_ptrt< d_internalt< keyT, valueT, equalT >, d_containert< keyT, valueT, equalT > > data
Definition: sharing_node.h:341
tvt
Definition: threeval.h:19
sharing_mapt::get_sharing_stats
static sharing_map_statst get_sharing_stats(Iterator begin, Iterator end, std::function< sharing_mapt &(const Iterator)> f=[](const Iterator it) -> sharing_mapt &{ return *it;})
Get sharing stats.
Definition: sharing_map.h:525
SHARING_MAPT2
#define SHARING_MAPT2(CV, ST)
Definition: sharing_map.h:43
sharing_mapt::get_container_node
innert * get_container_node(const key_type &k)
Definition: sharing_map.h:752
small_mapt::size
std::size_t size() const
Definition: small_map.h:576
sharing_mapt::num
size_type num
Definition: sharing_map.h:372
sharing_mapt::empty
bool empty() const
Check if map is empty.
Definition: sharing_map.h:230
sharing_mapt::at
mapped_type & at(const key_type &k, const tvt &key_exists=tvt::unknown())
Get element at key.
Definition: sharing_map.h:1016
sharing_mapt::not_found_msg
static const std::string not_found_msg
Definition: sharing_map.h:358
small_shared_two_way_ptrt::get
pointeet * get() const
Definition: small_shared_two_way_ptr.h:150
stack
#define stack(x)
Definition: parser.h:144
sharing_node_innert< key_type, mapped_type >
sharing_mapt::get_delta_view
void get_delta_view(const sharing_mapt &other, delta_viewt &delta_view, const bool only_common=true) const
Get a delta view of the elements in the map.
Definition: sharing_map.h:652
sharing_mapt::delta_view_itemt::other_m
const mapped_type & other_m
Definition: sharing_map.h:280
sharing_mapt::count_unmarked_nodes
std::size_t count_unmarked_nodes(bool leafs_only, std::set< void * > &marked, bool mark=true) const
Definition: sharing_map.h:425
SHARING_MAPT3
#define SHARING_MAPT3(T, CV, ST)
Definition: sharing_map.h:48
SM_ASSERT
#define SM_ASSERT(b)
Definition: sharing_map.h:35
sharing_mapt::delta_viewt
std::vector< delta_view_itemt > delta_viewt
Delta view of the key-value pairs in two maps.
Definition: sharing_map.h:286
r
static int8_t r
Definition: irep_hash.h:59
sharing_node_innert< key_type, mapped_type >::leaf_listt
d_ct::leaf_listt leaf_listt
Definition: sharing_node.h:114
size_type
unsignedbv_typet size_type()
Definition: c_types.cpp:58
sharing_mapt::sharing_map_statst::num_nodes
std::size_t num_nodes
Definition: sharing_map.h:308
sharing_node_baset
Definition: sharing_node.h:101
sharing_mapt::key_equal
equalT key_equal
Definition: sharing_map.h:142
sharing_mapt::size
size_type size() const
Get number of elements in map.
Definition: sharing_map.h:224
sharing_mapt::delta_view_itemt::m
const mapped_type & m
Definition: sharing_map.h:279
irep.h
sharing_mapt::~sharing_mapt
~sharing_mapt()
Definition: sharing_map.h:133
sharing_mapt::to_mapt
innert::to_mapt to_mapt
Definition: sharing_map.h:166