Merge pull request #1976 from YosysHQ/dave/fix-sim-const
[yosys.git] / kernel / hashlib.h
1 // This is free and unencumbered software released into the public domain.
2 //
3 // Anyone is free to copy, modify, publish, use, compile, sell, or
4 // distribute this software, either in source code form or as a compiled
5 // binary, for any purpose, commercial or non-commercial, and by any
6 // means.
7
8 // -------------------------------------------------------
9 // Written by Clifford Wolf <clifford@clifford.at> in 2014
10 // -------------------------------------------------------
11
12 #ifndef HASHLIB_H
13 #define HASHLIB_H
14
15 #include <stdexcept>
16 #include <algorithm>
17 #include <string>
18 #include <vector>
19
20 namespace hashlib {
21
22 const int hashtable_size_trigger = 2;
23 const int hashtable_size_factor = 3;
24
25 // The XOR version of DJB2
26 inline unsigned int mkhash(unsigned int a, unsigned int b) {
27 return ((a << 5) + a) ^ b;
28 }
29
30 // traditionally 5381 is used as starting value for the djb2 hash
31 const unsigned int mkhash_init = 5381;
32
33 // The ADD version of DJB2
34 // (use this version for cache locality in b)
35 inline unsigned int mkhash_add(unsigned int a, unsigned int b) {
36 return ((a << 5) + a) + b;
37 }
38
39 inline unsigned int mkhash_xorshift(unsigned int a) {
40 if (sizeof(a) == 4) {
41 a ^= a << 13;
42 a ^= a >> 17;
43 a ^= a << 5;
44 } else if (sizeof(a) == 8) {
45 a ^= a << 13;
46 a ^= a >> 7;
47 a ^= a << 17;
48 } else
49 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
50 return a;
51 }
52
53 template<typename T> struct hash_ops {
54 static inline bool cmp(const T &a, const T &b) {
55 return a == b;
56 }
57 static inline unsigned int hash(const T &a) {
58 return a.hash();
59 }
60 };
61
62 struct hash_int_ops {
63 template<typename T>
64 static inline bool cmp(T a, T b) {
65 return a == b;
66 }
67 };
68
69 template<> struct hash_ops<int32_t> : hash_int_ops
70 {
71 static inline unsigned int hash(int32_t a) {
72 return a;
73 }
74 };
75 template<> struct hash_ops<int64_t> : hash_int_ops
76 {
77 static inline unsigned int hash(int64_t a) {
78 return mkhash((unsigned int)(a), (unsigned int)(a >> 32));
79 }
80 };
81
82 template<> struct hash_ops<std::string> {
83 static inline bool cmp(const std::string &a, const std::string &b) {
84 return a == b;
85 }
86 static inline unsigned int hash(const std::string &a) {
87 unsigned int v = 0;
88 for (auto c : a)
89 v = mkhash(v, c);
90 return v;
91 }
92 };
93
94 template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
95 static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) {
96 return a == b;
97 }
98 static inline unsigned int hash(std::pair<P, Q> a) {
99 return mkhash(hash_ops<P>::hash(a.first), hash_ops<Q>::hash(a.second));
100 }
101 };
102
103 template<typename... T> struct hash_ops<std::tuple<T...>> {
104 static inline bool cmp(std::tuple<T...> a, std::tuple<T...> b) {
105 return a == b;
106 }
107 template<size_t I = 0>
108 static inline typename std::enable_if<I == sizeof...(T), unsigned int>::type hash(std::tuple<T...>) {
109 return mkhash_init;
110 }
111 template<size_t I = 0>
112 static inline typename std::enable_if<I != sizeof...(T), unsigned int>::type hash(std::tuple<T...> a) {
113 typedef hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
114 return mkhash(hash<I+1>(a), element_ops_t::hash(std::get<I>(a)));
115 }
116 };
117
118 template<typename T> struct hash_ops<std::vector<T>> {
119 static inline bool cmp(std::vector<T> a, std::vector<T> b) {
120 return a == b;
121 }
122 static inline unsigned int hash(std::vector<T> a) {
123 unsigned int h = mkhash_init;
124 for (auto k : a)
125 h = mkhash(h, hash_ops<T>::hash(k));
126 return h;
127 }
128 };
129
130 struct hash_cstr_ops {
131 static inline bool cmp(const char *a, const char *b) {
132 for (int i = 0; a[i] || b[i]; i++)
133 if (a[i] != b[i])
134 return false;
135 return true;
136 }
137 static inline unsigned int hash(const char *a) {
138 unsigned int hash = mkhash_init;
139 while (*a)
140 hash = mkhash(hash, *(a++));
141 return hash;
142 }
143 };
144
145 struct hash_ptr_ops {
146 static inline bool cmp(const void *a, const void *b) {
147 return a == b;
148 }
149 static inline unsigned int hash(const void *a) {
150 return (uintptr_t)a;
151 }
152 };
153
154 struct hash_obj_ops {
155 static inline bool cmp(const void *a, const void *b) {
156 return a == b;
157 }
158 template<typename T>
159 static inline unsigned int hash(const T *a) {
160 return a ? a->hash() : 0;
161 }
162 };
163
164 template<typename T>
165 inline unsigned int mkhash(const T &v) {
166 return hash_ops<T>().hash(v);
167 }
168
169 inline int hashtable_size(int min_size)
170 {
171 static std::vector<int> zero_and_some_primes = {
172 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
173 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
174 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
175 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
176 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
177 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
178 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
179 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
180 };
181
182 for (auto p : zero_and_some_primes)
183 if (p >= min_size) return p;
184
185 if (sizeof(int) == 4)
186 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
187
188 for (auto p : zero_and_some_primes)
189 if (100129 * p > min_size) return 100129 * p;
190
191 throw std::length_error("hash table exceeded maximum size.");
192 }
193
194 template<typename K, typename T, typename OPS = hash_ops<K>> class dict;
195 template<typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
196 template<typename K, typename OPS = hash_ops<K>> class pool;
197 template<typename K, typename OPS = hash_ops<K>> class mfp;
198
199 template<typename K, typename T, typename OPS>
200 class dict
201 {
202 struct entry_t
203 {
204 std::pair<K, T> udata;
205 int next;
206
207 entry_t() { }
208 entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
209 entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) { }
210 };
211
212 std::vector<int> hashtable;
213 std::vector<entry_t> entries;
214 OPS ops;
215
216 #ifdef NDEBUG
217 static inline void do_assert(bool) { }
218 #else
219 static inline void do_assert(bool cond) {
220 if (!cond) throw std::runtime_error("dict<> assert failed.");
221 }
222 #endif
223
224 int do_hash(const K &key) const
225 {
226 unsigned int hash = 0;
227 if (!hashtable.empty())
228 hash = ops.hash(key) % (unsigned int)(hashtable.size());
229 return hash;
230 }
231
232 void do_rehash()
233 {
234 hashtable.clear();
235 hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
236
237 for (int i = 0; i < int(entries.size()); i++) {
238 do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
239 int hash = do_hash(entries[i].udata.first);
240 entries[i].next = hashtable[hash];
241 hashtable[hash] = i;
242 }
243 }
244
245 int do_erase(int index, int hash)
246 {
247 do_assert(index < int(entries.size()));
248 if (hashtable.empty() || index < 0)
249 return 0;
250
251 int k = hashtable[hash];
252 do_assert(0 <= k && k < int(entries.size()));
253
254 if (k == index) {
255 hashtable[hash] = entries[index].next;
256 } else {
257 while (entries[k].next != index) {
258 k = entries[k].next;
259 do_assert(0 <= k && k < int(entries.size()));
260 }
261 entries[k].next = entries[index].next;
262 }
263
264 int back_idx = entries.size()-1;
265
266 if (index != back_idx)
267 {
268 int back_hash = do_hash(entries[back_idx].udata.first);
269
270 k = hashtable[back_hash];
271 do_assert(0 <= k && k < int(entries.size()));
272
273 if (k == back_idx) {
274 hashtable[back_hash] = index;
275 } else {
276 while (entries[k].next != back_idx) {
277 k = entries[k].next;
278 do_assert(0 <= k && k < int(entries.size()));
279 }
280 entries[k].next = index;
281 }
282
283 entries[index] = std::move(entries[back_idx]);
284 }
285
286 entries.pop_back();
287
288 if (entries.empty())
289 hashtable.clear();
290
291 return 1;
292 }
293
294 int do_lookup(const K &key, int &hash) const
295 {
296 if (hashtable.empty())
297 return -1;
298
299 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
300 ((dict*)this)->do_rehash();
301 hash = do_hash(key);
302 }
303
304 int index = hashtable[hash];
305
306 while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
307 index = entries[index].next;
308 do_assert(-1 <= index && index < int(entries.size()));
309 }
310
311 return index;
312 }
313
314 int do_insert(const K &key, int &hash)
315 {
316 if (hashtable.empty()) {
317 entries.emplace_back(std::pair<K, T>(key, T()), -1);
318 do_rehash();
319 hash = do_hash(key);
320 } else {
321 entries.emplace_back(std::pair<K, T>(key, T()), hashtable[hash]);
322 hashtable[hash] = entries.size() - 1;
323 }
324 return entries.size() - 1;
325 }
326
327 int do_insert(const std::pair<K, T> &value, int &hash)
328 {
329 if (hashtable.empty()) {
330 entries.emplace_back(value, -1);
331 do_rehash();
332 hash = do_hash(value.first);
333 } else {
334 entries.emplace_back(value, hashtable[hash]);
335 hashtable[hash] = entries.size() - 1;
336 }
337 return entries.size() - 1;
338 }
339
340 int do_insert(std::pair<K, T> &&rvalue, int &hash)
341 {
342 if (hashtable.empty()) {
343 auto key = rvalue.first;
344 entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), -1);
345 do_rehash();
346 hash = do_hash(key);
347 } else {
348 entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), hashtable[hash]);
349 hashtable[hash] = entries.size() - 1;
350 }
351 return entries.size() - 1;
352 }
353
354 public:
355 class const_iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
356 {
357 friend class dict;
358 protected:
359 const dict *ptr;
360 int index;
361 const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { }
362 public:
363 const_iterator() { }
364 const_iterator operator++() { index--; return *this; }
365 bool operator<(const const_iterator &other) const { return index > other.index; }
366 bool operator==(const const_iterator &other) const { return index == other.index; }
367 bool operator!=(const const_iterator &other) const { return index != other.index; }
368 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
369 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
370 };
371
372 class iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
373 {
374 friend class dict;
375 protected:
376 dict *ptr;
377 int index;
378 iterator(dict *ptr, int index) : ptr(ptr), index(index) { }
379 public:
380 iterator() { }
381 iterator operator++() { index--; return *this; }
382 bool operator<(const iterator &other) const { return index > other.index; }
383 bool operator==(const iterator &other) const { return index == other.index; }
384 bool operator!=(const iterator &other) const { return index != other.index; }
385 std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
386 std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
387 const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
388 const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
389 operator const_iterator() const { return const_iterator(ptr, index); }
390 };
391
392 dict()
393 {
394 }
395
396 dict(const dict &other)
397 {
398 entries = other.entries;
399 do_rehash();
400 }
401
402 dict(dict &&other)
403 {
404 swap(other);
405 }
406
407 dict &operator=(const dict &other) {
408 entries = other.entries;
409 do_rehash();
410 return *this;
411 }
412
413 dict &operator=(dict &&other) {
414 clear();
415 swap(other);
416 return *this;
417 }
418
419 dict(const std::initializer_list<std::pair<K, T>> &list)
420 {
421 for (auto &it : list)
422 insert(it);
423 }
424
425 template<class InputIterator>
426 dict(InputIterator first, InputIterator last)
427 {
428 insert(first, last);
429 }
430
431 template<class InputIterator>
432 void insert(InputIterator first, InputIterator last)
433 {
434 for (; first != last; ++first)
435 insert(*first);
436 }
437
438 std::pair<iterator, bool> insert(const K &key)
439 {
440 int hash = do_hash(key);
441 int i = do_lookup(key, hash);
442 if (i >= 0)
443 return std::pair<iterator, bool>(iterator(this, i), false);
444 i = do_insert(key, hash);
445 return std::pair<iterator, bool>(iterator(this, i), true);
446 }
447
448 std::pair<iterator, bool> insert(const std::pair<K, T> &value)
449 {
450 int hash = do_hash(value.first);
451 int i = do_lookup(value.first, hash);
452 if (i >= 0)
453 return std::pair<iterator, bool>(iterator(this, i), false);
454 i = do_insert(value, hash);
455 return std::pair<iterator, bool>(iterator(this, i), true);
456 }
457
458 std::pair<iterator, bool> insert(std::pair<K, T> &&rvalue)
459 {
460 int hash = do_hash(rvalue.first);
461 int i = do_lookup(rvalue.first, hash);
462 if (i >= 0)
463 return std::pair<iterator, bool>(iterator(this, i), false);
464 i = do_insert(std::forward<std::pair<K, T>>(rvalue), hash);
465 return std::pair<iterator, bool>(iterator(this, i), true);
466 }
467
468 std::pair<iterator, bool> emplace(K const &key, T const &value)
469 {
470 int hash = do_hash(key);
471 int i = do_lookup(key, hash);
472 if (i >= 0)
473 return std::pair<iterator, bool>(iterator(this, i), false);
474 i = do_insert(std::make_pair(key, value), hash);
475 return std::pair<iterator, bool>(iterator(this, i), true);
476 }
477
478 std::pair<iterator, bool> emplace(K const &key, T &&rvalue)
479 {
480 int hash = do_hash(key);
481 int i = do_lookup(key, hash);
482 if (i >= 0)
483 return std::pair<iterator, bool>(iterator(this, i), false);
484 i = do_insert(std::make_pair(key, std::forward<T>(rvalue)), hash);
485 return std::pair<iterator, bool>(iterator(this, i), true);
486 }
487
488 std::pair<iterator, bool> emplace(K &&rkey, T const &value)
489 {
490 int hash = do_hash(rkey);
491 int i = do_lookup(rkey, hash);
492 if (i >= 0)
493 return std::pair<iterator, bool>(iterator(this, i), false);
494 i = do_insert(std::make_pair(std::forward<K>(rkey), value), hash);
495 return std::pair<iterator, bool>(iterator(this, i), true);
496 }
497
498 std::pair<iterator, bool> emplace(K &&rkey, T &&rvalue)
499 {
500 int hash = do_hash(rkey);
501 int i = do_lookup(rkey, hash);
502 if (i >= 0)
503 return std::pair<iterator, bool>(iterator(this, i), false);
504 i = do_insert(std::make_pair(std::forward<K>(rkey), std::forward<T>(rvalue)), hash);
505 return std::pair<iterator, bool>(iterator(this, i), true);
506 }
507
508 int erase(const K &key)
509 {
510 int hash = do_hash(key);
511 int index = do_lookup(key, hash);
512 return do_erase(index, hash);
513 }
514
515 iterator erase(iterator it)
516 {
517 int hash = do_hash(it->first);
518 do_erase(it.index, hash);
519 return ++it;
520 }
521
522 int count(const K &key) const
523 {
524 int hash = do_hash(key);
525 int i = do_lookup(key, hash);
526 return i < 0 ? 0 : 1;
527 }
528
529 int count(const K &key, const_iterator it) const
530 {
531 int hash = do_hash(key);
532 int i = do_lookup(key, hash);
533 return i < 0 || i > it.index ? 0 : 1;
534 }
535
536 iterator find(const K &key)
537 {
538 int hash = do_hash(key);
539 int i = do_lookup(key, hash);
540 if (i < 0)
541 return end();
542 return iterator(this, i);
543 }
544
545 const_iterator find(const K &key) const
546 {
547 int hash = do_hash(key);
548 int i = do_lookup(key, hash);
549 if (i < 0)
550 return end();
551 return const_iterator(this, i);
552 }
553
554 T& at(const K &key)
555 {
556 int hash = do_hash(key);
557 int i = do_lookup(key, hash);
558 if (i < 0)
559 throw std::out_of_range("dict::at()");
560 return entries[i].udata.second;
561 }
562
563 const T& at(const K &key) const
564 {
565 int hash = do_hash(key);
566 int i = do_lookup(key, hash);
567 if (i < 0)
568 throw std::out_of_range("dict::at()");
569 return entries[i].udata.second;
570 }
571
572 const T& at(const K &key, const T &defval) const
573 {
574 int hash = do_hash(key);
575 int i = do_lookup(key, hash);
576 if (i < 0)
577 return defval;
578 return entries[i].udata.second;
579 }
580
581 T& operator[](const K &key)
582 {
583 int hash = do_hash(key);
584 int i = do_lookup(key, hash);
585 if (i < 0)
586 i = do_insert(std::pair<K, T>(key, T()), hash);
587 return entries[i].udata.second;
588 }
589
590 template<typename Compare = std::less<K>>
591 void sort(Compare comp = Compare())
592 {
593 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata.first, a.udata.first); });
594 do_rehash();
595 }
596
597 void swap(dict &other)
598 {
599 hashtable.swap(other.hashtable);
600 entries.swap(other.entries);
601 }
602
603 bool operator==(const dict &other) const {
604 if (size() != other.size())
605 return false;
606 for (auto &it : entries) {
607 auto oit = other.find(it.udata.first);
608 if (oit == other.end() || !(oit->second == it.udata.second))
609 return false;
610 }
611 return true;
612 }
613
614 bool operator!=(const dict &other) const {
615 return !operator==(other);
616 }
617
618 void reserve(size_t n) { entries.reserve(n); }
619 size_t size() const { return entries.size(); }
620 bool empty() const { return entries.empty(); }
621 void clear() { hashtable.clear(); entries.clear(); }
622
623 iterator begin() { return iterator(this, int(entries.size())-1); }
624 iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
625 iterator end() { return iterator(nullptr, -1); }
626
627 const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
628 const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
629 const_iterator end() const { return const_iterator(nullptr, -1); }
630 };
631
632 template<typename K, typename OPS>
633 class pool
634 {
635 template<typename, int, typename> friend class idict;
636
637 protected:
638 struct entry_t
639 {
640 K udata;
641 int next;
642
643 entry_t() { }
644 entry_t(const K &udata, int next) : udata(udata), next(next) { }
645 };
646
647 std::vector<int> hashtable;
648 std::vector<entry_t> entries;
649 OPS ops;
650
651 #ifdef NDEBUG
652 static inline void do_assert(bool) { }
653 #else
654 static inline void do_assert(bool cond) {
655 if (!cond) throw std::runtime_error("pool<> assert failed.");
656 }
657 #endif
658
659 int do_hash(const K &key) const
660 {
661 unsigned int hash = 0;
662 if (!hashtable.empty())
663 hash = ops.hash(key) % (unsigned int)(hashtable.size());
664 return hash;
665 }
666
667 void do_rehash()
668 {
669 hashtable.clear();
670 hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);
671
672 for (int i = 0; i < int(entries.size()); i++) {
673 do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
674 int hash = do_hash(entries[i].udata);
675 entries[i].next = hashtable[hash];
676 hashtable[hash] = i;
677 }
678 }
679
680 int do_erase(int index, int hash)
681 {
682 do_assert(index < int(entries.size()));
683 if (hashtable.empty() || index < 0)
684 return 0;
685
686 int k = hashtable[hash];
687 if (k == index) {
688 hashtable[hash] = entries[index].next;
689 } else {
690 while (entries[k].next != index) {
691 k = entries[k].next;
692 do_assert(0 <= k && k < int(entries.size()));
693 }
694 entries[k].next = entries[index].next;
695 }
696
697 int back_idx = entries.size()-1;
698
699 if (index != back_idx)
700 {
701 int back_hash = do_hash(entries[back_idx].udata);
702
703 k = hashtable[back_hash];
704 if (k == back_idx) {
705 hashtable[back_hash] = index;
706 } else {
707 while (entries[k].next != back_idx) {
708 k = entries[k].next;
709 do_assert(0 <= k && k < int(entries.size()));
710 }
711 entries[k].next = index;
712 }
713
714 entries[index] = std::move(entries[back_idx]);
715 }
716
717 entries.pop_back();
718
719 if (entries.empty())
720 hashtable.clear();
721
722 return 1;
723 }
724
725 int do_lookup(const K &key, int &hash) const
726 {
727 if (hashtable.empty())
728 return -1;
729
730 if (entries.size() * hashtable_size_trigger > hashtable.size()) {
731 ((pool*)this)->do_rehash();
732 hash = do_hash(key);
733 }
734
735 int index = hashtable[hash];
736
737 while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
738 index = entries[index].next;
739 do_assert(-1 <= index && index < int(entries.size()));
740 }
741
742 return index;
743 }
744
745 int do_insert(const K &value, int &hash)
746 {
747 if (hashtable.empty()) {
748 entries.push_back(entry_t(value, -1));
749 do_rehash();
750 hash = do_hash(value);
751 } else {
752 entries.push_back(entry_t(value, hashtable[hash]));
753 hashtable[hash] = entries.size() - 1;
754 }
755 return entries.size() - 1;
756 }
757
758 public:
759 class const_iterator : public std::iterator<std::forward_iterator_tag, K>
760 {
761 friend class pool;
762 protected:
763 const pool *ptr;
764 int index;
765 const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { }
766 public:
767 const_iterator() { }
768 const_iterator operator++() { index--; return *this; }
769 bool operator==(const const_iterator &other) const { return index == other.index; }
770 bool operator!=(const const_iterator &other) const { return index != other.index; }
771 const K &operator*() const { return ptr->entries[index].udata; }
772 const K *operator->() const { return &ptr->entries[index].udata; }
773 };
774
775 class iterator : public std::iterator<std::forward_iterator_tag, K>
776 {
777 friend class pool;
778 protected:
779 pool *ptr;
780 int index;
781 iterator(pool *ptr, int index) : ptr(ptr), index(index) { }
782 public:
783 iterator() { }
784 iterator operator++() { index--; return *this; }
785 bool operator==(const iterator &other) const { return index == other.index; }
786 bool operator!=(const iterator &other) const { return index != other.index; }
787 K &operator*() { return ptr->entries[index].udata; }
788 K *operator->() { return &ptr->entries[index].udata; }
789 const K &operator*() const { return ptr->entries[index].udata; }
790 const K *operator->() const { return &ptr->entries[index].udata; }
791 operator const_iterator() const { return const_iterator(ptr, index); }
792 };
793
794 pool()
795 {
796 }
797
798 pool(const pool &other)
799 {
800 entries = other.entries;
801 do_rehash();
802 }
803
804 pool(pool &&other)
805 {
806 swap(other);
807 }
808
809 pool &operator=(const pool &other) {
810 entries = other.entries;
811 do_rehash();
812 return *this;
813 }
814
815 pool &operator=(pool &&other) {
816 clear();
817 swap(other);
818 return *this;
819 }
820
821 pool(const std::initializer_list<K> &list)
822 {
823 for (auto &it : list)
824 insert(it);
825 }
826
827 template<class InputIterator>
828 pool(InputIterator first, InputIterator last)
829 {
830 insert(first, last);
831 }
832
833 template<class InputIterator>
834 void insert(InputIterator first, InputIterator last)
835 {
836 for (; first != last; ++first)
837 insert(*first);
838 }
839
840 std::pair<iterator, bool> insert(const K &value)
841 {
842 int hash = do_hash(value);
843 int i = do_lookup(value, hash);
844 if (i >= 0)
845 return std::pair<iterator, bool>(iterator(this, i), false);
846 i = do_insert(value, hash);
847 return std::pair<iterator, bool>(iterator(this, i), true);
848 }
849
850 int erase(const K &key)
851 {
852 int hash = do_hash(key);
853 int index = do_lookup(key, hash);
854 return do_erase(index, hash);
855 }
856
857 iterator erase(iterator it)
858 {
859 int hash = do_hash(*it);
860 do_erase(it.index, hash);
861 return ++it;
862 }
863
864 int count(const K &key) const
865 {
866 int hash = do_hash(key);
867 int i = do_lookup(key, hash);
868 return i < 0 ? 0 : 1;
869 }
870
871 int count(const K &key, const_iterator it) const
872 {
873 int hash = do_hash(key);
874 int i = do_lookup(key, hash);
875 return i < 0 || i > it.index ? 0 : 1;
876 }
877
878 iterator find(const K &key)
879 {
880 int hash = do_hash(key);
881 int i = do_lookup(key, hash);
882 if (i < 0)
883 return end();
884 return iterator(this, i);
885 }
886
887 const_iterator find(const K &key) const
888 {
889 int hash = do_hash(key);
890 int i = do_lookup(key, hash);
891 if (i < 0)
892 return end();
893 return const_iterator(this, i);
894 }
895
896 bool operator[](const K &key)
897 {
898 int hash = do_hash(key);
899 int i = do_lookup(key, hash);
900 return i >= 0;
901 }
902
903 template<typename Compare = std::less<K>>
904 void sort(Compare comp = Compare())
905 {
906 std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata, a.udata); });
907 do_rehash();
908 }
909
910 K pop()
911 {
912 iterator it = begin();
913 K ret = *it;
914 erase(it);
915 return ret;
916 }
917
918 void swap(pool &other)
919 {
920 hashtable.swap(other.hashtable);
921 entries.swap(other.entries);
922 }
923
924 bool operator==(const pool &other) const {
925 if (size() != other.size())
926 return false;
927 for (auto &it : entries)
928 if (!other.count(it.udata))
929 return false;
930 return true;
931 }
932
933 bool operator!=(const pool &other) const {
934 return !operator==(other);
935 }
936
937 bool hash() const {
938 unsigned int hashval = mkhash_init;
939 for (auto &it : entries)
940 hashval ^= ops.hash(it.udata);
941 return hashval;
942 }
943
944 void reserve(size_t n) { entries.reserve(n); }
945 size_t size() const { return entries.size(); }
946 bool empty() const { return entries.empty(); }
947 void clear() { hashtable.clear(); entries.clear(); }
948
949 iterator begin() { return iterator(this, int(entries.size())-1); }
950 iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
951 iterator end() { return iterator(nullptr, -1); }
952
953 const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
954 const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
955 const_iterator end() const { return const_iterator(nullptr, -1); }
956 };
957
958 template<typename K, int offset, typename OPS>
959 class idict
960 {
961 pool<K, OPS> database;
962
963 public:
964 class const_iterator : public std::iterator<std::forward_iterator_tag, K>
965 {
966 friend class idict;
967 protected:
968 const idict &container;
969 int index;
970 const_iterator(const idict &container, int index) : container(container), index(index) { }
971 public:
972 const_iterator() { }
973 const_iterator operator++() { index++; return *this; }
974 bool operator==(const const_iterator &other) const { return index == other.index; }
975 bool operator!=(const const_iterator &other) const { return index != other.index; }
976 const K &operator*() const { return container[index]; }
977 const K *operator->() const { return &container[index]; }
978 };
979
980 int operator()(const K &key)
981 {
982 int hash = database.do_hash(key);
983 int i = database.do_lookup(key, hash);
984 if (i < 0)
985 i = database.do_insert(key, hash);
986 return i + offset;
987 }
988
989 int at(const K &key) const
990 {
991 int hash = database.do_hash(key);
992 int i = database.do_lookup(key, hash);
993 if (i < 0)
994 throw std::out_of_range("idict::at()");
995 return i + offset;
996 }
997
998 int at(const K &key, int defval) const
999 {
1000 int hash = database.do_hash(key);
1001 int i = database.do_lookup(key, hash);
1002 if (i < 0)
1003 return defval;
1004 return i + offset;
1005 }
1006
1007 int count(const K &key) const
1008 {
1009 int hash = database.do_hash(key);
1010 int i = database.do_lookup(key, hash);
1011 return i < 0 ? 0 : 1;
1012 }
1013
1014 void expect(const K &key, int i)
1015 {
1016 int j = (*this)(key);
1017 if (i != j)
1018 throw std::out_of_range("idict::expect()");
1019 }
1020
1021 const K &operator[](int index) const
1022 {
1023 return database.entries.at(index - offset).udata;
1024 }
1025
1026 void swap(idict &other)
1027 {
1028 database.swap(other.database);
1029 }
1030
1031 void reserve(size_t n) { database.reserve(n); }
1032 size_t size() const { return database.size(); }
1033 bool empty() const { return database.empty(); }
1034 void clear() { database.clear(); }
1035
1036 const_iterator begin() const { return const_iterator(*this, offset); }
1037 const_iterator element(int n) const { return const_iterator(*this, n); }
1038 const_iterator end() const { return const_iterator(*this, offset + size()); }
1039 };
1040
1041 template<typename K, typename OPS>
1042 class mfp
1043 {
1044 mutable idict<K, 0, OPS> database;
1045 mutable std::vector<int> parents;
1046
1047 public:
1048 typedef typename idict<K, 0, OPS>::const_iterator const_iterator;
1049
1050 int operator()(const K &key) const
1051 {
1052 int i = database(key);
1053 parents.resize(database.size(), -1);
1054 return i;
1055 }
1056
1057 const K &operator[](int index) const
1058 {
1059 return database[index];
1060 }
1061
1062 int ifind(int i) const
1063 {
1064 int p = i, k = i;
1065
1066 while (parents[p] != -1)
1067 p = parents[p];
1068
1069 while (k != p) {
1070 int next_k = parents[k];
1071 parents[k] = p;
1072 k = next_k;
1073 }
1074
1075 return p;
1076 }
1077
1078 void imerge(int i, int j)
1079 {
1080 i = ifind(i);
1081 j = ifind(j);
1082
1083 if (i != j)
1084 parents[i] = j;
1085 }
1086
1087 void ipromote(int i)
1088 {
1089 int k = i;
1090
1091 while (k != -1) {
1092 int next_k = parents[k];
1093 parents[k] = i;
1094 k = next_k;
1095 }
1096
1097 parents[i] = -1;
1098 }
1099
1100 int lookup(const K &a) const
1101 {
1102 return ifind((*this)(a));
1103 }
1104
1105 const K &find(const K &a) const
1106 {
1107 int i = database.at(a, -1);
1108 if (i < 0)
1109 return a;
1110 return (*this)[ifind(i)];
1111 }
1112
1113 void merge(const K &a, const K &b)
1114 {
1115 imerge((*this)(a), (*this)(b));
1116 }
1117
1118 void promote(const K &a)
1119 {
1120 int i = database.at(a, -1);
1121 if (i >= 0)
1122 ipromote(i);
1123 }
1124
1125 void swap(mfp &other)
1126 {
1127 database.swap(other.database);
1128 parents.swap(other.parents);
1129 }
1130
1131 void reserve(size_t n) { database.reserve(n); }
1132 size_t size() const { return database.size(); }
1133 bool empty() const { return database.empty(); }
1134 void clear() { database.clear(); parents.clear(); }
1135
1136 const_iterator begin() const { return database.begin(); }
1137 const_iterator element(int n) const { return database.element(n); }
1138 const_iterator end() const { return database.end(); }
1139 };
1140
1141 } /* namespace hashlib */
1142
1143 #endif