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 unsigned int hash() const {
619 unsigned int h
= mkhash_init
;
620 for (auto &it
: entries
) {
621 h
= mkhash(h
, hash_ops
<K
>::hash(it
.udata
.first
));
622 h
= mkhash(h
, hash_ops
<T
>::hash(it
.udata
.second
));
627 void reserve(size_t n
) { entries
.reserve(n
); }
628 size_t size() const { return entries
.size(); }
629 bool empty() const { return entries
.empty(); }
630 void clear() { hashtable
.clear(); entries
.clear(); }
632 iterator
begin() { return iterator(this, int(entries
.size())-1); }
633 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
634 iterator
end() { return iterator(nullptr, -1); }
636 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
637 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
638 const_iterator
end() const { return const_iterator(nullptr, -1); }
641 template<typename K
, typename OPS
>
644 template<typename
, int, typename
> friend class idict
;
653 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
654 entry_t(K
&&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
657 std::vector
<int> hashtable
;
658 std::vector
<entry_t
> entries
;
662 static inline void do_assert(bool) { }
664 static inline void do_assert(bool cond
) {
665 if (!cond
) throw std::runtime_error("pool<> assert failed.");
669 int do_hash(const K
&key
) const
671 unsigned int hash
= 0;
672 if (!hashtable
.empty())
673 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
680 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
682 for (int i
= 0; i
< int(entries
.size()); i
++) {
683 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
684 int hash
= do_hash(entries
[i
].udata
);
685 entries
[i
].next
= hashtable
[hash
];
690 int do_erase(int index
, int hash
)
692 do_assert(index
< int(entries
.size()));
693 if (hashtable
.empty() || index
< 0)
696 int k
= hashtable
[hash
];
698 hashtable
[hash
] = entries
[index
].next
;
700 while (entries
[k
].next
!= index
) {
702 do_assert(0 <= k
&& k
< int(entries
.size()));
704 entries
[k
].next
= entries
[index
].next
;
707 int back_idx
= entries
.size()-1;
709 if (index
!= back_idx
)
711 int back_hash
= do_hash(entries
[back_idx
].udata
);
713 k
= hashtable
[back_hash
];
715 hashtable
[back_hash
] = index
;
717 while (entries
[k
].next
!= back_idx
) {
719 do_assert(0 <= k
&& k
< int(entries
.size()));
721 entries
[k
].next
= index
;
724 entries
[index
] = std::move(entries
[back_idx
]);
735 int do_lookup(const K
&key
, int &hash
) const
737 if (hashtable
.empty())
740 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
741 ((pool
*)this)->do_rehash();
745 int index
= hashtable
[hash
];
747 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
748 index
= entries
[index
].next
;
749 do_assert(-1 <= index
&& index
< int(entries
.size()));
755 int do_insert(const K
&value
, int &hash
)
757 if (hashtable
.empty()) {
758 entries
.emplace_back(value
, -1);
760 hash
= do_hash(value
);
762 entries
.emplace_back(value
, hashtable
[hash
]);
763 hashtable
[hash
] = entries
.size() - 1;
765 return entries
.size() - 1;
768 int do_insert(K
&&rvalue
, int &hash
)
770 if (hashtable
.empty()) {
771 entries
.emplace_back(std::forward
<K
>(rvalue
), -1);
773 hash
= do_hash(rvalue
);
775 entries
.emplace_back(std::forward
<K
>(rvalue
), hashtable
[hash
]);
776 hashtable
[hash
] = entries
.size() - 1;
778 return entries
.size() - 1;
782 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
788 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
791 const_iterator
operator++() { index
--; return *this; }
792 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
793 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
794 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
795 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
798 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
804 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
807 iterator
operator++() { index
--; return *this; }
808 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
809 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
810 K
&operator*() { return ptr
->entries
[index
].udata
; }
811 K
*operator->() { return &ptr
->entries
[index
].udata
; }
812 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
813 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
814 operator const_iterator() const { return const_iterator(ptr
, index
); }
821 pool(const pool
&other
)
823 entries
= other
.entries
;
832 pool
&operator=(const pool
&other
) {
833 entries
= other
.entries
;
838 pool
&operator=(pool
&&other
) {
844 pool(const std::initializer_list
<K
> &list
)
846 for (auto &it
: list
)
850 template<class InputIterator
>
851 pool(InputIterator first
, InputIterator last
)
856 template<class InputIterator
>
857 void insert(InputIterator first
, InputIterator last
)
859 for (; first
!= last
; ++first
)
863 std::pair
<iterator
, bool> insert(const 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(value
, hash
);
870 return std::pair
<iterator
, bool>(iterator(this, i
), true);
873 std::pair
<iterator
, bool> insert(K
&&rvalue
)
875 int hash
= do_hash(rvalue
);
876 int i
= do_lookup(rvalue
, hash
);
878 return std::pair
<iterator
, bool>(iterator(this, i
), false);
879 i
= do_insert(std::forward
<K
>(rvalue
), hash
);
880 return std::pair
<iterator
, bool>(iterator(this, i
), true);
883 template<typename
... Args
>
884 std::pair
<iterator
, bool> emplace(Args
&&... args
)
886 return insert(K(std::forward
<Args
>(args
)...));
889 int erase(const K
&key
)
891 int hash
= do_hash(key
);
892 int index
= do_lookup(key
, hash
);
893 return do_erase(index
, hash
);
896 iterator
erase(iterator it
)
898 int hash
= do_hash(*it
);
899 do_erase(it
.index
, hash
);
903 int count(const K
&key
) const
905 int hash
= do_hash(key
);
906 int i
= do_lookup(key
, hash
);
907 return i
< 0 ? 0 : 1;
910 int count(const K
&key
, const_iterator it
) const
912 int hash
= do_hash(key
);
913 int i
= do_lookup(key
, hash
);
914 return i
< 0 || i
> it
.index
? 0 : 1;
917 iterator
find(const K
&key
)
919 int hash
= do_hash(key
);
920 int i
= do_lookup(key
, hash
);
923 return iterator(this, i
);
926 const_iterator
find(const K
&key
) const
928 int hash
= do_hash(key
);
929 int i
= do_lookup(key
, hash
);
932 return const_iterator(this, i
);
935 bool operator[](const K
&key
)
937 int hash
= do_hash(key
);
938 int i
= do_lookup(key
, hash
);
942 template<typename Compare
= std::less
<K
>>
943 void sort(Compare comp
= Compare())
945 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
951 iterator it
= begin();
957 void swap(pool
&other
)
959 hashtable
.swap(other
.hashtable
);
960 entries
.swap(other
.entries
);
963 bool operator==(const pool
&other
) const {
964 if (size() != other
.size())
966 for (auto &it
: entries
)
967 if (!other
.count(it
.udata
))
972 bool operator!=(const pool
&other
) const {
973 return !operator==(other
);
977 unsigned int hashval
= mkhash_init
;
978 for (auto &it
: entries
)
979 hashval
^= ops
.hash(it
.udata
);
983 void reserve(size_t n
) { entries
.reserve(n
); }
984 size_t size() const { return entries
.size(); }
985 bool empty() const { return entries
.empty(); }
986 void clear() { hashtable
.clear(); entries
.clear(); }
988 iterator
begin() { return iterator(this, int(entries
.size())-1); }
989 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
990 iterator
end() { return iterator(nullptr, -1); }
992 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
993 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
994 const_iterator
end() const { return const_iterator(nullptr, -1); }
997 template<typename K
, int offset
, typename OPS
>
1000 pool
<K
, OPS
> database
;
1003 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
1007 const idict
&container
;
1009 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
1011 const_iterator() { }
1012 const_iterator
operator++() { index
++; return *this; }
1013 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
1014 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
1015 const K
&operator*() const { return container
[index
]; }
1016 const K
*operator->() const { return &container
[index
]; }
1019 int operator()(const K
&key
)
1021 int hash
= database
.do_hash(key
);
1022 int i
= database
.do_lookup(key
, hash
);
1024 i
= database
.do_insert(key
, hash
);
1028 int at(const K
&key
) const
1030 int hash
= database
.do_hash(key
);
1031 int i
= database
.do_lookup(key
, hash
);
1033 throw std::out_of_range("idict::at()");
1037 int at(const K
&key
, int defval
) const
1039 int hash
= database
.do_hash(key
);
1040 int i
= database
.do_lookup(key
, hash
);
1046 int count(const K
&key
) const
1048 int hash
= database
.do_hash(key
);
1049 int i
= database
.do_lookup(key
, hash
);
1050 return i
< 0 ? 0 : 1;
1053 void expect(const K
&key
, int i
)
1055 int j
= (*this)(key
);
1057 throw std::out_of_range("idict::expect()");
1060 const K
&operator[](int index
) const
1062 return database
.entries
.at(index
- offset
).udata
;
1065 void swap(idict
&other
)
1067 database
.swap(other
.database
);
1070 void reserve(size_t n
) { database
.reserve(n
); }
1071 size_t size() const { return database
.size(); }
1072 bool empty() const { return database
.empty(); }
1073 void clear() { database
.clear(); }
1075 const_iterator
begin() const { return const_iterator(*this, offset
); }
1076 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1077 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1080 template<typename K
, typename OPS
>
1083 mutable idict
<K
, 0, OPS
> database
;
1084 mutable std::vector
<int> parents
;
1087 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1089 int operator()(const K
&key
) const
1091 int i
= database(key
);
1092 parents
.resize(database
.size(), -1);
1096 const K
&operator[](int index
) const
1098 return database
[index
];
1101 int ifind(int i
) const
1105 while (parents
[p
] != -1)
1109 int next_k
= parents
[k
];
1117 void imerge(int i
, int j
)
1126 void ipromote(int i
)
1131 int next_k
= parents
[k
];
1139 int lookup(const K
&a
) const
1141 return ifind((*this)(a
));
1144 const K
&find(const K
&a
) const
1146 int i
= database
.at(a
, -1);
1149 return (*this)[ifind(i
)];
1152 void merge(const K
&a
, const K
&b
)
1154 imerge((*this)(a
), (*this)(b
));
1157 void promote(const K
&a
)
1159 int i
= database
.at(a
, -1);
1164 void swap(mfp
&other
)
1166 database
.swap(other
.database
);
1167 parents
.swap(other
.parents
);
1170 void reserve(size_t n
) { database
.reserve(n
); }
1171 size_t size() const { return database
.size(); }
1172 bool empty() const { return database
.empty(); }
1173 void clear() { database
.clear(); parents
.clear(); }
1175 const_iterator
begin() const { return database
.begin(); }
1176 const_iterator
element(int n
) const { return database
.element(n
); }
1177 const_iterator
end() const { return database
.end(); }
1180 } /* namespace hashlib */