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 bool operator<(const const_iterator
&other
) const { return index
> other
.index
; }
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 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
370 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
373 class iterator
: public std::iterator
<std::forward_iterator_tag
, std::pair
<K
, T
>>
379 iterator(dict
*ptr
, int index
) : ptr(ptr
), index(index
) { }
382 iterator
operator++() { index
--; return *this; }
383 bool operator<(const iterator
&other
) const { return index
> other
.index
; }
384 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
385 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
386 std::pair
<K
, T
> &operator*() { return ptr
->entries
[index
].udata
; }
387 std::pair
<K
, T
> *operator->() { return &ptr
->entries
[index
].udata
; }
388 const std::pair
<K
, T
> &operator*() const { return ptr
->entries
[index
].udata
; }
389 const std::pair
<K
, T
> *operator->() const { return &ptr
->entries
[index
].udata
; }
390 operator const_iterator() const { return const_iterator(ptr
, index
); }
397 dict(const dict
&other
)
399 entries
= other
.entries
;
408 dict
&operator=(const dict
&other
) {
409 entries
= other
.entries
;
414 dict
&operator=(dict
&&other
) {
420 dict(const std::initializer_list
<std::pair
<K
, T
>> &list
)
422 for (auto &it
: list
)
426 template<class InputIterator
>
427 dict(InputIterator first
, InputIterator last
)
432 template<class InputIterator
>
433 void insert(InputIterator first
, InputIterator last
)
435 for (; first
!= last
; ++first
)
439 std::pair
<iterator
, bool> insert(const K
&key
)
441 int hash
= do_hash(key
);
442 int i
= do_lookup(key
, hash
);
444 return std::pair
<iterator
, bool>(iterator(this, i
), false);
445 i
= do_insert(key
, hash
);
446 return std::pair
<iterator
, bool>(iterator(this, i
), true);
449 std::pair
<iterator
, bool> insert(const std::pair
<K
, T
> &value
)
451 int hash
= do_hash(value
.first
);
452 int i
= do_lookup(value
.first
, hash
);
454 return std::pair
<iterator
, bool>(iterator(this, i
), false);
455 i
= do_insert(value
, hash
);
456 return std::pair
<iterator
, bool>(iterator(this, i
), true);
459 std::pair
<iterator
, bool> insert(std::pair
<K
, T
> &&rvalue
)
461 int hash
= do_hash(rvalue
.first
);
462 int i
= do_lookup(rvalue
.first
, hash
);
464 return std::pair
<iterator
, bool>(iterator(this, i
), false);
465 i
= do_insert(std::forward
<std::pair
<K
, T
>>(rvalue
), hash
);
466 return std::pair
<iterator
, bool>(iterator(this, i
), true);
469 std::pair
<iterator
, bool> emplace(K
const &key
, T
const &value
)
471 int hash
= do_hash(key
);
472 int i
= do_lookup(key
, hash
);
474 return std::pair
<iterator
, bool>(iterator(this, i
), false);
475 i
= do_insert(std::make_pair(key
, value
), hash
);
476 return std::pair
<iterator
, bool>(iterator(this, i
), true);
479 std::pair
<iterator
, bool> emplace(K
const &key
, T
&&rvalue
)
481 int hash
= do_hash(key
);
482 int i
= do_lookup(key
, hash
);
484 return std::pair
<iterator
, bool>(iterator(this, i
), false);
485 i
= do_insert(std::make_pair(key
, std::forward
<T
>(rvalue
)), hash
);
486 return std::pair
<iterator
, bool>(iterator(this, i
), true);
489 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
const &value
)
491 int hash
= do_hash(rkey
);
492 int i
= do_lookup(rkey
, hash
);
494 return std::pair
<iterator
, bool>(iterator(this, i
), false);
495 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), value
), hash
);
496 return std::pair
<iterator
, bool>(iterator(this, i
), true);
499 std::pair
<iterator
, bool> emplace(K
&&rkey
, T
&&rvalue
)
501 int hash
= do_hash(rkey
);
502 int i
= do_lookup(rkey
, hash
);
504 return std::pair
<iterator
, bool>(iterator(this, i
), false);
505 i
= do_insert(std::make_pair(std::forward
<K
>(rkey
), std::forward
<T
>(rvalue
)), hash
);
506 return std::pair
<iterator
, bool>(iterator(this, i
), true);
509 int erase(const K
&key
)
511 int hash
= do_hash(key
);
512 int index
= do_lookup(key
, hash
);
513 return do_erase(index
, hash
);
516 iterator
erase(iterator it
)
518 int hash
= do_hash(it
->first
);
519 do_erase(it
.index
, hash
);
523 int count(const K
&key
) const
525 int hash
= do_hash(key
);
526 int i
= do_lookup(key
, hash
);
527 return i
< 0 ? 0 : 1;
530 int count(const K
&key
, const_iterator it
) const
532 int hash
= do_hash(key
);
533 int i
= do_lookup(key
, hash
);
534 return i
< 0 || i
> it
.index
? 0 : 1;
537 iterator
find(const K
&key
)
539 int hash
= do_hash(key
);
540 int i
= do_lookup(key
, hash
);
543 return iterator(this, i
);
546 const_iterator
find(const K
&key
) const
548 int hash
= do_hash(key
);
549 int i
= do_lookup(key
, hash
);
552 return const_iterator(this, i
);
557 int hash
= do_hash(key
);
558 int i
= do_lookup(key
, hash
);
560 throw std::out_of_range("dict::at()");
561 return entries
[i
].udata
.second
;
564 const T
& at(const K
&key
) const
566 int hash
= do_hash(key
);
567 int i
= do_lookup(key
, hash
);
569 throw std::out_of_range("dict::at()");
570 return entries
[i
].udata
.second
;
573 const T
& at(const K
&key
, const T
&defval
) const
575 int hash
= do_hash(key
);
576 int i
= do_lookup(key
, hash
);
579 return entries
[i
].udata
.second
;
582 T
& operator[](const K
&key
)
584 int hash
= do_hash(key
);
585 int i
= do_lookup(key
, hash
);
587 i
= do_insert(std::pair
<K
, T
>(key
, T()), hash
);
588 return entries
[i
].udata
.second
;
591 template<typename Compare
= std::less
<K
>>
592 void sort(Compare comp
= Compare())
594 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
.first
, a
.udata
.first
); });
598 void swap(dict
&other
)
600 hashtable
.swap(other
.hashtable
);
601 entries
.swap(other
.entries
);
604 bool operator==(const dict
&other
) const {
605 if (size() != other
.size())
607 for (auto &it
: entries
) {
608 auto oit
= other
.find(it
.udata
.first
);
609 if (oit
== other
.end() || !(oit
->second
== it
.udata
.second
))
615 bool operator!=(const dict
&other
) const {
616 return !operator==(other
);
619 unsigned int hash() const {
620 unsigned int h
= mkhash_init
;
621 for (auto &entry
: entries
) {
622 h
^= hash_ops
<K
>::hash(entry
.udata
.first
);
623 h
^= hash_ops
<T
>::hash(entry
.udata
.second
);
628 void reserve(size_t n
) { entries
.reserve(n
); }
629 size_t size() const { return entries
.size(); }
630 bool empty() const { return entries
.empty(); }
631 void clear() { hashtable
.clear(); entries
.clear(); }
633 iterator
begin() { return iterator(this, int(entries
.size())-1); }
634 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
635 iterator
end() { return iterator(nullptr, -1); }
637 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
638 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
639 const_iterator
end() const { return const_iterator(nullptr, -1); }
642 template<typename K
, typename OPS
>
645 template<typename
, int, typename
> friend class idict
;
654 entry_t(const K
&udata
, int next
) : udata(udata
), next(next
) { }
655 entry_t(K
&&udata
, int next
) : udata(std::move(udata
)), next(next
) { }
658 std::vector
<int> hashtable
;
659 std::vector
<entry_t
> entries
;
663 static inline void do_assert(bool) { }
665 static inline void do_assert(bool cond
) {
666 if (!cond
) throw std::runtime_error("pool<> assert failed.");
670 int do_hash(const K
&key
) const
672 unsigned int hash
= 0;
673 if (!hashtable
.empty())
674 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
681 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
683 for (int i
= 0; i
< int(entries
.size()); i
++) {
684 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
685 int hash
= do_hash(entries
[i
].udata
);
686 entries
[i
].next
= hashtable
[hash
];
691 int do_erase(int index
, int hash
)
693 do_assert(index
< int(entries
.size()));
694 if (hashtable
.empty() || index
< 0)
697 int k
= hashtable
[hash
];
699 hashtable
[hash
] = entries
[index
].next
;
701 while (entries
[k
].next
!= index
) {
703 do_assert(0 <= k
&& k
< int(entries
.size()));
705 entries
[k
].next
= entries
[index
].next
;
708 int back_idx
= entries
.size()-1;
710 if (index
!= back_idx
)
712 int back_hash
= do_hash(entries
[back_idx
].udata
);
714 k
= hashtable
[back_hash
];
716 hashtable
[back_hash
] = index
;
718 while (entries
[k
].next
!= back_idx
) {
720 do_assert(0 <= k
&& k
< int(entries
.size()));
722 entries
[k
].next
= index
;
725 entries
[index
] = std::move(entries
[back_idx
]);
736 int do_lookup(const K
&key
, int &hash
) const
738 if (hashtable
.empty())
741 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
742 ((pool
*)this)->do_rehash();
746 int index
= hashtable
[hash
];
748 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
749 index
= entries
[index
].next
;
750 do_assert(-1 <= index
&& index
< int(entries
.size()));
756 int do_insert(const K
&value
, int &hash
)
758 if (hashtable
.empty()) {
759 entries
.emplace_back(value
, -1);
761 hash
= do_hash(value
);
763 entries
.emplace_back(value
, hashtable
[hash
]);
764 hashtable
[hash
] = entries
.size() - 1;
766 return entries
.size() - 1;
769 int do_insert(K
&&rvalue
, int &hash
)
771 if (hashtable
.empty()) {
772 entries
.emplace_back(std::forward
<K
>(rvalue
), -1);
774 hash
= do_hash(rvalue
);
776 entries
.emplace_back(std::forward
<K
>(rvalue
), hashtable
[hash
]);
777 hashtable
[hash
] = entries
.size() - 1;
779 return entries
.size() - 1;
783 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
789 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
792 const_iterator
operator++() { index
--; return *this; }
793 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
794 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
795 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
796 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
799 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
805 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
808 iterator
operator++() { index
--; return *this; }
809 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
810 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
811 K
&operator*() { return ptr
->entries
[index
].udata
; }
812 K
*operator->() { return &ptr
->entries
[index
].udata
; }
813 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
814 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
815 operator const_iterator() const { return const_iterator(ptr
, index
); }
822 pool(const pool
&other
)
824 entries
= other
.entries
;
833 pool
&operator=(const pool
&other
) {
834 entries
= other
.entries
;
839 pool
&operator=(pool
&&other
) {
845 pool(const std::initializer_list
<K
> &list
)
847 for (auto &it
: list
)
851 template<class InputIterator
>
852 pool(InputIterator first
, InputIterator last
)
857 template<class InputIterator
>
858 void insert(InputIterator first
, InputIterator last
)
860 for (; first
!= last
; ++first
)
864 std::pair
<iterator
, bool> insert(const K
&value
)
866 int hash
= do_hash(value
);
867 int i
= do_lookup(value
, hash
);
869 return std::pair
<iterator
, bool>(iterator(this, i
), false);
870 i
= do_insert(value
, hash
);
871 return std::pair
<iterator
, bool>(iterator(this, i
), true);
874 std::pair
<iterator
, bool> insert(K
&&rvalue
)
876 int hash
= do_hash(rvalue
);
877 int i
= do_lookup(rvalue
, hash
);
879 return std::pair
<iterator
, bool>(iterator(this, i
), false);
880 i
= do_insert(std::forward
<K
>(rvalue
), hash
);
881 return std::pair
<iterator
, bool>(iterator(this, i
), true);
884 template<typename
... Args
>
885 std::pair
<iterator
, bool> emplace(Args
&&... args
)
887 return insert(K(std::forward
<Args
>(args
)...));
890 int erase(const K
&key
)
892 int hash
= do_hash(key
);
893 int index
= do_lookup(key
, hash
);
894 return do_erase(index
, hash
);
897 iterator
erase(iterator it
)
899 int hash
= do_hash(*it
);
900 do_erase(it
.index
, hash
);
904 int count(const K
&key
) const
906 int hash
= do_hash(key
);
907 int i
= do_lookup(key
, hash
);
908 return i
< 0 ? 0 : 1;
911 int count(const K
&key
, const_iterator it
) const
913 int hash
= do_hash(key
);
914 int i
= do_lookup(key
, hash
);
915 return i
< 0 || i
> it
.index
? 0 : 1;
918 iterator
find(const K
&key
)
920 int hash
= do_hash(key
);
921 int i
= do_lookup(key
, hash
);
924 return iterator(this, i
);
927 const_iterator
find(const K
&key
) const
929 int hash
= do_hash(key
);
930 int i
= do_lookup(key
, hash
);
933 return const_iterator(this, i
);
936 bool operator[](const K
&key
)
938 int hash
= do_hash(key
);
939 int i
= do_lookup(key
, hash
);
943 template<typename Compare
= std::less
<K
>>
944 void sort(Compare comp
= Compare())
946 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
952 iterator it
= begin();
958 void swap(pool
&other
)
960 hashtable
.swap(other
.hashtable
);
961 entries
.swap(other
.entries
);
964 bool operator==(const pool
&other
) const {
965 if (size() != other
.size())
967 for (auto &it
: entries
)
968 if (!other
.count(it
.udata
))
973 bool operator!=(const pool
&other
) const {
974 return !operator==(other
);
978 unsigned int hashval
= mkhash_init
;
979 for (auto &it
: entries
)
980 hashval
^= ops
.hash(it
.udata
);
984 void reserve(size_t n
) { entries
.reserve(n
); }
985 size_t size() const { return entries
.size(); }
986 bool empty() const { return entries
.empty(); }
987 void clear() { hashtable
.clear(); entries
.clear(); }
989 iterator
begin() { return iterator(this, int(entries
.size())-1); }
990 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
991 iterator
end() { return iterator(nullptr, -1); }
993 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
994 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
995 const_iterator
end() const { return const_iterator(nullptr, -1); }
998 template<typename K
, int offset
, typename OPS
>
1001 pool
<K
, OPS
> database
;
1004 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
1008 const idict
&container
;
1010 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
1012 const_iterator() { }
1013 const_iterator
operator++() { index
++; return *this; }
1014 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
1015 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
1016 const K
&operator*() const { return container
[index
]; }
1017 const K
*operator->() const { return &container
[index
]; }
1020 int operator()(const K
&key
)
1022 int hash
= database
.do_hash(key
);
1023 int i
= database
.do_lookup(key
, hash
);
1025 i
= database
.do_insert(key
, hash
);
1029 int at(const K
&key
) const
1031 int hash
= database
.do_hash(key
);
1032 int i
= database
.do_lookup(key
, hash
);
1034 throw std::out_of_range("idict::at()");
1038 int at(const K
&key
, int defval
) const
1040 int hash
= database
.do_hash(key
);
1041 int i
= database
.do_lookup(key
, hash
);
1047 int count(const K
&key
) const
1049 int hash
= database
.do_hash(key
);
1050 int i
= database
.do_lookup(key
, hash
);
1051 return i
< 0 ? 0 : 1;
1054 void expect(const K
&key
, int i
)
1056 int j
= (*this)(key
);
1058 throw std::out_of_range("idict::expect()");
1061 const K
&operator[](int index
) const
1063 return database
.entries
.at(index
- offset
).udata
;
1066 void swap(idict
&other
)
1068 database
.swap(other
.database
);
1071 void reserve(size_t n
) { database
.reserve(n
); }
1072 size_t size() const { return database
.size(); }
1073 bool empty() const { return database
.empty(); }
1074 void clear() { database
.clear(); }
1076 const_iterator
begin() const { return const_iterator(*this, offset
); }
1077 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1078 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1081 template<typename K
, typename OPS
>
1084 mutable idict
<K
, 0, OPS
> database
;
1085 mutable std::vector
<int> parents
;
1088 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1090 int operator()(const K
&key
) const
1092 int i
= database(key
);
1093 parents
.resize(database
.size(), -1);
1097 const K
&operator[](int index
) const
1099 return database
[index
];
1102 int ifind(int i
) const
1106 while (parents
[p
] != -1)
1110 int next_k
= parents
[k
];
1118 void imerge(int i
, int j
)
1127 void ipromote(int i
)
1132 int next_k
= parents
[k
];
1140 int lookup(const K
&a
) const
1142 return ifind((*this)(a
));
1145 const K
&find(const K
&a
) const
1147 int i
= database
.at(a
, -1);
1150 return (*this)[ifind(i
)];
1153 void merge(const K
&a
, const K
&b
)
1155 imerge((*this)(a
), (*this)(b
));
1158 void promote(const K
&a
)
1160 int i
= database
.at(a
, -1);
1165 void swap(mfp
&other
)
1167 database
.swap(other
.database
);
1168 parents
.swap(other
.parents
);
1171 void reserve(size_t n
) { database
.reserve(n
); }
1172 size_t size() const { return database
.size(); }
1173 bool empty() const { return database
.empty(); }
1174 void clear() { database
.clear(); parents
.clear(); }
1176 const_iterator
begin() const { return database
.begin(); }
1177 const_iterator
element(int n
) const { return database
.element(n
); }
1178 const_iterator
end() const { return database
.end(); }
1181 } /* namespace hashlib */