Halide
PerfectHashMap.h
Go to the documentation of this file.
1 #ifndef PERFECT_HASH_MAP_H
2 #define PERFECT_HASH_MAP_H
3 
4 #include <algorithm>
5 #include <iostream>
6 #include <vector>
7 
8 // Avoid a dependence on libHalide by defining a local variant we can use
10  const bool c;
11 
13  : c(c) {
14  }
15 
16  template<typename T>
18  if (!c) {
19  std::cerr << t;
20  }
21  return *this;
22  }
24  if (!c) {
25  exit(-1);
26  }
27  }
28 };
29 
30 // A specialized hash map used in the autoscheduler. It can only grow,
31 // and it requires a perfect hash in the form of "id" and "max_id"
32 // fields on each key. If the keys don't all have a consistent max_id,
33 // or if you call make_large with the wrong max_id, you get UB. If you
34 // think that might be happening, uncomment the assertions below for
35 // some extra checking.
36 
37 template<typename K, typename T, int max_small_size = 4, typename phm_assert = PerfectHashMapAsserter>
39 
40  using storage_type = std::vector<std::pair<const K *, T>>;
41 
42  storage_type storage;
43 
44  int occupied = 0;
45 
46  // Equivalent to storage[i], but broken out into a separate method
47  // to allow for bounds checks when debugging this.
48  std::pair<const K *, T> &storage_bucket(int i) {
49  /*
50  phm_assert(i >= 0 && i < (int)storage.size())
51  << "Out of bounds access: " << i << " " << storage.size() << "\n";
52  */
53  return storage[i];
54  }
55 
56  const std::pair<const K *, T> &storage_bucket(int i) const {
57  /*
58  phm_assert(i >= 0 && i < (int)storage.size())
59  << "Out of bounds access: " << i << " " << storage.size() << "\n";
60  */
61  return storage[i];
62  }
63 
64  enum {
65  Empty = 0, // No storage allocated
66  Small = 1, // Storage is just an array of key/value pairs
67  Large = 2 // Storage is an array with empty slots, indexed by the 'id' field of each key
68  } state = Empty;
69 
70  void upgrade_from_empty_to_small() {
71  storage.resize(max_small_size);
72  state = Small;
73  }
74 
75  void upgrade_from_empty_to_large(int n) {
76  storage.resize(n);
77  state = Large;
78  }
79 
80  void upgrade_from_small_to_large(int n) {
81  phm_assert(occupied <= max_small_size) << occupied << " " << max_small_size << "\n";
82  storage_type tmp(n);
83  state = Large;
84  tmp.swap(storage);
85  int o = occupied;
86  for (int i = 0; i < o; i++) {
87  emplace_large(tmp[i].first, std::move(tmp[i].second));
88  }
89  occupied = o;
90  }
91 
92  // Methods when the map is in the empty state
93  T &emplace_empty(const K *n, T &&t) {
94  upgrade_from_empty_to_small();
95  storage_bucket(0).first = n;
96  storage_bucket(0).second = std::move(t);
97  occupied = 1;
98  return storage_bucket(0).second;
99  }
100 
101  const T &get_empty(const K *n) const {
102  phm_assert(0) << "Calling get on an empty PerfectHashMap";
103  return unreachable_value();
104  }
105 
106  T &get_empty(const K *n) {
107  phm_assert(0) << "Calling get on an empty PerfectHashMap";
108  return unreachable_value();
109  }
110 
111  T &get_or_create_empty(const K *n) {
112  occupied = 1;
113  return emplace_empty(n, T());
114  }
115 
116  bool contains_empty(const K *n) const {
117  return false;
118  }
119 
120  // Methods when the map is in the small state
121  int find_index_small(const K *n) const {
122  int i;
123  for (i = 0; i < (int)occupied; i++) {
124  if (storage_bucket(i).first == n) return i;
125  }
126  return i;
127  }
128 
129  T &emplace_small(const K *n, T &&t) {
130  int idx = find_index_small(n);
131  if (idx >= max_small_size) {
132  upgrade_from_small_to_large((int)(n->max_id));
133  return emplace_large(n, std::move(t));
134  }
135  auto &p = storage_bucket(idx);
136  if (p.first == nullptr) {
137  occupied++;
138  p.first = n;
139  }
140  p.second = std::move(t);
141  return p.second;
142  }
143 
144  const T &get_small(const K *n) const {
145  int idx = find_index_small(n);
146  return storage_bucket(idx).second;
147  }
148 
149  T &get_small(const K *n) {
150  int idx = find_index_small(n);
151  return storage_bucket(idx).second;
152  }
153 
154  T &get_or_create_small(const K *n) {
155  int idx = find_index_small(n);
156  if (idx >= max_small_size) {
157  upgrade_from_small_to_large((int)(n->max_id));
158  return get_or_create_large(n);
159  }
160  auto &p = storage_bucket(idx);
161  if (p.first == nullptr) {
162  occupied++;
163  p.first = n;
164  }
165  return p.second;
166  }
167 
168  bool contains_small(const K *n) const {
169  int idx = find_index_small(n);
170  return (idx < max_small_size) && (storage_bucket(idx).first == n);
171  }
172 
173  // Methods when the map is in the large state
174  T &emplace_large(const K *n, T &&t) {
175  auto &p = storage_bucket(n->id);
176  if (!p.first) occupied++;
177  p.first = n;
178  p.second = std::move(t);
179  return p.second;
180  }
181 
182  const T &get_large(const K *n) const {
183  return storage_bucket(n->id).second;
184  }
185 
186  T &get_large(const K *n) {
187  return storage_bucket(n->id).second;
188  }
189 
190  T &get_or_create_large(const K *n) {
191  auto &p = storage_bucket(n->id);
192  if (p.first == nullptr) {
193  occupied++;
194  p.first = n;
195  }
196  return storage_bucket(n->id).second;
197  }
198 
199  bool contains_large(const K *n) const {
200  return storage_bucket(n->id).first != nullptr;
201  }
202 
203  void check_key(const K *n) const {
204  /*
205  phm_assert(n->id >= 0 && n->id < n->max_id)
206  << "Invalid hash key: " << n->id << " " << n->max_id << "\n";
207  phm_assert(state != Large || (int)storage.size() == n->max_id)
208  << "Inconsistent key count: " << n->max_id << " vs " << storage.size() << "\n";
209  */
210  }
211 
212  // Helpers used to pacify compilers
213  T &unreachable_value() {
214  return storage_bucket(0).second;
215  }
216 
217  const T &unreachable_value() const {
218  return storage_bucket(0).second;
219  }
220 
221 public:
222  // Jump straight to the large state
223  void make_large(int n) {
224  if (state == Empty) {
225  upgrade_from_empty_to_large(n);
226  } else if (state == Small) {
227  upgrade_from_small_to_large(n);
228  }
229  }
230 
231  T &emplace(const K *n, T &&t) {
232  check_key(n);
233  switch (state) {
234  case Empty:
235  return emplace_empty(n, std::move(t));
236  case Small:
237  return emplace_small(n, std::move(t));
238  case Large:
239  return emplace_large(n, std::move(t));
240  }
241  return unreachable_value();
242  }
243 
244  T &insert(const K *n, const T &t) {
245  check_key(n);
246  T tmp(t);
247  switch (state) {
248  case Empty:
249  return emplace_empty(n, std::move(tmp));
250  case Small:
251  return emplace_small(n, std::move(tmp));
252  case Large:
253  return emplace_large(n, std::move(tmp));
254  }
255  return unreachable_value();
256  }
257 
258  const T &get(const K *n) const {
259  check_key(n);
260  switch (state) {
261  case Empty:
262  return get_empty(n);
263  case Small:
264  return get_small(n);
265  case Large:
266  return get_large(n);
267  }
268  return unreachable_value();
269  }
270 
271  T &get(const K *n) {
272  check_key(n);
273  switch (state) {
274  case Empty:
275  return get_empty(n);
276  case Small:
277  return get_small(n);
278  case Large:
279  return get_large(n);
280  }
281  return unreachable_value();
282  }
283 
284  T &get_or_create(const K *n) {
285  check_key(n);
286  switch (state) {
287  case Empty:
288  return get_or_create_empty(n);
289  case Small:
290  return get_or_create_small(n);
291  case Large:
292  return get_or_create_large(n);
293  }
294  return unreachable_value();
295  }
296 
297  bool contains(const K *n) const {
298  check_key(n);
299  switch (state) {
300  case Empty:
301  return contains_empty(n);
302  case Small:
303  return contains_small(n);
304  case Large:
305  return contains_large(n);
306  }
307  return false; // Unreachable
308  }
309 
310  size_t size() const {
311  return occupied;
312  }
313 
314  struct iterator {
315  std::pair<const K *, T> *iter, *end;
316 
317  void operator++(int) {
318  do {
319  iter++;
320  } while (iter != end && iter->first == nullptr);
321  }
322 
323  void operator++() {
324  (*this)++;
325  }
326 
327  const K *key() const {
328  return iter->first;
329  }
330 
331  T &value() const {
332  return iter->second;
333  }
334 
335  bool operator!=(const iterator &other) const {
336  return iter != other.iter;
337  }
338 
339  bool operator==(const iterator &other) const {
340  return iter == other.iter;
341  }
342 
343  std::pair<const K *, T> &operator*() {
344  return *iter;
345  }
346  };
347 
348  struct const_iterator {
349  const std::pair<const K *, T> *iter, *end;
350 
351  void operator++(int) {
352  do {
353  iter++;
354  } while (iter != end && iter->first == nullptr);
355  }
356 
357  void operator++() {
358  (*this)++;
359  }
360 
361  const K *key() const {
362  return iter->first;
363  }
364 
365  const T &value() const {
366  return iter->second;
367  }
368 
369  bool operator!=(const const_iterator &other) const {
370  return iter != other.iter;
371  }
372 
373  bool operator==(const const_iterator &other) const {
374  return iter == other.iter;
375  }
376 
377  const std::pair<const K *, T> &operator*() const {
378  return *iter;
379  }
380  };
381 
382  iterator begin() {
383  if (state == Empty) return end();
384  iterator it;
385  it.iter = storage.data();
386  it.end = it.iter + storage.size();
387  if (it.key() == nullptr) it++;
388  phm_assert(it.iter == it.end || it.key());
389  return it;
390  }
391 
392  iterator end() {
393  iterator it;
394  it.iter = it.end = storage.data() + storage.size();
395  return it;
396  }
397 
398  const_iterator begin() const {
399  if (storage.empty()) return end();
400  const_iterator it;
401  it.iter = storage.data();
402  it.end = it.iter + storage.size();
403  if (it.key() == nullptr) it++;
404  phm_assert(it.iter == it.end || it.key());
405  return it;
406  }
407 
408  const_iterator end() const {
409  const_iterator it;
410  it.iter = it.end = storage.data() + storage.size();
411  return it;
412  }
413 };
414 
415 #endif
PerfectHashMapAsserter::~PerfectHashMapAsserter
~PerfectHashMapAsserter()
Definition: PerfectHashMap.h:23
PerfectHashMapAsserter::c
const bool c
Definition: PerfectHashMap.h:10
PerfectHashMap::make_large
void make_large(int n)
Definition: PerfectHashMap.h:223
PerfectHashMap::const_iterator::operator!=
bool operator!=(const const_iterator &other) const
Definition: PerfectHashMap.h:369
PerfectHashMap::iterator::operator*
std::pair< const K *, T > & operator*()
Definition: PerfectHashMap.h:343
PerfectHashMap::const_iterator::operator++
void operator++()
Definition: PerfectHashMap.h:357
PerfectHashMap::begin
const_iterator begin() const
Definition: PerfectHashMap.h:398
PerfectHashMap::contains
bool contains(const K *n) const
Definition: PerfectHashMap.h:297
PerfectHashMap::const_iterator::value
const T & value() const
Definition: PerfectHashMap.h:365
PerfectHashMapAsserter::operator<<
PerfectHashMapAsserter & operator<<(T &&t)
Definition: PerfectHashMap.h:17
PerfectHashMap::iterator::key
const K * key() const
Definition: PerfectHashMap.h:327
PerfectHashMap::const_iterator::key
const K * key() const
Definition: PerfectHashMap.h:361
PerfectHashMap::get
const T & get(const K *n) const
Definition: PerfectHashMap.h:258
PerfectHashMap::end
const_iterator end() const
Definition: PerfectHashMap.h:408
PerfectHashMap::iterator::iter
std::pair< const K *, T > * iter
Definition: PerfectHashMap.h:315
PerfectHashMap::iterator::operator==
bool operator==(const iterator &other) const
Definition: PerfectHashMap.h:339
PerfectHashMap::const_iterator::operator++
void operator++(int)
Definition: PerfectHashMap.h:351
PerfectHashMap::iterator::value
T & value() const
Definition: PerfectHashMap.h:331
PerfectHashMap::const_iterator
Definition: PerfectHashMap.h:348
PerfectHashMap::insert
T & insert(const K *n, const T &t)
Definition: PerfectHashMap.h:244
PerfectHashMap::end
iterator end()
Definition: PerfectHashMap.h:392
PerfectHashMap::const_iterator::iter
const std::pair< const K *, T > * iter
Definition: PerfectHashMap.h:349
PerfectHashMap::emplace
T & emplace(const K *n, T &&t)
Definition: PerfectHashMap.h:231
PerfectHashMapAsserter
Definition: PerfectHashMap.h:9
PerfectHashMap::iterator::operator++
void operator++()
Definition: PerfectHashMap.h:323
PerfectHashMapAsserter::PerfectHashMapAsserter
PerfectHashMapAsserter(bool c)
Definition: PerfectHashMap.h:12
PerfectHashMap::iterator::operator!=
bool operator!=(const iterator &other) const
Definition: PerfectHashMap.h:335
PerfectHashMap
Definition: PerfectHashMap.h:38
PerfectHashMap::const_iterator::end
const std::pair< const K *, T > * end
Definition: PerfectHashMap.h:349
PerfectHashMap::begin
iterator begin()
Definition: PerfectHashMap.h:382
PerfectHashMap::const_iterator::operator*
const std::pair< const K *, T > & operator*() const
Definition: PerfectHashMap.h:377
PerfectHashMap::const_iterator::operator==
bool operator==(const const_iterator &other) const
Definition: PerfectHashMap.h:373
PerfectHashMap::iterator::end
std::pair< const K *, T > * end
Definition: PerfectHashMap.h:315
PerfectHashMap::iterator::operator++
void operator++(int)
Definition: PerfectHashMap.h:317
PerfectHashMap::get_or_create
T & get_or_create(const K *n)
Definition: PerfectHashMap.h:284
PerfectHashMap::iterator
Definition: PerfectHashMap.h:314
PerfectHashMap::size
size_t size() const
Definition: PerfectHashMap.h:310
PerfectHashMap::get
T & get(const K *n)
Definition: PerfectHashMap.h:271