--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Ion Gazta�aga 2006-2007\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+#ifndef BOOST_INTRUSIVE_IHASHTABLE_HPP\r
+#define BOOST_INTRUSIVE_IHASHTABLE_HPP\r
+\r
+#include "config_begin.hpp"\r
+//std C++\r
+#include <functional>\r
+#include <iterator>\r
+#include <utility>\r
+#include <algorithm>\r
+//boost\r
+#include <boost/utility.hpp>\r
+#include <boost/compressed_pair.hpp>\r
+#include <boost/assert.hpp>\r
+#include <boost/static_assert.hpp>\r
+#include <boost/functional/hash.hpp>\r
+//General intrusive utilities\r
+#include "pointer_type.hpp"\r
+#include "pointer_to_other.hpp"\r
+#include "../linking_policy.hpp"\r
+//Implementation utilities\r
+#include "../iunordered_set_hook.hpp"\r
+#include "../islist.hpp"\r
+#include <cstddef>\r
+#include <iterator>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+namespace detail {\r
+\r
+template<int Dummy = 0>\r
+struct prime_list_holder\r
+{\r
+ static const std::size_t prime_list[];\r
+ static const std::size_t prime_list_size;\r
+};\r
+\r
+template<int Dummy>\r
+const std::size_t prime_list_holder<Dummy>::prime_list[] = {\r
+ 53ul, 97ul, 193ul, 389ul, 769ul,\r
+ 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,\r
+ 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,\r
+ 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,\r
+ 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\r
+ 1610612741ul, 3221225473ul, 4294967291ul };\r
+\r
+template<int Dummy>\r
+const std::size_t prime_list_holder<Dummy>::prime_list_size\r
+ = sizeof(prime_list)/sizeof(std::size_t);\r
+\r
+//! The class template ihashtable is an intrusive hash table container, that\r
+//! is used to construct intrusive unordered_set and unordered_multiset containers. The\r
+//! no-throw guarantee holds only, if the Equal object and Hasher don't throw.\r
+template< class ValueTraits\r
+ , class Hash = boost::hash<typename ValueTraits::value_type>\r
+ , class Equal = std::equal_to<typename ValueTraits::value_type>\r
+ , bool ConstantTimeSize = true\r
+ , class SizeType = std::size_t\r
+ >\r
+class ihashtable\r
+ : private detail::size_holder<ConstantTimeSize, SizeType>\r
+{\r
+ private:\r
+ template<class T, class Self, class NodeTraits>\r
+ class hashtable_iterator;\r
+\r
+ typedef islist<ValueTraits, false, SizeType> islist_impl;\r
+\r
+ struct bucket_type_impl\r
+ : private islist_impl\r
+ {\r
+ friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>;\r
+\r
+ bucket_type_impl()\r
+ {}\r
+\r
+ bucket_type_impl(const bucket_type_impl &)\r
+ {}\r
+\r
+ bucket_type_impl &operator=(const bucket_type_impl&)\r
+ { islist_impl::clear(); }\r
+ };\r
+\r
+ static islist_impl &islist_from_bucket(bucket_type_impl &b)\r
+ { return static_cast<islist_impl&>(b); }\r
+\r
+ static const islist_impl &islist_from_bucket(const bucket_type_impl &b)\r
+ { return static_cast<const islist_impl&>(b); }\r
+\r
+ typedef ihashtable<ValueTraits, Hash, Equal\r
+ ,ConstantTimeSize, SizeType> this_type; \r
+ typedef typename ValueTraits::node_traits node_traits;\r
+ typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;\r
+\r
+ //noncopyable\r
+ ihashtable (const ihashtable&);\r
+ ihashtable operator =(const ihashtable&);\r
+\r
+ public:\r
+ typedef typename ValueTraits::value_type value_type;\r
+ typedef typename ValueTraits::pointer pointer;\r
+ typedef typename ValueTraits::const_pointer const_pointer;\r
+ typedef value_type& reference;\r
+ typedef const value_type& const_reference;\r
+ typedef SizeType size_type;\r
+ typedef typename std::iterator_traits\r
+ <pointer>::difference_type difference_type;\r
+ typedef value_type key_type;\r
+ typedef Hash hasher;\r
+ typedef Equal key_equal;\r
+ typedef bucket_type_impl bucket_type;\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, bucket_type>::type bucket_ptr;\r
+ typedef typename islist_impl::iterator local_iterator;\r
+ typedef typename islist_impl::const_iterator const_local_iterator;\r
+\r
+ class const_iterator;\r
+ class iterator;\r
+\r
+ private:\r
+ typedef typename node_traits::node node;\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, node>::type node_ptr;\r
+ typedef typename boost::pointer_to_other\r
+ <node_ptr, const node>::type const_node_ptr;\r
+ //typedef hashtable_algorithms<node_traits> node_algorithms;\r
+ typedef slist_algorithms<node_traits> node_algorithms;\r
+ enum { safemode_or_autounlink = \r
+ (int)ValueTraits::linking_policy == (int)auto_unlink ||\r
+ (int)ValueTraits::linking_policy == (int)safe_mode_link };\r
+\r
+ //Constant-time size is incompatible with auto-unlink hooks!\r
+ BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
+\r
+ struct bucket_info_t\r
+ {\r
+ bucket_ptr buckets_;\r
+ size_type buckets_len_;\r
+ } ;\r
+\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, bucket_info_t>::type bucket_info_ptr;\r
+\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, const bucket_info_t>::type const_bucket_info_ptr;\r
+\r
+ //User scattered boost::compressed pair to get EBO all compilers\r
+ boost::compressed_pair\r
+ <boost::compressed_pair<bucket_info_t, Hash>\r
+ ,Equal> members_;\r
+\r
+ const Equal &priv_equal() const\r
+ { return members_.second(); }\r
+\r
+ Equal &priv_equal()\r
+ { return members_.second(); }\r
+\r
+ const_bucket_info_ptr priv_bucket_info() const\r
+ { return &members_.first().first(); }\r
+\r
+ bucket_info_ptr priv_bucket_info()\r
+ { return &members_.first().first(); }\r
+\r
+ const Hash &priv_hasher() const\r
+ { return members_.first().second(); }\r
+\r
+ Hash &priv_hasher()\r
+ { return members_.first().second(); }\r
+\r
+ const bucket_ptr &priv_buckets() const\r
+ { return members_.first().first().buckets_; }\r
+\r
+ bucket_ptr &priv_buckets()\r
+ { return members_.first().first().buckets_; }\r
+\r
+ const size_type &priv_buckets_len() const\r
+ { return members_.first().first().buckets_len_; }\r
+\r
+ size_type &priv_buckets_len()\r
+ { return members_.first().first().buckets_len_; }\r
+\r
+ static node_ptr uncast(const_node_ptr ptr)\r
+ {\r
+ using boost::get_pointer;\r
+ return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
+ }\r
+\r
+ static bucket_info_ptr uncast(const_bucket_info_ptr ptr)\r
+ {\r
+ using boost::get_pointer;\r
+ return bucket_info_ptr(const_cast<bucket_info_t*>(get_pointer(ptr)));\r
+ }\r
+\r
+ template<class T, class Self, class NodeTraits>\r
+ class hashtable_iterator\r
+ : public std::iterator<std::forward_iterator_tag, T>\r
+ {\r
+ protected:\r
+ explicit hashtable_iterator\r
+ (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
+ : local_it_ (ptr), bucket_info_ (bucket_info), n_bucket_ (n_bucket)\r
+ {}\r
+\r
+ public:\r
+ hashtable_iterator ()\r
+ {}\r
+\r
+ Self& operator++()\r
+ {\r
+ using boost::get_pointer;\r
+ ++local_it_;\r
+ size_type buckets_len = bucket_info_->buckets_len_;\r
+ bucket_ptr buckets = bucket_info_->buckets_;\r
+ while (local_it_ == islist_from_bucket(buckets[n_bucket_]).end()){\r
+ if (++n_bucket_ == buckets_len) {\r
+ local_it_ = invalid_local_it(*bucket_info_);\r
+ break;\r
+ }\r
+ local_it_ = islist_from_bucket(buckets[n_bucket_]).begin();\r
+ }\r
+ return static_cast<Self&> (*this);\r
+ }\r
+\r
+ Self operator++(int)\r
+ {\r
+ Self result(local_it_, bucket_info_, n_bucket_);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ bool operator== (const Self& i) const\r
+ { return local_it_ == i.local(); }\r
+\r
+ bool operator!= (const Self& i) const\r
+ { return !operator== (i); }\r
+\r
+ Self &set_internals\r
+ (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
+ {\r
+ local_it_ = ptr; bucket_info_ = bucket_info; n_bucket_ = n_bucket;\r
+ return static_cast<Self&>(*this);\r
+ }\r
+\r
+ local_iterator local() const\r
+ { return local_it_; }\r
+\r
+ bucket_info_ptr priv_bucket_info() const\r
+ { return bucket_info_; }\r
+\r
+ size_type bucket_num() const\r
+ { return n_bucket_; }\r
+\r
+ private:\r
+ local_iterator local_it_;\r
+ bucket_info_ptr bucket_info_;\r
+ size_type n_bucket_;\r
+ };\r
+\r
+ public:\r
+\r
+ class iterator\r
+ : public hashtable_iterator <value_type, iterator, node_traits>\r
+ {\r
+ private:\r
+ typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::pointer private_pointer;\r
+ typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::reference private_reference;\r
+ typedef hashtable_iterator<private_vt, iterator, node_traits> inherited;\r
+\r
+ public:\r
+ iterator()\r
+ {}\r
+\r
+ private_pointer operator->() const\r
+ { return &*this->local(); }\r
+\r
+ private_reference operator*() const\r
+ { return *this->local(); }\r
+\r
+ private:\r
+ explicit iterator\r
+ (local_iterator local_it, bucket_info_ptr bucket_info, size_type n_bucket)\r
+ : inherited(local_it, bucket_info, n_bucket)\r
+ {}\r
+\r
+ friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>; \r
+ friend class hashtable_iterator<private_vt, iterator, node_traits>;\r
+ friend class const_iterator;\r
+ };\r
+\r
+ class const_iterator\r
+ : public hashtable_iterator<const value_type, const_iterator, node_traits>\r
+ {\r
+ private:\r
+ typedef const typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_pointer private_pointer;\r
+ typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_reference private_reference;\r
+ typedef hashtable_iterator<private_vt, const_iterator, node_traits> inherited;\r
+\r
+ public:\r
+ const_iterator()\r
+ {}\r
+\r
+ const_iterator(const typename ihashtable::iterator& it)\r
+ : inherited (it.local(), it.priv_bucket_info(), it.bucket_num())\r
+ {}\r
+\r
+ const_iterator & operator=(const typename ihashtable::iterator& it)\r
+ { return inherited::set_internals(it.local(), it.priv_bucket_info(), it.bucket_num()); }\r
+\r
+ private_pointer operator->() const\r
+ { return &*this->local(); }\r
+\r
+ private_reference operator*() const\r
+ { return *this->local(); }\r
+\r
+ private:\r
+ explicit const_iterator\r
+ (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
+ : inherited(ptr, bucket_info, n_bucket)\r
+ {}\r
+\r
+ friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>; \r
+ friend class hashtable_iterator<private_vt, const_iterator, node_traits>;\r
+ };\r
+\r
+ //typedef typename node_algorithms::insert_commit_data insert_commit_data;\r
+ struct insert_commit_data\r
+ {\r
+ local_iterator prev_pos;\r
+ size_type bucket_num;\r
+ };\r
+\r
+ ihashtable( bucket_ptr buckets\r
+ , size_type buckets_len\r
+ , const Hash & hasher = Hash()\r
+ , const Equal &equal = Equal()) \r
+ : members_(boost::compressed_pair<bucket_info_t, Hash>(hasher)/*hasher*/, equal)\r
+ {\r
+ \r
+ BOOST_ASSERT(buckets_len != 0);\r
+ priv_buckets() = buckets;\r
+ priv_buckets_len() = buckets_len;\r
+ priv_clear_buckets();\r
+ size_traits::set_size(size_type(0));\r
+ }\r
+\r
+ ~ihashtable() \r
+ { this->clear(); }\r
+\r
+ iterator begin()\r
+ {\r
+ size_type bucket_num;\r
+ local_iterator local_it = priv_begin(bucket_num);\r
+ return iterator( local_it\r
+ , this->priv_bucket_info()\r
+ , bucket_num);\r
+ }\r
+\r
+ const_iterator begin() const\r
+ {\r
+ size_type bucket_num;\r
+ local_iterator local_it = priv_begin(bucket_num);\r
+ return const_iterator( local_it\r
+ , uncast(this->priv_bucket_info())\r
+ , bucket_num);\r
+ }\r
+\r
+ iterator end()\r
+ {\r
+ using boost::get_pointer;\r
+ bucket_info_t *info = get_pointer(this->priv_bucket_info());\r
+ return iterator(invalid_local_it(*info), 0, info->buckets_len_);\r
+ }\r
+\r
+ const_iterator end() const\r
+ {\r
+ using boost::get_pointer;\r
+ const bucket_info_t *info = get_pointer(this->priv_bucket_info());\r
+ return const_iterator(invalid_local_it(*info), 0, info->buckets_len_);\r
+ }\r
+\r
+ hasher hash_function() const\r
+ { return this->priv_hasher(); }\r
+\r
+ key_equal key_eq() const\r
+ { return this->priv_equal(); }\r
+\r
+ bool empty() const\r
+ {\r
+ if(ConstantTimeSize){\r
+ return !size();\r
+ }\r
+ else{\r
+ using boost::get_pointer;\r
+ size_type buckets_len = this->priv_buckets_len();\r
+ const bucket_type *b = get_pointer(this->priv_buckets());\r
+ for (size_type n = 0; n < buckets_len; ++n, ++b){\r
+ if(!b->empty()){\r
+ return false;\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+ }\r
+\r
+ size_type size() const\r
+ {\r
+ if(ConstantTimeSize)\r
+ return size_traits::get_size();\r
+ else{\r
+ size_type len = 0;\r
+ using boost::get_pointer;\r
+ size_type buckets_len = this->priv_buckets_len();\r
+ const bucket_type *b = get_pointer(this->priv_buckets());\r
+ for (size_type n = 0; n < buckets_len; ++n, ++b){\r
+ len += b->size();\r
+ }\r
+ return len;\r
+ }\r
+ }\r
+\r
+ void swap(ihashtable& other)\r
+ {\r
+ using std::swap;\r
+ //These can throw\r
+ swap(this->priv_equal(), other.priv_equal());\r
+ swap(this->priv_hasher(), other.priv_hasher());\r
+ //These can't throw\r
+ swap(this->priv_buckets(), other.priv_buckets());\r
+ swap(this->priv_buckets_len(), other.priv_buckets_len());\r
+ if(ConstantTimeSize){\r
+ size_type backup = size_traits::get_size();\r
+ size_traits::set_size(other.get_size());\r
+ other.set_size(backup);\r
+ }\r
+ }\r
+\r
+ template <class Cloner, class Destroyer>\r
+ void clone_from(const ihashtable &src, Cloner cloner, Destroyer destroyer)\r
+ {\r
+ this->clear_and_destroy(destroyer);\r
+ if(!ConstantTimeSize || !src.empty()){\r
+ const size_type src_bucket_count = src.bucket_count();\r
+ const size_type dst_bucket_count = this->bucket_count();\r
+\r
+ //If src bucket count is bigger or equal, structural copy is possible\r
+ if(src_bucket_count >= dst_bucket_count){\r
+ //First clone the first ones\r
+ const bucket_ptr src_buckets = src.priv_buckets();\r
+ const bucket_ptr dst_buckets = this->priv_buckets();\r
+ size_type constructed;\r
+ try{\r
+ for( constructed = 0\r
+ ; constructed < dst_bucket_count\r
+ ; ++constructed){\r
+ dst_buckets[constructed].clone_and_reverse_from(src_buckets[constructed], cloner, destroyer);\r
+ }\r
+ if(src_bucket_count != dst_bucket_count){\r
+ //Now insert the remaining ones using the modulo trick\r
+ for(//"constructed" comes from the previous loop\r
+ ; constructed < src_bucket_count\r
+ ; ++constructed){\r
+ bucket_type &dst_b = dst_buckets[constructed % dst_bucket_count];\r
+ bucket_type &src_b = src_buckets[constructed];\r
+ for( local_iterator b(src_b.begin()), e(src_b.end())\r
+ ; b != e\r
+ ; ++b){\r
+ dst_b.push_front(*cloner(*b));\r
+ }\r
+ }\r
+ }\r
+ }\r
+ catch(...){\r
+ while(constructed--){\r
+ dst_buckets[constructed].clear_and_destroy(destroyer);\r
+ }\r
+ throw;\r
+ }\r
+ size_traits::set_size(src.get_size());\r
+ }\r
+ else{\r
+ //Unlike previous cloning algorithm, this can throw\r
+ //if cloner, the hasher or comparison functor throw\r
+ const_iterator b(src.begin()), e(src.end());\r
+ try{\r
+ for(; b != e; ++b){\r
+ this->insert_equal(*cloner(*b));\r
+ }\r
+ }\r
+ catch(...){\r
+ this->clear_and_destroy(destroyer);\r
+ throw;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ iterator insert_equal(value_type &value)\r
+ {\r
+ size_type bucket_num;\r
+ local_iterator it = priv_find(value, this->priv_hasher(), this->priv_equal(), bucket_num);\r
+ bucket_type &b = this->priv_buckets()[bucket_num];\r
+ if(it == invalid_local_it(*this->priv_bucket_info())){\r
+ it = b.before_begin();\r
+ }\r
+ size_traits::increment();\r
+ return iterator(b.insert_after(it, value), this->priv_bucket_info(), bucket_num);\r
+ }\r
+\r
+ template<class Iterator>\r
+ void insert_equal(Iterator b, Iterator e)\r
+ {\r
+ for (; b != e; ++b)\r
+ this->insert_equal(*b);\r
+ }\r
+\r
+ std::pair<iterator, bool> insert_unique(value_type &value)\r
+ {\r
+ insert_commit_data commit_data;\r
+ std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);\r
+ if(!ret.second)\r
+ return ret;\r
+ return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);\r
+ }\r
+\r
+ template<class Iterator>\r
+ void insert_unique(Iterator b, Iterator e)\r
+ {\r
+ for (; b != e; ++b)\r
+ this->insert_unique(*b);\r
+ }\r
+\r
+ std::pair<iterator, bool> insert_unique_check\r
+ (const value_type &value, insert_commit_data &commit_data)\r
+ { return insert_unique_check(value, this->priv_hasher(), this->priv_equal(), commit_data); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ std::pair<iterator, bool> insert_unique_check\r
+ ( const KeyType &key\r
+ , KeyHasher hasher\r
+ , KeyValueEqual key_value_eq\r
+ , insert_commit_data &commit_data)\r
+ {\r
+ commit_data.prev_pos = \r
+ priv_find(key, hasher, key_value_eq, commit_data.bucket_num);\r
+ bool success = commit_data.prev_pos == invalid_local_it(*this->priv_bucket_info());\r
+ if(success){\r
+ commit_data.prev_pos = this->priv_buckets()[commit_data.bucket_num].before_begin();\r
+ }\r
+ return std::pair<iterator, bool>\r
+ (iterator(commit_data.prev_pos, this->priv_bucket_info(), commit_data.bucket_num)\r
+ ,success);\r
+ }\r
+\r
+ iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)\r
+ {\r
+ bucket_type &b = this->priv_buckets()[commit_data.bucket_num];\r
+ size_traits::increment();\r
+ return iterator( b.insert_after(commit_data.prev_pos, value)\r
+ , this->priv_bucket_info()\r
+ , commit_data.bucket_num);\r
+ }\r
+\r
+ void erase(const_iterator i)\r
+ { erase_and_destroy(i, detail::null_destroyer()); }\r
+\r
+ void erase(const_iterator b, const_iterator e)\r
+ { erase_and_destroy(b, e, detail::null_destroyer()); }\r
+\r
+ size_type erase(const value_type &value)\r
+ { return this->erase(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
+ { return erase_and_destroy(key, hasher, equal, detail::null_destroyer()); }\r
+\r
+ template<class Destroyer>\r
+ void erase_and_destroy(const_iterator i, Destroyer destroyer)\r
+ {\r
+ local_iterator to_erase(i.local());\r
+ size_type n_bucket = i.bucket_num();\r
+ bucket_type &b = this->priv_buckets()[n_bucket];\r
+ b.erase_after_and_destroy(b.previous(to_erase), destroyer);\r
+ size_traits::decrement();\r
+ }\r
+\r
+ template<class Destroyer>\r
+ void erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)\r
+ {\r
+ if(b == e) return;\r
+\r
+ //Get the bucket number and local iterator for both iterators\r
+ size_type first_bucket_num\r
+ = b.bucket_num();\r
+ local_iterator before_first_local_it\r
+ = priv_buckets()[first_bucket_num].previous(b.local());\r
+ size_type last_bucket_num;\r
+ local_iterator last_local_it;\r
+\r
+ //For the end iterator, we will assign the end iterator\r
+ //of the last bucket\r
+ if(e == end()){\r
+ last_bucket_num = this->bucket_count() - 1;\r
+ last_local_it = priv_buckets()[last_bucket_num].end();\r
+ }\r
+ else{\r
+ last_bucket_num = e.bucket_num();\r
+ last_local_it = e.local();\r
+ }\r
+\r
+ const bucket_ptr buckets = priv_buckets();\r
+ //First erase the nodes of the first bucket\r
+ {\r
+ bucket_type &first_b = buckets[first_bucket_num];\r
+ local_iterator nxt(before_first_local_it); ++nxt;\r
+ local_iterator end = first_b.end();\r
+ while(nxt != end){\r
+ nxt = first_b.erase_after_and_destroy(before_first_local_it, destroyer);\r
+ size_traits::decrement();\r
+ }\r
+ }\r
+\r
+ //Now fully clear the intermediate buckets\r
+ for(size_type i = first_bucket_num+1; i < last_bucket_num; ++i){\r
+ bucket_type &b = buckets[i];\r
+ if(b.empty())\r
+ continue;\r
+ local_iterator b_begin(b.before_begin());\r
+ local_iterator nxt(b_begin); ++nxt;\r
+ local_iterator end = b.end();\r
+ while(nxt != end){\r
+ nxt = b.erase_after_and_destroy(b_begin, destroyer);\r
+ size_traits::decrement();\r
+ }\r
+ }\r
+\r
+ //Now erase nodes from the last bucket\r
+ {\r
+ bucket_type &last_b = buckets[last_bucket_num];\r
+ local_iterator b_begin(last_b.before_begin());\r
+ local_iterator nxt(b_begin); ++nxt;\r
+ while(nxt != last_local_it){\r
+ nxt = last_b.erase_after_and_destroy(b_begin, destroyer);\r
+ size_traits::decrement();\r
+ }\r
+ }\r
+ }\r
+\r
+ template<class Destroyer>\r
+ size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
+ { return erase_and_destroy(value, priv_hasher(), priv_equal(), destroyer); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
+ size_type erase_and_destroy(const KeyType& key, KeyHasher hasher\r
+ ,KeyValueEqual equal, Destroyer destroyer)\r
+ {\r
+ size_type count(0);\r
+\r
+ if(ConstantTimeSize && this->empty()){\r
+ return 0;\r
+ }\r
+\r
+ bucket_type &b = this->priv_buckets()[hasher(key) % this->priv_buckets_len()];\r
+ local_iterator it = b.begin();\r
+ local_iterator prev = b.before_begin();\r
+\r
+ bool found = false;\r
+ //Find equal value\r
+ while(it != b.end()){\r
+ if(equal(key, *it)){\r
+ found = true;\r
+ break;\r
+ }\r
+ ++prev;\r
+ ++it;\r
+ }\r
+ \r
+ if(!found)\r
+ return 0;\r
+\r
+ //If found erase all equal values\r
+ for(local_iterator end = b.end(); it != end && equal(key, *it); ++count){\r
+ it = b.erase_after_and_destroy(prev, destroyer);\r
+ size_traits::decrement();\r
+ }\r
+ return count;\r
+ }\r
+\r
+ void clear()\r
+ {\r
+ if(safemode_or_autounlink){\r
+ priv_clear_buckets();\r
+ }\r
+ size_traits::set_size(size_type(0));\r
+ }\r
+\r
+ template<class Destroyer>\r
+ void clear_and_destroy(Destroyer destroyer)\r
+ {\r
+ if(!ConstantTimeSize || !this->empty()){\r
+ size_type num_buckets = this->bucket_count();\r
+ bucket_ptr b = this->priv_buckets();\r
+ for(; num_buckets--; ++b){\r
+ b->clear_and_destroy(destroyer);\r
+ }\r
+ size_traits::set_size(size_type(0));\r
+ }\r
+ }\r
+\r
+ size_type count(const value_type &value) const\r
+ { return this->count(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ size_type count(const KeyType &key, const KeyHasher &hasher, const KeyValueEqual &equal) const\r
+ {\r
+ size_type bucket_n1, bucket_n2, count;\r
+ priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
+ return count;\r
+ }\r
+\r
+ iterator find(const value_type &value)\r
+ { return find(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ iterator find(const KeyType &key, KeyHasher hasher, KeyValueEqual equal)\r
+ {\r
+ size_type bucket_n;\r
+ local_iterator local_it = priv_find(key, hasher, equal, bucket_n);\r
+ return iterator( local_it\r
+ , this->priv_bucket_info()\r
+ , bucket_n);\r
+ }\r
+\r
+ const_iterator find(const value_type &value) const\r
+ { return find(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ const_iterator find\r
+ (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const\r
+ {\r
+ size_type bucket_n;\r
+ local_iterator local_it = priv_find(key, hasher, equal, bucket_n);\r
+ return const_iterator( local_it\r
+ , uncast(this->priv_bucket_info())\r
+ , bucket_n);\r
+ }\r
+\r
+ std::pair<iterator,iterator> equal_range(const value_type &value)\r
+ { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ std::pair<iterator,iterator> equal_range\r
+ (const KeyType &key, KeyHasher hasher, KeyValueEqual equal)\r
+ {\r
+ size_type bucket_n1, bucket_n2, count;\r
+ std::pair<local_iterator, local_iterator> ret\r
+ = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
+ return std::pair<iterator, iterator>\r
+ ( iterator( ret.first, this->priv_bucket_info(), bucket_n1)\r
+ , iterator( ret.second, this->priv_bucket_info(), bucket_n2) );\r
+ }\r
+\r
+ std::pair<const_iterator, const_iterator>\r
+ equal_range(const value_type &value) const\r
+ { return this->equal_range(value, this->priv_hasher(), this->priv_equal()); }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ std::pair<const_iterator,const_iterator> equal_range\r
+ (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const\r
+ {\r
+ size_type bucket_n1, bucket_n2, count;\r
+ std::pair<local_iterator, local_iterator> ret\r
+ = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
+ return std::pair<const_iterator, const_iterator>\r
+ ( const_iterator( ret.first, uncast(this->priv_bucket_info()), bucket_n1)\r
+ , const_iterator( ret.second, uncast(this->priv_bucket_info()), bucket_n2) );\r
+ }\r
+\r
+ size_type bucket_count() const\r
+ { return this->priv_buckets_len(); }\r
+\r
+ size_type bucket_size(size_type n)\r
+ { return this->priv_buckets()[n].size(); }\r
+\r
+ size_type bucket(const key_type& k)\r
+ { return this->bucket(k, this->priv_hasher()); }\r
+\r
+ template<class KeyType, class KeyHasher>\r
+ size_type bucket(const KeyType& k, const KeyHasher &hasher)\r
+ { return hasher(k) % this->priv_buckets_len(); }\r
+\r
+ bucket_ptr bucket_pointer() const\r
+ { return this->priv_buckets(); }\r
+\r
+ local_iterator begin(size_type n)\r
+ { return this->priv_buckets()[n].begin(); }\r
+\r
+ const_local_iterator begin(size_type n) const\r
+ { return const_cast<const bucket_type&>(this->priv_buckets()[n]).begin(); }\r
+\r
+ local_iterator end(size_type n)\r
+ { return this->priv_buckets()[n].end(); }\r
+\r
+ const_local_iterator end(size_type n) const\r
+ { return const_cast<const bucket_type&>(this->priv_buckets()[n]).end(); }\r
+\r
+ void rehash(bucket_ptr new_buckets, size_type new_buckets_len)\r
+ {\r
+ bucket_ptr old_buckets = this->priv_buckets();\r
+ size_type old_buckets_len = this->priv_buckets_len();\r
+\r
+ try{\r
+ size_type n = 0;\r
+ bool same_buffer = old_buckets == new_buckets;\r
+ //If we are shrinking the bucket array, just rehash the last nodes\r
+ if(same_buffer && (old_buckets_len > new_buckets_len)){\r
+ n = new_buckets_len;\r
+ }\r
+\r
+ //Iterate through nodes\r
+ for(; n < old_buckets_len; ++n){\r
+ bucket_type &old_bucket = old_buckets[n];\r
+ local_iterator before_i(old_bucket.before_begin());\r
+ local_iterator end(old_bucket.end());\r
+ local_iterator i(old_bucket.begin());\r
+ for(;i != end; ++i){\r
+ size_type new_n = this->priv_hasher()(*i) % new_buckets_len;\r
+ //If this is a buffer expansion don't move if it's not necessary\r
+ if(same_buffer && new_n == n){\r
+ ++before_i;\r
+ }\r
+ else{\r
+ bucket_type &new_b = new_buckets[new_n];\r
+ new_b.splice_after(new_b.before_begin(), old_bucket, before_i);\r
+ i = before_i;\r
+ }\r
+ }\r
+ }\r
+\r
+ this->priv_buckets() = new_buckets;\r
+ this->priv_buckets_len() = new_buckets_len;\r
+ }\r
+ catch(...){\r
+ for(size_type n = 0; n < new_buckets_len; ++n){\r
+ new_buckets[n].clear();\r
+ old_buckets[n].clear();\r
+ }\r
+ size_traits::set_size(size_type(0));\r
+ throw;\r
+ }\r
+ }\r
+\r
+ iterator current(value_type &value)\r
+ {\r
+ return iterator( bucket_type::current(value)\r
+ , this->priv_bucket_info()\r
+ , this->priv_hasher()(value) % this->priv_buckets_len());\r
+ }\r
+\r
+ const_iterator current(const value_type &value) const\r
+ {\r
+ return const_iterator( bucket_type::current(const_cast<value_type&>(value))\r
+ , uncast(this->priv_bucket_info())\r
+ , this->priv_hasher()(value) % this->priv_buckets_len());\r
+ }\r
+\r
+ static local_iterator current_local(value_type &value)\r
+ { return bucket_type::current(value); }\r
+\r
+ static const_local_iterator current_local(const value_type &value)\r
+ { return bucket_type::current(value); }\r
+\r
+ // no throw\r
+ static size_type suggested_upper_bucket_count(size_type n)\r
+ {\r
+ const std::size_t *primes = &prime_list_holder<0>::prime_list[0];\r
+ const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;\r
+ size_type const* bound =\r
+ std::lower_bound(primes, primes_end, n);\r
+ if(bound == primes_end)\r
+ bound--;\r
+ return size_type(*bound);\r
+ }\r
+\r
+ // no throw\r
+ static size_type suggested_lower_bucket_count(size_type n)\r
+ {\r
+ const std::size_t *primes = &prime_list_holder<0>::prime_list[0];\r
+ const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;\r
+ size_type const* bound =\r
+ std::upper_bound(primes, primes_end, n);\r
+ if(bound != primes_end)\r
+ bound--;\r
+ return size_type(*bound);\r
+ }\r
+\r
+ private:\r
+\r
+ static local_iterator invalid_local_it(const bucket_info_t &b)\r
+ { return b.buckets_->end(); }\r
+\r
+ local_iterator priv_begin(size_type &bucket_num) const\r
+ {\r
+ size_type buckets_len = this->priv_buckets_len();\r
+ for (bucket_num = 0; bucket_num < buckets_len; ++bucket_num){\r
+ bucket_type &b = this->priv_buckets()[bucket_num];\r
+ if(!b.empty())\r
+ return b.begin();\r
+ }\r
+ return invalid_local_it(*this->priv_bucket_info());\r
+ }\r
+\r
+ void priv_clear_buckets()\r
+ { priv_clear_buckets(this->priv_buckets(), this->priv_buckets_len()); }\r
+\r
+ static void priv_clear_buckets(bucket_ptr buckets_ptr, size_type buckets_len)\r
+ {\r
+ for(; buckets_len--; ++buckets_ptr){\r
+ buckets_ptr->clear();\r
+ }\r
+ }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ local_iterator priv_find\r
+ ( const KeyType &key, KeyHasher hasher\r
+ , KeyValueEqual equal, size_type &bucket_number) const\r
+ {\r
+ size_type b_len(this->priv_buckets_len());\r
+ bucket_number = hasher(key) % b_len;\r
+\r
+ if(ConstantTimeSize && this->empty()){\r
+ return invalid_local_it(*this->priv_bucket_info());\r
+ }\r
+ \r
+ bucket_type &b = this->priv_buckets()[bucket_number];\r
+ local_iterator it = b.begin();\r
+\r
+ while(it != b.end()){\r
+ if(equal(key, *it)){\r
+ return it;\r
+ }\r
+ ++it;\r
+ }\r
+\r
+ return invalid_local_it(*this->priv_bucket_info());\r
+ }\r
+\r
+ template<class KeyType, class KeyHasher, class KeyValueEqual>\r
+ std::pair<local_iterator, local_iterator> priv_equal_range\r
+ ( const KeyType &key\r
+ , KeyHasher hasher\r
+ , KeyValueEqual equal\r
+ , size_type &bucket_number_first\r
+ , size_type &bucket_number_second\r
+ , size_type &count) const\r
+ {\r
+ count = 0;\r
+ //Let's see if the element is present\r
+ std::pair<local_iterator, local_iterator> to_return\r
+ ( priv_find(key, hasher, equal, bucket_number_first)\r
+ , invalid_local_it(*this->priv_bucket_info()));\r
+ if(to_return.first == to_return.second){\r
+ bucket_number_second = bucket_number_first;\r
+ return to_return;\r
+ }\r
+ ++count;\r
+ //If it's present, find the first that it's not equal in\r
+ //the same bucket\r
+ bucket_type &b = this->priv_buckets()[bucket_number_first];\r
+ local_iterator it = to_return.first;\r
+ ++it;\r
+\r
+ while(it != b.end()){\r
+ if(!equal(key, *it)){\r
+ to_return.second = it;\r
+ bucket_number_second = bucket_number_first;\r
+ return to_return;\r
+ }\r
+ ++it;\r
+ ++count;\r
+ }\r
+ \r
+ //If we reached the end, find the first, non-empty bucket\r
+ for(bucket_number_second = bucket_number_first+1\r
+ ; bucket_number_second != this->priv_buckets_len()\r
+ ; ++bucket_number_second){\r
+ bucket_type &b = this->priv_buckets()[bucket_number_second];\r
+ if(!b.empty()){\r
+ to_return.second = b.begin();\r
+ return to_return;\r
+ }\r
+ }\r
+\r
+ //Otherwise, return the end node\r
+ to_return.second = invalid_local_it(*this->priv_bucket_info());\r
+ return to_return;\r
+ }\r
+};\r
+\r
+} //namespace detail\r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_IHASHTABLE_HPP\r
projects / senf.git / blobdiff