cprover
irep_hash_container.cpp
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Hashing IREPs
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
12 #include "irep_hash_container.h"
13 
14 #include "irep.h"
15 #include "irep_hash.h"
16 
18 {
19  // the ptr-hash provides a speedup of up to 3x
20 
21  ptr_hasht::const_iterator it=ptr_hash.find(&irep.read());
22 
23  if(it!=ptr_hash.end())
24  return it->second;
25 
26  packedt packed;
27  pack(irep, packed);
28  size_t id=numbering.number(packed);
29 
30  ptr_hash[&irep.read()]=id;
31 
32  return id;
33 }
34 
36  const packedt &p) const
37 {
38  size_t result=p.size(); // seed
39  for(auto elem : p)
40  result=hash_combine(result, elem);
41  return result;
42 }
43 
45  const irept &irep,
46  packedt &packed)
47 {
48  const irept::subt &sub=irep.get_sub();
49  const irept::named_subt &named_sub=irep.get_named_sub();
50  const irept::named_subt &comments=irep.get_comments();
51 
52  packed.reserve(
53  1+1+sub.size()+named_sub.size()*2+
54  (full?comments.size()*2:0));
55 
56  packed.push_back(irep_id_hash()(irep.id()));
57 
58  packed.push_back(sub.size());
59  forall_irep(it, sub)
60  packed.push_back(number(*it));
61 
62  packed.push_back(named_sub.size());
63  forall_named_irep(it, named_sub)
64  {
65  packed.push_back(irep_id_hash()(it->first)); // id
66  packed.push_back(number(it->second)); // sub-irep
67  }
68 
69  if(full)
70  {
71  packed.push_back(comments.size());
72  forall_named_irep(it, comments)
73  {
74  packed.push_back(irep_id_hash()(it->first)); // id
75  packed.push_back(number(it->second)); // sub-irep
76  }
77  }
78 }
IREP Hash Container.
std::vector< irept > subt
Definition: irep.h:91
std::vector< size_t > packedt
#define forall_named_irep(it, irep)
Definition: irep.h:70
subt & get_sub()
Definition: irep.h:245
const dt & read() const
Definition: irep.h:332
const irep_idt & id() const
Definition: irep.h:189
dstring_hash irep_id_hash
Definition: irep.h:35
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
void pack(const irept &irep, packedt &)
named_subt & get_named_sub()
Definition: irep.h:247
irep hash functions
#define hash_combine(h1, h2)
Definition: irep_hash.h:120
size_t number(const irept &irep)
number_type number(const T &a)
Definition: numbering.h:27
size_t operator()(const packedt &p) const
#define forall_irep(it, irep)
Definition: irep.h:62