Go to the documentation of this file.
12 #ifndef CPROVER_UTIL_SHARING_MAP_H
13 #define CPROVER_UTIL_SHARING_MAP_H
27 #include <type_traits>
36 #ifdef SM_INTERNAL_CHECKS
37 #define SM_ASSERT(b) INVARIANT(b, "Sharing map internal invariant")
48 #define SHARING_MAPT(type) \
55 type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
57 #define SHARING_MAPTV(return_type, V) \
65 return_type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
72 #define SHARING_MAPT2(cv_qualifiers, return_type) \
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>
90 #define SHARING_MAPT3(template_parameter, cv_qualifiers, return_type) \
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>
107 #define SHARING_MAPT4(template_parameter, return_type) \
111 bool fail_if_equal, \
114 template <class template_parameter> \
115 return_type sharing_mapt<keyT, valueT, fail_if_equal, hashT, equalT>
186 bool fail_if_equal =
false,
187 typename hashT = std::hash<keyT>,
188 typename equalT = std::equal_to<keyT>>
204 typedef std::vector<key_type>
keyst;
221 typename std::conditional<fail_if_equal, std::equal_to<valueT>, falset>::
250 typedef typename std::conditional<
252 real_value_comparatort,
288 template <
class valueU>
291 template <
class valueU>
296 replace(k, std::forward<valueU>(m));
300 insert(k, std::forward<valueU>(m));
312 template <
class valueU>
346 std::size_t tmp =
num;
384 typedef std::pair<const key_type &, const mapped_type &>
view_itemt;
388 typedef std::vector<view_itemt>
viewt;
505 const bool only_common =
true)
const;
509 const bool only_common =
true)
const;
523 #if !defined(_MSC_VER)
524 struct sharing_map_statst
553 template <
class Iterator>
558 [](
const Iterator it) ->
sharing_mapt & {
return *it; });
569 template <
class Iterator>
597 template <
class valueU>
599 const std::size_t starting_level,
600 const std::size_t key_suffix,
601 const std::size_t bit_last,
627 const std::size_t level,
629 const bool only_common)
const;
635 std::set<const void *> &marked,
636 bool mark =
true)
const;
662 std::stack<const nodet *> stack;
667 const nodet *ip = stack.top();
677 for(
const auto item : m)
679 stack.push(&item.second);
693 for(
const auto &l : ll)
695 f(l.get_key(), l.get_value());
699 while(!stack.empty());
703 ::count_unmarked_nodes(
705 std::set<const void *> &marked,
713 std::stack<const nodet *> stack;
718 const nodet *ip = stack.top();
722 const unsigned use_count = ip->
use_count();
724 const void *raw_ptr =
731 if(marked.find(raw_ptr) != marked.end())
738 marked.insert(raw_ptr);
752 for(
const auto item : m)
754 stack.push(&item.second);
773 for(
const auto &l : ll)
778 }
while(!stack.empty());
783 #if !defined(_MSC_VER)
790 std::set<const void *> marked;
797 for(Iterator it = begin; it != end; it++)
799 sms.num_nodes += f(it).count_unmarked_nodes(
false, marked,
false);
805 for(Iterator it = begin; it != end; it++)
807 sms.num_unique_nodes += f(it).count_unmarked_nodes(
false, marked,
true);
813 for(Iterator it = begin; it != end; it++)
815 sms.num_leafs += f(it).count_unmarked_nodes(
true, marked,
false);
821 for(Iterator it = begin; it != end; it++)
823 sms.num_unique_leafs += f(it).count_unmarked_nodes(
true, marked,
true);
830 ::get_sharing_stats_map(Iterator begin, Iterator end)
832 return get_sharing_stats<Iterator>(
833 begin, end, [](
const Iterator it) ->
sharing_mapt & {
return it->second; });
864 const std::size_t level,
866 const bool only_common) const
868 const auto &k = leaf.get_key();
869 std::size_t key =
hash()(k);
871 key >>= level * chunk;
873 const nodet *ip = &inner;
878 std::size_t bit = key & mask;
887 delta_view.push_back({k, leaf.get_value()});
900 if(leaf.shares_with(l2))
903 if(leaf.get_key() == l2.get_key())
905 delta_view.push_back({k, leaf.get_value(), l2.get_value()});
910 delta_view.push_back({k, leaf.get_value()});
920 if(equalT()(leaf.get_key(), ip->
get_key()))
922 delta_view.push_back({k, leaf.get_value(), ip->
get_value()});
926 delta_view.push_back({k, leaf.get_value()});
939 const bool only_common) const
950 gather_all(map, delta_view);
956 typedef std::pair<const nodet *, const nodet *> stack_itemt;
957 std::stack<stack_itemt> stack;
959 std::stack<std::size_t> level_stack;
968 if(map.shares_with(other.map))
971 stack.push(stack_itemt(&map, &other.map));
976 const stack_itemt &si = stack.top();
978 const nodet *ip1 = si.first;
979 const nodet *ip2 = si.second;
985 const std::size_t level = level_stack.top();
999 const nodet &child = item.second;
1008 gather_all(child, delta_view);
1013 stack.push(stack_itemt(&child, p));
1014 level_stack.push(level + 1);
1024 const nodet &child = item.second;
1028 stack.push(stack_itemt(&child, ip2));
1033 level_stack.push(dummy_level);
1046 add_item_if_not_shared(*ip1, *ip2, level, delta_view, only_common);
1054 delta_view.push_back(
1057 else if(!only_common)
1072 if(l1.shares_with(*ip2))
1079 if(equalT()(k1, ip2->
get_key()))
1081 delta_view.push_back({k1, l1.get_value(), ip2->
get_value()});
1083 else if(!only_common)
1085 delta_view.push_back({k1, l1.get_value()});
1102 if(!l1.shares_with(*p))
1105 delta_view.push_back({k1, l1.get_value(), p->
get_value()});
1108 else if(!only_common)
1111 delta_view.push_back({k1, l1.get_value()});
1117 while(!stack.empty());
1122 const bool only_common) const
1125 get_delta_view(other, delta_view, only_common);
1133 std::size_t key =
hash()(k);
1139 std::size_t bit = key & mask;
1166 std::size_t key =
hash()(k);
1167 const nodet *ip = ↦
1172 std::size_t bit = key & mask;
1188 return equalT()(ip->
get_key(), k) ? ip :
nullptr;
1205 nodet *del =
nullptr;
1206 std::size_t del_bit = 0;
1208 std::size_t key =
hash()(k);
1213 std::size_t bit = key & mask;
1217 if(m.
size() > 1 || del ==
nullptr)
1248 if(std::next(ll.begin()) == ll.end())
1269 const std::size_t starting_level,
1270 const std::size_t key_suffix,
1271 const std::size_t bit_last,
1282 std::size_t key_existing =
hash()(leaf.
get_key());
1283 key_existing >>= chunk * starting_level;
1286 leaf_kept.
swap(leaf);
1293 std::size_t level = starting_level + 1;
1294 std::size_t key = key_suffix;
1296 key_existing >>= chunk;
1305 std::size_t bit_existing = key_existing & mask;
1306 std::size_t bit = key & mask;
1308 if(bit != bit_existing)
1318 l2.
make_leaf(k, std::forward<valueU>(m));
1327 key_existing >>= chunk;
1330 }
while(level < levels);
1350 std::size_t key =
hash()(k);
1356 std::size_t level = 0;
1360 std::size_t bit = key & mask;
1371 if(level < levels - 1)
1381 child.
place_leaf(k, std::forward<valueU>(m));
1401 migrate(level, key, bit, *ip, k, std::forward<valueU>(m));
1413 child.
place_leaf(k, std::forward<valueU>(m));
1425 nodet &lp = get_leaf_node(k);
1429 "values should not be replaced with equal values to maximize sharing");
1437 nodet &lp = get_leaf_node(k);
1445 "sharing_mapt::update should make some change. Consider using read-only "
1446 "method to check if an update is needed beforehand");
1452 const nodet *lp = get_leaf_node(k);
1467 SHARING_MAPT(
const std::size_t)::mask = 0xffff >> (16 - chunk);
1468 SHARING_MAPT(
const std::size_t)::levels = bits / chunk;
const d_it & read_internal() const
std::vector< delta_view_itemt > delta_viewt
Delta view of the key-value pairs in two maps.
#define UNREACHABLE
This should be used to mark dead code.
dstringt has one field, an unsigned integer no which is an index into a static table of strings.
bool is_defined_leaf() const
Stats about sharing between several sharing map instances.
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.
void gather_all(const nodet &n, delta_viewt &delta_view) const
d_ct::leaf_listt leaf_listt
#define SHARING_MAPT(type)
Macro to abbreviate the out-of-class definitions of methods and static variables of sharing_mapt.
size_type size() const
Get number of elements in map.
const keyT & get_key() const
bool is_in_both_maps() const
static void insert_view_item(sorted_viewt &v, view_itemt &&vi)
A map implemented as a tree where subtrees can be shared between different maps.
static const std::size_t levels
delta_viewt get_delta_view(const sharing_mapt &other, const bool only_common=true) const
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...
void update(const key_type &k, std::function< void(mapped_type &)> mutator)
Update an element in place; element must exist in map.
const d_ct & read_container() const
std::conditional< fail_if_equal, real_value_comparatort, noop_value_comparatort >::type value_comparatort
void erase_if_exists(const key_type &k)
Erase element if it exists.
use_countt use_count() const
void replace(const union_find_replacet &replace_map, string_not_contains_constraintt &constraint)
sorted_viewt get_sorted_view() const
Convenience function to get a sorted view of the map elements.
std::size_t count_unmarked_nodes(bool leafs_only, std::set< const void * > &marked, bool mark=true) const
bool operator()(const mapped_type &)
const d_lt & read_leaf() const
static const std::size_t chunk
bool is_defined_container() const
bool is_defined_internal() const
const leaf_listt & get_container() const
void remove_leaf(const keyT &k)
std::set< view_itemt > sorted_viewt
std::size_t num_unique_leafs
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...
const valueT & get_value() const
#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...
static sharing_map_statst get_sharing_stats_map(Iterator begin, Iterator end)
Get sharing stats.
real_value_comparatort(const mapped_type &old_value)
std::pair< const key_type &, const mapped_type & > view_itemt
std::vector< view_itemt > viewt
View of the key-value pairs in the map.
void iterate(const nodet &n, std::function< void(const key_type &k, const mapped_type &m)> f) const
const to_mapt & get_to_map() const
std::size_t num_unique_nodes
std::vector< key_type > keyst
const mapped_type & get_other_map_value() const
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.
std::conditional< fail_if_equal, std::equal_to< valueT >, falset >::type value_equalt
#define PRECONDITION(CONDITION)
static const std::size_t mask
void place_leaf(const keyT &k, valueU &&v)
void insert_or_replace(const key_type &k, valueU &&m)
bool empty() const
Check if map is empty.
void swap(sharing_nodet &other)
bool shares_with(const sharing_nodet &other) const
void remove_child(const std::size_t n)
delta_view_itemt(const key_type &k, const mapped_type &m)
nonstd::optional< T > optionalt
bool has_key(const key_type &k) const
Check if key is in map.
void insert(const key_type &k, valueU &&m)
Insert element, element must not exist in map.
static const std::size_t dummy_level
void swap(sharing_mapt &other)
Swap with other map.
const leaft * find_leaf(const keyT &k) const
const d_it::innert * find_child(const std::size_t n) const
sharing_nodet< key_type, mapped_type > nodet
static const std::size_t bits
void replace(const key_type &k, valueU &&m)
Replace element, element must exist in map.
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.
nodet & get_leaf_node(const key_type &k)
bool operator()(const mapped_type &lhs, const mapped_type &rhs)
const mapped_type * other_m
noop_value_comparatort(const mapped_type &)
#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...
const nodet * get_leaf_node(const key_type &k) const
d_it::innert & add_child(const std::size_t n)
bool is_container() const
#define SHARING_MAPTV(return_type, V)
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.
#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...
void set_value(valueU &&v)
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
void mutate_value(std::function< void(valueT &)> mutator)
void erase(const key_type &k)
Erase element, element must exist in map.
void make_leaf(const keyT &k, valueU &&v)
const T * as_const_ptr(T *t)
Return a pointer to the same object but ensures the type is pointer to const.
optionalt< std::reference_wrapper< const mapped_type > > find(const key_type &k) const
Find element.
static void insert_view_item(viewt &v, view_itemt &&vi)
bool operator()(const mapped_type &new_value)
delta_view_itemt(const key_type &k, const mapped_type &m, const mapped_type &other_m)
nodet::leaf_listt leaf_listt