cprover
merge_irep.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module:
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
9 #include "merge_irep.h"
10 
11 #include "irep_hash.h"
12 
13 std::size_t to_be_merged_irept::hash() const
14 {
15  std::size_t result=hash_string(id());
16 
17  const irept::subt &sub=get_sub();
18  const irept::named_subt &named_sub=get_named_sub();
19 
20  forall_irep(it, sub)
21  result=hash_combine(result, static_cast<const merged_irept &>(*it).hash());
22 
23  forall_named_irep(it, named_sub)
24  {
25  result=hash_combine(result, hash_string(it->first));
26  result=
28  result, static_cast<const merged_irept &>(it->second).hash());
29  }
30 
31  result=hash_finalize(result, named_sub.size()+sub.size());
32 
33  return result;
34 }
35 
37 {
38  if(id()!=other.id())
39  return false;
40 
41  const irept::subt &sub=get_sub();
42  const irept::subt &o_sub=other.get_sub();
43  const irept::named_subt &named_sub=get_named_sub();
44  const irept::named_subt &o_named_sub=other.get_named_sub();
45 
46  if(sub.size()!=o_sub.size())
47  return true;
48  if(named_sub.size()!=o_named_sub.size())
49  return true;
50 
51  {
52  irept::subt::const_iterator s_it=sub.begin();
53  irept::subt::const_iterator os_it=o_sub.begin();
54 
55  for(; s_it!=sub.end(); s_it++, os_it++)
56  if(static_cast<const merged_irept &>(*s_it)!=
57  static_cast<const merged_irept &>(*os_it))
58  return false;
59  }
60 
61  {
62  irept::named_subt::const_iterator s_it=named_sub.begin();
63  irept::named_subt::const_iterator os_it=o_named_sub.begin();
64 
65  for(; s_it!=named_sub.end(); s_it++, os_it++)
66  if(s_it->first!=os_it->first ||
67  static_cast<const merged_irept &>(s_it->second)!=
68  static_cast<const merged_irept &>(os_it->second))
69  return false;
70  }
71 
72  return true;
73 }
74 
76 {
77  // first see if it's already a merged_irep
78 
79  merged_irep_storet::const_iterator entry=
80  merged_irep_store.find(merged_irept(irep));
81 
82  if(entry!=merged_irep_store.end())
83  return *entry; // nothing to do
84 
85  // need to build new irep that will be in the container
86  irept new_irep(irep.id());
87 
88  const irept::subt &src_sub=irep.get_sub();
89  irept::subt &dest_sub=new_irep.get_sub();
90  dest_sub.reserve(src_sub.size());
91 
92  forall_irep(it, src_sub)
93  dest_sub.push_back(merged(*it)); // recursive call
94 
95  const irept::named_subt &src_named_sub=irep.get_named_sub();
96  irept::named_subt &dest_named_sub=new_irep.get_named_sub();
97 
98  forall_named_irep(it, src_named_sub)
99  #ifdef SUB_IS_LIST
100  dest_named_sub.push_back(
101  std::make_pair(it->first, merged(it->second))); // recursive call
102  #else
103  dest_named_sub[it->first]=merged(it->second); // recursive call
104  #endif
105 
106  std::pair<to_be_merged_irep_storet::const_iterator, bool> result=
107  to_be_merged_irep_store.insert(to_be_merged_irept(new_irep));
108 
109  if(result.second) // really new, record
110  merged_irep_store.insert(merged_irept(new_irep));
111 
112  return
113  static_cast<const merged_irept &>(
114  static_cast<const irept &>(*result.first));
115 }
116 
118 {
119  // only useful if there is sharing
120  #ifdef SHARING
121  irep=merged(irep);
122  #endif
123 }
124 
125 const irept &merge_irept::merged(const irept &irep)
126 {
127  irep_storet::const_iterator entry=irep_store.find(irep);
128  if(entry!=irep_store.end())
129  return *entry;
130 
131  irept new_irep(irep.id());
132 
133  const irept::subt &src_sub=irep.get_sub();
134  irept::subt &dest_sub=new_irep.get_sub();
135  dest_sub.reserve(src_sub.size());
136 
137  forall_irep(it, src_sub)
138  dest_sub.push_back(merged(*it)); // recursive call
139 
140  const irept::named_subt &src_named_sub=irep.get_named_sub();
141  irept::named_subt &dest_named_sub=new_irep.get_named_sub();
142 
143  forall_named_irep(it, src_named_sub)
144  #ifdef SUB_IS_LIST
145  dest_named_sub.push_back(
146  std::make_pair(it->first, merged(it->second))); // recursive call
147  #else
148  dest_named_sub[it->first]=merged(it->second); // recursive call
149  #endif
150 
151  const irept::named_subt &src_comments=irep.get_comments();
152  irept::named_subt &dest_comments=new_irep.get_comments();
153 
154  forall_named_irep(it, src_comments)
155  #ifdef SUB_IS_LIST
156  dest_comments.push_back(
157  std::make_pair(it->first, merged(it->second))); // recursive call
158  #else
159  dest_comments[it->first]=merged(it->second); // recursive call
160  #endif
161 
162  return *irep_store.insert(new_irep).first;
163 }
164 
166 {
167  // only useful if there is sharing
168  #ifdef SHARING
169  irep=merged(irep);
170  #endif
171 }
172 
174 {
175  irep_storet::const_iterator entry=irep_store.find(irep);
176  if(entry!=irep_store.end())
177  return *entry;
178 
179  irept new_irep(irep.id());
180 
181  const irept::subt &src_sub=irep.get_sub();
182  irept::subt &dest_sub=new_irep.get_sub();
183  dest_sub.reserve(src_sub.size());
184 
185  forall_irep(it, src_sub)
186  dest_sub.push_back(merged(*it)); // recursive call
187 
188  const irept::named_subt &src_named_sub=irep.get_named_sub();
189  irept::named_subt &dest_named_sub=new_irep.get_named_sub();
190 
191  forall_named_irep(it, src_named_sub)
192  #ifdef SUB_IS_LIST
193  dest_named_sub.push_back(
194  std::make_pair(it->first, merged(it->second))); // recursive call
195  #else
196  dest_named_sub[it->first]=merged(it->second); // recursive call
197  #endif
198 
199  const irept::named_subt &src_comments=irep.get_comments();
200  irept::named_subt &dest_comments=new_irep.get_comments();
201 
202  forall_named_irep(it, src_comments)
203  #ifdef SUB_IS_LIST
204  dest_comments.push_back(
205  std::make_pair(it->first, merged(it->second))); // recursive call
206  #else
207  dest_comments[it->first]=merged(it->second); // recursive call
208  #endif
209 
210  return *irep_store.insert(new_irep).first;
211 }
std::size_t hash() const
Definition: merge_irep.cpp:13
std::vector< irept > subt
Definition: irep.h:91
to_be_merged_irept(const irept &src)
Definition: merge_irep.h:68
void operator()(irept &)
Definition: merge_irep.cpp:117
#define forall_named_irep(it, irep)
Definition: irep.h:70
subt & get_sub()
Definition: irep.h:245
const irep_idt & id() const
Definition: irep.h:189
const irept & merged(const irept &irep)
Definition: merge_irep.cpp:173
#define hash_finalize(h1, len)
Definition: irep_hash.h:122
named_subt & get_comments()
Definition: irep.h:249
Base class for tree-like data structures with sharing.
Definition: irep.h:87
std::map< irep_namet, irept > named_subt
Definition: irep.h:100
bool operator==(const to_be_merged_irept &other) const
Definition: merge_irep.cpp:36
named_subt & get_named_sub()
Definition: irep.h:247
void operator()(irept &)
Definition: merge_irep.cpp:165
size_t hash_string(const dstringt &s)
Definition: dstring.h:168
irep hash functions
const irept & merged(const irept &irep)
Definition: merge_irep.cpp:125
#define hash_combine(h1, h2)
Definition: irep_hash.h:120
const merged_irept & merged(const irept &)
Definition: merge_irep.cpp:75
const irept & find(const irep_namet &name) const
Definition: irep.cpp:285
#define forall_irep(it, irep)
Definition: irep.h:62