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 const 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 template<typename
... Args
>
875 std::pair
<iterator
, bool> emplace(Args
&&... args
)
877 return insert(K(std::forward
<Args
>(args
)...));
880 int erase(const K
&key
)
882 int hash
= do_hash(key
);
883 int index
= do_lookup(key
, hash
);
884 return do_erase(index
, hash
);
887 iterator
erase(iterator it
)
889 int hash
= do_hash(*it
);
890 do_erase(it
.index
, hash
);
894 int count(const K
&key
) const
896 int hash
= do_hash(key
);
897 int i
= do_lookup(key
, hash
);
898 return i
< 0 ? 0 : 1;
901 int count(const K
&key
, const_iterator it
) const
903 int hash
= do_hash(key
);
904 int i
= do_lookup(key
, hash
);
905 return i
< 0 || i
> it
.index
? 0 : 1;
908 iterator
find(const K
&key
)
910 int hash
= do_hash(key
);
911 int i
= do_lookup(key
, hash
);
914 return iterator(this, i
);
917 const_iterator
find(const K
&key
) const
919 int hash
= do_hash(key
);
920 int i
= do_lookup(key
, hash
);
923 return const_iterator(this, i
);
926 bool operator[](const K
&key
)
928 int hash
= do_hash(key
);
929 int i
= do_lookup(key
, hash
);
933 template<typename Compare
= std::less
<K
>>
934 void sort(Compare comp
= Compare())
936 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
942 iterator it
= begin();
948 void swap(pool
&other
)
950 hashtable
.swap(other
.hashtable
);
951 entries
.swap(other
.entries
);
954 bool operator==(const pool
&other
) const {
955 if (size() != other
.size())
957 for (auto &it
: entries
)
958 if (!other
.count(it
.udata
))
963 bool operator!=(const pool
&other
) const {
964 return !operator==(other
);
968 unsigned int hashval
= mkhash_init
;
969 for (auto &it
: entries
)
970 hashval
^= ops
.hash(it
.udata
);
974 void reserve(size_t n
) { entries
.reserve(n
); }
975 size_t size() const { return entries
.size(); }
976 bool empty() const { return entries
.empty(); }
977 void clear() { hashtable
.clear(); entries
.clear(); }
979 iterator
begin() { return iterator(this, int(entries
.size())-1); }
980 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
981 iterator
end() { return iterator(nullptr, -1); }
983 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
984 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
985 const_iterator
end() const { return const_iterator(nullptr, -1); }
988 template<typename K
, int offset
, typename OPS
>
991 pool
<K
, OPS
> database
;
994 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
998 const idict
&container
;
1000 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
1002 const_iterator() { }
1003 const_iterator
operator++() { index
++; return *this; }
1004 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
1005 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
1006 const K
&operator*() const { return container
[index
]; }
1007 const K
*operator->() const { return &container
[index
]; }
1010 int operator()(const K
&key
)
1012 int hash
= database
.do_hash(key
);
1013 int i
= database
.do_lookup(key
, hash
);
1015 i
= database
.do_insert(key
, hash
);
1019 int at(const K
&key
) const
1021 int hash
= database
.do_hash(key
);
1022 int i
= database
.do_lookup(key
, hash
);
1024 throw std::out_of_range("idict::at()");
1028 int at(const K
&key
, int defval
) const
1030 int hash
= database
.do_hash(key
);
1031 int i
= database
.do_lookup(key
, hash
);
1037 int count(const K
&key
) const
1039 int hash
= database
.do_hash(key
);
1040 int i
= database
.do_lookup(key
, hash
);
1041 return i
< 0 ? 0 : 1;
1044 void expect(const K
&key
, int i
)
1046 int j
= (*this)(key
);
1048 throw std::out_of_range("idict::expect()");
1051 const K
&operator[](int index
) const
1053 return database
.entries
.at(index
- offset
).udata
;
1056 void swap(idict
&other
)
1058 database
.swap(other
.database
);
1061 void reserve(size_t n
) { database
.reserve(n
); }
1062 size_t size() const { return database
.size(); }
1063 bool empty() const { return database
.empty(); }
1064 void clear() { database
.clear(); }
1066 const_iterator
begin() const { return const_iterator(*this, offset
); }
1067 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1068 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1071 template<typename K
, typename OPS
>
1074 mutable idict
<K
, 0, OPS
> database
;
1075 mutable std::vector
<int> parents
;
1078 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1080 int operator()(const K
&key
) const
1082 int i
= database(key
);
1083 parents
.resize(database
.size(), -1);
1087 const K
&operator[](int index
) const
1089 return database
[index
];
1092 int ifind(int i
) const
1096 while (parents
[p
] != -1)
1100 int next_k
= parents
[k
];
1108 void imerge(int i
, int j
)
1117 void ipromote(int i
)
1122 int next_k
= parents
[k
];
1130 int lookup(const K
&a
) const
1132 return ifind((*this)(a
));
1135 const K
&find(const K
&a
) const
1137 int i
= database
.at(a
, -1);
1140 return (*this)[ifind(i
)];
1143 void merge(const K
&a
, const K
&b
)
1145 imerge((*this)(a
), (*this)(b
));
1148 void promote(const K
&a
)
1150 int i
= database
.at(a
, -1);
1155 void swap(mfp
&other
)
1157 database
.swap(other
.database
);
1158 parents
.swap(other
.parents
);
1161 void reserve(size_t n
) { database
.reserve(n
); }
1162 size_t size() const { return database
.size(); }
1163 bool empty() const { return database
.empty(); }
1164 void clear() { database
.clear(); parents
.clear(); }
1166 const_iterator
begin() const { return database
.begin(); }
1167 const_iterator
element(int n
) const { return database
.element(n
); }
1168 const_iterator
end() const { return database
.end(); }
1171 } /* namespace hashlib */