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 <set>
23 #include <stack>
24 #include <stdexcept>
25 #include <string>
26 #include <tuple>
27 #include <type_traits>
28 #include <vector>
29 
30 #include "as_const.h"
31 #include "irep.h"
32 #include "optional.h"
33 #include "sharing_node.h"
34 #include "threeval.h"
35 
36 #ifdef SM_INTERNAL_CHECKS
37 #define SM_ASSERT(b) INVARIANT(b, "Sharing map internal invariant")
38 #else
39 #define SM_ASSERT(b)
40 #endif
41 
42 // clang-format off
43 
48 #define SHARING_MAPT(type) \
49  template < \
50  typename keyT, \
51  typename valueT, \
52  bool fail_if_equal, \
53  typename hashT, \
54  typename equalT> \
55  type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
56 
62 #define SHARING_MAPT2(cv_qualifiers, return_type) \
63  template < \
64  typename keyT, \
65  typename valueT, \
66  bool fail_if_equal, \
67  typename hashT, \
68  typename equalT> \
69  cv_qualifiers typename \
70  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>::return_type \
71  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
72 
80 #define SHARING_MAPT3(template_parameter, cv_qualifiers, return_type) \
81  template < \
82  typename keyT, \
83  typename valueT, \
84  bool fail_if_equal, \
85  typename hashT, \
86  typename equalT> \
87  template <class template_parameter> \
88  cv_qualifiers typename \
89  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>::return_type \
90  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
91 
97 #define SHARING_MAPT4(template_parameter, return_type) \
98  template < \
99  typename keyT, \
100  typename valueT, \
101  bool fail_if_equal, \
102  typename hashT, \
103  typename equalT> \
104  template <class template_parameter> \
105  return_type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
106 // clang-format on
107 
173 template <
174  typename keyT,
175  typename valueT,
176  bool fail_if_equal = false,
177  typename hashT = std::hash<keyT>,
178  typename equalT = std::equal_to<keyT>>
180 {
181 public:
183  {
184  }
185 
186  typedef keyT key_type;
187  typedef valueT mapped_type;
188 
189  typedef hashT hash;
190  typedef equalT key_equal;
191 
192  typedef std::size_t size_type;
193 
194  typedef std::vector<key_type> keyst;
195 
196 protected:
198 
199  typedef typename nodet::to_mapt to_mapt;
200  typedef typename nodet::leaf_listt leaf_listt;
201 
202  struct falset
203  {
204  bool operator()(const mapped_type &lhs, const mapped_type &rhs)
205  {
206  return false;
207  }
208  };
209 
210  typedef
211  typename std::conditional<fail_if_equal, std::equal_to<valueT>, falset>::
213 
215  {
217  {
218  }
219 
220  bool operator()(const mapped_type &)
221  {
222  return false;
223  }
224  };
225 
227  {
231  {
232  }
233 
234  bool operator()(const mapped_type &new_value)
235  {
236  return old_value == new_value;
237  }
238  };
239 
240  typedef typename std::conditional<
241  fail_if_equal,
242  real_value_comparatort,
243  noop_value_comparatort>::type value_comparatort;
244 
245 public:
246  // interface
247 
255  void erase(const key_type &k);
256 
264  void erase_if_exists(const key_type &k)
265  {
266  if(has_key(k))
267  erase(k);
268  }
269 
278  template <class valueU>
279  void insert(const key_type &k, valueU &&m);
280 
289  template <class valueU>
290  void replace(const key_type &k, valueU &&m);
291 
303  void update(const key_type &k, std::function<void(mapped_type &)> mutator);
304 
314  find(const key_type &k) const;
315 
319  void swap(sharing_mapt &other)
320  {
321  map.swap(other.map);
322 
323  std::size_t tmp = num;
324  num=other.num;
325  other.num=tmp;
326  }
327 
331  size_type size() const
332  {
333  return num;
334  }
335 
337  bool empty() const
338  {
339  return num==0;
340  }
341 
343  void clear()
344  {
345  map.clear();
346  num=0;
347  }
348 
354  bool has_key(const key_type &k) const
355  {
356  return get_leaf_node(k)!=nullptr;
357  }
358 
359  // views
360 
361  typedef std::pair<const key_type &, const mapped_type &> view_itemt;
362 
365  typedef std::vector<view_itemt> viewt;
366 
368  {
369  public:
371  const key_type &k,
372  const mapped_type &m,
373  const mapped_type &other_m)
374  : k(k), m(m), other_m(&other_m)
375  {
376  }
377 
379  : k(k), m(m), other_m(nullptr)
380  {
381  }
382 
383  const key_type &k;
384 
385  const mapped_type &m;
386 
387  bool is_in_both_maps() const
388  {
389  return other_m != nullptr;
390  }
391 
393  {
395  return *other_m;
396  }
397 
398  private:
400  };
401 
405  typedef std::vector<delta_view_itemt> delta_viewt;
406 
416  void get_view(viewt &view) const;
417 
452  const sharing_mapt &other,
453  delta_viewt &delta_view,
454  const bool only_common = true) const;
455 
459  void
460  iterate(std::function<void(const key_type &k, const mapped_type &m)> f) const
461  {
462  if(empty())
463  return;
464 
465  iterate(map, f);
466  }
467 
468 #if !defined(_MSC_VER)
469  struct sharing_map_statst
481  {
482  std::size_t num_nodes = 0;
483  std::size_t num_unique_nodes = 0;
484  std::size_t num_leafs = 0;
485  std::size_t num_unique_leafs = 0;
486  };
487 
498  template <class Iterator>
499  static sharing_map_statst get_sharing_stats(
500  Iterator begin,
501  Iterator end,
502  std::function<sharing_mapt &(const Iterator)> f =
503  [](const Iterator it) -> sharing_mapt & { return *it; });
504 
514  template <class Iterator>
515  static sharing_map_statst get_sharing_stats_map(Iterator begin, Iterator end);
516 #endif
517 
518 protected:
519  // helpers
520 
522  const nodet *get_leaf_node(const key_type &k) const;
523 
542  template <class valueU>
543  void migrate(
544  const std::size_t starting_level,
545  const std::size_t key_suffix,
546  const std::size_t bit_last,
547  nodet &inner,
548  const key_type &k,
549  valueU &&m);
550 
551  void iterate(
552  const nodet &n,
553  std::function<void(const key_type &k, const mapped_type &m)> f) const;
554 
570  const nodet &leaf,
571  const nodet &inner,
572  const std::size_t level,
573  delta_viewt &delta_view,
574  const bool only_common) const;
575 
576  void gather_all(const nodet &n, delta_viewt &delta_view) const;
577 
578  std::size_t count_unmarked_nodes(
579  bool leafs_only,
580  std::set<const void *> &marked,
581  bool mark = true) const;
582 
583  static const std::size_t dummy_level;
584 
585  // config
586  static const std::size_t bits;
587  static const std::size_t chunk;
588 
589  // derived config
590  static const std::size_t mask;
591  static const std::size_t levels;
592 
593  // key-value map
595 
596  // number of elements in the map
598 };
599 
600 SHARING_MAPT(void)
601 ::iterate(
602  const nodet &n,
603  std::function<void(const key_type &k, const mapped_type &m)> f) const
604 {
605  SM_ASSERT(!n.empty());
606 
607  std::stack<const nodet *> stack;
608  stack.push(&n);
609 
610  do
611  {
612  const nodet *ip = stack.top();
613  stack.pop();
614 
615  SM_ASSERT(!ip->empty());
616 
617  if(ip->is_internal())
618  {
619  const to_mapt &m = ip->get_to_map();
620  SM_ASSERT(!m.empty());
621 
622  for(const auto item : m)
623  {
624  stack.push(&item.second);
625  }
626  }
627  else if(ip->is_leaf())
628  {
629  f(ip->get_key(), ip->get_value());
630  }
631  else
632  {
634 
635  const leaf_listt &ll = ip->get_container();
636  SM_ASSERT(!ll.empty());
637 
638  for(const auto &l : ll)
639  {
640  f(l.get_key(), l.get_value());
641  }
642  }
643  }
644  while(!stack.empty());
645 }
646 
647 SHARING_MAPT(std::size_t)
648 ::count_unmarked_nodes(
649  bool leafs_only,
650  std::set<const void *> &marked,
651  bool mark) const
652 {
653  if(empty())
654  return 0;
655 
656  unsigned count = 0;
657 
658  std::stack<const nodet *> stack;
659  stack.push(&map);
660 
661  do
662  {
663  const nodet *ip = stack.top();
664  SM_ASSERT(!ip->empty());
665  stack.pop();
666 
667  const unsigned use_count = ip->use_count();
668 
669  const void *raw_ptr =
670  ip->is_internal() ? (const void *)&ip->read_internal()
671  : ip->is_leaf() ? (const void *)&ip->read_leaf()
672  : (const void *)&ip->read_container();
673 
674  if(use_count >= 2)
675  {
676  if(marked.find(raw_ptr) != marked.end())
677  {
678  continue;
679  }
680 
681  if(mark)
682  {
683  marked.insert(raw_ptr);
684  }
685  }
686 
687  if(ip->is_internal())
688  {
689  if(!leafs_only)
690  {
691  count++;
692  }
693 
694  const to_mapt &m = ip->get_to_map();
695  SM_ASSERT(!m.empty());
696 
697  for(const auto item : m)
698  {
699  stack.push(&item.second);
700  }
701  }
702  else if(ip->is_leaf())
703  {
704  count++;
705  }
706  else
707  {
709 
710  if(!leafs_only)
711  {
712  count++;
713  }
714 
715  const leaf_listt &ll = ip->get_container();
716  SM_ASSERT(!ll.empty());
717 
718  for(const auto &l : ll)
719  {
720  stack.push(&l);
721  }
722  }
723  } while(!stack.empty());
724 
725  return count;
726 }
727 
728 #if !defined(_MSC_VER)
729 SHARING_MAPT3(Iterator, , sharing_map_statst)
730 ::get_sharing_stats(
731  Iterator begin,
732  Iterator end,
733  std::function<sharing_mapt &(const Iterator)> f)
734 {
735  std::set<const void *> marked;
736  sharing_map_statst sms;
737 
738  // We do a separate pass over the tree for each statistic. This is not very
739  // efficient but the function is intended only for diagnosis purposes anyways.
740 
741  // number of nodes
742  for(Iterator it = begin; it != end; it++)
743  {
744  sms.num_nodes += f(it).count_unmarked_nodes(false, marked, false);
745  }
746 
747  SM_ASSERT(marked.empty());
748 
749  // number of unique nodes
750  for(Iterator it = begin; it != end; it++)
751  {
752  sms.num_unique_nodes += f(it).count_unmarked_nodes(false, marked, true);
753  }
754 
755  marked.clear();
756 
757  // number of leafs
758  for(Iterator it = begin; it != end; it++)
759  {
760  sms.num_leafs += f(it).count_unmarked_nodes(true, marked, false);
761  }
762 
763  SM_ASSERT(marked.empty());
764 
765  // number of unique leafs
766  for(Iterator it = begin; it != end; it++)
767  {
768  sms.num_unique_leafs += f(it).count_unmarked_nodes(true, marked, true);
769  }
770 
771  return sms;
772 }
773 
774 SHARING_MAPT3(Iterator, , sharing_map_statst)
775 ::get_sharing_stats_map(Iterator begin, Iterator end)
776 {
777  return get_sharing_stats<Iterator>(
778  begin, end, [](const Iterator it) -> sharing_mapt & { return it->second; });
779 }
780 #endif
781 
782 SHARING_MAPT(void)::get_view(viewt &view) const
783 {
784  SM_ASSERT(view.empty());
785 
786  if(empty())
787  return;
788 
789  auto f = [&view](const key_type &k, const mapped_type &m) {
790  view.push_back(view_itemt(k, m));
791  };
792 
793  iterate(map, f);
794 }
795 
796 SHARING_MAPT(void)
797 ::gather_all(const nodet &n, delta_viewt &delta_view) const
798 {
799  auto f = [&delta_view](const key_type &k, const mapped_type &m) {
800  delta_view.push_back(delta_view_itemt(k, m));
801  };
802 
803  iterate(n, f);
804 }
805 
806 SHARING_MAPT(void)::add_item_if_not_shared(
807  const nodet &leaf,
808  const nodet &inner,
809  const std::size_t level,
810  delta_viewt &delta_view,
811  const bool only_common) const
812 {
813  const auto &k = leaf.get_key();
814  std::size_t key = hash()(k);
815 
816  key >>= level * chunk;
817 
818  const nodet *ip = &inner;
820 
821  while(true)
822  {
823  std::size_t bit = key & mask;
824 
825  ip = ip->find_child(bit);
826 
827  // only in first map
828  if(ip == nullptr)
829  {
830  if(!only_common)
831  {
832  delta_view.push_back({k, leaf.get_value()});
833  }
834 
835  return;
836  }
837 
838  SM_ASSERT(!ip->empty());
839 
840  // potentially in both maps
841  if(ip->is_container())
842  {
843  for(const auto &l2 : ip->get_container())
844  {
845  if(leaf.shares_with(l2))
846  return;
847 
848  if(leaf.get_key() == l2.get_key())
849  {
850  delta_view.push_back({k, leaf.get_value(), l2.get_value()});
851  return;
852  }
853  }
854 
855  delta_view.push_back({k, leaf.get_value()});
856 
857  return;
858  }
859 
860  if(ip->is_leaf())
861  {
862  if(ip->shares_with(leaf))
863  return;
864 
865  if(equalT()(leaf.get_key(), ip->get_key()))
866  {
867  delta_view.push_back({k, leaf.get_value(), ip->get_value()});
868  return;
869  }
870 
871  delta_view.push_back({k, leaf.get_value()});
872 
873  return;
874  }
875 
876  key >>= chunk;
877  }
878 }
879 
880 SHARING_MAPT(void)
881 ::get_delta_view(
882  const sharing_mapt &other,
883  delta_viewt &delta_view,
884  const bool only_common) const
885 {
886  SM_ASSERT(delta_view.empty());
887 
888  if(empty())
889  return;
890 
891  if(other.empty())
892  {
893  if(!only_common)
894  {
895  gather_all(map, delta_view);
896  }
897 
898  return;
899  }
900 
901  typedef std::pair<const nodet *, const nodet *> stack_itemt;
902  std::stack<stack_itemt> stack;
903 
904  std::stack<std::size_t> level_stack;
905 
906  // We do a DFS "in lockstep" simultaneously on both maps. For
907  // corresponding nodes we check whether they are shared between the
908  // maps, and if not, we recurse into the corresponding subtrees.
909 
910  // The stack contains the children of already visited nodes that we
911  // still have to visit during the traversal.
912 
913  if(map.shares_with(other.map))
914  return;
915 
916  stack.push(stack_itemt(&map, &other.map));
917  level_stack.push(0);
918 
919  do
920  {
921  const stack_itemt &si = stack.top();
922 
923  const nodet *ip1 = si.first;
924  const nodet *ip2 = si.second;
925 
926  SM_ASSERT(!ip1->shares_with(*ip2));
927 
928  stack.pop();
929 
930  const std::size_t level = level_stack.top();
931  level_stack.pop();
932 
933  SM_ASSERT(!ip1->empty());
934  SM_ASSERT(!ip2->empty());
935 
936  if(ip1->is_internal())
937  {
938  SM_ASSERT(!ip2->is_container());
939 
940  if(ip2->is_internal())
941  {
942  for(const auto item : ip1->get_to_map())
943  {
944  const nodet &child = item.second;
945 
946  const nodet *p;
947  p = ip2->find_child(item.first);
948 
949  if(p == nullptr)
950  {
951  if(!only_common)
952  {
953  gather_all(child, delta_view);
954  }
955  }
956  else if(!child.shares_with(*p))
957  {
958  stack.push(stack_itemt(&child, p));
959  level_stack.push(level + 1);
960  }
961  }
962  }
963  else
964  {
965  SM_ASSERT(ip2->is_leaf());
966 
967  for(const auto item : ip1->get_to_map())
968  {
969  const nodet &child = item.second;
970 
971  if(!child.shares_with(*ip2))
972  {
973  stack.push(stack_itemt(&child, ip2));
974 
975  // The level is not needed when the node of the left map is an
976  // internal node, and the node of the right map is a leaf node,
977  // hence we just push a dummy element
978  level_stack.push(dummy_level);
979  }
980  }
981  }
982  }
983  else if(ip1->is_leaf())
984  {
985  SM_ASSERT(!ip2->is_container());
986 
987  if(ip2->is_internal())
988  {
989  SM_ASSERT(level != dummy_level);
990 
991  add_item_if_not_shared(*ip1, *ip2, level, delta_view, only_common);
992  }
993  else
994  {
995  SM_ASSERT(ip2->is_leaf());
996 
997  if(equalT()(ip1->get_key(), ip2->get_key()))
998  {
999  delta_view.push_back(
1000  {ip1->get_key(), ip1->get_value(), ip2->get_value()});
1001  }
1002  else if(!only_common)
1003  {
1004  delta_view.push_back({ip1->get_key(), ip1->get_value()});
1005  }
1006  }
1007  }
1008  else
1009  {
1010  SM_ASSERT(ip1->is_container());
1011  SM_ASSERT(!ip2->is_internal());
1012 
1013  if(ip2->is_leaf())
1014  {
1015  for(const auto &l1 : ip1->get_container())
1016  {
1017  if(l1.shares_with(*ip2))
1018  {
1019  continue;
1020  }
1021 
1022  const key_type &k1 = l1.get_key();
1023 
1024  if(equalT()(k1, ip2->get_key()))
1025  {
1026  delta_view.push_back({k1, l1.get_value(), ip2->get_value()});
1027  }
1028  else if(!only_common)
1029  {
1030  delta_view.push_back({k1, l1.get_value()});
1031  }
1032  }
1033  }
1034  else
1035  {
1036  SM_ASSERT(ip2->is_container());
1037 
1038  for(const auto &l1 : ip1->get_container())
1039  {
1040  const key_type &k1 = l1.get_key();
1041  const nodet *p;
1042 
1043  p = ip2->find_leaf(k1);
1044 
1045  if(p != nullptr)
1046  {
1047  if(!l1.shares_with(*p))
1048  {
1049  SM_ASSERT(other.has_key(k1));
1050  delta_view.push_back({k1, l1.get_value(), p->get_value()});
1051  }
1052  }
1053  else if(!only_common)
1054  {
1055  SM_ASSERT(!other.has_key(k1));
1056  delta_view.push_back({k1, l1.get_value()});
1057  }
1058  }
1059  }
1060  }
1061  }
1062  while(!stack.empty());
1063 }
1064 
1065 SHARING_MAPT2(, nodet &)::get_leaf_node(const key_type &k)
1066 {
1067  SM_ASSERT(has_key(k));
1068 
1069  std::size_t key = hash()(k);
1070  nodet *ip = &map;
1072 
1073  while(true)
1074  {
1075  std::size_t bit = key & mask;
1076 
1077  ip = &ip->add_child(bit);
1078  PRECONDITION(!ip->empty()); // since the key must exist in the map
1079 
1080  if(ip->is_internal())
1081  {
1082  key >>= chunk;
1083  continue;
1084  }
1085  else if(ip->is_leaf())
1086  {
1087  return *ip;
1088  }
1089  else
1090  {
1092  return *ip->find_leaf(k);
1093  }
1094  }
1095 }
1096 
1097 SHARING_MAPT2(const, nodet *)::get_leaf_node(const key_type &k) const
1098 {
1099  if(empty())
1100  return nullptr;
1101 
1102  std::size_t key = hash()(k);
1103  const nodet *ip = &map;
1105 
1106  while(true)
1107  {
1108  std::size_t bit = key & mask;
1109 
1110  ip = ip->find_child(bit);
1111 
1112  if(ip == nullptr)
1113  return nullptr;
1114 
1115  SM_ASSERT(!ip->empty());
1116 
1117  if(ip->is_internal())
1118  {
1119  key >>= chunk;
1120  continue;
1121  }
1122  else if(ip->is_leaf())
1123  {
1124  return equalT()(ip->get_key(), k) ? ip : nullptr;
1125  }
1126  else
1127  {
1129  return ip->find_leaf(k); // returns nullptr if leaf is not found
1130  }
1131  }
1132 
1133  UNREACHABLE;
1134  return nullptr;
1135 }
1136 
1137 SHARING_MAPT(void)::erase(const key_type &k)
1138 {
1139  SM_ASSERT(has_key(k));
1140 
1141  nodet *del = nullptr;
1142  std::size_t del_bit = 0;
1143 
1144  std::size_t key = hash()(k);
1145  nodet *ip = &map;
1146 
1147  while(true)
1148  {
1149  std::size_t bit = key & mask;
1150 
1151  const to_mapt &m = as_const_ptr(ip)->get_to_map();
1152 
1153  if(m.size() > 1 || del == nullptr)
1154  {
1155  del = ip;
1156  del_bit=bit;
1157  }
1158 
1159  ip = &ip->add_child(bit);
1160 
1161  PRECONDITION(!ip->empty());
1162 
1163  if(ip->is_internal())
1164  {
1165  key >>= chunk;
1166  continue;
1167  }
1168  else if(ip->is_leaf())
1169  {
1170  PRECONDITION(equalT()(ip->get_key(), k));
1171  del->remove_child(del_bit);
1172 
1173  num--;
1174 
1175  return;
1176  }
1177  else
1178  {
1180  const leaf_listt &ll = as_const_ptr(ip)->get_container();
1181  PRECONDITION(!ll.empty());
1182 
1183  // forward list has one element
1184  if(std::next(ll.begin()) == ll.end())
1185  {
1186  PRECONDITION(equalT()(ll.front().get_key(), k));
1187  del->remove_child(del_bit);
1188  }
1189  else
1190  {
1191  ip->remove_leaf(k);
1192  }
1193 
1194  num--;
1195 
1196  return;
1197  }
1198  }
1199 
1200  UNREACHABLE;
1201 }
1202 
1203 SHARING_MAPT4(valueU, void)
1204 ::migrate(
1205  const std::size_t starting_level,
1206  const std::size_t key_suffix,
1207  const std::size_t bit_last,
1208  nodet &inner,
1209  const key_type &k,
1210  valueU &&m)
1211 {
1212  SM_ASSERT(starting_level < levels - 1);
1213  SM_ASSERT(inner.is_defined_internal());
1214 
1215  nodet &leaf = inner.add_child(bit_last);
1216  SM_ASSERT(leaf.is_defined_leaf());
1217 
1218  std::size_t key_existing = hash()(leaf.get_key());
1219  key_existing >>= chunk * starting_level;
1220 
1221  nodet leaf_kept;
1222  leaf_kept.swap(leaf);
1223 
1224  nodet *ip = &leaf;
1225  SM_ASSERT(ip->empty());
1226 
1227  // Find place for both elements
1228 
1229  std::size_t level = starting_level + 1;
1230  std::size_t key = key_suffix;
1231 
1232  key_existing >>= chunk;
1233  key >>= chunk;
1234 
1235  SM_ASSERT(level < levels);
1236 
1237  do
1238  {
1239  SM_ASSERT(ip->empty());
1240 
1241  std::size_t bit_existing = key_existing & mask;
1242  std::size_t bit = key & mask;
1243 
1244  if(bit != bit_existing)
1245  {
1246  // Place found
1247 
1248  nodet &l1 = ip->add_child(bit_existing);
1249  SM_ASSERT(l1.empty());
1250  l1.swap(leaf_kept);
1251 
1252  nodet &l2 = ip->add_child(bit);
1253  SM_ASSERT(l2.empty());
1254  l2.make_leaf(k, std::forward<valueU>(m));
1255 
1256  return;
1257  }
1258 
1259  SM_ASSERT(bit == bit_existing);
1260  ip = &ip->add_child(bit);
1261 
1262  key >>= chunk;
1263  key_existing >>= chunk;
1264 
1265  level++;
1266  } while(level < levels);
1267 
1268  // Hash collision, create container and add both elements to it
1269 
1270  PRECONDITION(!equalT()(k, leaf_kept.get_key()));
1271 
1272  SM_ASSERT(ip->empty());
1273  // Make container and add existing leaf
1274  ip->get_container().push_front(leaf_kept);
1275 
1277  // Insert new element in same container
1278  ip->place_leaf(k, std::forward<valueU>(m));
1279 }
1280 
1281 SHARING_MAPT4(valueU, void)
1282 ::insert(const key_type &k, valueU &&m)
1283 {
1284  SM_ASSERT(!has_key(k));
1285 
1286  std::size_t key = hash()(k);
1287  nodet *ip = &map;
1288 
1289  // The root must be an internal node
1290  SM_ASSERT(ip->is_internal());
1291 
1292  std::size_t level = 0;
1293 
1294  while(true)
1295  {
1296  std::size_t bit = key & mask;
1297 
1298  SM_ASSERT(ip != nullptr);
1299  SM_ASSERT(ip->is_internal());
1300  SM_ASSERT(level == 0 || !ip->empty());
1301 
1302  nodet &child = ip->add_child(bit);
1303 
1304  // Place is unoccupied
1305  if(child.empty())
1306  {
1307  if(level < levels - 1)
1308  {
1309  // Create leaf
1310  child.make_leaf(k, m);
1311  }
1312  else
1313  {
1314  SM_ASSERT(level == levels - 1);
1315 
1316  // Create container and insert leaf
1317  child.place_leaf(k, std::forward<valueU>(m));
1318 
1320  }
1321 
1322  num++;
1323 
1324  return;
1325  }
1326  else if(child.is_internal())
1327  {
1328  ip = &child;
1329  key >>= chunk;
1330  level++;
1331 
1332  continue;
1333  }
1334  else if(child.is_leaf())
1335  {
1336  // migrate leaf downwards
1337  migrate(level, key, bit, *ip, k, std::forward<valueU>(m));
1338 
1339  num++;
1340 
1341  return;
1342  }
1343  else
1344  {
1346  SM_ASSERT(level == levels - 1);
1347 
1348  // Add to the container
1349  child.place_leaf(k, std::forward<valueU>(m));
1350 
1351  num++;
1352 
1353  return;
1354  }
1355  }
1356 }
1357 
1358 SHARING_MAPT4(valueU, void)
1359 ::replace(const key_type &k, valueU &&m)
1360 {
1361  nodet &lp = get_leaf_node(k);
1362 
1363  INVARIANT(
1364  !value_equalt()(lp.get_value(), m),
1365  "values should not be replaced with equal values to maximize sharing");
1366 
1367  lp.set_value(std::forward<valueU>(m));
1368 }
1369 
1370 SHARING_MAPT(void)
1371 ::update(const key_type &k, std::function<void(mapped_type &)> mutator)
1372 {
1373  nodet &lp = get_leaf_node(k);
1374 
1375  value_comparatort comparator(lp.get_value());
1376 
1377  lp.mutate_value(mutator);
1378 
1379  INVARIANT(
1380  !comparator(lp.get_value()),
1381  "sharing_mapt::update should make some change. Consider using read-only "
1382  "method to check if an update is needed beforehand");
1383 }
1384 
1385 SHARING_MAPT2(optionalt<std::reference_wrapper<const, mapped_type>>)::find(
1386  const key_type &k) const
1387 {
1388  const nodet *lp = get_leaf_node(k);
1389 
1390  if(lp == nullptr)
1391  return {};
1392 
1394 }
1395 
1396 // static constants
1397 
1398 SHARING_MAPT(const std::size_t)::dummy_level = 0xff;
1399 
1400 SHARING_MAPT(const std::size_t)::bits = 30;
1401 SHARING_MAPT(const std::size_t)::chunk = 3;
1402 
1403 SHARING_MAPT(const std::size_t)::mask = 0xffff >> (16 - chunk);
1404 SHARING_MAPT(const std::size_t)::levels = bits / chunk;
1405 
1406 #endif
sharing_nodet::read_internal
const d_it & read_internal() const
Definition: sharing_node.h:205
sharing_mapt::falset
Definition: sharing_map.h:203
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:405
UNREACHABLE
#define UNREACHABLE
This should be used to mark dead code.
Definition: invariant.h:504
dstringt
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
Definition: dstring.h:37
sharing_nodet::is_defined_leaf
bool is_defined_leaf() const
Definition: sharing_node.h:200
sharing_mapt::sharing_map_statst
Stats about sharing between several sharing map instances.
Definition: sharing_map.h:481
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:881
sharing_mapt::gather_all
void gather_all(const nodet &n, delta_viewt &delta_view) const
Definition: sharing_map.h:797
sharing_nodet< key_type, mapped_type >::leaf_listt
d_ct::leaf_listt leaf_listt
Definition: sharing_node.h:122
SHARING_MAPT
#define SHARING_MAPT(type)
Macro to abbreviate the out-of-class definitions of methods and static variables of sharing_mapt.
Definition: sharing_map.h:48
sharing_mapt::size
size_type size() const
Get number of elements in map.
Definition: sharing_map.h:331
sharing_nodet::get_key
const keyT & get_key() const
Definition: sharing_node.h:375
sharing_mapt::delta_view_itemt::is_in_both_maps
bool is_in_both_maps() const
Definition: sharing_map.h:387
sharing_mapt::sharing_map_statst::num_nodes
std::size_t num_nodes
Definition: sharing_map.h:482
sharing_mapt
A map implemented as a tree where subtrees can be shared between different maps.
Definition: sharing_map.h:180
sharing_mapt::levels
static const std::size_t levels
Definition: sharing_map.h:591
sharing_nodet::is_leaf
bool is_leaf() const
Definition: sharing_node.h:185
threeval.h
sharing_mapt::update
void update(const key_type &k, std::function< void(mapped_type &)> mutator)
Update an element in place; element must exist in map.
Definition: sharing_map.h:1371
sharing_nodet::read_container
const d_ct & read_container() const
Definition: sharing_node.h:212
optional.h
sharing_mapt::value_comparatort
std::conditional< fail_if_equal, real_value_comparatort, noop_value_comparatort >::type value_comparatort
Definition: sharing_map.h:243
sharing_mapt::delta_view_itemt
Definition: sharing_map.h:368
sharing_mapt::erase_if_exists
void erase_if_exists(const key_type &k)
Erase element if it exists.
Definition: sharing_map.h:264
sharing_nodet::use_count
use_countt use_count() const
Definition: sharing_node.h:163
sharing_node.h
Sharing node.
replace
void replace(const union_find_replacet &replace_map, string_not_contains_constraintt &constraint)
Definition: string_constraint.cpp:67
sharing_mapt::count_unmarked_nodes
std::size_t count_unmarked_nodes(bool leafs_only, std::set< const void * > &marked, bool mark=true) const
Definition: sharing_map.h:648
sharing_mapt::key_equal
equalT key_equal
Definition: sharing_map.h:190
sharing_mapt::noop_value_comparatort::operator()
bool operator()(const mapped_type &)
Definition: sharing_map.h:220
sharing_nodet::read_leaf
const d_lt & read_leaf() const
Definition: sharing_node.h:219
sharing_mapt::hash
hashT hash
Definition: sharing_map.h:189
sharing_nodet::is_internal
bool is_internal() const
Definition: sharing_node.h:175
sharing_mapt::map
nodet map
Definition: sharing_map.h:594
sharing_mapt::chunk
static const std::size_t chunk
Definition: sharing_map.h:587
sharing_nodet::is_defined_container
bool is_defined_container() const
Definition: sharing_node.h:195
sharing_nodet::is_defined_internal
bool is_defined_internal() const
Definition: sharing_node.h:190
sharing_nodet::get_container
const leaf_listt & get_container() const
Definition: sharing_node.h:238
sharing_nodet::remove_leaf
void remove_leaf(const keyT &k)
Definition: sharing_node.h:301
sharing_mapt::sharing_map_statst::num_unique_leafs
std::size_t num_unique_leafs
Definition: sharing_map.h:485
sharing_mapt::delta_view_itemt::m
const mapped_type & m
Definition: sharing_map.h:385
sharing_mapt::add_item_if_not_shared
void add_item_if_not_shared(const nodet &leaf, const nodet &inner, const std::size_t level, delta_viewt &delta_view, const bool only_common) const
Add a delta item to the delta view if the value in the container (which must only contain a single le...
Definition: sharing_map.h:806
sharing_nodet::get_value
const valueT & get_value() const
Definition: sharing_node.h:386
SHARING_MAPT4
#define SHARING_MAPT4(template_parameter, return_type)
Macro to abbreviate the out-of-class definitions of template methods of sharing_mapt with a single te...
Definition: sharing_map.h:97
sharing_mapt::real_value_comparatort
Definition: sharing_map.h:227
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:775
sharing_mapt::size_type
std::size_t size_type
Definition: sharing_map.h:192
sharing_mapt::to_mapt
nodet::to_mapt to_mapt
Definition: sharing_map.h:199
sharing_mapt::real_value_comparatort::real_value_comparatort
real_value_comparatort(const mapped_type &old_value)
Definition: sharing_map.h:229
sharing_mapt::view_itemt
std::pair< const key_type &, const mapped_type & > view_itemt
Definition: sharing_map.h:361
sharing_mapt::mapped_type
valueT mapped_type
Definition: sharing_map.h:187
small_mapt::empty
bool empty() const
Definition: small_map.h:532
sharing_mapt::viewt
std::vector< view_itemt > viewt
View of the key-value pairs in the map.
Definition: sharing_map.h:365
sharing_mapt::iterate
void iterate(const nodet &n, std::function< void(const key_type &k, const mapped_type &m)> f) const
Definition: sharing_map.h:601
sharing_nodet::get_to_map
const to_mapt & get_to_map() const
Definition: sharing_node.h:228
sharing_mapt::sharing_map_statst::num_unique_nodes
std::size_t num_unique_nodes
Definition: sharing_map.h:483
sharing_mapt::keyst
std::vector< key_type > keyst
Definition: sharing_map.h:194
sharing_mapt::delta_view_itemt::get_other_map_value
const mapped_type & get_other_map_value() const
Definition: sharing_map.h:392
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:730
sharing_mapt::value_equalt
std::conditional< fail_if_equal, std::equal_to< valueT >, falset >::type value_equalt
Definition: sharing_map.h:212
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
sharing_mapt::noop_value_comparatort
Definition: sharing_map.h:215
sharing_mapt::mask
static const std::size_t mask
Definition: sharing_map.h:590
sharing_nodet::place_leaf
void place_leaf(const keyT &k, valueU &&v)
Definition: sharing_node.h:287
sharing_mapt::sharing_map_statst::num_leafs
std::size_t num_leafs
Definition: sharing_map.h:484
sharing_mapt::empty
bool empty() const
Check if map is empty.
Definition: sharing_map.h:337
sharing_nodet::swap
void swap(sharing_nodet &other)
Definition: sharing_node.h:168
small_mapt< innert >
sharing_nodet::shares_with
bool shares_with(const sharing_nodet &other) const
Definition: sharing_node.h:155
sharing_nodet::remove_child
void remove_child(const std::size_t n)
Definition: sharing_node.h:363
sharing_mapt::key_type
keyT key_type
Definition: sharing_map.h:186
sharing_mapt::delta_view_itemt::delta_view_itemt
delta_view_itemt(const key_type &k, const mapped_type &m)
Definition: sharing_map.h:378
optionalt
nonstd::optional< T > optionalt
Definition: optional.h:35
sharing_mapt::has_key
bool has_key(const key_type &k) const
Check if key is in map.
Definition: sharing_map.h:354
sharing_mapt::clear
void clear()
Clear map.
Definition: sharing_map.h:343
sharing_mapt::insert
void insert(const key_type &k, valueU &&m)
Insert element, element must not exist in map.
Definition: sharing_map.h:1282
sharing_mapt::dummy_level
static const std::size_t dummy_level
Definition: sharing_map.h:583
sharing_mapt::swap
void swap(sharing_mapt &other)
Swap with other map.
Definition: sharing_map.h:319
sharing_nodet::find_leaf
const leaft * find_leaf(const keyT &k) const
Definition: sharing_node.h:250
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:782
sharing_nodet::find_child
const d_it::innert * find_child(const std::size_t n) const
Definition: sharing_node.h:342
sharing_mapt::nodet
sharing_nodet< key_type, mapped_type > nodet
Definition: sharing_map.h:197
small_mapt::size
std::size_t size() const
Definition: small_map.h:526
sharing_mapt::bits
static const std::size_t bits
Definition: sharing_map.h:586
sharing_mapt::delta_view_itemt::k
const key_type & k
Definition: sharing_map.h:383
sharing_mapt::replace
void replace(const key_type &k, valueU &&m)
Replace element, element must exist in map.
Definition: sharing_map.h:1359
sharing_mapt::migrate
void migrate(const std::size_t starting_level, const std::size_t key_suffix, const std::size_t bit_last, nodet &inner, const key_type &k, valueU &&m)
Move a leaf node further down the tree such as to resolve a collision with another key-value pair.
Definition: sharing_map.h:1204
sharing_mapt::get_leaf_node
nodet & get_leaf_node(const key_type &k)
Definition: sharing_map.h:1065
sharing_mapt::falset::operator()
bool operator()(const mapped_type &lhs, const mapped_type &rhs)
Definition: sharing_map.h:204
sharing_nodet< key_type, mapped_type >
sharing_mapt::delta_view_itemt::other_m
const mapped_type * other_m
Definition: sharing_map.h:399
sharing_mapt::noop_value_comparatort::noop_value_comparatort
noop_value_comparatort(const mapped_type &)
Definition: sharing_map.h:216
SHARING_MAPT3
#define SHARING_MAPT3(template_parameter, cv_qualifiers, return_type)
Macro to abbreviate the out-of-class definitions of template methods of sharing_mapt with a single te...
Definition: sharing_map.h:80
sharing_mapt::get_leaf_node
const nodet * get_leaf_node(const key_type &k) const
Definition: sharing_map.h:1097
sharing_mapt::real_value_comparatort::old_value
mapped_type old_value
Definition: sharing_map.h:228
sharing_nodet::add_child
d_it::innert & add_child(const std::size_t n)
Definition: sharing_node.h:355
sharing_nodet::is_container
bool is_container() const
Definition: sharing_node.h:180
SM_ASSERT
#define SM_ASSERT(b)
Definition: sharing_map.h:39
sharing_mapt::iterate
void iterate(std::function< void(const key_type &k, const mapped_type &m)> f) const
Call a function for every key-value pair in the map.
Definition: sharing_map.h:460
SHARING_MAPT2
#define SHARING_MAPT2(cv_qualifiers, return_type)
Macro to abbreviate the out-of-class definitions of methods of sharing_mapt with a return type that i...
Definition: sharing_map.h:62
sharing_nodet::set_value
void set_value(valueU &&v)
Definition: sharing_node.h:402
INVARIANT
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition: invariant.h:424
sharing_nodet::mutate_value
void mutate_value(std::function< void(valueT &)> mutator)
Definition: sharing_node.h:419
sharing_mapt::erase
void erase(const key_type &k)
Erase element, element must exist in map.
Definition: sharing_map.h:1137
sharing_mapt::~sharing_mapt
~sharing_mapt()
Definition: sharing_map.h:182
sharing_nodet::empty
bool empty() const
Definition: sharing_node.h:142
sharing_nodet::make_leaf
void make_leaf(const keyT &k, valueU &&v)
Definition: sharing_node.h:394
as_const.h
sharing_mapt::num
size_type num
Definition: sharing_map.h:597
sharing_nodet::clear
void clear()
Definition: sharing_node.h:147
as_const_ptr
const T * as_const_ptr(T *t)
Return a pointer to the same object but ensures the type is pointer to const.
Definition: as_const.h:21
sharing_mapt::find
optionalt< std::reference_wrapper< const mapped_type > > find(const key_type &k) const
Find element.
Definition: sharing_map.h:1385
irep.h
sharing_mapt::real_value_comparatort::operator()
bool operator()(const mapped_type &new_value)
Definition: sharing_map.h:234
sharing_mapt::delta_view_itemt::delta_view_itemt
delta_view_itemt(const key_type &k, const mapped_type &m, const mapped_type &other_m)
Definition: sharing_map.h:370
sharing_mapt::leaf_listt
nodet::leaf_listt leaf_listt
Definition: sharing_map.h:200