1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Ion Gazta�aga 2006-2007
\r
5 // Distributed under the Boost Software License, Version 1.0.
\r
6 // (See accompanying file LICENSE_1_0.txt or copy at
\r
7 // http://www.boost.org/LICENSE_1_0.txt)
\r
9 // See http://www.boost.org/libs/intrusive for documentation.
\r
11 /////////////////////////////////////////////////////////////////////////////
\r
12 #ifndef BOOST_INTRUSIVE_IHASHTABLE_HPP
\r
13 #define BOOST_INTRUSIVE_IHASHTABLE_HPP
\r
15 #include "config_begin.hpp"
\r
17 #include <functional>
\r
20 #include <algorithm>
\r
22 #include <boost/utility.hpp>
\r
23 #include <boost/compressed_pair.hpp>
\r
24 #include <boost/assert.hpp>
\r
25 #include <boost/static_assert.hpp>
\r
26 #include <boost/functional/hash.hpp>
\r
27 //General intrusive utilities
\r
28 #include "pointer_type.hpp"
\r
29 #include "pointer_to_other.hpp"
\r
30 #include "../linking_policy.hpp"
\r
31 //Implementation utilities
\r
32 #include "../iunordered_set_hook.hpp"
\r
33 #include "../islist.hpp"
\r
38 namespace intrusive {
\r
41 template<int Dummy = 0>
\r
42 struct prime_list_holder
\r
44 static const std::size_t prime_list[];
\r
45 static const std::size_t prime_list_size;
\r
49 const std::size_t prime_list_holder<Dummy>::prime_list[] = {
\r
50 53ul, 97ul, 193ul, 389ul, 769ul,
\r
51 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
\r
52 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
\r
53 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
\r
54 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
\r
55 1610612741ul, 3221225473ul, 4294967291ul };
\r
58 const std::size_t prime_list_holder<Dummy>::prime_list_size
\r
59 = sizeof(prime_list)/sizeof(std::size_t);
\r
61 //! The class template ihashtable is an intrusive hash table container, that
\r
62 //! is used to construct intrusive unordered_set and unordered_multiset containers. The
\r
63 //! no-throw guarantee holds only, if the Equal object and Hasher don't throw.
\r
64 template< class ValueTraits
\r
65 , class Hash = boost::hash<typename ValueTraits::value_type>
\r
66 , class Equal = std::equal_to<typename ValueTraits::value_type>
\r
67 , bool ConstantTimeSize = true
\r
68 , class SizeType = std::size_t
\r
71 : private detail::size_holder<ConstantTimeSize, SizeType>
\r
74 template<class T, class Self, class NodeTraits>
\r
75 class hashtable_iterator;
\r
77 typedef islist<ValueTraits, false, SizeType> islist_impl;
\r
79 struct bucket_type_impl
\r
80 : private islist_impl
\r
82 friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>;
\r
87 bucket_type_impl(const bucket_type_impl &)
\r
90 bucket_type_impl &operator=(const bucket_type_impl&)
\r
91 { islist_impl::clear(); }
\r
94 static islist_impl &islist_from_bucket(bucket_type_impl &b)
\r
95 { return static_cast<islist_impl&>(b); }
\r
97 static const islist_impl &islist_from_bucket(const bucket_type_impl &b)
\r
98 { return static_cast<const islist_impl&>(b); }
\r
100 typedef ihashtable<ValueTraits, Hash, Equal
\r
101 ,ConstantTimeSize, SizeType> this_type;
\r
102 typedef typename ValueTraits::node_traits node_traits;
\r
103 typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;
\r
106 ihashtable (const ihashtable&);
\r
107 ihashtable operator =(const ihashtable&);
\r
110 typedef typename ValueTraits::value_type value_type;
\r
111 typedef typename ValueTraits::pointer pointer;
\r
112 typedef typename ValueTraits::const_pointer const_pointer;
\r
113 typedef value_type& reference;
\r
114 typedef const value_type& const_reference;
\r
115 typedef SizeType size_type;
\r
116 typedef typename std::iterator_traits
\r
117 <pointer>::difference_type difference_type;
\r
118 typedef value_type key_type;
\r
119 typedef Hash hasher;
\r
120 typedef Equal key_equal;
\r
121 typedef bucket_type_impl bucket_type;
\r
122 typedef typename boost::pointer_to_other
\r
123 <pointer, bucket_type>::type bucket_ptr;
\r
124 typedef typename islist_impl::iterator local_iterator;
\r
125 typedef typename islist_impl::const_iterator const_local_iterator;
\r
127 class const_iterator;
\r
131 typedef typename node_traits::node node;
\r
132 typedef typename boost::pointer_to_other
\r
133 <pointer, node>::type node_ptr;
\r
134 typedef typename boost::pointer_to_other
\r
135 <node_ptr, const node>::type const_node_ptr;
\r
136 //typedef hashtable_algorithms<node_traits> node_algorithms;
\r
137 typedef slist_algorithms<node_traits> node_algorithms;
\r
138 enum { safemode_or_autounlink =
\r
139 (int)ValueTraits::linking_policy == (int)auto_unlink ||
\r
140 (int)ValueTraits::linking_policy == (int)safe_mode_link };
\r
142 //Constant-time size is incompatible with auto-unlink hooks!
\r
143 BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));
\r
145 struct bucket_info_t
\r
147 bucket_ptr buckets_;
\r
148 size_type buckets_len_;
\r
151 typedef typename boost::pointer_to_other
\r
152 <pointer, bucket_info_t>::type bucket_info_ptr;
\r
154 typedef typename boost::pointer_to_other
\r
155 <pointer, const bucket_info_t>::type const_bucket_info_ptr;
\r
157 //User scattered boost::compressed pair to get EBO all compilers
\r
158 boost::compressed_pair
\r
159 <boost::compressed_pair<bucket_info_t, Hash>
\r
162 const Equal &priv_equal() const
\r
163 { return members_.second(); }
\r
165 Equal &priv_equal()
\r
166 { return members_.second(); }
\r
168 const_bucket_info_ptr priv_bucket_info() const
\r
169 { return &members_.first().first(); }
\r
171 bucket_info_ptr priv_bucket_info()
\r
172 { return &members_.first().first(); }
\r
174 const Hash &priv_hasher() const
\r
175 { return members_.first().second(); }
\r
177 Hash &priv_hasher()
\r
178 { return members_.first().second(); }
\r
180 const bucket_ptr &priv_buckets() const
\r
181 { return members_.first().first().buckets_; }
\r
183 bucket_ptr &priv_buckets()
\r
184 { return members_.first().first().buckets_; }
\r
186 const size_type &priv_buckets_len() const
\r
187 { return members_.first().first().buckets_len_; }
\r
189 size_type &priv_buckets_len()
\r
190 { return members_.first().first().buckets_len_; }
\r
192 static node_ptr uncast(const_node_ptr ptr)
\r
194 using boost::get_pointer;
\r
195 return node_ptr(const_cast<node*>(get_pointer(ptr)));
\r
198 static bucket_info_ptr uncast(const_bucket_info_ptr ptr)
\r
200 using boost::get_pointer;
\r
201 return bucket_info_ptr(const_cast<bucket_info_t*>(get_pointer(ptr)));
\r
204 template<class T, class Self, class NodeTraits>
\r
205 class hashtable_iterator
\r
206 : public std::iterator<std::forward_iterator_tag, T>
\r
209 explicit hashtable_iterator
\r
210 (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)
\r
211 : local_it_ (ptr), bucket_info_ (bucket_info), n_bucket_ (n_bucket)
\r
215 hashtable_iterator ()
\r
220 using boost::get_pointer;
\r
222 size_type buckets_len = bucket_info_->buckets_len_;
\r
223 bucket_ptr buckets = bucket_info_->buckets_;
\r
224 while (local_it_ == islist_from_bucket(buckets[n_bucket_]).end()){
\r
225 if (++n_bucket_ == buckets_len) {
\r
226 local_it_ = invalid_local_it(*bucket_info_);
\r
229 local_it_ = islist_from_bucket(buckets[n_bucket_]).begin();
\r
231 return static_cast<Self&> (*this);
\r
234 Self operator++(int)
\r
236 Self result(local_it_, bucket_info_, n_bucket_);
\r
241 bool operator== (const Self& i) const
\r
242 { return local_it_ == i.local(); }
\r
244 bool operator!= (const Self& i) const
\r
245 { return !operator== (i); }
\r
247 Self &set_internals
\r
248 (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)
\r
250 local_it_ = ptr; bucket_info_ = bucket_info; n_bucket_ = n_bucket;
\r
251 return static_cast<Self&>(*this);
\r
254 local_iterator local() const
\r
255 { return local_it_; }
\r
257 bucket_info_ptr priv_bucket_info() const
\r
258 { return bucket_info_; }
\r
260 size_type bucket_num() const
\r
261 { return n_bucket_; }
\r
264 local_iterator local_it_;
\r
265 bucket_info_ptr bucket_info_;
\r
266 size_type n_bucket_;
\r
272 : public hashtable_iterator <value_type, iterator, node_traits>
\r
275 typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type private_vt;
\r
276 typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::pointer private_pointer;
\r
277 typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::reference private_reference;
\r
278 typedef hashtable_iterator<private_vt, iterator, node_traits> inherited;
\r
284 private_pointer operator->() const
\r
285 { return &*this->local(); }
\r
287 private_reference operator*() const
\r
288 { return *this->local(); }
\r
292 (local_iterator local_it, bucket_info_ptr bucket_info, size_type n_bucket)
\r
293 : inherited(local_it, bucket_info, n_bucket)
\r
296 friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>;
\r
297 friend class hashtable_iterator<private_vt, iterator, node_traits>;
\r
298 friend class const_iterator;
\r
301 class const_iterator
\r
302 : public hashtable_iterator<const value_type, const_iterator, node_traits>
\r
305 typedef const typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type private_vt;
\r
306 typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_pointer private_pointer;
\r
307 typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_reference private_reference;
\r
308 typedef hashtable_iterator<private_vt, const_iterator, node_traits> inherited;
\r
314 const_iterator(const typename ihashtable::iterator& it)
\r
315 : inherited (it.local(), it.priv_bucket_info(), it.bucket_num())
\r
318 const_iterator & operator=(const typename ihashtable::iterator& it)
\r
319 { return inherited::set_internals(it.local(), it.priv_bucket_info(), it.bucket_num()); }
\r
321 private_pointer operator->() const
\r
322 { return &*this->local(); }
\r
324 private_reference operator*() const
\r
325 { return *this->local(); }
\r
328 explicit const_iterator
\r
329 (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)
\r
330 : inherited(ptr, bucket_info, n_bucket)
\r
333 friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>;
\r
334 friend class hashtable_iterator<private_vt, const_iterator, node_traits>;
\r
337 //typedef typename node_algorithms::insert_commit_data insert_commit_data;
\r
338 struct insert_commit_data
\r
340 local_iterator prev_pos;
\r
341 size_type bucket_num;
\r
344 ihashtable( bucket_ptr buckets
\r
345 , size_type buckets_len
\r
346 , const Hash & hasher = Hash()
\r
347 , const Equal &equal = Equal())
\r
348 : members_(boost::compressed_pair<bucket_info_t, Hash>(hasher)/*hasher*/, equal)
\r
351 BOOST_ASSERT(buckets_len != 0);
\r
352 priv_buckets() = buckets;
\r
353 priv_buckets_len() = buckets_len;
\r
354 priv_clear_buckets();
\r
355 size_traits::set_size(size_type(0));
\r
363 size_type bucket_num;
\r
364 local_iterator local_it = priv_begin(bucket_num);
\r
365 return iterator( local_it
\r
366 , this->priv_bucket_info()
\r
370 const_iterator begin() const
\r
372 size_type bucket_num;
\r
373 local_iterator local_it = priv_begin(bucket_num);
\r
374 return const_iterator( local_it
\r
375 , uncast(this->priv_bucket_info())
\r
381 using boost::get_pointer;
\r
382 bucket_info_t *info = get_pointer(this->priv_bucket_info());
\r
383 return iterator(invalid_local_it(*info), 0, info->buckets_len_);
\r
386 const_iterator end() const
\r
388 using boost::get_pointer;
\r
389 const bucket_info_t *info = get_pointer(this->priv_bucket_info());
\r
390 return const_iterator(invalid_local_it(*info), 0, info->buckets_len_);
\r
393 hasher hash_function() const
\r
394 { return this->priv_hasher(); }
\r
396 key_equal key_eq() const
\r
397 { return this->priv_equal(); }
\r
401 if(ConstantTimeSize){
\r
405 using boost::get_pointer;
\r
406 size_type buckets_len = this->priv_buckets_len();
\r
407 const bucket_type *b = get_pointer(this->priv_buckets());
\r
408 for (size_type n = 0; n < buckets_len; ++n, ++b){
\r
417 size_type size() const
\r
419 if(ConstantTimeSize)
\r
420 return size_traits::get_size();
\r
423 using boost::get_pointer;
\r
424 size_type buckets_len = this->priv_buckets_len();
\r
425 const bucket_type *b = get_pointer(this->priv_buckets());
\r
426 for (size_type n = 0; n < buckets_len; ++n, ++b){
\r
433 void swap(ihashtable& other)
\r
437 swap(this->priv_equal(), other.priv_equal());
\r
438 swap(this->priv_hasher(), other.priv_hasher());
\r
439 //These can't throw
\r
440 swap(this->priv_buckets(), other.priv_buckets());
\r
441 swap(this->priv_buckets_len(), other.priv_buckets_len());
\r
442 if(ConstantTimeSize){
\r
443 size_type backup = size_traits::get_size();
\r
444 size_traits::set_size(other.get_size());
\r
445 other.set_size(backup);
\r
449 template <class Cloner, class Destroyer>
\r
450 void clone_from(const ihashtable &src, Cloner cloner, Destroyer destroyer)
\r
452 this->clear_and_destroy(destroyer);
\r
453 if(!ConstantTimeSize || !src.empty()){
\r
454 const size_type src_bucket_count = src.bucket_count();
\r
455 const size_type dst_bucket_count = this->bucket_count();
\r
457 //If src bucket count is bigger or equal, structural copy is possible
\r
458 if(src_bucket_count >= dst_bucket_count){
\r
459 //First clone the first ones
\r
460 const bucket_ptr src_buckets = src.priv_buckets();
\r
461 const bucket_ptr dst_buckets = this->priv_buckets();
\r
462 size_type constructed;
\r
464 for( constructed = 0
\r
465 ; constructed < dst_bucket_count
\r
467 dst_buckets[constructed].clone_and_reverse_from(src_buckets[constructed], cloner, destroyer);
\r
469 if(src_bucket_count != dst_bucket_count){
\r
470 //Now insert the remaining ones using the modulo trick
\r
471 for(//"constructed" comes from the previous loop
\r
472 ; constructed < src_bucket_count
\r
474 bucket_type &dst_b = dst_buckets[constructed % dst_bucket_count];
\r
475 bucket_type &src_b = src_buckets[constructed];
\r
476 for( local_iterator b(src_b.begin()), e(src_b.end())
\r
479 dst_b.push_front(*cloner(*b));
\r
485 while(constructed--){
\r
486 dst_buckets[constructed].clear_and_destroy(destroyer);
\r
490 size_traits::set_size(src.get_size());
\r
493 //Unlike previous cloning algorithm, this can throw
\r
494 //if cloner, the hasher or comparison functor throw
\r
495 const_iterator b(src.begin()), e(src.end());
\r
497 for(; b != e; ++b){
\r
498 this->insert_equal(*cloner(*b));
\r
502 this->clear_and_destroy(destroyer);
\r
509 iterator insert_equal(value_type &value)
\r
511 size_type bucket_num;
\r
512 local_iterator it = priv_find(value, this->priv_hasher(), this->priv_equal(), bucket_num);
\r
513 bucket_type &b = this->priv_buckets()[bucket_num];
\r
514 if(it == invalid_local_it(*this->priv_bucket_info())){
\r
515 it = b.before_begin();
\r
517 size_traits::increment();
\r
518 return iterator(b.insert_after(it, value), this->priv_bucket_info(), bucket_num);
\r
521 template<class Iterator>
\r
522 void insert_equal(Iterator b, Iterator e)
\r
524 for (; b != e; ++b)
\r
525 this->insert_equal(*b);
\r
528 std::pair<iterator, bool> insert_unique(value_type &value)
\r
530 insert_commit_data commit_data;
\r
531 std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);
\r
534 return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);
\r
537 template<class Iterator>
\r
538 void insert_unique(Iterator b, Iterator e)
\r
540 for (; b != e; ++b)
\r
541 this->insert_unique(*b);
\r
544 std::pair<iterator, bool> insert_unique_check
\r
545 (const value_type &value, insert_commit_data &commit_data)
\r
546 { return insert_unique_check(value, this->priv_hasher(), this->priv_equal(), commit_data); }
\r
548 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
549 std::pair<iterator, bool> insert_unique_check
\r
550 ( const KeyType &key
\r
552 , KeyValueEqual key_value_eq
\r
553 , insert_commit_data &commit_data)
\r
555 commit_data.prev_pos =
\r
556 priv_find(key, hasher, key_value_eq, commit_data.bucket_num);
\r
557 bool success = commit_data.prev_pos == invalid_local_it(*this->priv_bucket_info());
\r
559 commit_data.prev_pos = this->priv_buckets()[commit_data.bucket_num].before_begin();
\r
561 return std::pair<iterator, bool>
\r
562 (iterator(commit_data.prev_pos, this->priv_bucket_info(), commit_data.bucket_num)
\r
566 iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)
\r
568 bucket_type &b = this->priv_buckets()[commit_data.bucket_num];
\r
569 size_traits::increment();
\r
570 return iterator( b.insert_after(commit_data.prev_pos, value)
\r
571 , this->priv_bucket_info()
\r
572 , commit_data.bucket_num);
\r
575 void erase(const_iterator i)
\r
576 { erase_and_destroy(i, detail::null_destroyer()); }
\r
578 void erase(const_iterator b, const_iterator e)
\r
579 { erase_and_destroy(b, e, detail::null_destroyer()); }
\r
581 size_type erase(const value_type &value)
\r
582 { return this->erase(value, this->priv_hasher(), this->priv_equal()); }
\r
584 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
585 size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
586 { return erase_and_destroy(key, hasher, equal, detail::null_destroyer()); }
\r
588 template<class Destroyer>
\r
589 void erase_and_destroy(const_iterator i, Destroyer destroyer)
\r
591 local_iterator to_erase(i.local());
\r
592 size_type n_bucket = i.bucket_num();
\r
593 bucket_type &b = this->priv_buckets()[n_bucket];
\r
594 b.erase_after_and_destroy(b.previous(to_erase), destroyer);
\r
595 size_traits::decrement();
\r
598 template<class Destroyer>
\r
599 void erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)
\r
603 //Get the bucket number and local iterator for both iterators
\r
604 size_type first_bucket_num
\r
606 local_iterator before_first_local_it
\r
607 = priv_buckets()[first_bucket_num].previous(b.local());
\r
608 size_type last_bucket_num;
\r
609 local_iterator last_local_it;
\r
611 //For the end iterator, we will assign the end iterator
\r
612 //of the last bucket
\r
614 last_bucket_num = this->bucket_count() - 1;
\r
615 last_local_it = priv_buckets()[last_bucket_num].end();
\r
618 last_bucket_num = e.bucket_num();
\r
619 last_local_it = e.local();
\r
622 const bucket_ptr buckets = priv_buckets();
\r
623 //First erase the nodes of the first bucket
\r
625 bucket_type &first_b = buckets[first_bucket_num];
\r
626 local_iterator nxt(before_first_local_it); ++nxt;
\r
627 local_iterator end = first_b.end();
\r
629 nxt = first_b.erase_after_and_destroy(before_first_local_it, destroyer);
\r
630 size_traits::decrement();
\r
634 //Now fully clear the intermediate buckets
\r
635 for(size_type i = first_bucket_num+1; i < last_bucket_num; ++i){
\r
636 bucket_type &b = buckets[i];
\r
639 local_iterator b_begin(b.before_begin());
\r
640 local_iterator nxt(b_begin); ++nxt;
\r
641 local_iterator end = b.end();
\r
643 nxt = b.erase_after_and_destroy(b_begin, destroyer);
\r
644 size_traits::decrement();
\r
648 //Now erase nodes from the last bucket
\r
650 bucket_type &last_b = buckets[last_bucket_num];
\r
651 local_iterator b_begin(last_b.before_begin());
\r
652 local_iterator nxt(b_begin); ++nxt;
\r
653 while(nxt != last_local_it){
\r
654 nxt = last_b.erase_after_and_destroy(b_begin, destroyer);
\r
655 size_traits::decrement();
\r
660 template<class Destroyer>
\r
661 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
662 { return erase_and_destroy(value, priv_hasher(), priv_equal(), destroyer); }
\r
664 template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>
\r
665 size_type erase_and_destroy(const KeyType& key, KeyHasher hasher
\r
666 ,KeyValueEqual equal, Destroyer destroyer)
\r
668 size_type count(0);
\r
670 if(ConstantTimeSize && this->empty()){
\r
674 bucket_type &b = this->priv_buckets()[hasher(key) % this->priv_buckets_len()];
\r
675 local_iterator it = b.begin();
\r
676 local_iterator prev = b.before_begin();
\r
678 bool found = false;
\r
680 while(it != b.end()){
\r
681 if(equal(key, *it)){
\r
692 //If found erase all equal values
\r
693 for(local_iterator end = b.end(); it != end && equal(key, *it); ++count){
\r
694 it = b.erase_after_and_destroy(prev, destroyer);
\r
695 size_traits::decrement();
\r
702 if(safemode_or_autounlink){
\r
703 priv_clear_buckets();
\r
705 size_traits::set_size(size_type(0));
\r
708 template<class Destroyer>
\r
709 void clear_and_destroy(Destroyer destroyer)
\r
711 if(!ConstantTimeSize || !this->empty()){
\r
712 size_type num_buckets = this->bucket_count();
\r
713 bucket_ptr b = this->priv_buckets();
\r
714 for(; num_buckets--; ++b){
\r
715 b->clear_and_destroy(destroyer);
\r
717 size_traits::set_size(size_type(0));
\r
721 size_type count(const value_type &value) const
\r
722 { return this->count(value, this->priv_hasher(), this->priv_equal()); }
\r
724 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
725 size_type count(const KeyType &key, const KeyHasher &hasher, const KeyValueEqual &equal) const
\r
727 size_type bucket_n1, bucket_n2, count;
\r
728 priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);
\r
732 iterator find(const value_type &value)
\r
733 { return find(value, this->priv_hasher(), this->priv_equal()); }
\r
735 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
736 iterator find(const KeyType &key, KeyHasher hasher, KeyValueEqual equal)
\r
738 size_type bucket_n;
\r
739 local_iterator local_it = priv_find(key, hasher, equal, bucket_n);
\r
740 return iterator( local_it
\r
741 , this->priv_bucket_info()
\r
745 const_iterator find(const value_type &value) const
\r
746 { return find(value, this->priv_hasher(), this->priv_equal()); }
\r
748 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
749 const_iterator find
\r
750 (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const
\r
752 size_type bucket_n;
\r
753 local_iterator local_it = priv_find(key, hasher, equal, bucket_n);
\r
754 return const_iterator( local_it
\r
755 , uncast(this->priv_bucket_info())
\r
759 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
760 { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); }
\r
762 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
763 std::pair<iterator,iterator> equal_range
\r
764 (const KeyType &key, KeyHasher hasher, KeyValueEqual equal)
\r
766 size_type bucket_n1, bucket_n2, count;
\r
767 std::pair<local_iterator, local_iterator> ret
\r
768 = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);
\r
769 return std::pair<iterator, iterator>
\r
770 ( iterator( ret.first, this->priv_bucket_info(), bucket_n1)
\r
771 , iterator( ret.second, this->priv_bucket_info(), bucket_n2) );
\r
774 std::pair<const_iterator, const_iterator>
\r
775 equal_range(const value_type &value) const
\r
776 { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); }
\r
778 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
779 std::pair<const_iterator,const_iterator> equal_range
\r
780 (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const
\r
782 size_type bucket_n1, bucket_n2, count;
\r
783 std::pair<local_iterator, local_iterator> ret
\r
784 = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);
\r
785 return std::pair<const_iterator, const_iterator>
\r
786 ( const_iterator( ret.first, uncast(this->priv_bucket_info()), bucket_n1)
\r
787 , const_iterator( ret.second, uncast(this->priv_bucket_info()), bucket_n2) );
\r
790 size_type bucket_count() const
\r
791 { return this->priv_buckets_len(); }
\r
793 size_type bucket_size(size_type n)
\r
794 { return this->priv_buckets()[n].size(); }
\r
796 size_type bucket(const key_type& k)
\r
797 { return this->bucket(k, this->priv_hasher()); }
\r
799 template<class KeyType, class KeyHasher>
\r
800 size_type bucket(const KeyType& k, const KeyHasher &hasher)
\r
801 { return hasher(k) % this->priv_buckets_len(); }
\r
803 bucket_ptr bucket_pointer() const
\r
804 { return this->priv_buckets(); }
\r
806 local_iterator begin(size_type n)
\r
807 { return this->priv_buckets()[n].begin(); }
\r
809 const_local_iterator begin(size_type n) const
\r
810 { return const_cast<const bucket_type&>(this->priv_buckets()[n]).begin(); }
\r
812 local_iterator end(size_type n)
\r
813 { return this->priv_buckets()[n].end(); }
\r
815 const_local_iterator end(size_type n) const
\r
816 { return const_cast<const bucket_type&>(this->priv_buckets()[n]).end(); }
\r
818 void rehash(bucket_ptr new_buckets, size_type new_buckets_len)
\r
820 bucket_ptr old_buckets = this->priv_buckets();
\r
821 size_type old_buckets_len = this->priv_buckets_len();
\r
825 bool same_buffer = old_buckets == new_buckets;
\r
826 //If we are shrinking the bucket array, just rehash the last nodes
\r
827 if(same_buffer && (old_buckets_len > new_buckets_len)){
\r
828 n = new_buckets_len;
\r
831 //Iterate through nodes
\r
832 for(; n < old_buckets_len; ++n){
\r
833 bucket_type &old_bucket = old_buckets[n];
\r
834 local_iterator before_i(old_bucket.before_begin());
\r
835 local_iterator end(old_bucket.end());
\r
836 local_iterator i(old_bucket.begin());
\r
837 for(;i != end; ++i){
\r
838 size_type new_n = this->priv_hasher()(*i) % new_buckets_len;
\r
839 //If this is a buffer expansion don't move if it's not necessary
\r
840 if(same_buffer && new_n == n){
\r
844 bucket_type &new_b = new_buckets[new_n];
\r
845 new_b.splice_after(new_b.before_begin(), old_bucket, before_i);
\r
851 this->priv_buckets() = new_buckets;
\r
852 this->priv_buckets_len() = new_buckets_len;
\r
855 for(size_type n = 0; n < new_buckets_len; ++n){
\r
856 new_buckets[n].clear();
\r
857 old_buckets[n].clear();
\r
859 size_traits::set_size(size_type(0));
\r
864 iterator current(value_type &value)
\r
866 return iterator( bucket_type::current(value)
\r
867 , this->priv_bucket_info()
\r
868 , this->priv_hasher()(value) % this->priv_buckets_len());
\r
871 const_iterator current(const value_type &value) const
\r
873 return const_iterator( bucket_type::current(const_cast<value_type&>(value))
\r
874 , uncast(this->priv_bucket_info())
\r
875 , this->priv_hasher()(value) % this->priv_buckets_len());
\r
878 static local_iterator current_local(value_type &value)
\r
879 { return bucket_type::current(value); }
\r
881 static const_local_iterator current_local(const value_type &value)
\r
882 { return bucket_type::current(value); }
\r
885 static size_type suggested_upper_bucket_count(size_type n)
\r
887 const std::size_t *primes = &prime_list_holder<0>::prime_list[0];
\r
888 const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;
\r
889 size_type const* bound =
\r
890 std::lower_bound(primes, primes_end, n);
\r
891 if(bound == primes_end)
\r
893 return size_type(*bound);
\r
897 static size_type suggested_lower_bucket_count(size_type n)
\r
899 const std::size_t *primes = &prime_list_holder<0>::prime_list[0];
\r
900 const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;
\r
901 size_type const* bound =
\r
902 std::upper_bound(primes, primes_end, n);
\r
903 if(bound != primes_end)
\r
905 return size_type(*bound);
\r
910 static local_iterator invalid_local_it(const bucket_info_t &b)
\r
911 { return b.buckets_->end(); }
\r
913 local_iterator priv_begin(size_type &bucket_num) const
\r
915 size_type buckets_len = this->priv_buckets_len();
\r
916 for (bucket_num = 0; bucket_num < buckets_len; ++bucket_num){
\r
917 bucket_type &b = this->priv_buckets()[bucket_num];
\r
921 return invalid_local_it(*this->priv_bucket_info());
\r
924 void priv_clear_buckets()
\r
925 { priv_clear_buckets(this->priv_buckets(), this->priv_buckets_len()); }
\r
927 static void priv_clear_buckets(bucket_ptr buckets_ptr, size_type buckets_len)
\r
929 for(; buckets_len--; ++buckets_ptr){
\r
930 buckets_ptr->clear();
\r
934 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
935 local_iterator priv_find
\r
936 ( const KeyType &key, KeyHasher hasher
\r
937 , KeyValueEqual equal, size_type &bucket_number) const
\r
939 size_type b_len(this->priv_buckets_len());
\r
940 bucket_number = hasher(key) % b_len;
\r
942 if(ConstantTimeSize && this->empty()){
\r
943 return invalid_local_it(*this->priv_bucket_info());
\r
946 bucket_type &b = this->priv_buckets()[bucket_number];
\r
947 local_iterator it = b.begin();
\r
949 while(it != b.end()){
\r
950 if(equal(key, *it)){
\r
956 return invalid_local_it(*this->priv_bucket_info());
\r
959 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
960 std::pair<local_iterator, local_iterator> priv_equal_range
\r
961 ( const KeyType &key
\r
963 , KeyValueEqual equal
\r
964 , size_type &bucket_number_first
\r
965 , size_type &bucket_number_second
\r
966 , size_type &count) const
\r
969 //Let's see if the element is present
\r
970 std::pair<local_iterator, local_iterator> to_return
\r
971 ( priv_find(key, hasher, equal, bucket_number_first)
\r
972 , invalid_local_it(*this->priv_bucket_info()));
\r
973 if(to_return.first == to_return.second){
\r
974 bucket_number_second = bucket_number_first;
\r
978 //If it's present, find the first that it's not equal in
\r
980 bucket_type &b = this->priv_buckets()[bucket_number_first];
\r
981 local_iterator it = to_return.first;
\r
984 while(it != b.end()){
\r
985 if(!equal(key, *it)){
\r
986 to_return.second = it;
\r
987 bucket_number_second = bucket_number_first;
\r
994 //If we reached the end, find the first, non-empty bucket
\r
995 for(bucket_number_second = bucket_number_first+1
\r
996 ; bucket_number_second != this->priv_buckets_len()
\r
997 ; ++bucket_number_second){
\r
998 bucket_type &b = this->priv_buckets()[bucket_number_second];
\r
1000 to_return.second = b.begin();
\r
1005 //Otherwise, return the end node
\r
1006 to_return.second = invalid_local_it(*this->priv_bucket_info());
\r
1011 } //namespace detail
\r
1012 } //namespace intrusive
\r
1013 } //namespace boost
\r
1015 #include "config_end.hpp"
\r
1017 #endif //BOOST_INTRUSIVE_IHASHTABLE_HPP
\r