cprover
irep_hash_container.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: IREP Hash Container
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
11 
12 #ifndef CPROVER_UTIL_IREP_HASH_CONTAINER_H
13 #define CPROVER_UTIL_IREP_HASH_CONTAINER_H
14 
15 #include <vector>
16 
17 #include "irep.h"
18 #include "numbering.h"
19 
21 {
22 public:
23  std::size_t number(const irept &irep);
24 
25  explicit irep_hash_container_baset(bool _full):full(_full)
26  {
27  }
28 
29  void clear()
30  {
31  numbering.clear();
32  }
33 
34 protected:
35  // replacing the following two hash-tables by
36  // std::maps doesn't make much difference in performance
37 
38  // this is the first level: address of the content
39 
41  {
42  std::size_t operator()(const void *p) const
43  {
44  return (std::size_t)p;
45  }
46  };
47 
48  struct irep_entryt
49  {
50  std::size_t number;
51  irept irep; // copy to keep addresses stable
52  };
53 
54  typedef std::unordered_map<const void *, irep_entryt, pointer_hasht>
57 
58  // this is the second level: content
59 
60  typedef std::vector<std::size_t> packedt;
61 
62  struct vector_hasht
63  {
64  std::size_t operator()(const packedt &p) const;
65  };
66 
69 
70  void pack(const irept &irep, packedt &);
71 
72  bool full;
73 };
74 
75 // excludes comments
78 {
79 public:
81  {
82  }
83 };
84 
85 // includes comments
88 {
89 public:
91  {
92  }
93 };
94 
95 template <typename Key, typename T>
97 {
98 protected:
99  using mapt = std::map<std::size_t, T>;
100 
101 public:
102  using key_type = Key;
103  using mapped_type = T;
104  using value_type = std::pair<const Key, T>;
105  using const_iterator = typename mapt::const_iterator;
106  using iterator = typename mapt::iterator;
107 
108  const_iterator find(const Key &key) const
109  {
110  return map.find(hash_container.number(key));
111  }
112 
113  iterator find(const Key &key)
114  {
115  return map.find(hash_container.number(key));
116  }
117 
119  {
120  return map.begin();
121  }
122 
124  {
125  return map.begin();
126  }
127 
129  {
130  return map.end();
131  }
132 
134  {
135  return map.end();
136  }
137 
138  void clear()
139  {
141  map.clear();
142  }
143 
144  std::size_t size() const
145  {
146  return map.size();
147  }
148 
149  bool empty() const
150  {
151  return map.empty();
152  }
153 
154  T &operator[](const Key &key)
155  {
156  const std::size_t i = hash_container.number(key);
157  return map[i];
158  }
159 
160  std::pair<iterator, bool> insert(const value_type &value)
161  {
162  const std::size_t i = hash_container.number(value.first);
163  return map.emplace(i, value.second);
164  }
165 
166  void erase(iterator it)
167  {
168  map.erase(it);
169  }
170 
172  {
173  std::swap(hash_container, other.hash_container);
174  std::swap(map, other.map);
175  }
176 
177 protected:
180 };
181 
182 #endif // CPROVER_UTIL_IREP_HASH_CONTAINER_H
const_iterator find(const Key &key) const
iterator find(const Key &key)
T & operator[](const Key &key)
std::unordered_map< const void *, irep_entryt, pointer_hasht > ptr_hasht
std::size_t operator()(const void *p) const
typename mapt::iterator iterator
std::map< std::size_t, T > mapt
std::vector< std::size_t > packedt
Base class for tree-like data structures with sharing.
Definition: irep.h:156
void pack(const irept &irep, packedt &)
const_iterator end() const
std::pair< const Key, T > value_type
typename mapt::const_iterator const_iterator
void erase(iterator it)
std::size_t number(const irept &irep)
hash_numbering< packedt, vector_hasht > numberingt
const_iterator begin() const
std::size_t operator()(const packedt &p) const
void swap(irep_hash_mapt< Key, T > &other)
irep_hash_containert hash_container
std::pair< iterator, bool > insert(const value_type &value)
std::size_t size() const