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 
57 #define SHARING_MAPTV(return_type, V) \
58  template < \
59  typename keyT, \
60  typename valueT, \
61  bool fail_if_equal, \
62  typename hashT, \
63  typename equalT> \
64  template <class V> \
65  return_type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
66 
72 #define SHARING_MAPT2(cv_qualifiers, return_type) \
73  template < \
74  typename keyT, \
75  typename valueT, \
76  bool fail_if_equal, \
77  typename hashT, \
78  typename equalT> \
79  cv_qualifiers typename \
80  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>::return_type \
81  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
82 
90 #define SHARING_MAPT3(template_parameter, cv_qualifiers, return_type) \
91  template < \
92  typename keyT, \
93  typename valueT, \
94  bool fail_if_equal, \
95  typename hashT, \
96  typename equalT> \
97  template <class template_parameter> \
98  cv_qualifiers typename \
99  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>::return_type \
100  sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
101 
107 #define SHARING_MAPT4(template_parameter, return_type) \
108  template < \
109  typename keyT, \
110  typename valueT, \
111  bool fail_if_equal, \
112  typename hashT, \
113  typename equalT> \
114  template <class template_parameter> \
115  return_type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
116 // clang-format on
117 
183 template <
184  typename keyT,
185  typename valueT,
186  bool fail_if_equal = false,
187  typename hashT = std::hash<keyT>,
188  typename equalT = std::equal_to<keyT>>
190 {
191 public:
193  {
194  }
195 
196  typedef keyT key_type;
197  typedef valueT mapped_type;
198 
199  typedef hashT hash;
200  typedef equalT key_equal;
201 
202  typedef std::size_t size_type;
203 
204  typedef std::vector<key_type> keyst;
205 
206 protected:
208 
209  typedef typename nodet::to_mapt to_mapt;
210  typedef typename nodet::leaf_listt leaf_listt;
211 
212  struct falset
213  {
214  bool operator()(const mapped_type &lhs, const mapped_type &rhs)
215  {
216  return false;
217  }
218  };
219 
220  typedef
221  typename std::conditional<fail_if_equal, std::equal_to<valueT>, falset>::
223 
225  {
227  {
228  }
229 
230  bool operator()(const mapped_type &)
231  {
232  return false;
233  }
234  };
235 
237  {
241  {
242  }
243 
244  bool operator()(const mapped_type &new_value)
245  {
246  return old_value == new_value;
247  }
248  };
249 
250  typedef typename std::conditional<
251  fail_if_equal,
252  real_value_comparatort,
253  noop_value_comparatort>::type value_comparatort;
254 
255 public:
256  // interface
257 
265  void erase(const key_type &k);
266 
274  void erase_if_exists(const key_type &k)
275  {
276  if(has_key(k))
277  erase(k);
278  }
279 
288  template <class valueU>
289  void insert(const key_type &k, valueU &&m);
290 
291  template <class valueU>
292  void insert_or_replace(const key_type &k, valueU &&m)
293  {
294  if(has_key(k))
295  {
296  replace(k, std::forward<valueU>(m));
297  }
298  else
299  {
300  insert(k, std::forward<valueU>(m));
301  }
302  }
303 
312  template <class valueU>
313  void replace(const key_type &k, valueU &&m);
314 
326  void update(const key_type &k, std::function<void(mapped_type &)> mutator);
327 
337  find(const key_type &k) const;
338 
342  void swap(sharing_mapt &other)
343  {
344  map.swap(other.map);
345 
346  std::size_t tmp = num;
347  num=other.num;
348  other.num=tmp;
349  }
350 
354  size_type size() const
355  {
356  return num;
357  }
358 
360  bool empty() const
361  {
362  return num==0;
363  }
364 
366  void clear()
367  {
368  map.clear();
369  num=0;
370  }
371 
377  bool has_key(const key_type &k) const
378  {
379  return get_leaf_node(k)!=nullptr;
380  }
381 
382  // views
383 
384  typedef std::pair<const key_type &, const mapped_type &> view_itemt;
385 
388  typedef std::vector<view_itemt> viewt;
389  typedef std::set<view_itemt> sorted_viewt;
390 
391  static void insert_view_item(viewt &v, view_itemt &&vi)
392  {
393  v.push_back(vi);
394  }
395 
397  {
398  v.insert(vi);
399  }
400 
402  {
403  public:
405  const key_type &k,
406  const mapped_type &m,
407  const mapped_type &other_m)
408  : k(k), m(m), other_m(&other_m)
409  {
410  }
411 
413  : k(k), m(m), other_m(nullptr)
414  {
415  }
416 
417  const key_type &k;
418 
419  const mapped_type &m;
420 
421  bool is_in_both_maps() const
422  {
423  return other_m != nullptr;
424  }
425 
427  {
429  return *other_m;
430  }
431 
432  private:
434  };
435 
439  typedef std::vector<delta_view_itemt> delta_viewt;
440 
450  template <class V>
451  void get_view(V &view) const;
452  viewt get_view() const
453  {
454  viewt result;
455  get_view(result);
456  return result;
457  }
463  {
464  sorted_viewt result;
465  get_view(result);
466  return result;
467  }
468 
503  const sharing_mapt &other,
504  delta_viewt &delta_view,
505  const bool only_common = true) const;
506 
508  const sharing_mapt &other,
509  const bool only_common = true) const;
510 
514  void
515  iterate(std::function<void(const key_type &k, const mapped_type &m)> f) const
516  {
517  if(empty())
518  return;
519 
520  iterate(map, f);
521  }
522 
523 #if !defined(_MSC_VER)
524  struct sharing_map_statst
536  {
537  std::size_t num_nodes = 0;
538  std::size_t num_unique_nodes = 0;
539  std::size_t num_leafs = 0;
540  std::size_t num_unique_leafs = 0;
541  };
542 
553  template <class Iterator>
554  static sharing_map_statst get_sharing_stats(
555  Iterator begin,
556  Iterator end,
557  std::function<sharing_mapt &(const Iterator)> f =
558  [](const Iterator it) -> sharing_mapt & { return *it; });
559 
569  template <class Iterator>
570  static sharing_map_statst get_sharing_stats_map(Iterator begin, Iterator end);
571 #endif
572 
573 protected:
574  // helpers
575 
577  const nodet *get_leaf_node(const key_type &k) const;
578 
597  template <class valueU>
598  void migrate(
599  const std::size_t starting_level,
600  const std::size_t key_suffix,
601  const std::size_t bit_last,
602  nodet &inner,
603  const key_type &k,
604  valueU &&m);
605 
606  void iterate(
607  const nodet &n,
608  std::function<void(const key_type &k, const mapped_type &m)> f) const;
609 
625  const nodet &leaf,
626  const nodet &inner,
627  const std::size_t level,
628  delta_viewt &delta_view,
629  const bool only_common) const;
630 
631  void gather_all(const nodet &n, delta_viewt &delta_view) const;
632 
633  std::size_t count_unmarked_nodes(
634  bool leafs_only,
635  std::set<const void *> &marked,
636  bool mark = true) const;
637 
638  static const std::size_t dummy_level;
639 
640  // config
641  static const std::size_t bits;
642  static const std::size_t chunk;
643 
644  // derived config
645  static const std::size_t mask;
646  static const std::size_t levels;
647 
648  // key-value map
650 
651  // number of elements in the map
653 };
654 
655 SHARING_MAPT(void)
656 ::iterate(
657  const nodet &n,
658  std::function<void(const key_type &k, const mapped_type &m)> f) const
659 {
660  SM_ASSERT(!n.empty());
661 
662  std::stack<const nodet *> stack;
663  stack.push(&n);
664 
665  do
666  {
667  const nodet *ip = stack.top();
668  stack.pop();
669 
670  SM_ASSERT(!ip->empty());
671 
672  if(ip->is_internal())
673  {
674  const to_mapt &m = ip->get_to_map();
675  SM_ASSERT(!m.empty());
676 
677  for(const auto item : m)
678  {
679  stack.push(&item.second);
680  }
681  }
682  else if(ip->is_leaf())
683  {
684  f(ip->get_key(), ip->get_value());
685  }
686  else
687  {
689 
690  const leaf_listt &ll = ip->get_container();
691  SM_ASSERT(!ll.empty());
692 
693  for(const auto &l : ll)
694  {
695  f(l.get_key(), l.get_value());
696  }
697  }
698  }
699  while(!stack.empty());
700 }
701 
702 SHARING_MAPT(std::size_t)
703 ::count_unmarked_nodes(
704  bool leafs_only,
705  std::set<const void *> &marked,
706  bool mark) const
707 {
708  if(empty())
709  return 0;
710 
711  unsigned count = 0;
712 
713  std::stack<const nodet *> stack;
714  stack.push(&map);
715 
716  do
717  {
718  const nodet *ip = stack.top();
719  SM_ASSERT(!ip->empty());
720  stack.pop();
721 
722  const unsigned use_count = ip->use_count();
723 
724  const void *raw_ptr =
725  ip->is_internal() ? (const void *)&ip->read_internal()
726  : ip->is_leaf() ? (const void *)&ip->read_leaf()
727  : (const void *)&ip->read_container();
728 
729  if(use_count >= 2)
730  {
731  if(marked.find(raw_ptr) != marked.end())
732  {
733  continue;
734  }
735 
736  if(mark)
737  {
738  marked.insert(raw_ptr);
739  }
740  }
741 
742  if(ip->is_internal())
743  {
744  if(!leafs_only)
745  {
746  count++;
747  }
748 
749  const to_mapt &m = ip->get_to_map();
750  SM_ASSERT(!m.empty());
751 
752  for(const auto item : m)
753  {
754  stack.push(&item.second);
755  }
756  }
757  else if(ip->is_leaf())
758  {
759  count++;
760  }
761  else
762  {
764 
765  if(!leafs_only)
766  {
767  count++;
768  }
769 
770  const leaf_listt &ll = ip->get_container();
771  SM_ASSERT(!ll.empty());
772 
773  for(const auto &l : ll)
774  {
775  stack.push(&l);
776  }
777  }
778  } while(!stack.empty());
779 
780  return count;
781 }
782 
783 #if !defined(_MSC_VER)
784 SHARING_MAPT3(Iterator, , sharing_map_statst)
785 ::get_sharing_stats(
786  Iterator begin,
787  Iterator end,
788  std::function<sharing_mapt &(const Iterator)> f)
789 {
790  std::set<const void *> marked;
791  sharing_map_statst sms;
792 
793  // We do a separate pass over the tree for each statistic. This is not very
794  // efficient but the function is intended only for diagnosis purposes anyways.
795 
796  // number of nodes
797  for(Iterator it = begin; it != end; it++)
798  {
799  sms.num_nodes += f(it).count_unmarked_nodes(false, marked, false);
800  }
801 
802  SM_ASSERT(marked.empty());
803 
804  // number of unique nodes
805  for(Iterator it = begin; it != end; it++)
806  {
807  sms.num_unique_nodes += f(it).count_unmarked_nodes(false, marked, true);
808  }
809 
810  marked.clear();
811 
812  // number of leafs
813  for(Iterator it = begin; it != end; it++)
814  {
815  sms.num_leafs += f(it).count_unmarked_nodes(true, marked, false);
816  }
817 
818  SM_ASSERT(marked.empty());
819 
820  // number of unique leafs
821  for(Iterator it = begin; it != end; it++)
822  {
823  sms.num_unique_leafs += f(it).count_unmarked_nodes(true, marked, true);
824  }
825 
826  return sms;
827 }
828 
829 SHARING_MAPT3(Iterator, , sharing_map_statst)
830 ::get_sharing_stats_map(Iterator begin, Iterator end)
831 {
832  return get_sharing_stats<Iterator>(
833  begin, end, [](const Iterator it) -> sharing_mapt & { return it->second; });
834 }
835 #endif
836 
837 SHARING_MAPTV(void, view_type)::get_view(view_type &view) const
838 {
839  SM_ASSERT(view.empty());
840 
841  if(empty())
842  return;
843 
844  auto f = [&view](const key_type &k, const mapped_type &m) {
845  insert_view_item(view, view_itemt(k, m));
846  };
847 
848  iterate(map, f);
849 }
850 
851 SHARING_MAPT(void)
852 ::gather_all(const nodet &n, delta_viewt &delta_view) const
853 {
854  auto f = [&delta_view](const key_type &k, const mapped_type &m) {
855  delta_view.push_back(delta_view_itemt(k, m));
856  };
857 
858  iterate(n, f);
859 }
860 
861 SHARING_MAPT(void)::add_item_if_not_shared(
862  const nodet &leaf,
863  const nodet &inner,
864  const std::size_t level,
865  delta_viewt &delta_view,
866  const bool only_common) const
867 {
868  const auto &k = leaf.get_key();
869  std::size_t key = hash()(k);
870 
871  key >>= level * chunk;
872 
873  const nodet *ip = &inner;
875 
876  while(true)
877  {
878  std::size_t bit = key & mask;
879 
880  ip = ip->find_child(bit);
881 
882  // only in first map
883  if(ip == nullptr)
884  {
885  if(!only_common)
886  {
887  delta_view.push_back({k, leaf.get_value()});
888  }
889 
890  return;
891  }
892 
893  SM_ASSERT(!ip->empty());
894 
895  // potentially in both maps
896  if(ip->is_container())
897  {
898  for(const auto &l2 : ip->get_container())
899  {
900  if(leaf.shares_with(l2))
901  return;
902 
903  if(leaf.get_key() == l2.get_key())
904  {
905  delta_view.push_back({k, leaf.get_value(), l2.get_value()});
906  return;
907  }
908  }
909 
910  delta_view.push_back({k, leaf.get_value()});
911 
912  return;
913  }
914 
915  if(ip->is_leaf())
916  {
917  if(ip->shares_with(leaf))
918  return;
919 
920  if(equalT()(leaf.get_key(), ip->get_key()))
921  {
922  delta_view.push_back({k, leaf.get_value(), ip->get_value()});
923  return;
924  }
925 
926  delta_view.push_back({k, leaf.get_value()});
927 
928  return;
929  }
930 
931  key >>= chunk;
932  }
933 }
934 
935 SHARING_MAPT(void)
936 ::get_delta_view(
937  const sharing_mapt &other,
938  delta_viewt &delta_view,
939  const bool only_common) const
940 {
941  SM_ASSERT(delta_view.empty());
942 
943  if(empty())
944  return;
945 
946  if(other.empty())
947  {
948  if(!only_common)
949  {
950  gather_all(map, delta_view);
951  }
952 
953  return;
954  }
955 
956  typedef std::pair<const nodet *, const nodet *> stack_itemt;
957  std::stack<stack_itemt> stack;
958 
959  std::stack<std::size_t> level_stack;
960 
961  // We do a DFS "in lockstep" simultaneously on both maps. For
962  // corresponding nodes we check whether they are shared between the
963  // maps, and if not, we recurse into the corresponding subtrees.
964 
965  // The stack contains the children of already visited nodes that we
966  // still have to visit during the traversal.
967 
968  if(map.shares_with(other.map))
969  return;
970 
971  stack.push(stack_itemt(&map, &other.map));
972  level_stack.push(0);
973 
974  do
975  {
976  const stack_itemt &si = stack.top();
977 
978  const nodet *ip1 = si.first;
979  const nodet *ip2 = si.second;
980 
981  SM_ASSERT(!ip1->shares_with(*ip2));
982 
983  stack.pop();
984 
985  const std::size_t level = level_stack.top();
986  level_stack.pop();
987 
988  SM_ASSERT(!ip1->empty());
989  SM_ASSERT(!ip2->empty());
990 
991  if(ip1->is_internal())
992  {
993  SM_ASSERT(!ip2->is_container());
994 
995  if(ip2->is_internal())
996  {
997  for(const auto item : ip1->get_to_map())
998  {
999  const nodet &child = item.second;
1000 
1001  const nodet *p;
1002  p = ip2->find_child(item.first);
1003 
1004  if(p == nullptr)
1005  {
1006  if(!only_common)
1007  {
1008  gather_all(child, delta_view);
1009  }
1010  }
1011  else if(!child.shares_with(*p))
1012  {
1013  stack.push(stack_itemt(&child, p));
1014  level_stack.push(level + 1);
1015  }
1016  }
1017  }
1018  else
1019  {
1020  SM_ASSERT(ip2->is_leaf());
1021 
1022  for(const auto item : ip1->get_to_map())
1023  {
1024  const nodet &child = item.second;
1025 
1026  if(!child.shares_with(*ip2))
1027  {
1028  stack.push(stack_itemt(&child, ip2));
1029 
1030  // The level is not needed when the node of the left map is an
1031  // internal node, and the node of the right map is a leaf node,
1032  // hence we just push a dummy element
1033  level_stack.push(dummy_level);
1034  }
1035  }
1036  }
1037  }
1038  else if(ip1->is_leaf())
1039  {
1040  SM_ASSERT(!ip2->is_container());
1041 
1042  if(ip2->is_internal())
1043  {
1044  SM_ASSERT(level != dummy_level);
1045 
1046  add_item_if_not_shared(*ip1, *ip2, level, delta_view, only_common);
1047  }
1048  else
1049  {
1050  SM_ASSERT(ip2->is_leaf());
1051 
1052  if(equalT()(ip1->get_key(), ip2->get_key()))
1053  {
1054  delta_view.push_back(
1055  {ip1->get_key(), ip1->get_value(), ip2->get_value()});
1056  }
1057  else if(!only_common)
1058  {
1059  delta_view.push_back({ip1->get_key(), ip1->get_value()});
1060  }
1061  }
1062  }
1063  else
1064  {
1065  SM_ASSERT(ip1->is_container());
1066  SM_ASSERT(!ip2->is_internal());
1067 
1068  if(ip2->is_leaf())
1069  {
1070  for(const auto &l1 : ip1->get_container())
1071  {
1072  if(l1.shares_with(*ip2))
1073  {
1074  continue;
1075  }
1076 
1077  const key_type &k1 = l1.get_key();
1078 
1079  if(equalT()(k1, ip2->get_key()))
1080  {
1081  delta_view.push_back({k1, l1.get_value(), ip2->get_value()});
1082  }
1083  else if(!only_common)
1084  {
1085  delta_view.push_back({k1, l1.get_value()});
1086  }
1087  }
1088  }
1089  else
1090  {
1091  SM_ASSERT(ip2->is_container());
1092 
1093  for(const auto &l1 : ip1->get_container())
1094  {
1095  const key_type &k1 = l1.get_key();
1096  const nodet *p;
1097 
1098  p = ip2->find_leaf(k1);
1099 
1100  if(p != nullptr)
1101  {
1102  if(!l1.shares_with(*p))
1103  {
1104  SM_ASSERT(other.has_key(k1));
1105  delta_view.push_back({k1, l1.get_value(), p->get_value()});
1106  }
1107  }
1108  else if(!only_common)
1109  {
1110  SM_ASSERT(!other.has_key(k1));
1111  delta_view.push_back({k1, l1.get_value()});
1112  }
1113  }
1114  }
1115  }
1116  }
1117  while(!stack.empty());
1118 }
1119 
1120 SHARING_MAPT2(, delta_viewt)::get_delta_view(
1121  const sharing_mapt &other,
1122  const bool only_common) const
1123 {
1124  delta_viewt delta_view;
1125  get_delta_view(other, delta_view, only_common);
1126  return delta_view;
1127 }
1128 
1129 SHARING_MAPT2(, nodet &)::get_leaf_node(const key_type &k)
1130 {
1131  SM_ASSERT(has_key(k));
1132 
1133  std::size_t key = hash()(k);
1134  nodet *ip = &map;
1136 
1137  while(true)
1138  {
1139  std::size_t bit = key & mask;
1140 
1141  ip = &ip->add_child(bit);
1142  PRECONDITION(!ip->empty()); // since the key must exist in the map
1143 
1144  if(ip->is_internal())
1145  {
1146  key >>= chunk;
1147  continue;
1148  }
1149  else if(ip->is_leaf())
1150  {
1151  return *ip;
1152  }
1153  else
1154  {
1156  return *ip->find_leaf(k);
1157  }
1158  }
1159 }
1160 
1161 SHARING_MAPT2(const, nodet *)::get_leaf_node(const key_type &k) const
1162 {
1163  if(empty())
1164  return nullptr;
1165 
1166  std::size_t key = hash()(k);
1167  const nodet *ip = &map;
1169 
1170  while(true)
1171  {
1172  std::size_t bit = key & mask;
1173 
1174  ip = ip->find_child(bit);
1175 
1176  if(ip == nullptr)
1177  return nullptr;
1178 
1179  SM_ASSERT(!ip->empty());
1180 
1181  if(ip->is_internal())
1182  {
1183  key >>= chunk;
1184  continue;
1185  }
1186  else if(ip->is_leaf())
1187  {
1188  return equalT()(ip->get_key(), k) ? ip : nullptr;
1189  }
1190  else
1191  {
1193  return ip->find_leaf(k); // returns nullptr if leaf is not found
1194  }
1195  }
1196 
1197  UNREACHABLE;
1198  return nullptr;
1199 }
1200 
1201 SHARING_MAPT(void)::erase(const key_type &k)
1202 {
1203  SM_ASSERT(has_key(k));
1204 
1205  nodet *del = nullptr;
1206  std::size_t del_bit = 0;
1207 
1208  std::size_t key = hash()(k);
1209  nodet *ip = &map;
1210 
1211  while(true)
1212  {
1213  std::size_t bit = key & mask;
1214 
1215  const to_mapt &m = as_const_ptr(ip)->get_to_map();
1216 
1217  if(m.size() > 1 || del == nullptr)
1218  {
1219  del = ip;
1220  del_bit=bit;
1221  }
1222 
1223  ip = &ip->add_child(bit);
1224 
1225  PRECONDITION(!ip->empty());
1226 
1227  if(ip->is_internal())
1228  {
1229  key >>= chunk;
1230  continue;
1231  }
1232  else if(ip->is_leaf())
1233  {
1234  PRECONDITION(equalT()(ip->get_key(), k));
1235  del->remove_child(del_bit);
1236 
1237  num--;
1238 
1239  return;
1240  }
1241  else
1242  {
1244  const leaf_listt &ll = as_const_ptr(ip)->get_container();
1245  PRECONDITION(!ll.empty());
1246 
1247  // forward list has one element
1248  if(std::next(ll.begin()) == ll.end())
1249  {
1250  PRECONDITION(equalT()(ll.front().get_key(), k));
1251  del->remove_child(del_bit);
1252  }
1253  else
1254  {
1255  ip->remove_leaf(k);
1256  }
1257 
1258  num--;
1259 
1260  return;
1261  }
1262  }
1263 
1264  UNREACHABLE;
1265 }
1266 
1267 SHARING_MAPT4(valueU, void)
1268 ::migrate(
1269  const std::size_t starting_level,
1270  const std::size_t key_suffix,
1271  const std::size_t bit_last,
1272  nodet &inner,
1273  const key_type &k,
1274  valueU &&m)
1275 {
1276  SM_ASSERT(starting_level < levels - 1);
1277  SM_ASSERT(inner.is_defined_internal());
1278 
1279  nodet &leaf = inner.add_child(bit_last);
1280  SM_ASSERT(leaf.is_defined_leaf());
1281 
1282  std::size_t key_existing = hash()(leaf.get_key());
1283  key_existing >>= chunk * starting_level;
1284 
1285  nodet leaf_kept;
1286  leaf_kept.swap(leaf);
1287 
1288  nodet *ip = &leaf;
1289  SM_ASSERT(ip->empty());
1290 
1291  // Find place for both elements
1292 
1293  std::size_t level = starting_level + 1;
1294  std::size_t key = key_suffix;
1295 
1296  key_existing >>= chunk;
1297  key >>= chunk;
1298 
1299  SM_ASSERT(level < levels);
1300 
1301  do
1302  {
1303  SM_ASSERT(ip->empty());
1304 
1305  std::size_t bit_existing = key_existing & mask;
1306  std::size_t bit = key & mask;
1307 
1308  if(bit != bit_existing)
1309  {
1310  // Place found
1311 
1312  nodet &l1 = ip->add_child(bit_existing);
1313  SM_ASSERT(l1.empty());
1314  l1.swap(leaf_kept);
1315 
1316  nodet &l2 = ip->add_child(bit);
1317  SM_ASSERT(l2.empty());
1318  l2.make_leaf(k, std::forward<valueU>(m));
1319 
1320  return;
1321  }
1322 
1323  SM_ASSERT(bit == bit_existing);
1324  ip = &ip->add_child(bit);
1325 
1326  key >>= chunk;
1327  key_existing >>= chunk;
1328 
1329  level++;
1330  } while(level < levels);
1331 
1332  // Hash collision, create container and add both elements to it
1333 
1334  PRECONDITION(!equalT()(k, leaf_kept.get_key()));
1335 
1336  SM_ASSERT(ip->empty());
1337  // Make container and add existing leaf
1338  ip->get_container().push_front(leaf_kept);
1339 
1341  // Insert new element in same container
1342  ip->place_leaf(k, std::forward<valueU>(m));
1343 }
1344 
1345 SHARING_MAPT4(valueU, void)
1346 ::insert(const key_type &k, valueU &&m)
1347 {
1348  SM_ASSERT(!has_key(k));
1349 
1350  std::size_t key = hash()(k);
1351  nodet *ip = &map;
1352 
1353  // The root must be an internal node
1354  SM_ASSERT(ip->is_internal());
1355 
1356  std::size_t level = 0;
1357 
1358  while(true)
1359  {
1360  std::size_t bit = key & mask;
1361 
1362  SM_ASSERT(ip != nullptr);
1363  SM_ASSERT(ip->is_internal());
1364  SM_ASSERT(level == 0 || !ip->empty());
1365 
1366  nodet &child = ip->add_child(bit);
1367 
1368  // Place is unoccupied
1369  if(child.empty())
1370  {
1371  if(level < levels - 1)
1372  {
1373  // Create leaf
1374  child.make_leaf(k, m);
1375  }
1376  else
1377  {
1378  SM_ASSERT(level == levels - 1);
1379 
1380  // Create container and insert leaf
1381  child.place_leaf(k, std::forward<valueU>(m));
1382 
1384  }
1385 
1386  num++;
1387 
1388  return;
1389  }
1390  else if(child.is_internal())
1391  {
1392  ip = &child;
1393  key >>= chunk;
1394  level++;
1395 
1396  continue;
1397  }
1398  else if(child.is_leaf())
1399  {
1400  // migrate leaf downwards
1401  migrate(level, key, bit, *ip, k, std::forward<valueU>(m));
1402 
1403  num++;
1404 
1405  return;
1406  }
1407  else
1408  {
1410  SM_ASSERT(level == levels - 1);
1411 
1412  // Add to the container
1413  child.place_leaf(k, std::forward<valueU>(m));
1414 
1415  num++;
1416 
1417  return;
1418  }
1419  }
1420 }
1421 
1422 SHARING_MAPT4(valueU, void)
1423 ::replace(const key_type &k, valueU &&m)
1424 {
1425  nodet &lp = get_leaf_node(k);
1426 
1427  INVARIANT(
1428  !value_equalt()(lp.get_value(), m),
1429  "values should not be replaced with equal values to maximize sharing");
1430 
1431  lp.set_value(std::forward<valueU>(m));
1432 }
1433 
1434 SHARING_MAPT(void)
1435 ::update(const key_type &k, std::function<void(mapped_type &)> mutator)
1436 {
1437  nodet &lp = get_leaf_node(k);
1438 
1439  value_comparatort comparator(lp.get_value());
1440 
1441  lp.mutate_value(mutator);
1442 
1443  INVARIANT(
1444  !comparator(lp.get_value()),
1445  "sharing_mapt::update should make some change. Consider using read-only "
1446  "method to check if an update is needed beforehand");
1447 }
1448 
1449 SHARING_MAPT2(optionalt<std::reference_wrapper<const, mapped_type>>)::find(
1450  const key_type &k) const
1451 {
1452  const nodet *lp = get_leaf_node(k);
1453 
1454  if(lp == nullptr)
1455  return {};
1456 
1458 }
1459 
1460 // static constants
1461 
1462 SHARING_MAPT(const std::size_t)::dummy_level = 0xff;
1463 
1464 SHARING_MAPT(const std::size_t)::bits = 30;
1465 SHARING_MAPT(const std::size_t)::chunk = 3;
1466 
1467 SHARING_MAPT(const std::size_t)::mask = 0xffff >> (16 - chunk);
1468 SHARING_MAPT(const std::size_t)::levels = bits / chunk;
1469 
1470 #endif
sharing_nodet::read_internal
const d_it & read_internal() const
Definition: sharing_node.h:205
sharing_mapt::falset
Definition: sharing_map.h:213
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:439
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:536
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:936
sharing_mapt::gather_all
void gather_all(const nodet &n, delta_viewt &delta_view) const
Definition: sharing_map.h:852
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:354
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:421
sharing_mapt::insert_view_item
static void insert_view_item(sorted_viewt &v, view_itemt &&vi)
Definition: sharing_map.h:396
sharing_mapt::sharing_map_statst::num_nodes
std::size_t num_nodes
Definition: sharing_map.h:537
sharing_mapt
A map implemented as a tree where subtrees can be shared between different maps.
Definition: sharing_map.h:190
sharing_mapt::levels
static const std::size_t levels
Definition: sharing_map.h:646
sharing_mapt::get_delta_view
delta_viewt get_delta_view(const sharing_mapt &other, const bool only_common=true) const
Definition: sharing_map.h:1120
sharing_nodet::is_leaf
bool is_leaf() const
Definition: sharing_node.h:185
sharing_mapt::get_view
void get_view(V &view) const
Get a view of the elements in the map A view is a list of pairs with the components being const refer...
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:1435
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:253
sharing_mapt::delta_view_itemt
Definition: sharing_map.h:402
sharing_mapt::erase_if_exists
void erase_if_exists(const key_type &k)
Erase element if it exists.
Definition: sharing_map.h:274
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::get_sorted_view
sorted_viewt get_sorted_view() const
Convenience function to get a sorted view of the map elements.
Definition: sharing_map.h:462
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:703
sharing_mapt::key_equal
equalT key_equal
Definition: sharing_map.h:200
sharing_mapt::noop_value_comparatort::operator()
bool operator()(const mapped_type &)
Definition: sharing_map.h:230
sharing_nodet::read_leaf
const d_lt & read_leaf() const
Definition: sharing_node.h:219
sharing_mapt::hash
hashT hash
Definition: sharing_map.h:199
sharing_nodet::is_internal
bool is_internal() const
Definition: sharing_node.h:175
sharing_mapt::map
nodet map
Definition: sharing_map.h:649
sharing_mapt::chunk
static const std::size_t chunk
Definition: sharing_map.h:642
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::sorted_viewt
std::set< view_itemt > sorted_viewt
Definition: sharing_map.h:389
sharing_mapt::sharing_map_statst::num_unique_leafs
std::size_t num_unique_leafs
Definition: sharing_map.h:540
sharing_mapt::delta_view_itemt::m
const mapped_type & m
Definition: sharing_map.h:419
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:861
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:107
sharing_mapt::real_value_comparatort
Definition: sharing_map.h:237
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:830
sharing_mapt::size_type
std::size_t size_type
Definition: sharing_map.h:202
sharing_mapt::to_mapt
nodet::to_mapt to_mapt
Definition: sharing_map.h:209
sharing_mapt::real_value_comparatort::real_value_comparatort
real_value_comparatort(const mapped_type &old_value)
Definition: sharing_map.h:239
sharing_mapt::view_itemt
std::pair< const key_type &, const mapped_type & > view_itemt
Definition: sharing_map.h:384
sharing_mapt::mapped_type
valueT mapped_type
Definition: sharing_map.h:197
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:388
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:656
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:538
sharing_mapt::keyst
std::vector< key_type > keyst
Definition: sharing_map.h:204
sharing_mapt::delta_view_itemt::get_other_map_value
const mapped_type & get_other_map_value() const
Definition: sharing_map.h:426
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:785
sharing_mapt::value_equalt
std::conditional< fail_if_equal, std::equal_to< valueT >, falset >::type value_equalt
Definition: sharing_map.h:222
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:464
sharing_mapt::noop_value_comparatort
Definition: sharing_map.h:225
sharing_mapt::mask
static const std::size_t mask
Definition: sharing_map.h:645
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:539
sharing_mapt::insert_or_replace
void insert_or_replace(const key_type &k, valueU &&m)
Definition: sharing_map.h:292
sharing_mapt::empty
bool empty() const
Check if map is empty.
Definition: sharing_map.h:360
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:196
sharing_mapt::delta_view_itemt::delta_view_itemt
delta_view_itemt(const key_type &k, const mapped_type &m)
Definition: sharing_map.h:412
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:377
sharing_mapt::clear
void clear()
Clear map.
Definition: sharing_map.h:366
sharing_mapt::insert
void insert(const key_type &k, valueU &&m)
Insert element, element must not exist in map.
Definition: sharing_map.h:1346
sharing_mapt::dummy_level
static const std::size_t dummy_level
Definition: sharing_map.h:638
sharing_mapt::swap
void swap(sharing_mapt &other)
Swap with other map.
Definition: sharing_map.h:342
sharing_nodet::find_leaf
const leaft * find_leaf(const keyT &k) const
Definition: sharing_node.h:250
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:207
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:641
sharing_mapt::delta_view_itemt::k
const key_type & k
Definition: sharing_map.h:417
sharing_mapt::replace
void replace(const key_type &k, valueU &&m)
Replace element, element must exist in map.
Definition: sharing_map.h:1423
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:1268
sharing_mapt::get_leaf_node
nodet & get_leaf_node(const key_type &k)
Definition: sharing_map.h:1129
sharing_mapt::falset::operator()
bool operator()(const mapped_type &lhs, const mapped_type &rhs)
Definition: sharing_map.h:214
sharing_nodet< key_type, mapped_type >
sharing_mapt::delta_view_itemt::other_m
const mapped_type * other_m
Definition: sharing_map.h:433
sharing_mapt::get_view
viewt get_view() const
Definition: sharing_map.h:452
sharing_mapt::noop_value_comparatort::noop_value_comparatort
noop_value_comparatort(const mapped_type &)
Definition: sharing_map.h:226
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:90
sharing_mapt::get_leaf_node
const nodet * get_leaf_node(const key_type &k) const
Definition: sharing_map.h:1161
sharing_mapt::real_value_comparatort::old_value
mapped_type old_value
Definition: sharing_map.h:238
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_MAPTV
#define SHARING_MAPTV(return_type, V)
Definition: sharing_map.h:57
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:515
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:72
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:1201
sharing_mapt::~sharing_mapt
~sharing_mapt()
Definition: sharing_map.h:192
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:652
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:1449
sharing_mapt::insert_view_item
static void insert_view_item(viewt &v, view_itemt &&vi)
Definition: sharing_map.h:391
irep.h
sharing_mapt::real_value_comparatort::operator()
bool operator()(const mapped_type &new_value)
Definition: sharing_map.h:244
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:404
sharing_mapt::leaf_listt
nodet::leaf_listt leaf_listt
Definition: sharing_map.h:210