1 // This is free and unencumbered software released into the public domain.
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
8 // -------------------------------------------------------
9 // Written by Claire Xenia Wolf <claire@yosyshq.com> in 2014
10 // -------------------------------------------------------
22 const int hashtable_size_trigger
= 2;
23 const int hashtable_size_factor
= 3;
25 // The XOR version of DJB2
26 inline unsigned int mkhash(unsigned int a
, unsigned int b
) {
27 return ((a
<< 5) + a
) ^ b
;
30 // traditionally 5381 is used as starting value for the djb2 hash
31 const unsigned int mkhash_init
= 5381;
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
;
39 inline unsigned int mkhash_xorshift(unsigned int a
) {
44 } else if (sizeof(a
) == 8) {
49 throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
53 template<typename T
> struct hash_ops
{
54 static inline bool cmp(const T
&a
, const T
&b
) {
57 static inline unsigned int hash(const T
&a
) {
64 static inline bool cmp(T a
, T b
) {
69 template<> struct hash_ops
<bool> : hash_int_ops
71 static inline unsigned int hash(bool a
) {
75 template<> struct hash_ops
<int32_t> : hash_int_ops
77 static inline unsigned int hash(int32_t a
) {
81 template<> struct hash_ops
<int64_t> : hash_int_ops
83 static inline unsigned int hash(int64_t a
) {
84 return mkhash((unsigned int)(a
), (unsigned int)(a
>> 32));
88 template<> struct hash_ops
<std::string
> {
89 static inline bool cmp(const std::string
&a
, const std::string
&b
) {
92 static inline unsigned int hash(const std::string
&a
) {
100 template<typename P
, typename Q
> struct hash_ops
<std::pair
<P
, Q
>> {
101 static inline bool cmp(std::pair
<P
, Q
> a
, std::pair
<P
, Q
> b
) {
104 static inline unsigned int hash(std::pair
<P
, Q
> a
) {
105 return mkhash(hash_ops
<P
>::hash(a
.first
), hash_ops
<Q
>::hash(a
.second
));
109 template<typename
... T
> struct hash_ops
<std::tuple
<T
...>> {
110 static inline bool cmp(std::tuple
<T
...> a
, std::tuple
<T
...> b
) {
113 template<size_t I
= 0>
114 static inline typename
std::enable_if
<I
== sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...>) {
117 template<size_t I
= 0>
118 static inline typename
std::enable_if
<I
!= sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...> a
) {
119 typedef hash_ops
<typename
std::tuple_element
<I
, std::tuple
<T
...>>::type
> element_ops_t
;
120 return mkhash(hash
<I
+1>(a
), element_ops_t::hash(std::get
<I
>(a
)));
124 template<typename T
> struct hash_ops
<std::vector
<T
>> {
125 static inline bool cmp(std::vector
<T
> a
, std::vector
<T
> b
) {
128 static inline unsigned int hash(std::vector
<T
> a
) {
129 unsigned int h
= mkhash_init
;
131 h
= mkhash(h
, hash_ops
<T
>::hash(k
));
136 struct hash_cstr_ops
{
137 static inline bool cmp(const char *a
, const char *b
) {
138 for (int i
= 0; a
[i
] || b
[i
]; i
++)
143 static inline unsigned int hash(const char *a
) {
144 unsigned int hash
= mkhash_init
;
146 hash
= mkhash(hash
, *(a
++));
151 struct hash_ptr_ops
{
152 static inline bool cmp(const void *a
, const void *b
) {
155 static inline unsigned int hash(const void *a
) {
160 struct hash_obj_ops
{
161 static inline bool cmp(const void *a
, const void *b
) {
165 static inline unsigned int hash(const T
*a
) {
166 return a
? a
->hash() : 0;
171 inline unsigned int mkhash(const T
&v
) {
172 return hash_ops
<T
>().hash(v
);
175 inline int hashtable_size(int min_size
)
177 static std::vector
<int> zero_and_some_primes
= {
178 0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
179 853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
180 12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
181 120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
182 897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
183 5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
184 25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
185 121590311, 151987889, 189984863, 237481091, 296851369, 371064217
188 for (auto p
: zero_and_some_primes
)
189 if (p
>= min_size
) return p
;
191 if (sizeof(int) == 4)
192 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
194 for (auto p
: zero_and_some_primes
)
195 if (100129 * p
> min_size
) return 100129 * p
;
197 throw std::length_error("hash table exceeded maximum size.");
200 template<typename K
, typename T
, typename OPS
= hash_ops
<K
>> class dict
;
201 template<typename K
, int offset
= 0, typename OPS
= hash_ops
<K
>> class idict
;
202 template<typename K
, typename OPS
= hash_ops
<K
>> class pool
;
203 template<typename K
, typename OPS
= hash_ops
<K
>> class mfp
;
205 template<typename K
, typename T
, typename OPS
>
210 std::pair
<K
, T
> udata
;
214 entry_t(const std::pair
<K
, T
> &udata
, int next
) : udata(udata
), next(next
) { }
215 entry_t(std::pair
<K
, T
> &&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
216 bool operator<(const entry_t
&other
) const { return udata
.first
< other
.udata
.first
; }
219 std::vector
<int> hashtable
;
220 std::vector
<entry_t
> entries
;
224 static inline void do_assert(bool) { }
226 static inline void do_assert(bool cond
) {
227 if (!cond
) throw std::runtime_error("dict<> assert failed.");
231 int do_hash(const K
&key
) const
233 unsigned int hash
= 0;
234 if (!hashtable
.empty())
235 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
242 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
244 for (int i
= 0; i
< int(entries
.size()); i
++) {
245 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
246 int hash
= do_hash(entries
[i
].udata
.first
);
247 entries
[i
].next
= hashtable
[hash
];
252 int do_erase(int index
, int hash
)
254 do_assert(index
< int(entries
.size()));
255 if (hashtable
.empty() || index
< 0)
258 int k
= hashtable
[hash
];
259 do_assert(0 <= k
&& k
< int(entries
.size()));
262 hashtable
[hash
] = entries
[index
].next
;
264 while (entries
[k
].next
!= index
) {
266 do_assert(0 <= k
&& k
< int(entries
.size()));
268 entries
[k
].next
= entries
[index
].next
;
271 int back_idx
= entries
.size()-1;
273 if (index
!= back_idx
)
275 int back_hash
= do_hash(entries
[back_idx
].udata
.first
);
277 k
= hashtable
[back_hash
];
278 do_assert(0 <= k
&& k
< int(entries
.size()));
281 hashtable
[back_hash
] = index
;
283 while (entries
[k
].next
!= back_idx
) {
285 do_assert(0 <= k
&& k
< int(entries
.size()));
287 entries
[k
].next
= index
;
290 entries
[index
] = std::move(entries
[back_idx
]);
301 int do_lookup(const K
&key
, int &hash
) const
303 if (hashtable
.empty())
306 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
307 ((dict
*)this)->do_rehash();
311 int index
= hashtable
[hash
];
313 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
.first
, key
)) {
314 index
= entries
[index
].next
;
315 do_assert(-1 <= index
&& index
< int(entries
.size()));
321 int do_insert(const K
&key
, int &hash
)
323 if (hashtable
.empty()) {
324 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), -1);
328 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), hashtable
[hash
]);
329 hashtable
[hash
] = entries
.size() - 1;
331 return entries
.size() - 1;
334 int do_insert(const std::pair
<K
, T
> &value
, int &hash
)
336 if (hashtable
.empty()) {
337 entries
.emplace_back(value
, -1);
339 hash
= do_hash(value
.first
);
341 entries
.emplace_back(value
, hashtable
[hash
]);
342 hashtable
[hash
] = entries
.size() - 1;
344 return entries
.size() - 1;
347 int do_insert(std::pair
<K
, T
> &&rvalue
, int &hash
)
349 if (hashtable
.empty()) {
350 auto key
= rvalue
.first
;
351 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), -1);
355 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), hashtable
[hash
]);
356 hashtable
[hash
] = entries
.size() - 1;
358 return entries
.size() - 1;
362 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
368 const_iterator(const dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
371 const_iterator
operator++() { index
--; return *this; }
372 const_iterator
operator+=(int amt
) { index
-= amt
; return *this; }
373 bool operator<(const const_iterator
&other
) const { return index
> other
.index
; }
374 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
375 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
376 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
377 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
380 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
386 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
389 iterator
operator++() { index
--; return *this; }
390 iterator
operator+=(int amt
) { index
-= amt
; return *this; }
391 bool operator<(const iterator
&other
) const { return index
> other
.index
; }
392 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
393 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
394 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
395 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
396 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
397 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
398 operator const_iterator() const { return const_iterator(ptr
, index
); }
405 dict(const dict
&other
)
407 entries
= other
.entries
;
416 dict
&operator=(const dict
&other
) {
417 entries
= other
.entries
;
422 dict
&operator=(dict
&&other
) {
428 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
430 for (auto &it
: list
)
434 template<class InputIterator
>
435 dict(InputIterator first
, InputIterator last
)
440 template<class InputIterator
>
441 void insert(InputIterator first
, InputIterator last
)
443 for (; first
!= last
; ++first
)
447 std::pair
<iterator
, bool> insert(const K
&key
)
449 int hash
= do_hash(key
);
450 int i
= do_lookup(key
, hash
);
452 return std::pair
<iterator
, bool>(iterator(this, i
), false);
453 i
= do_insert(key
, hash
);
454 return std::pair
<iterator
, bool>(iterator(this, i
), true);
457 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
459 int hash
= do_hash(value
.first
);
460 int i
= do_lookup(value
.first
, hash
);
462 return std::pair
<iterator
, bool>(iterator(this, i
), false);
463 i
= do_insert(value
, hash
);
464 return std::pair
<iterator
, bool>(iterator(this, i
), true);
467 std::pair
<iterator
, bool> insert(std::pair
<K
, T
> &&rvalue
)
469 int hash
= do_hash(rvalue
.first
);
470 int i
= do_lookup(rvalue
.first
, hash
);
472 return std::pair
<iterator
, bool>(iterator(this, i
), false);
473 i
= do_insert(std::forward
<std::pair
<K
, T
>>(rvalue
), hash
);
474 return std::pair
<iterator
, bool>(iterator(this, i
), true);
477 std::pair
<iterator
, bool> emplace(K
const &key
, T
const &value
)
479 int hash
= do_hash(key
);
480 int i
= do_lookup(key
, hash
);
482 return std::pair
<iterator
, bool>(iterator(this, i
), false);
483 i
= do_insert(std::make_pair(key
, value
), hash
);
484 return std::pair
<iterator
, bool>(iterator(this, i
), true);
487 std::pair
<iterator
, bool> emplace(K
const &key
, T
&&rvalue
)
489 int hash
= do_hash(key
);
490 int i
= do_lookup(key
, hash
);
492 return std::pair
<iterator
, bool>(iterator(this, i
), false);
493 i
= do_insert(std::make_pair(key
, std::forward
<T
>(rvalue
)), hash
);
494 return std::pair
<iterator
, bool>(iterator(this, i
), true);
497 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
const &value
)
499 int hash
= do_hash(rkey
);
500 int i
= do_lookup(rkey
, hash
);
502 return std::pair
<iterator
, bool>(iterator(this, i
), false);
503 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), value
), hash
);
504 return std::pair
<iterator
, bool>(iterator(this, i
), true);
507 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
&&rvalue
)
509 int hash
= do_hash(rkey
);
510 int i
= do_lookup(rkey
, hash
);
512 return std::pair
<iterator
, bool>(iterator(this, i
), false);
513 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), std::forward
<T
>(rvalue
)), hash
);
514 return std::pair
<iterator
, bool>(iterator(this, i
), true);
517 int erase(const K
&key
)
519 int hash
= do_hash(key
);
520 int index
= do_lookup(key
, hash
);
521 return do_erase(index
, hash
);
524 iterator
erase(iterator it
)
526 int hash
= do_hash(it
->first
);
527 do_erase(it
.index
, hash
);
531 int count(const K
&key
) const
533 int hash
= do_hash(key
);
534 int i
= do_lookup(key
, hash
);
535 return i
< 0 ? 0 : 1;
538 int count(const K
&key
, const_iterator it
) const
540 int hash
= do_hash(key
);
541 int i
= do_lookup(key
, hash
);
542 return i
< 0 || i
> it
.index
? 0 : 1;
545 iterator
find(const K
&key
)
547 int hash
= do_hash(key
);
548 int i
= do_lookup(key
, hash
);
551 return iterator(this, i
);
554 const_iterator
find(const K
&key
) const
556 int hash
= do_hash(key
);
557 int i
= do_lookup(key
, hash
);
560 return const_iterator(this, i
);
565 int hash
= do_hash(key
);
566 int i
= do_lookup(key
, hash
);
568 throw std::out_of_range("dict::at()");
569 return entries
[i
].udata
.second
;
572 const T
& at(const K
&key
) const
574 int hash
= do_hash(key
);
575 int i
= do_lookup(key
, hash
);
577 throw std::out_of_range("dict::at()");
578 return entries
[i
].udata
.second
;
581 const T
& at(const K
&key
, const T
&defval
) const
583 int hash
= do_hash(key
);
584 int i
= do_lookup(key
, hash
);
587 return entries
[i
].udata
.second
;
590 T
& operator[](const K
&key
)
592 int hash
= do_hash(key
);
593 int i
= do_lookup(key
, hash
);
595 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
596 return entries
[i
].udata
.second
;
599 template<typename Compare
= std::less
<K
>>
600 void sort(Compare comp
= Compare())
602 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
606 void swap(dict
&other
)
608 hashtable
.swap(other
.hashtable
);
609 entries
.swap(other
.entries
);
612 bool operator==(const dict
&other
) const {
613 if (size() != other
.size())
615 for (auto &it
: entries
) {
616 auto oit
= other
.find(it
.udata
.first
);
617 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
623 bool operator!=(const dict
&other
) const {
624 return !operator==(other
);
627 unsigned int hash() const {
628 unsigned int h
= mkhash_init
;
629 for (auto &entry
: entries
) {
630 h
^= hash_ops
<K
>::hash(entry
.udata
.first
);
631 h
^= hash_ops
<T
>::hash(entry
.udata
.second
);
636 void reserve(size_t n
) { entries
.reserve(n
); }
637 size_t size() const { return entries
.size(); }
638 bool empty() const { return entries
.empty(); }
639 void clear() { hashtable
.clear(); entries
.clear(); }
641 iterator
begin() { return iterator(this, int(entries
.size())-1); }
642 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
643 iterator
end() { return iterator(nullptr, -1); }
645 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
646 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
647 const_iterator
end() const { return const_iterator(nullptr, -1); }
650 template<typename K
, typename OPS
>
653 template<typename
, int, typename
> friend class idict
;
662 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
663 entry_t(K
&&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
666 std::vector
<int> hashtable
;
667 std::vector
<entry_t
> entries
;
671 static inline void do_assert(bool) { }
673 static inline void do_assert(bool cond
) {
674 if (!cond
) throw std::runtime_error("pool<> assert failed.");
678 int do_hash(const K
&key
) const
680 unsigned int hash
= 0;
681 if (!hashtable
.empty())
682 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
689 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
691 for (int i
= 0; i
< int(entries
.size()); i
++) {
692 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
693 int hash
= do_hash(entries
[i
].udata
);
694 entries
[i
].next
= hashtable
[hash
];
699 int do_erase(int index
, int hash
)
701 do_assert(index
< int(entries
.size()));
702 if (hashtable
.empty() || index
< 0)
705 int k
= hashtable
[hash
];
707 hashtable
[hash
] = entries
[index
].next
;
709 while (entries
[k
].next
!= index
) {
711 do_assert(0 <= k
&& k
< int(entries
.size()));
713 entries
[k
].next
= entries
[index
].next
;
716 int back_idx
= entries
.size()-1;
718 if (index
!= back_idx
)
720 int back_hash
= do_hash(entries
[back_idx
].udata
);
722 k
= hashtable
[back_hash
];
724 hashtable
[back_hash
] = index
;
726 while (entries
[k
].next
!= back_idx
) {
728 do_assert(0 <= k
&& k
< int(entries
.size()));
730 entries
[k
].next
= index
;
733 entries
[index
] = std::move(entries
[back_idx
]);
744 int do_lookup(const K
&key
, int &hash
) const
746 if (hashtable
.empty())
749 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
750 ((pool
*)this)->do_rehash();
754 int index
= hashtable
[hash
];
756 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
757 index
= entries
[index
].next
;
758 do_assert(-1 <= index
&& index
< int(entries
.size()));
764 int do_insert(const K
&value
, int &hash
)
766 if (hashtable
.empty()) {
767 entries
.emplace_back(value
, -1);
769 hash
= do_hash(value
);
771 entries
.emplace_back(value
, hashtable
[hash
]);
772 hashtable
[hash
] = entries
.size() - 1;
774 return entries
.size() - 1;
777 int do_insert(K
&&rvalue
, int &hash
)
779 if (hashtable
.empty()) {
780 entries
.emplace_back(std::forward
<K
>(rvalue
), -1);
782 hash
= do_hash(rvalue
);
784 entries
.emplace_back(std::forward
<K
>(rvalue
), hashtable
[hash
]);
785 hashtable
[hash
] = entries
.size() - 1;
787 return entries
.size() - 1;
791 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
797 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
800 const_iterator
operator++() { index
--; return *this; }
801 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
802 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
803 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
804 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
807 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
813 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
816 iterator
operator++() { index
--; return *this; }
817 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
818 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
819 K
&operator*() { return ptr
->entries
[index
].udata
; }
820 K
*operator->() { return &ptr
->entries
[index
].udata
; }
821 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
822 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
823 operator const_iterator() const { return const_iterator(ptr
, index
); }
830 pool(const pool
&other
)
832 entries
= other
.entries
;
841 pool
&operator=(const pool
&other
) {
842 entries
= other
.entries
;
847 pool
&operator=(pool
&&other
) {
853 pool(const std::initializer_list
<K
> &list
)
855 for (auto &it
: list
)
859 template<class InputIterator
>
860 pool(InputIterator first
, InputIterator last
)
865 template<class InputIterator
>
866 void insert(InputIterator first
, InputIterator last
)
868 for (; first
!= last
; ++first
)
872 std::pair
<iterator
, bool> insert(const K
&value
)
874 int hash
= do_hash(value
);
875 int i
= do_lookup(value
, hash
);
877 return std::pair
<iterator
, bool>(iterator(this, i
), false);
878 i
= do_insert(value
, hash
);
879 return std::pair
<iterator
, bool>(iterator(this, i
), true);
882 std::pair
<iterator
, bool> insert(K
&&rvalue
)
884 int hash
= do_hash(rvalue
);
885 int i
= do_lookup(rvalue
, hash
);
887 return std::pair
<iterator
, bool>(iterator(this, i
), false);
888 i
= do_insert(std::forward
<K
>(rvalue
), hash
);
889 return std::pair
<iterator
, bool>(iterator(this, i
), true);
892 template<typename
... Args
>
893 std::pair
<iterator
, bool> emplace(Args
&&... args
)
895 return insert(K(std::forward
<Args
>(args
)...));
898 int erase(const K
&key
)
900 int hash
= do_hash(key
);
901 int index
= do_lookup(key
, hash
);
902 return do_erase(index
, hash
);
905 iterator
erase(iterator it
)
907 int hash
= do_hash(*it
);
908 do_erase(it
.index
, hash
);
912 int count(const K
&key
) const
914 int hash
= do_hash(key
);
915 int i
= do_lookup(key
, hash
);
916 return i
< 0 ? 0 : 1;
919 int count(const K
&key
, const_iterator it
) const
921 int hash
= do_hash(key
);
922 int i
= do_lookup(key
, hash
);
923 return i
< 0 || i
> it
.index
? 0 : 1;
926 iterator
find(const K
&key
)
928 int hash
= do_hash(key
);
929 int i
= do_lookup(key
, hash
);
932 return iterator(this, i
);
935 const_iterator
find(const K
&key
) const
937 int hash
= do_hash(key
);
938 int i
= do_lookup(key
, hash
);
941 return const_iterator(this, i
);
944 bool operator[](const K
&key
)
946 int hash
= do_hash(key
);
947 int i
= do_lookup(key
, hash
);
951 template<typename Compare
= std::less
<K
>>
952 void sort(Compare comp
= Compare())
954 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
960 iterator it
= begin();
966 void swap(pool
&other
)
968 hashtable
.swap(other
.hashtable
);
969 entries
.swap(other
.entries
);
972 bool operator==(const pool
&other
) const {
973 if (size() != other
.size())
975 for (auto &it
: entries
)
976 if (!other
.count(it
.udata
))
981 bool operator!=(const pool
&other
) const {
982 return !operator==(other
);
986 unsigned int hashval
= mkhash_init
;
987 for (auto &it
: entries
)
988 hashval
^= ops
.hash(it
.udata
);
992 void reserve(size_t n
) { entries
.reserve(n
); }
993 size_t size() const { return entries
.size(); }
994 bool empty() const { return entries
.empty(); }
995 void clear() { hashtable
.clear(); entries
.clear(); }
997 iterator
begin() { return iterator(this, int(entries
.size())-1); }
998 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
999 iterator
end() { return iterator(nullptr, -1); }
1001 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
1002 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
1003 const_iterator
end() const { return const_iterator(nullptr, -1); }
1006 template<typename K
, int offset
, typename OPS
>
1009 pool
<K
, OPS
> database
;
1012 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
1016 const idict
&container
;
1018 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
1020 const_iterator() { }
1021 const_iterator
operator++() { index
++; return *this; }
1022 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
1023 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
1024 const K
&operator*() const { return container
[index
]; }
1025 const K
*operator->() const { return &container
[index
]; }
1028 int operator()(const K
&key
)
1030 int hash
= database
.do_hash(key
);
1031 int i
= database
.do_lookup(key
, hash
);
1033 i
= database
.do_insert(key
, hash
);
1037 int at(const K
&key
) const
1039 int hash
= database
.do_hash(key
);
1040 int i
= database
.do_lookup(key
, hash
);
1042 throw std::out_of_range("idict::at()");
1046 int at(const K
&key
, int defval
) const
1048 int hash
= database
.do_hash(key
);
1049 int i
= database
.do_lookup(key
, hash
);
1055 int count(const K
&key
) const
1057 int hash
= database
.do_hash(key
);
1058 int i
= database
.do_lookup(key
, hash
);
1059 return i
< 0 ? 0 : 1;
1062 void expect(const K
&key
, int i
)
1064 int j
= (*this)(key
);
1066 throw std::out_of_range("idict::expect()");
1069 const K
&operator[](int index
) const
1071 return database
.entries
.at(index
- offset
).udata
;
1074 void swap(idict
&other
)
1076 database
.swap(other
.database
);
1079 void reserve(size_t n
) { database
.reserve(n
); }
1080 size_t size() const { return database
.size(); }
1081 bool empty() const { return database
.empty(); }
1082 void clear() { database
.clear(); }
1084 const_iterator
begin() const { return const_iterator(*this, offset
); }
1085 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1086 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1089 template<typename K
, typename OPS
>
1092 mutable idict
<K
, 0, OPS
> database
;
1093 mutable std::vector
<int> parents
;
1096 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1098 int operator()(const K
&key
) const
1100 int i
= database(key
);
1101 parents
.resize(database
.size(), -1);
1105 const K
&operator[](int index
) const
1107 return database
[index
];
1110 int ifind(int i
) const
1114 while (parents
[p
] != -1)
1118 int next_k
= parents
[k
];
1126 void imerge(int i
, int j
)
1135 void ipromote(int i
)
1140 int next_k
= parents
[k
];
1148 int lookup(const K
&a
) const
1150 return ifind((*this)(a
));
1153 const K
&find(const K
&a
) const
1155 int i
= database
.at(a
, -1);
1158 return (*this)[ifind(i
)];
1161 void merge(const K
&a
, const K
&b
)
1163 imerge((*this)(a
), (*this)(b
));
1166 void promote(const K
&a
)
1168 int i
= database
.at(a
, -1);
1173 void swap(mfp
&other
)
1175 database
.swap(other
.database
);
1176 parents
.swap(other
.parents
);
1179 void reserve(size_t n
) { database
.reserve(n
); }
1180 size_t size() const { return database
.size(); }
1181 bool empty() const { return database
.empty(); }
1182 void clear() { database
.clear(); parents
.clear(); }
1184 const_iterator
begin() const { return database
.begin(); }
1185 const_iterator
element(int n
) const { return database
.element(n
); }
1186 const_iterator
end() const { return database
.end(); }
1189 } /* namespace hashlib */