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 Clifford Wolf <clifford@clifford.at> 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
<int32_t> : hash_int_ops
71 static inline unsigned int hash(int32_t a
) {
75 template<> struct hash_ops
<int64_t> : hash_int_ops
77 static inline unsigned int hash(int64_t a
) {
78 return mkhash((unsigned int)(a
), (unsigned int)(a
>> 32));
82 template<> struct hash_ops
<std::string
> {
83 static inline bool cmp(const std::string
&a
, const std::string
&b
) {
86 static inline unsigned int hash(const std::string
&a
) {
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
) {
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
));
103 template<typename
... T
> struct hash_ops
<std::tuple
<T
...>> {
104 static inline bool cmp(std::tuple
<T
...> a
, std::tuple
<T
...> b
) {
107 template<size_t I
= 0>
108 static inline typename
std::enable_if
<I
== sizeof...(T
), unsigned int>::type
hash(std::tuple
<T
...>) {
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
)));
118 template<typename T
> struct hash_ops
<std::vector
<T
>> {
119 static inline bool cmp(std::vector
<T
> a
, std::vector
<T
> b
) {
122 static inline unsigned int hash(std::vector
<T
> a
) {
123 unsigned int h
= mkhash_init
;
125 h
= mkhash(h
, hash_ops
<T
>::hash(k
));
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
++)
137 static inline unsigned int hash(const char *a
) {
138 unsigned int hash
= mkhash_init
;
140 hash
= mkhash(hash
, *(a
++));
145 struct hash_ptr_ops
{
146 static inline bool cmp(const void *a
, const void *b
) {
149 static inline unsigned int hash(const void *a
) {
154 struct hash_obj_ops
{
155 static inline bool cmp(const void *a
, const void *b
) {
159 static inline unsigned int hash(const T
*a
) {
160 return a
? a
->hash() : 0;
165 inline unsigned int mkhash(const T
&v
) {
166 return hash_ops
<T
>().hash(v
);
169 inline int hashtable_size(int min_size
)
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
182 for (auto p
: zero_and_some_primes
)
183 if (p
>= min_size
) return p
;
185 if (sizeof(int) == 4)
186 throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");
188 for (auto p
: zero_and_some_primes
)
189 if (100129 * p
> min_size
) return 100129 * p
;
191 throw std::length_error("hash table exceeded maximum size.");
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
;
199 template<typename K
, typename T
, typename OPS
>
204 std::pair
<K
, T
> udata
;
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
) { }
212 std::vector
<int> hashtable
;
213 std::vector
<entry_t
> entries
;
217 static inline void do_assert(bool) { }
219 static inline void do_assert(bool cond
) {
220 if (!cond
) throw std::runtime_error("dict<> assert failed.");
224 int do_hash(const K
&key
) const
226 unsigned int hash
= 0;
227 if (!hashtable
.empty())
228 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
235 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
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
];
245 int do_erase(int index
, int hash
)
247 do_assert(index
< int(entries
.size()));
248 if (hashtable
.empty() || index
< 0)
251 int k
= hashtable
[hash
];
252 do_assert(0 <= k
&& k
< int(entries
.size()));
255 hashtable
[hash
] = entries
[index
].next
;
257 while (entries
[k
].next
!= index
) {
259 do_assert(0 <= k
&& k
< int(entries
.size()));
261 entries
[k
].next
= entries
[index
].next
;
264 int back_idx
= entries
.size()-1;
266 if (index
!= back_idx
)
268 int back_hash
= do_hash(entries
[back_idx
].udata
.first
);
270 k
= hashtable
[back_hash
];
271 do_assert(0 <= k
&& k
< int(entries
.size()));
274 hashtable
[back_hash
] = index
;
276 while (entries
[k
].next
!= back_idx
) {
278 do_assert(0 <= k
&& k
< int(entries
.size()));
280 entries
[k
].next
= index
;
283 entries
[index
] = std::move(entries
[back_idx
]);
294 int do_lookup(const K
&key
, int &hash
) const
296 if (hashtable
.empty())
299 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
300 ((dict
*)this)->do_rehash();
304 int index
= hashtable
[hash
];
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()));
314 int do_insert(const K
&key
, int &hash
)
316 if (hashtable
.empty()) {
317 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), -1);
321 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), hashtable
[hash
]);
322 hashtable
[hash
] = entries
.size() - 1;
324 return entries
.size() - 1;
327 int do_insert(const std::pair
<K
, T
> &value
, int &hash
)
329 if (hashtable
.empty()) {
330 entries
.emplace_back(value
, -1);
332 hash
= do_hash(value
.first
);
334 entries
.emplace_back(value
, hashtable
[hash
]);
335 hashtable
[hash
] = entries
.size() - 1;
337 return entries
.size() - 1;
340 int do_insert(std::pair
<K
, T
> &&rvalue
, int &hash
)
342 if (hashtable
.empty()) {
343 auto key
= rvalue
.first
;
344 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), -1);
348 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), hashtable
[hash
]);
349 hashtable
[hash
] = entries
.size() - 1;
351 return entries
.size() - 1;
355 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
361 const_iterator(const dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
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
; }
372 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
378 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
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
); }
396 dict(const dict
&other
)
398 entries
= other
.entries
;
407 dict
&operator=(const dict
&other
) {
408 entries
= other
.entries
;
413 dict
&operator=(dict
&&other
) {
419 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
421 for (auto &it
: list
)
425 template<class InputIterator
>
426 dict(InputIterator first
, InputIterator last
)
431 template<class InputIterator
>
432 void insert(InputIterator first
, InputIterator last
)
434 for (; first
!= last
; ++first
)
438 std::pair
<iterator
, bool> insert(const K
&key
)
440 int hash
= do_hash(key
);
441 int i
= do_lookup(key
, hash
);
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);
448 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
450 int hash
= do_hash(value
.first
);
451 int i
= do_lookup(value
.first
, hash
);
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);
458 std::pair
<iterator
, bool> insert(std::pair
<K
, T
> &&rvalue
)
460 int hash
= do_hash(rvalue
.first
);
461 int i
= do_lookup(rvalue
.first
, hash
);
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);
468 std::pair
<iterator
, bool> emplace(K
const &key
, T
const &value
)
470 int hash
= do_hash(key
);
471 int i
= do_lookup(key
, hash
);
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);
478 std::pair
<iterator
, bool> emplace(K
const &key
, T
&&rvalue
)
480 int hash
= do_hash(key
);
481 int i
= do_lookup(key
, hash
);
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);
488 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
const &value
)
490 int hash
= do_hash(rkey
);
491 int i
= do_lookup(rkey
, hash
);
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);
498 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
&&rvalue
)
500 int hash
= do_hash(rkey
);
501 int i
= do_lookup(rkey
, hash
);
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);
508 int erase(const K
&key
)
510 int hash
= do_hash(key
);
511 int index
= do_lookup(key
, hash
);
512 return do_erase(index
, hash
);
515 iterator
erase(iterator it
)
517 int hash
= do_hash(it
->first
);
518 do_erase(it
.index
, hash
);
522 int count(const K
&key
) const
524 int hash
= do_hash(key
);
525 int i
= do_lookup(key
, hash
);
526 return i
< 0 ? 0 : 1;
529 int count(const K
&key
, const_iterator it
) const
531 int hash
= do_hash(key
);
532 int i
= do_lookup(key
, hash
);
533 return i
< 0 || i
> it
.index
? 0 : 1;
536 iterator
find(const K
&key
)
538 int hash
= do_hash(key
);
539 int i
= do_lookup(key
, hash
);
542 return iterator(this, i
);
545 const_iterator
find(const K
&key
) const
547 int hash
= do_hash(key
);
548 int i
= do_lookup(key
, hash
);
551 return const_iterator(this, i
);
556 int hash
= do_hash(key
);
557 int i
= do_lookup(key
, hash
);
559 throw std::out_of_range("dict::at()");
560 return entries
[i
].udata
.second
;
563 const T
& at(const K
&key
) const
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 T
at(const K
&key
, const T
&defval
) const
574 int hash
= do_hash(key
);
575 int i
= do_lookup(key
, hash
);
578 return entries
[i
].udata
.second
;
581 T
& operator[](const K
&key
)
583 int hash
= do_hash(key
);
584 int i
= do_lookup(key
, hash
);
586 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
587 return entries
[i
].udata
.second
;
590 template<typename Compare
= std::less
<K
>>
591 void sort(Compare comp
= Compare())
593 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
597 void swap(dict
&other
)
599 hashtable
.swap(other
.hashtable
);
600 entries
.swap(other
.entries
);
603 bool operator==(const dict
&other
) const {
604 if (size() != other
.size())
606 for (auto &it
: entries
) {
607 auto oit
= other
.find(it
.udata
.first
);
608 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
614 bool operator!=(const dict
&other
) const {
615 return !operator==(other
);
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(); }
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); }
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); }
632 template<typename K
, typename OPS
>
635 template<typename
, int, typename
> friend class idict
;
644 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
647 std::vector
<int> hashtable
;
648 std::vector
<entry_t
> entries
;
652 static inline void do_assert(bool) { }
654 static inline void do_assert(bool cond
) {
655 if (!cond
) throw std::runtime_error("pool<> assert failed.");
659 int do_hash(const K
&key
) const
661 unsigned int hash
= 0;
662 if (!hashtable
.empty())
663 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
670 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
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
];
680 int do_erase(int index
, int hash
)
682 do_assert(index
< int(entries
.size()));
683 if (hashtable
.empty() || index
< 0)
686 int k
= hashtable
[hash
];
688 hashtable
[hash
] = entries
[index
].next
;
690 while (entries
[k
].next
!= index
) {
692 do_assert(0 <= k
&& k
< int(entries
.size()));
694 entries
[k
].next
= entries
[index
].next
;
697 int back_idx
= entries
.size()-1;
699 if (index
!= back_idx
)
701 int back_hash
= do_hash(entries
[back_idx
].udata
);
703 k
= hashtable
[back_hash
];
705 hashtable
[back_hash
] = index
;
707 while (entries
[k
].next
!= back_idx
) {
709 do_assert(0 <= k
&& k
< int(entries
.size()));
711 entries
[k
].next
= index
;
714 entries
[index
] = std::move(entries
[back_idx
]);
725 int do_lookup(const K
&key
, int &hash
) const
727 if (hashtable
.empty())
730 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
731 ((pool
*)this)->do_rehash();
735 int index
= hashtable
[hash
];
737 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
738 index
= entries
[index
].next
;
739 do_assert(-1 <= index
&& index
< int(entries
.size()));
745 int do_insert(const K
&value
, int &hash
)
747 if (hashtable
.empty()) {
748 entries
.emplace_back(value
, -1);
750 hash
= do_hash(value
);
752 entries
.emplace_back(value
, hashtable
[hash
]);
753 hashtable
[hash
] = entries
.size() - 1;
755 return entries
.size() - 1;
758 int do_insert(K
&&value
, int &hash
)
760 if (hashtable
.empty()) {
761 entries
.emplace_back(std::forward
<K
>(value
), -1);
763 hash
= do_hash(value
);
765 entries
.emplace_back(std::forward
<K
>(value
), hashtable
[hash
]);
766 hashtable
[hash
] = entries
.size() - 1;
768 return entries
.size() - 1;
772 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
778 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
781 const_iterator
operator++() { index
--; return *this; }
782 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
783 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
784 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
785 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
788 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
794 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
797 iterator
operator++() { index
--; return *this; }
798 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
799 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
800 K
&operator*() { return ptr
->entries
[index
].udata
; }
801 K
*operator->() { return &ptr
->entries
[index
].udata
; }
802 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
803 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
804 operator const_iterator() const { return const_iterator(ptr
, index
); }
811 pool(const pool
&other
)
813 entries
= other
.entries
;
822 pool
&operator=(const pool
&other
) {
823 entries
= other
.entries
;
828 pool
&operator=(pool
&&other
) {
834 pool(const std::initializer_list
<K
> &list
)
836 for (auto &it
: list
)
840 template<class InputIterator
>
841 pool(InputIterator first
, InputIterator last
)
846 template<class InputIterator
>
847 void insert(InputIterator first
, InputIterator last
)
849 for (; first
!= last
; ++first
)
853 std::pair
<iterator
, bool> insert(const K
&value
)
855 int hash
= do_hash(value
);
856 int i
= do_lookup(value
, hash
);
858 return std::pair
<iterator
, bool>(iterator(this, i
), false);
859 i
= do_insert(value
, hash
);
860 return std::pair
<iterator
, bool>(iterator(this, i
), true);
863 std::pair
<iterator
, bool> insert(K
&&value
)
865 int hash
= do_hash(value
);
866 int i
= do_lookup(value
, hash
);
868 return std::pair
<iterator
, bool>(iterator(this, i
), false);
869 i
= do_insert(std::forward
<K
>(value
), hash
);
870 return std::pair
<iterator
, bool>(iterator(this, i
), true);
873 int erase(const K
&key
)
875 int hash
= do_hash(key
);
876 int index
= do_lookup(key
, hash
);
877 return do_erase(index
, hash
);
880 iterator
erase(iterator it
)
882 int hash
= do_hash(*it
);
883 do_erase(it
.index
, hash
);
887 int count(const K
&key
) const
889 int hash
= do_hash(key
);
890 int i
= do_lookup(key
, hash
);
891 return i
< 0 ? 0 : 1;
894 int count(const K
&key
, const_iterator it
) const
896 int hash
= do_hash(key
);
897 int i
= do_lookup(key
, hash
);
898 return i
< 0 || i
> it
.index
? 0 : 1;
901 iterator
find(const K
&key
)
903 int hash
= do_hash(key
);
904 int i
= do_lookup(key
, hash
);
907 return iterator(this, i
);
910 const_iterator
find(const K
&key
) const
912 int hash
= do_hash(key
);
913 int i
= do_lookup(key
, hash
);
916 return const_iterator(this, i
);
919 bool operator[](const K
&key
)
921 int hash
= do_hash(key
);
922 int i
= do_lookup(key
, hash
);
926 template<typename Compare
= std::less
<K
>>
927 void sort(Compare comp
= Compare())
929 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
935 iterator it
= begin();
941 void swap(pool
&other
)
943 hashtable
.swap(other
.hashtable
);
944 entries
.swap(other
.entries
);
947 bool operator==(const pool
&other
) const {
948 if (size() != other
.size())
950 for (auto &it
: entries
)
951 if (!other
.count(it
.udata
))
956 bool operator!=(const pool
&other
) const {
957 return !operator==(other
);
961 unsigned int hashval
= mkhash_init
;
962 for (auto &it
: entries
)
963 hashval
^= ops
.hash(it
.udata
);
967 void reserve(size_t n
) { entries
.reserve(n
); }
968 size_t size() const { return entries
.size(); }
969 bool empty() const { return entries
.empty(); }
970 void clear() { hashtable
.clear(); entries
.clear(); }
972 iterator
begin() { return iterator(this, int(entries
.size())-1); }
973 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
974 iterator
end() { return iterator(nullptr, -1); }
976 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
977 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
978 const_iterator
end() const { return const_iterator(nullptr, -1); }
981 template<typename K
, int offset
, typename OPS
>
984 pool
<K
, OPS
> database
;
987 typedef typename pool
<K
, OPS
>::const_iterator const_iterator
;
989 int operator()(const K
&key
)
991 int hash
= database
.do_hash(key
);
992 int i
= database
.do_lookup(key
, hash
);
994 i
= database
.do_insert(key
, hash
);
998 int at(const K
&key
) const
1000 int hash
= database
.do_hash(key
);
1001 int i
= database
.do_lookup(key
, hash
);
1003 throw std::out_of_range("idict::at()");
1007 int at(const K
&key
, int defval
) const
1009 int hash
= database
.do_hash(key
);
1010 int i
= database
.do_lookup(key
, hash
);
1016 int count(const K
&key
) const
1018 int hash
= database
.do_hash(key
);
1019 int i
= database
.do_lookup(key
, hash
);
1020 return i
< 0 ? 0 : 1;
1023 void expect(const K
&key
, int i
)
1025 int j
= (*this)(key
);
1027 throw std::out_of_range("idict::expect()");
1030 const K
&operator[](int index
) const
1032 return database
.entries
.at(index
- offset
).udata
;
1035 void swap(idict
&other
)
1037 database
.swap(other
.database
);
1040 void reserve(size_t n
) { database
.reserve(n
); }
1041 size_t size() const { return database
.size(); }
1042 bool empty() const { return database
.empty(); }
1043 void clear() { database
.clear(); }
1045 const_iterator
begin() const { return database
.begin(); }
1046 const_iterator
element(int n
) const { return database
.element(n
); }
1047 const_iterator
end() const { return database
.end(); }
1050 template<typename K
, typename OPS
>
1053 mutable idict
<K
, 0, OPS
> database
;
1054 mutable std::vector
<int> parents
;
1057 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1059 int operator()(const K
&key
) const
1061 int i
= database(key
);
1062 parents
.resize(database
.size(), -1);
1066 const K
&operator[](int index
) const
1068 return database
[index
];
1071 int ifind(int i
) const
1075 while (parents
[p
] != -1)
1079 int next_k
= parents
[k
];
1087 void imerge(int i
, int j
)
1096 void ipromote(int i
)
1101 int next_k
= parents
[k
];
1109 int lookup(const K
&a
) const
1111 return ifind((*this)(a
));
1114 const K
&find(const K
&a
) const
1116 int i
= database
.at(a
, -1);
1119 return (*this)[ifind(i
)];
1122 void merge(const K
&a
, const K
&b
)
1124 imerge((*this)(a
), (*this)(b
));
1127 void promote(const K
&a
)
1129 int i
= database
.at(a
, -1);
1134 void swap(mfp
&other
)
1136 database
.swap(other
.database
);
1137 parents
.swap(other
.parents
);
1140 void reserve(size_t n
) { database
.reserve(n
); }
1141 size_t size() const { return database
.size(); }
1142 bool empty() const { return database
.empty(); }
1143 void clear() { database
.clear(); parents
.clear(); }
1145 const_iterator
begin() const { return database
.begin(); }
1146 const_iterator
element(int n
) const { return database
.element(n
); }
1147 const_iterator
end() const { return database
.end(); }
1150 } /* namespace hashlib */