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
) { }
210 bool operator<(const entry_t
&other
) const { return udata
.first
< other
.udata
.first
; }
213 std::vector
<int> hashtable
;
214 std::vector
<entry_t
> entries
;
218 static inline void do_assert(bool) { }
220 static inline void do_assert(bool cond
) {
221 if (!cond
) throw std::runtime_error("dict<> assert failed.");
225 int do_hash(const K
&key
) const
227 unsigned int hash
= 0;
228 if (!hashtable
.empty())
229 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
236 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
238 for (int i
= 0; i
< int(entries
.size()); i
++) {
239 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
240 int hash
= do_hash(entries
[i
].udata
.first
);
241 entries
[i
].next
= hashtable
[hash
];
246 int do_erase(int index
, int hash
)
248 do_assert(index
< int(entries
.size()));
249 if (hashtable
.empty() || index
< 0)
252 int k
= hashtable
[hash
];
253 do_assert(0 <= k
&& k
< int(entries
.size()));
256 hashtable
[hash
] = entries
[index
].next
;
258 while (entries
[k
].next
!= index
) {
260 do_assert(0 <= k
&& k
< int(entries
.size()));
262 entries
[k
].next
= entries
[index
].next
;
265 int back_idx
= entries
.size()-1;
267 if (index
!= back_idx
)
269 int back_hash
= do_hash(entries
[back_idx
].udata
.first
);
271 k
= hashtable
[back_hash
];
272 do_assert(0 <= k
&& k
< int(entries
.size()));
275 hashtable
[back_hash
] = index
;
277 while (entries
[k
].next
!= back_idx
) {
279 do_assert(0 <= k
&& k
< int(entries
.size()));
281 entries
[k
].next
= index
;
284 entries
[index
] = std::move(entries
[back_idx
]);
295 int do_lookup(const K
&key
, int &hash
) const
297 if (hashtable
.empty())
300 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
301 ((dict
*)this)->do_rehash();
305 int index
= hashtable
[hash
];
307 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
.first
, key
)) {
308 index
= entries
[index
].next
;
309 do_assert(-1 <= index
&& index
< int(entries
.size()));
315 int do_insert(const K
&key
, int &hash
)
317 if (hashtable
.empty()) {
318 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), -1);
322 entries
.emplace_back(std::pair
<K
, T
>(key
, T()), hashtable
[hash
]);
323 hashtable
[hash
] = entries
.size() - 1;
325 return entries
.size() - 1;
328 int do_insert(const std::pair
<K
, T
> &value
, int &hash
)
330 if (hashtable
.empty()) {
331 entries
.emplace_back(value
, -1);
333 hash
= do_hash(value
.first
);
335 entries
.emplace_back(value
, hashtable
[hash
]);
336 hashtable
[hash
] = entries
.size() - 1;
338 return entries
.size() - 1;
341 int do_insert(std::pair
<K
, T
> &&rvalue
, int &hash
)
343 if (hashtable
.empty()) {
344 auto key
= rvalue
.first
;
345 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), -1);
349 entries
.emplace_back(std::forward
<std::pair
<K
, T
>>(rvalue
), hashtable
[hash
]);
350 hashtable
[hash
] = entries
.size() - 1;
352 return entries
.size() - 1;
356 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
362 const_iterator(const dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
365 const_iterator
operator++() { index
--; return *this; }
366 const_iterator
operator+=(int amt
) { index
-= amt
; return *this; }
367 bool operator<(const const_iterator
&other
) const { return index
> other
.index
; }
368 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
369 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
370 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
371 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
374 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
380 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
383 iterator
operator++() { index
--; return *this; }
384 iterator
operator+=(int amt
) { index
-= amt
; return *this; }
385 bool operator<(const iterator
&other
) const { return index
> other
.index
; }
386 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
387 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
388 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
389 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
390 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
391 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
392 operator const_iterator() const { return const_iterator(ptr
, index
); }
399 dict(const dict
&other
)
401 entries
= other
.entries
;
410 dict
&operator=(const dict
&other
) {
411 entries
= other
.entries
;
416 dict
&operator=(dict
&&other
) {
422 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
424 for (auto &it
: list
)
428 template<class InputIterator
>
429 dict(InputIterator first
, InputIterator last
)
434 template<class InputIterator
>
435 void insert(InputIterator first
, InputIterator last
)
437 for (; first
!= last
; ++first
)
441 std::pair
<iterator
, bool> insert(const K
&key
)
443 int hash
= do_hash(key
);
444 int i
= do_lookup(key
, hash
);
446 return std::pair
<iterator
, bool>(iterator(this, i
), false);
447 i
= do_insert(key
, hash
);
448 return std::pair
<iterator
, bool>(iterator(this, i
), true);
451 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
453 int hash
= do_hash(value
.first
);
454 int i
= do_lookup(value
.first
, hash
);
456 return std::pair
<iterator
, bool>(iterator(this, i
), false);
457 i
= do_insert(value
, hash
);
458 return std::pair
<iterator
, bool>(iterator(this, i
), true);
461 std::pair
<iterator
, bool> insert(std::pair
<K
, T
> &&rvalue
)
463 int hash
= do_hash(rvalue
.first
);
464 int i
= do_lookup(rvalue
.first
, hash
);
466 return std::pair
<iterator
, bool>(iterator(this, i
), false);
467 i
= do_insert(std::forward
<std::pair
<K
, T
>>(rvalue
), hash
);
468 return std::pair
<iterator
, bool>(iterator(this, i
), true);
471 std::pair
<iterator
, bool> emplace(K
const &key
, T
const &value
)
473 int hash
= do_hash(key
);
474 int i
= do_lookup(key
, hash
);
476 return std::pair
<iterator
, bool>(iterator(this, i
), false);
477 i
= do_insert(std::make_pair(key
, value
), hash
);
478 return std::pair
<iterator
, bool>(iterator(this, i
), true);
481 std::pair
<iterator
, bool> emplace(K
const &key
, T
&&rvalue
)
483 int hash
= do_hash(key
);
484 int i
= do_lookup(key
, hash
);
486 return std::pair
<iterator
, bool>(iterator(this, i
), false);
487 i
= do_insert(std::make_pair(key
, std::forward
<T
>(rvalue
)), hash
);
488 return std::pair
<iterator
, bool>(iterator(this, i
), true);
491 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
const &value
)
493 int hash
= do_hash(rkey
);
494 int i
= do_lookup(rkey
, hash
);
496 return std::pair
<iterator
, bool>(iterator(this, i
), false);
497 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), value
), hash
);
498 return std::pair
<iterator
, bool>(iterator(this, i
), true);
501 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
&&rvalue
)
503 int hash
= do_hash(rkey
);
504 int i
= do_lookup(rkey
, hash
);
506 return std::pair
<iterator
, bool>(iterator(this, i
), false);
507 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), std::forward
<T
>(rvalue
)), hash
);
508 return std::pair
<iterator
, bool>(iterator(this, i
), true);
511 int erase(const K
&key
)
513 int hash
= do_hash(key
);
514 int index
= do_lookup(key
, hash
);
515 return do_erase(index
, hash
);
518 iterator
erase(iterator it
)
520 int hash
= do_hash(it
->first
);
521 do_erase(it
.index
, hash
);
525 int count(const K
&key
) const
527 int hash
= do_hash(key
);
528 int i
= do_lookup(key
, hash
);
529 return i
< 0 ? 0 : 1;
532 int count(const K
&key
, const_iterator it
) const
534 int hash
= do_hash(key
);
535 int i
= do_lookup(key
, hash
);
536 return i
< 0 || i
> it
.index
? 0 : 1;
539 iterator
find(const K
&key
)
541 int hash
= do_hash(key
);
542 int i
= do_lookup(key
, hash
);
545 return iterator(this, i
);
548 const_iterator
find(const K
&key
) const
550 int hash
= do_hash(key
);
551 int i
= do_lookup(key
, hash
);
554 return const_iterator(this, i
);
559 int hash
= do_hash(key
);
560 int i
= do_lookup(key
, hash
);
562 throw std::out_of_range("dict::at()");
563 return entries
[i
].udata
.second
;
566 const T
& at(const K
&key
) const
568 int hash
= do_hash(key
);
569 int i
= do_lookup(key
, hash
);
571 throw std::out_of_range("dict::at()");
572 return entries
[i
].udata
.second
;
575 const T
& at(const K
&key
, const T
&defval
) const
577 int hash
= do_hash(key
);
578 int i
= do_lookup(key
, hash
);
581 return entries
[i
].udata
.second
;
584 T
& operator[](const K
&key
)
586 int hash
= do_hash(key
);
587 int i
= do_lookup(key
, hash
);
589 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
590 return entries
[i
].udata
.second
;
593 template<typename Compare
= std::less
<K
>>
594 void sort(Compare comp
= Compare())
596 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
600 void swap(dict
&other
)
602 hashtable
.swap(other
.hashtable
);
603 entries
.swap(other
.entries
);
606 bool operator==(const dict
&other
) const {
607 if (size() != other
.size())
609 for (auto &it
: entries
) {
610 auto oit
= other
.find(it
.udata
.first
);
611 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
617 bool operator!=(const dict
&other
) const {
618 return !operator==(other
);
621 unsigned int hash() const {
622 unsigned int h
= mkhash_init
;
623 for (auto &entry
: entries
) {
624 h
^= hash_ops
<K
>::hash(entry
.udata
.first
);
625 h
^= hash_ops
<T
>::hash(entry
.udata
.second
);
630 void reserve(size_t n
) { entries
.reserve(n
); }
631 size_t size() const { return entries
.size(); }
632 bool empty() const { return entries
.empty(); }
633 void clear() { hashtable
.clear(); entries
.clear(); }
635 iterator
begin() { return iterator(this, int(entries
.size())-1); }
636 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
637 iterator
end() { return iterator(nullptr, -1); }
639 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
640 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
641 const_iterator
end() const { return const_iterator(nullptr, -1); }
644 template<typename K
, typename OPS
>
647 template<typename
, int, typename
> friend class idict
;
656 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
657 entry_t(K
&&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
660 std::vector
<int> hashtable
;
661 std::vector
<entry_t
> entries
;
665 static inline void do_assert(bool) { }
667 static inline void do_assert(bool cond
) {
668 if (!cond
) throw std::runtime_error("pool<> assert failed.");
672 int do_hash(const K
&key
) const
674 unsigned int hash
= 0;
675 if (!hashtable
.empty())
676 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
683 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
685 for (int i
= 0; i
< int(entries
.size()); i
++) {
686 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
687 int hash
= do_hash(entries
[i
].udata
);
688 entries
[i
].next
= hashtable
[hash
];
693 int do_erase(int index
, int hash
)
695 do_assert(index
< int(entries
.size()));
696 if (hashtable
.empty() || index
< 0)
699 int k
= hashtable
[hash
];
701 hashtable
[hash
] = entries
[index
].next
;
703 while (entries
[k
].next
!= index
) {
705 do_assert(0 <= k
&& k
< int(entries
.size()));
707 entries
[k
].next
= entries
[index
].next
;
710 int back_idx
= entries
.size()-1;
712 if (index
!= back_idx
)
714 int back_hash
= do_hash(entries
[back_idx
].udata
);
716 k
= hashtable
[back_hash
];
718 hashtable
[back_hash
] = index
;
720 while (entries
[k
].next
!= back_idx
) {
722 do_assert(0 <= k
&& k
< int(entries
.size()));
724 entries
[k
].next
= index
;
727 entries
[index
] = std::move(entries
[back_idx
]);
738 int do_lookup(const K
&key
, int &hash
) const
740 if (hashtable
.empty())
743 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
744 ((pool
*)this)->do_rehash();
748 int index
= hashtable
[hash
];
750 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
751 index
= entries
[index
].next
;
752 do_assert(-1 <= index
&& index
< int(entries
.size()));
758 int do_insert(const K
&value
, int &hash
)
760 if (hashtable
.empty()) {
761 entries
.emplace_back(value
, -1);
763 hash
= do_hash(value
);
765 entries
.emplace_back(value
, hashtable
[hash
]);
766 hashtable
[hash
] = entries
.size() - 1;
768 return entries
.size() - 1;
771 int do_insert(K
&&rvalue
, int &hash
)
773 if (hashtable
.empty()) {
774 entries
.emplace_back(std::forward
<K
>(rvalue
), -1);
776 hash
= do_hash(rvalue
);
778 entries
.emplace_back(std::forward
<K
>(rvalue
), hashtable
[hash
]);
779 hashtable
[hash
] = entries
.size() - 1;
781 return entries
.size() - 1;
785 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
791 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
794 const_iterator
operator++() { index
--; return *this; }
795 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
796 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
797 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
798 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
801 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
807 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
810 iterator
operator++() { index
--; return *this; }
811 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
812 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
813 K
&operator*() { return ptr
->entries
[index
].udata
; }
814 K
*operator->() { return &ptr
->entries
[index
].udata
; }
815 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
816 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
817 operator const_iterator() const { return const_iterator(ptr
, index
); }
824 pool(const pool
&other
)
826 entries
= other
.entries
;
835 pool
&operator=(const pool
&other
) {
836 entries
= other
.entries
;
841 pool
&operator=(pool
&&other
) {
847 pool(const std::initializer_list
<K
> &list
)
849 for (auto &it
: list
)
853 template<class InputIterator
>
854 pool(InputIterator first
, InputIterator last
)
859 template<class InputIterator
>
860 void insert(InputIterator first
, InputIterator last
)
862 for (; first
!= last
; ++first
)
866 std::pair
<iterator
, bool> insert(const K
&value
)
868 int hash
= do_hash(value
);
869 int i
= do_lookup(value
, hash
);
871 return std::pair
<iterator
, bool>(iterator(this, i
), false);
872 i
= do_insert(value
, hash
);
873 return std::pair
<iterator
, bool>(iterator(this, i
), true);
876 std::pair
<iterator
, bool> insert(K
&&rvalue
)
878 int hash
= do_hash(rvalue
);
879 int i
= do_lookup(rvalue
, hash
);
881 return std::pair
<iterator
, bool>(iterator(this, i
), false);
882 i
= do_insert(std::forward
<K
>(rvalue
), hash
);
883 return std::pair
<iterator
, bool>(iterator(this, i
), true);
886 template<typename
... Args
>
887 std::pair
<iterator
, bool> emplace(Args
&&... args
)
889 return insert(K(std::forward
<Args
>(args
)...));
892 int erase(const K
&key
)
894 int hash
= do_hash(key
);
895 int index
= do_lookup(key
, hash
);
896 return do_erase(index
, hash
);
899 iterator
erase(iterator it
)
901 int hash
= do_hash(*it
);
902 do_erase(it
.index
, hash
);
906 int count(const K
&key
) const
908 int hash
= do_hash(key
);
909 int i
= do_lookup(key
, hash
);
910 return i
< 0 ? 0 : 1;
913 int count(const K
&key
, const_iterator it
) const
915 int hash
= do_hash(key
);
916 int i
= do_lookup(key
, hash
);
917 return i
< 0 || i
> it
.index
? 0 : 1;
920 iterator
find(const K
&key
)
922 int hash
= do_hash(key
);
923 int i
= do_lookup(key
, hash
);
926 return iterator(this, i
);
929 const_iterator
find(const K
&key
) const
931 int hash
= do_hash(key
);
932 int i
= do_lookup(key
, hash
);
935 return const_iterator(this, i
);
938 bool operator[](const K
&key
)
940 int hash
= do_hash(key
);
941 int i
= do_lookup(key
, hash
);
945 template<typename Compare
= std::less
<K
>>
946 void sort(Compare comp
= Compare())
948 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
954 iterator it
= begin();
960 void swap(pool
&other
)
962 hashtable
.swap(other
.hashtable
);
963 entries
.swap(other
.entries
);
966 bool operator==(const pool
&other
) const {
967 if (size() != other
.size())
969 for (auto &it
: entries
)
970 if (!other
.count(it
.udata
))
975 bool operator!=(const pool
&other
) const {
976 return !operator==(other
);
980 unsigned int hashval
= mkhash_init
;
981 for (auto &it
: entries
)
982 hashval
^= ops
.hash(it
.udata
);
986 void reserve(size_t n
) { entries
.reserve(n
); }
987 size_t size() const { return entries
.size(); }
988 bool empty() const { return entries
.empty(); }
989 void clear() { hashtable
.clear(); entries
.clear(); }
991 iterator
begin() { return iterator(this, int(entries
.size())-1); }
992 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
993 iterator
end() { return iterator(nullptr, -1); }
995 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
996 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
997 const_iterator
end() const { return const_iterator(nullptr, -1); }
1000 template<typename K
, int offset
, typename OPS
>
1003 pool
<K
, OPS
> database
;
1006 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
1010 const idict
&container
;
1012 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
1014 const_iterator() { }
1015 const_iterator
operator++() { index
++; return *this; }
1016 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
1017 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
1018 const K
&operator*() const { return container
[index
]; }
1019 const K
*operator->() const { return &container
[index
]; }
1022 int operator()(const K
&key
)
1024 int hash
= database
.do_hash(key
);
1025 int i
= database
.do_lookup(key
, hash
);
1027 i
= database
.do_insert(key
, hash
);
1031 int at(const K
&key
) const
1033 int hash
= database
.do_hash(key
);
1034 int i
= database
.do_lookup(key
, hash
);
1036 throw std::out_of_range("idict::at()");
1040 int at(const K
&key
, int defval
) const
1042 int hash
= database
.do_hash(key
);
1043 int i
= database
.do_lookup(key
, hash
);
1049 int count(const K
&key
) const
1051 int hash
= database
.do_hash(key
);
1052 int i
= database
.do_lookup(key
, hash
);
1053 return i
< 0 ? 0 : 1;
1056 void expect(const K
&key
, int i
)
1058 int j
= (*this)(key
);
1060 throw std::out_of_range("idict::expect()");
1063 const K
&operator[](int index
) const
1065 return database
.entries
.at(index
- offset
).udata
;
1068 void swap(idict
&other
)
1070 database
.swap(other
.database
);
1073 void reserve(size_t n
) { database
.reserve(n
); }
1074 size_t size() const { return database
.size(); }
1075 bool empty() const { return database
.empty(); }
1076 void clear() { database
.clear(); }
1078 const_iterator
begin() const { return const_iterator(*this, offset
); }
1079 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1080 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1083 template<typename K
, typename OPS
>
1086 mutable idict
<K
, 0, OPS
> database
;
1087 mutable std::vector
<int> parents
;
1090 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1092 int operator()(const K
&key
) const
1094 int i
= database(key
);
1095 parents
.resize(database
.size(), -1);
1099 const K
&operator[](int index
) const
1101 return database
[index
];
1104 int ifind(int i
) const
1108 while (parents
[p
] != -1)
1112 int next_k
= parents
[k
];
1120 void imerge(int i
, int j
)
1129 void ipromote(int i
)
1134 int next_k
= parents
[k
];
1142 int lookup(const K
&a
) const
1144 return ifind((*this)(a
));
1147 const K
&find(const K
&a
) const
1149 int i
= database
.at(a
, -1);
1152 return (*this)[ifind(i
)];
1155 void merge(const K
&a
, const K
&b
)
1157 imerge((*this)(a
), (*this)(b
));
1160 void promote(const K
&a
)
1162 int i
= database
.at(a
, -1);
1167 void swap(mfp
&other
)
1169 database
.swap(other
.database
);
1170 parents
.swap(other
.parents
);
1173 void reserve(size_t n
) { database
.reserve(n
); }
1174 size_t size() const { return database
.size(); }
1175 bool empty() const { return database
.empty(); }
1176 void clear() { database
.clear(); parents
.clear(); }
1178 const_iterator
begin() const { return database
.begin(); }
1179 const_iterator
element(int n
) const { return database
.element(n
); }
1180 const_iterator
end() const { return database
.end(); }
1183 } /* namespace hashlib */