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
) { }
647 std::vector
<int> hashtable
;
648 std::vector
<entry_t
> entries
;
652 static inline void do_assert(bool) { }
654 static inline void do_assert(bool cond
) {
655 if (!cond
) throw std::runtime_error("pool<> assert failed.");
659 int do_hash(const K
&key
) const
661 unsigned int hash
= 0;
662 if (!hashtable
.empty())
663 hash
= ops
.hash(key
) % (unsigned int)(hashtable
.size());
670 hashtable
.resize(hashtable_size(entries
.capacity() * hashtable_size_factor
), -1);
672 for (int i
= 0; i
< int(entries
.size()); i
++) {
673 do_assert(-1 <= entries
[i
].next
&& entries
[i
].next
< int(entries
.size()));
674 int hash
= do_hash(entries
[i
].udata
);
675 entries
[i
].next
= hashtable
[hash
];
680 int do_erase(int index
, int hash
)
682 do_assert(index
< int(entries
.size()));
683 if (hashtable
.empty() || index
< 0)
686 int k
= hashtable
[hash
];
688 hashtable
[hash
] = entries
[index
].next
;
690 while (entries
[k
].next
!= index
) {
692 do_assert(0 <= k
&& k
< int(entries
.size()));
694 entries
[k
].next
= entries
[index
].next
;
697 int back_idx
= entries
.size()-1;
699 if (index
!= back_idx
)
701 int back_hash
= do_hash(entries
[back_idx
].udata
);
703 k
= hashtable
[back_hash
];
705 hashtable
[back_hash
] = index
;
707 while (entries
[k
].next
!= back_idx
) {
709 do_assert(0 <= k
&& k
< int(entries
.size()));
711 entries
[k
].next
= index
;
714 entries
[index
] = std::move(entries
[back_idx
]);
725 int do_lookup(const K
&key
, int &hash
) const
727 if (hashtable
.empty())
730 if (entries
.size() * hashtable_size_trigger
> hashtable
.size()) {
731 ((pool
*)this)->do_rehash();
735 int index
= hashtable
[hash
];
737 while (index
>= 0 && !ops
.cmp(entries
[index
].udata
, key
)) {
738 index
= entries
[index
].next
;
739 do_assert(-1 <= index
&& index
< int(entries
.size()));
745 int do_insert(const K
&value
, int &hash
)
747 if (hashtable
.empty()) {
748 entries
.push_back(entry_t(value
, -1));
750 hash
= do_hash(value
);
752 entries
.push_back(entry_t(value
, hashtable
[hash
]));
753 hashtable
[hash
] = entries
.size() - 1;
755 return entries
.size() - 1;
759 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
765 const_iterator(const pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
768 const_iterator
operator++() { index
--; return *this; }
769 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
770 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
771 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
772 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
775 class iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
781 iterator(pool
*ptr
, int index
) : ptr(ptr
), index(index
) { }
784 iterator
operator++() { index
--; return *this; }
785 bool operator==(const iterator
&other
) const { return index
== other
.index
; }
786 bool operator!=(const iterator
&other
) const { return index
!= other
.index
; }
787 K
&operator*() { return ptr
->entries
[index
].udata
; }
788 K
*operator->() { return &ptr
->entries
[index
].udata
; }
789 const K
&operator*() const { return ptr
->entries
[index
].udata
; }
790 const K
*operator->() const { return &ptr
->entries
[index
].udata
; }
791 operator const_iterator() const { return const_iterator(ptr
, index
); }
798 pool(const pool
&other
)
800 entries
= other
.entries
;
809 pool
&operator=(const pool
&other
) {
810 entries
= other
.entries
;
815 pool
&operator=(pool
&&other
) {
821 pool(const std::initializer_list
<K
> &list
)
823 for (auto &it
: list
)
827 template<class InputIterator
>
828 pool(InputIterator first
, InputIterator last
)
833 template<class InputIterator
>
834 void insert(InputIterator first
, InputIterator last
)
836 for (; first
!= last
; ++first
)
840 std::pair
<iterator
, bool> insert(const K
&value
)
842 int hash
= do_hash(value
);
843 int i
= do_lookup(value
, hash
);
845 return std::pair
<iterator
, bool>(iterator(this, i
), false);
846 i
= do_insert(value
, hash
);
847 return std::pair
<iterator
, bool>(iterator(this, i
), true);
850 int erase(const K
&key
)
852 int hash
= do_hash(key
);
853 int index
= do_lookup(key
, hash
);
854 return do_erase(index
, hash
);
857 iterator
erase(iterator it
)
859 int hash
= do_hash(*it
);
860 do_erase(it
.index
, hash
);
864 int count(const K
&key
) const
866 int hash
= do_hash(key
);
867 int i
= do_lookup(key
, hash
);
868 return i
< 0 ? 0 : 1;
871 int count(const K
&key
, const_iterator it
) const
873 int hash
= do_hash(key
);
874 int i
= do_lookup(key
, hash
);
875 return i
< 0 || i
> it
.index
? 0 : 1;
878 iterator
find(const K
&key
)
880 int hash
= do_hash(key
);
881 int i
= do_lookup(key
, hash
);
884 return iterator(this, i
);
887 const_iterator
find(const K
&key
) const
889 int hash
= do_hash(key
);
890 int i
= do_lookup(key
, hash
);
893 return const_iterator(this, i
);
896 bool operator[](const K
&key
)
898 int hash
= do_hash(key
);
899 int i
= do_lookup(key
, hash
);
903 template<typename Compare
= std::less
<K
>>
904 void sort(Compare comp
= Compare())
906 std::sort(entries
.begin(), entries
.end(), [comp
](const entry_t
&a
, const entry_t
&b
){ return comp(b
.udata
, a
.udata
); });
912 iterator it
= begin();
918 void swap(pool
&other
)
920 hashtable
.swap(other
.hashtable
);
921 entries
.swap(other
.entries
);
924 bool operator==(const pool
&other
) const {
925 if (size() != other
.size())
927 for (auto &it
: entries
)
928 if (!other
.count(it
.udata
))
933 bool operator!=(const pool
&other
) const {
934 return !operator==(other
);
938 unsigned int hashval
= mkhash_init
;
939 for (auto &it
: entries
)
940 hashval
^= ops
.hash(it
.udata
);
944 void reserve(size_t n
) { entries
.reserve(n
); }
945 size_t size() const { return entries
.size(); }
946 bool empty() const { return entries
.empty(); }
947 void clear() { hashtable
.clear(); entries
.clear(); }
949 iterator
begin() { return iterator(this, int(entries
.size())-1); }
950 iterator
element(int n
) { return iterator(this, int(entries
.size())-1-n
); }
951 iterator
end() { return iterator(nullptr, -1); }
953 const_iterator
begin() const { return const_iterator(this, int(entries
.size())-1); }
954 const_iterator
element(int n
) const { return const_iterator(this, int(entries
.size())-1-n
); }
955 const_iterator
end() const { return const_iterator(nullptr, -1); }
958 template<typename K
, int offset
, typename OPS
>
961 pool
<K
, OPS
> database
;
964 class const_iterator
: public std::iterator
<std::forward_iterator_tag
, K
>
968 const idict
&container
;
970 const_iterator(const idict
&container
, int index
) : container(container
), index(index
) { }
973 const_iterator
operator++() { index
++; return *this; }
974 bool operator==(const const_iterator
&other
) const { return index
== other
.index
; }
975 bool operator!=(const const_iterator
&other
) const { return index
!= other
.index
; }
976 const K
&operator*() const { return container
[index
]; }
977 const K
*operator->() const { return &container
[index
]; }
980 int operator()(const K
&key
)
982 int hash
= database
.do_hash(key
);
983 int i
= database
.do_lookup(key
, hash
);
985 i
= database
.do_insert(key
, hash
);
989 int at(const K
&key
) const
991 int hash
= database
.do_hash(key
);
992 int i
= database
.do_lookup(key
, hash
);
994 throw std::out_of_range("idict::at()");
998 int at(const K
&key
, int defval
) const
1000 int hash
= database
.do_hash(key
);
1001 int i
= database
.do_lookup(key
, hash
);
1007 int count(const K
&key
) const
1009 int hash
= database
.do_hash(key
);
1010 int i
= database
.do_lookup(key
, hash
);
1011 return i
< 0 ? 0 : 1;
1014 void expect(const K
&key
, int i
)
1016 int j
= (*this)(key
);
1018 throw std::out_of_range("idict::expect()");
1021 const K
&operator[](int index
) const
1023 return database
.entries
.at(index
- offset
).udata
;
1026 void swap(idict
&other
)
1028 database
.swap(other
.database
);
1031 void reserve(size_t n
) { database
.reserve(n
); }
1032 size_t size() const { return database
.size(); }
1033 bool empty() const { return database
.empty(); }
1034 void clear() { database
.clear(); }
1036 const_iterator
begin() const { return const_iterator(*this, offset
); }
1037 const_iterator
element(int n
) const { return const_iterator(*this, n
); }
1038 const_iterator
end() const { return const_iterator(*this, offset
+ size()); }
1041 template<typename K
, typename OPS
>
1044 mutable idict
<K
, 0, OPS
> database
;
1045 mutable std::vector
<int> parents
;
1048 typedef typename idict
<K
, 0, OPS
>::const_iterator const_iterator
;
1050 int operator()(const K
&key
) const
1052 int i
= database(key
);
1053 parents
.resize(database
.size(), -1);
1057 const K
&operator[](int index
) const
1059 return database
[index
];
1062 int ifind(int i
) const
1066 while (parents
[p
] != -1)
1070 int next_k
= parents
[k
];
1078 void imerge(int i
, int j
)
1087 void ipromote(int i
)
1092 int next_k
= parents
[k
];
1100 int lookup(const K
&a
) const
1102 return ifind((*this)(a
));
1105 const K
&find(const K
&a
) const
1107 int i
= database
.at(a
, -1);
1110 return (*this)[ifind(i
)];
1113 void merge(const K
&a
, const K
&b
)
1115 imerge((*this)(a
), (*this)(b
));
1118 void promote(const K
&a
)
1120 int i
= database
.at(a
, -1);
1125 void swap(mfp
&other
)
1127 database
.swap(other
.database
);
1128 parents
.swap(other
.parents
);
1131 void reserve(size_t n
) { database
.reserve(n
); }
1132 size_t size() const { return database
.size(); }
1133 bool empty() const { return database
.empty(); }
1134 void clear() { database
.clear(); parents
.clear(); }
1136 const_iterator
begin() const { return database
.begin(); }
1137 const_iterator
element(int n
) const { return database
.element(n
); }
1138 const_iterator
end() const { return database
.end(); }
1141 } /* namespace hashlib */