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
) { }
645 entry_t(K
&&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
648 std::vector
<int> hashtable
;
649 std::vector
<entry_t
> entries
;
653 static inline void do_assert(bool) { }
655 static inline void do_assert(bool cond
) {
656 if (!cond
) throw std::runtime_error("pool<> assert failed.");
660 int do_hash(const K
&key
) const
662 unsigned int hash
= 0;
663 if (!hashtable
.empty())
664 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
671 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
673 for (int i
= 0; i
< int(entries
.size()); i
++) {
674 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
675 int hash
= do_hash(entries
[i
].udata
);
676 entries
[i
].next
= hashtable
[hash
];
681 int do_erase(int index
, int hash
)
683 do_assert(index
< int(entries
.size()));
684 if (hashtable
.empty() || index
< 0)
687 int k
= hashtable
[hash
];
689 hashtable
[hash
] = entries
[index
].next
;
691 while (entries
[k
].next
!= index
) {
693 do_assert(0 <= k
&& k
< int(entries
.size()));
695 entries
[k
].next
= entries
[index
].next
;
698 int back_idx
= entries
.size()-1;
700 if (index
!= back_idx
)
702 int back_hash
= do_hash(entries
[back_idx
].udata
);
704 k
= hashtable
[back_hash
];
706 hashtable
[back_hash
] = index
;
708 while (entries
[k
].next
!= back_idx
) {
710 do_assert(0 <= k
&& k
< int(entries
.size()));
712 entries
[k
].next
= index
;
715 entries
[index
] = std::move(entries
[back_idx
]);
726 int do_lookup(const K
&key
, int &hash
) const
728 if (hashtable
.empty())
731 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
732 ((pool
*)this)->do_rehash();
736 int index
= hashtable
[hash
];
738 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
739 index
= entries
[index
].next
;
740 do_assert(-1 <= index
&& index
< int(entries
.size()));
746 int do_insert(const K
&value
, int &hash
)
748 if (hashtable
.empty()) {
749 entries
.emplace_back(value
, -1);
751 hash
= do_hash(value
);
753 entries
.emplace_back(value
, hashtable
[hash
]);
754 hashtable
[hash
] = entries
.size() - 1;
756 return entries
.size() - 1;
759 int do_insert(K
&&rvalue
, int &hash
)
761 if (hashtable
.empty()) {
762 entries
.emplace_back(std::forward
<K
>(rvalue
), -1);
764 hash
= do_hash(rvalue
);
766 entries
.emplace_back(std::forward
<K
>(rvalue
), hashtable
[hash
]);
767 hashtable
[hash
] = entries
.size() - 1;
769 return entries
.size() - 1;
773 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
779 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
782 const_iterator
operator++() { index
--; return *this; }
783 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
784 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
785 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
786 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
789 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
795 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
798 iterator
operator++() { index
--; return *this; }
799 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
800 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
801 K
&operator*() { return ptr
->entries
[index
].udata
; }
802 K
*operator->() { return &ptr
->entries
[index
].udata
; }
803 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
804 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
805 operator const_iterator() const { return const_iterator(ptr
, index
); }
812 pool(const pool
&other
)
814 entries
= other
.entries
;
823 pool
&operator=(const pool
&other
) {
824 entries
= other
.entries
;
829 pool
&operator=(pool
&&other
) {
835 pool(const std::initializer_list
<K
> &list
)
837 for (auto &it
: list
)
841 template<class InputIterator
>
842 pool(InputIterator first
, InputIterator last
)
847 template<class InputIterator
>
848 void insert(InputIterator first
, InputIterator last
)
850 for (; first
!= last
; ++first
)
854 std::pair
<iterator
, bool> insert(const K
&value
)
856 int hash
= do_hash(value
);
857 int i
= do_lookup(value
, hash
);
859 return std::pair
<iterator
, bool>(iterator(this, i
), false);
860 i
= do_insert(value
, hash
);
861 return std::pair
<iterator
, bool>(iterator(this, i
), true);
864 std::pair
<iterator
, bool> insert(K
&&rvalue
)
866 int hash
= do_hash(rvalue
);
867 int i
= do_lookup(rvalue
, hash
);
869 return std::pair
<iterator
, bool>(iterator(this, i
), false);
870 i
= do_insert(std::forward
<K
>(rvalue
), hash
);
871 return std::pair
<iterator
, bool>(iterator(this, i
), true);
874 int erase(const K
&key
)
876 int hash
= do_hash(key
);
877 int index
= do_lookup(key
, hash
);
878 return do_erase(index
, hash
);
881 iterator
erase(iterator it
)
883 int hash
= do_hash(*it
);
884 do_erase(it
.index
, hash
);
888 int count(const K
&key
) const
890 int hash
= do_hash(key
);
891 int i
= do_lookup(key
, hash
);
892 return i
< 0 ? 0 : 1;
895 int count(const K
&key
, const_iterator it
) const
897 int hash
= do_hash(key
);
898 int i
= do_lookup(key
, hash
);
899 return i
< 0 || i
> it
.index
? 0 : 1;
902 iterator
find(const K
&key
)
904 int hash
= do_hash(key
);
905 int i
= do_lookup(key
, hash
);
908 return iterator(this, i
);
911 const_iterator
find(const K
&key
) const
913 int hash
= do_hash(key
);
914 int i
= do_lookup(key
, hash
);
917 return const_iterator(this, i
);
920 bool operator[](const K
&key
)
922 int hash
= do_hash(key
);
923 int i
= do_lookup(key
, hash
);
927 template<typename Compare
= std::less
<K
>>
928 void sort(Compare comp
= Compare())
930 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
936 iterator it
= begin();
942 void swap(pool
&other
)
944 hashtable
.swap(other
.hashtable
);
945 entries
.swap(other
.entries
);
948 bool operator==(const pool
&other
) const {
949 if (size() != other
.size())
951 for (auto &it
: entries
)
952 if (!other
.count(it
.udata
))
957 bool operator!=(const pool
&other
) const {
958 return !operator==(other
);
962 unsigned int hashval
= mkhash_init
;
963 for (auto &it
: entries
)
964 hashval
^= ops
.hash(it
.udata
);
968 void reserve(size_t n
) { entries
.reserve(n
); }
969 size_t size() const { return entries
.size(); }
970 bool empty() const { return entries
.empty(); }
971 void clear() { hashtable
.clear(); entries
.clear(); }
973 iterator
begin() { return iterator(this, int(entries
.size())-1); }
974 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
975 iterator
end() { return iterator(nullptr, -1); }
977 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
978 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
979 const_iterator
end() const { return const_iterator(nullptr, -1); }
982 template<typename K
, int offset
, typename OPS
>
985 pool
<K
, OPS
> database
;
988 typedef typename pool
<K
, OPS
>::const_iterator const_iterator
;
990 int operator()(const K
&key
)
992 int hash
= database
.do_hash(key
);
993 int i
= database
.do_lookup(key
, hash
);
995 i
= database
.do_insert(key
, hash
);
999 int at(const K
&key
) const
1001 int hash
= database
.do_hash(key
);
1002 int i
= database
.do_lookup(key
, hash
);
1004 throw std::out_of_range("idict::at()");
1008 int at(const K
&key
, int defval
) const
1010 int hash
= database
.do_hash(key
);
1011 int i
= database
.do_lookup(key
, hash
);
1017 int count(const K
&key
) const
1019 int hash
= database
.do_hash(key
);
1020 int i
= database
.do_lookup(key
, hash
);
1021 return i
< 0 ? 0 : 1;
1024 void expect(const K
&key
, int i
)
1026 int j
= (*this)(key
);
1028 throw std::out_of_range("idict::expect()");
1031 const K
&operator[](int index
) const
1033 return database
.entries
.at(index
- offset
).udata
;
1036 void swap(idict
&other
)
1038 database
.swap(other
.database
);
1041 void reserve(size_t n
) { database
.reserve(n
); }
1042 size_t size() const { return database
.size(); }
1043 bool empty() const { return database
.empty(); }
1044 void clear() { database
.clear(); }
1046 const_iterator
begin() const { return database
.begin(); }
1047 const_iterator
element(int n
) const { return database
.element(n
); }
1048 const_iterator
end() const { return database
.end(); }
1051 template<typename K
, typename OPS
>
1054 mutable idict
<K
, 0, OPS
> database
;
1055 mutable std::vector
<int> parents
;
1058 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1060 int operator()(const K
&key
) const
1062 int i
= database(key
);
1063 parents
.resize(database
.size(), -1);
1067 const K
&operator[](int index
) const
1069 return database
[index
];
1072 int ifind(int i
) const
1076 while (parents
[p
] != -1)
1080 int next_k
= parents
[k
];
1088 void imerge(int i
, int j
)
1097 void ipromote(int i
)
1102 int next_k
= parents
[k
];
1110 int lookup(const K
&a
) const
1112 return ifind((*this)(a
));
1115 const K
&find(const K
&a
) const
1117 int i
= database
.at(a
, -1);
1120 return (*this)[ifind(i
)];
1123 void merge(const K
&a
, const K
&b
)
1125 imerge((*this)(a
), (*this)(b
));
1128 void promote(const K
&a
)
1130 int i
= database
.at(a
, -1);
1135 void swap(mfp
&other
)
1137 database
.swap(other
.database
);
1138 parents
.swap(other
.parents
);
1141 void reserve(size_t n
) { database
.reserve(n
); }
1142 size_t size() const { return database
.size(); }
1143 bool empty() const { return database
.empty(); }
1144 void clear() { database
.clear(); parents
.clear(); }
1146 const_iterator
begin() const { return database
.begin(); }
1147 const_iterator
element(int n
) const { return database
.element(n
); }
1148 const_iterator
end() const { return database
.end(); }
1151 } /* namespace hashlib */