diff options
author | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:24:46 +0900 |
---|---|---|
committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:25:39 +0900 |
commit | 4fadd968fa12130524c8380f33fcfe25d4de79e5 (patch) | |
tree | fd26a490cd15388d42fc6652b3c5c13012e7f93e /boost/intrusive | |
parent | b5c87084afaef42b2d058f68091be31988a6a874 (diff) | |
download | boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.gz boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.bz2 boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.zip |
Imported Upstream version 1.65.0upstream/1.65.0
Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/intrusive')
-rw-r--r-- | boost/intrusive/bstree.hpp | 3 | ||||
-rw-r--r-- | boost/intrusive/detail/default_header_holder.hpp | 4 | ||||
-rw-r--r-- | boost/intrusive/detail/ebo_functor_holder.hpp | 2 | ||||
-rw-r--r-- | boost/intrusive/detail/hashtable_node.hpp | 2 | ||||
-rw-r--r-- | boost/intrusive/detail/hook_traits.hpp | 10 | ||||
-rw-r--r-- | boost/intrusive/detail/iterator.hpp | 110 | ||||
-rw-r--r-- | boost/intrusive/detail/node_to_value.hpp | 2 | ||||
-rw-r--r-- | boost/intrusive/detail/pointer_element.hpp | 168 | ||||
-rw-r--r-- | boost/intrusive/detail/to_raw_pointer.hpp | 47 | ||||
-rw-r--r-- | boost/intrusive/detail/tree_value_compare.hpp | 12 | ||||
-rw-r--r-- | boost/intrusive/hashtable.hpp | 127 | ||||
-rw-r--r-- | boost/intrusive/member_value_traits.hpp | 6 | ||||
-rw-r--r-- | boost/intrusive/pointer_traits.hpp | 4 |
13 files changed, 204 insertions, 293 deletions
diff --git a/boost/intrusive/bstree.hpp b/boost/intrusive/bstree.hpp index 1eeab55113..ac67e864a0 100644 --- a/boost/intrusive/bstree.hpp +++ b/boost/intrusive/bstree.hpp @@ -255,7 +255,8 @@ struct get_key_of_value<void, T> template<class ValuePtr, class VoidOrKeyOfValue, class VoidOrKeyComp> struct bst_key_types { - typedef typename pointer_element<ValuePtr>::type value_type; + typedef typename + boost::movelib::pointer_element<ValuePtr>::type value_type; typedef typename get_key_of_value < VoidOrKeyOfValue, value_type>::type key_of_value; typedef typename key_of_value::type key_type; diff --git a/boost/intrusive/detail/default_header_holder.hpp b/boost/intrusive/detail/default_header_holder.hpp index 288f8a0e41..ba561b5f5b 100644 --- a/boost/intrusive/detail/default_header_holder.hpp +++ b/boost/intrusive/detail/default_header_holder.hpp @@ -23,7 +23,7 @@ #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/to_raw_pointer.hpp> +#include <boost/move/detail/to_raw_pointer.hpp> namespace boost { namespace intrusive { @@ -48,7 +48,7 @@ struct default_header_holder : public NodeTraits::node // (unsafe) downcast used to implement container-from-iterator BOOST_INTRUSIVE_FORCEINLINE static default_header_holder* get_holder(const node_ptr &p) - { return static_cast< default_header_holder* >(boost::intrusive::detail::to_raw_pointer(p)); } + { return static_cast< default_header_holder* >(boost::movelib::to_raw_pointer(p)); } }; // type function producing the header node holder diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp index 31b2f81398..27415c1170 100644 --- a/boost/intrusive/detail/ebo_functor_holder.hpp +++ b/boost/intrusive/detail/ebo_functor_holder.hpp @@ -35,7 +35,7 @@ namespace detail { #define BOOST_INTRUSIVE_TT_DECL #endif -#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(UNDER_CE) +#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(_M_ARM64) && !defined(UNDER_CE) #define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS #endif diff --git a/boost/intrusive/detail/hashtable_node.hpp b/boost/intrusive/detail/hashtable_node.hpp index 8f8718e9a7..d3b11d1b22 100644 --- a/boost/intrusive/detail/hashtable_node.hpp +++ b/boost/intrusive/detail/hashtable_node.hpp @@ -246,7 +246,7 @@ class hashtable_iterator void increment() { const bucket_traits &rbuck_traits = this->priv_bucket_traits(); - bucket_type* const buckets = boost::intrusive::detail::to_raw_pointer(rbuck_traits.bucket_begin()); + bucket_type* const buckets = boost::movelib::to_raw_pointer(rbuck_traits.bucket_begin()); const size_type buckets_len = rbuck_traits.bucket_count(); ++slist_it_; diff --git a/boost/intrusive/detail/hook_traits.hpp b/boost/intrusive/detail/hook_traits.hpp index 2a16061a54..7a6f206ca2 100644 --- a/boost/intrusive/detail/hook_traits.hpp +++ b/boost/intrusive/detail/hook_traits.hpp @@ -26,7 +26,7 @@ #include <boost/intrusive/detail/parent_from_member.hpp> #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/detail/to_raw_pointer.hpp> +#include <boost/move/detail/to_raw_pointer.hpp> #include <boost/intrusive/detail/node_holder.hpp> namespace boost { @@ -128,14 +128,14 @@ struct mhtraits { return pointer_traits<pointer>::pointer_to (*detail::parent_from_member<T, Hook> - (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + (static_cast<Hook*>(boost::movelib::to_raw_pointer(n)), P)); } BOOST_INTRUSIVE_FORCEINLINE static const_pointer to_value_ptr(const const_node_ptr & n) { return pointer_traits<const_pointer>::pointer_to (*detail::parent_from_member<T, Hook> - (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + (static_cast<const Hook*>(boost::movelib::to_raw_pointer(n)), P)); } }; @@ -161,10 +161,10 @@ struct fhtraits static const link_mode_type link_mode = hook_type::hooktags::link_mode; static node_ptr to_node_ptr(reference value) - { return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + { return static_cast<node*>(boost::movelib::to_raw_pointer(Functor::to_hook_ptr(value))); } static const_node_ptr to_node_ptr(const_reference value) - { return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + { return static_cast<const node*>(boost::movelib::to_raw_pointer(Functor::to_hook_ptr(value))); } static pointer to_value_ptr(const node_ptr & n) { return Functor::to_value_ptr(to_hook_ptr(n)); } diff --git a/boost/intrusive/detail/iterator.hpp b/boost/intrusive/detail/iterator.hpp index 2ae6abb7d0..c25be430a2 100644 --- a/boost/intrusive/detail/iterator.hpp +++ b/boost/intrusive/detail/iterator.hpp @@ -27,6 +27,24 @@ #include <boost/move/detail/iterator_traits.hpp> #include <boost/move/detail/meta_utils_core.hpp> +namespace boost{ +namespace iterators{ + +struct incrementable_traversal_tag; +struct single_pass_traversal_tag; +struct forward_traversal_tag; +struct bidirectional_traversal_tag; +struct random_access_traversal_tag; + +namespace detail{ + +template <class Category, class Traversal> +struct iterator_category_with_traversal; + +} //namespace boost{ +} //namespace iterators{ +} //namespace detail{ + namespace boost { namespace intrusive { @@ -46,6 +64,28 @@ struct iterator }; //////////////////////////////////////// +// iterator_[dis|en]able_if_boost_iterator +//////////////////////////////////////// +template<class I> +struct is_boost_iterator +{ + static const bool value = false; +}; + +template<class Category, class Traversal> +struct is_boost_iterator< boost::iterators::detail::iterator_category_with_traversal<Category, Traversal> > +{ + static const bool value = true; +}; + +template<class I, class R = void> +struct iterator_enable_if_boost_iterator + : ::boost::move_detail::enable_if_c + < is_boost_iterator<typename boost::intrusive::iterator_traits<I>::iterator_category >::value + , R> +{}; + +//////////////////////////////////////// // iterator_[dis|en]able_if_tag //////////////////////////////////////// template<class I, class Tag, class R = void> @@ -69,6 +109,23 @@ struct iterator_disable_if_tag {}; //////////////////////////////////////// +// iterator_[dis|en]able_if_tag +//////////////////////////////////////// +template<class I, class Tag, class Tag2, class R = void> +struct iterator_enable_if_convertible_tag + : ::boost::move_detail::enable_if_c + < ::boost::move_detail::is_same_or_convertible + < typename boost::intrusive::iterator_traits<I>::iterator_category + , Tag + >::value && + !::boost::move_detail::is_same_or_convertible + < typename boost::intrusive::iterator_traits<I>::iterator_category + , Tag2 + >::value + , R> +{}; + +//////////////////////////////////////// // iterator_[dis|en]able_if_tag_difference_type //////////////////////////////////////// template<class I, class Tag> @@ -84,8 +141,9 @@ struct iterator_disable_if_tag_difference_type //////////////////// // advance //////////////////// + template<class InputIt, class Distance> -typename iterator_enable_if_tag<InputIt, std::input_iterator_tag>::type +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::input_iterator_tag>::type iterator_advance(InputIt& it, Distance n) { while(n--) @@ -101,7 +159,7 @@ typename iterator_enable_if_tag<InputIt, std::forward_iterator_tag>::type } template<class InputIt, class Distance> -typename iterator_enable_if_tag<InputIt, std::bidirectional_iterator_tag>::type +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::bidirectional_iterator_tag>::type iterator_advance(InputIt& it, Distance n) { for (; 0 < n; --n) @@ -117,6 +175,54 @@ BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_tag<InputIt, std::random it += n; } +template<class InputIt, class Distance> +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag + <InputIt, const boost::iterators::incrementable_traversal_tag&, const boost::iterators::single_pass_traversal_tag&>::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag + <InputIt, const boost::iterators::single_pass_traversal_tag &, const boost::iterators::forward_traversal_tag&>::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag + <InputIt, const boost::iterators::forward_traversal_tag&, const boost::iterators::bidirectional_traversal_tag&>::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag + <InputIt, const boost::iterators::bidirectional_traversal_tag&, const boost::iterators::random_access_traversal_tag&>::type + iterator_advance(InputIt& it, Distance n) +{ + for (; 0 < n; --n) + ++it; + for (; n < 0; ++n) + --it; +} + +class fake{}; + +template<class InputIt, class Distance> +BOOST_INTRUSIVE_FORCEINLINE typename iterator_enable_if_convertible_tag + <InputIt, const boost::iterators::random_access_traversal_tag&, const fake&>::type + iterator_advance(InputIt& it, Distance n) +{ + it += n; +} + //////////////////// // distance //////////////////// diff --git a/boost/intrusive/detail/node_to_value.hpp b/boost/intrusive/detail/node_to_value.hpp index 5af3347345..218e78e4e0 100644 --- a/boost/intrusive/detail/node_to_value.hpp +++ b/boost/intrusive/detail/node_to_value.hpp @@ -59,7 +59,7 @@ struct constptr {} const void *get_ptr() const - { return boost::intrusive::detail::to_raw_pointer(const_void_ptr_); } + { return boost::movelib::to_raw_pointer(const_void_ptr_); } ConstVoidPtr const_void_ptr_; }; diff --git a/boost/intrusive/detail/pointer_element.hpp b/boost/intrusive/detail/pointer_element.hpp deleted file mode 100644 index dd26e3cf0b..0000000000 --- a/boost/intrusive/detail/pointer_element.hpp +++ /dev/null @@ -1,168 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2014-2014. Distributed under the Boost -// Software License, Version 1.0. (See accompanying file -// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -// -// See http://www.boost.org/libs/intrusive for documentation. -// -////////////////////////////////////////////////////////////////////////////// - -#ifndef BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP -#define BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP - -#ifndef BOOST_CONFIG_HPP -# include <boost/config.hpp> -#endif - -#if defined(BOOST_HAS_PRAGMA_ONCE) -# pragma once -#endif - -#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP -#include <boost/intrusive/detail/workaround.hpp> -#endif //BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP - -namespace boost { -namespace intrusive { -namespace detail{ - -////////////////////// -//struct first_param -////////////////////// - -template <typename T> struct first_param -{ typedef void type; }; - -#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template <template <typename, typename...> class TemplateClass, typename T, typename... Args> - struct first_param< TemplateClass<T, Args...> > - { - typedef T type; - }; - -#else //C++03 compilers - - template < template //0arg - <class - > class TemplateClass, class T - > - struct first_param - < TemplateClass<T> > - { typedef T type; }; - - template < template //1arg - <class,class - > class TemplateClass, class T - , class P0> - struct first_param - < TemplateClass<T, P0> > - { typedef T type; }; - - template < template //2arg - <class,class,class - > class TemplateClass, class T - , class P0, class P1> - struct first_param - < TemplateClass<T, P0, P1> > - { typedef T type; }; - - template < template //3arg - <class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2> - struct first_param - < TemplateClass<T, P0, P1, P2> > - { typedef T type; }; - - template < template //4arg - <class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3> - struct first_param - < TemplateClass<T, P0, P1, P2, P3> > - { typedef T type; }; - - template < template //5arg - <class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4> > - { typedef T type; }; - - template < template //6arg - <class,class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4, class P5> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4, P5> > - { typedef T type; }; - - template < template //7arg - <class,class,class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4, class P5, class P6> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6> > - { typedef T type; }; - - template < template //8arg - <class,class,class,class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7> > - { typedef T type; }; - - template < template //9arg - <class,class,class,class,class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8> > - { typedef T type; }; - -#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - -template <typename T> -struct has_internal_pointer_element -{ - template <typename X> - static char test(int, typename X::element_type*); - - template <typename X> - static int test(...); - - static const bool value = (1 == sizeof(test<T>(0, 0))); -}; - -template<class Ptr, bool = has_internal_pointer_element<Ptr>::value> -struct pointer_element_impl -{ - typedef typename Ptr::element_type type; -}; - -template<class Ptr> -struct pointer_element_impl<Ptr, false> -{ - typedef typename boost::intrusive::detail::first_param<Ptr>::type type; -}; - -} //namespace detail{ - -template <typename Ptr> -struct pointer_element -{ - typedef typename ::boost::intrusive::detail::pointer_element_impl<Ptr>::type type; -}; - -template <typename T> -struct pointer_element<T*> -{ typedef T type; }; - -} //namespace container { -} //namespace boost { - -#endif // defined(BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP) diff --git a/boost/intrusive/detail/to_raw_pointer.hpp b/boost/intrusive/detail/to_raw_pointer.hpp deleted file mode 100644 index 8ea884959d..0000000000 --- a/boost/intrusive/detail/to_raw_pointer.hpp +++ /dev/null @@ -1,47 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2014-2014 -// -// Distributed under the Boost Software License, Version 1.0. -// (See accompanying file LICENSE_1_0.txt or copy at -// http://www.boost.org/LICENSE_1_0.txt) -// -// See http://www.boost.org/libs/intrusive for documentation. -// -///////////////////////////////////////////////////////////////////////////// - -#ifndef BOOST_INTRUSIVE_DETAIL_TO_RAW_POINTER_HPP -#define BOOST_INTRUSIVE_DETAIL_TO_RAW_POINTER_HPP - -#ifndef BOOST_CONFIG_HPP -# include <boost/config.hpp> -#endif - -#if defined(BOOST_HAS_PRAGMA_ONCE) -# pragma once -#endif - -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/workaround.hpp> -#include <boost/intrusive/detail/pointer_element.hpp> - -namespace boost { -namespace intrusive { -namespace detail { - -template <class T> -BOOST_INTRUSIVE_FORCEINLINE T* to_raw_pointer(T* p) -{ return p; } - -template <class Pointer> -BOOST_INTRUSIVE_FORCEINLINE typename boost::intrusive::pointer_element<Pointer>::type* -to_raw_pointer(const Pointer &p) -{ return boost::intrusive::detail::to_raw_pointer(p.operator->()); } - -} //namespace detail -} //namespace intrusive -} //namespace boost - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP diff --git a/boost/intrusive/detail/tree_value_compare.hpp b/boost/intrusive/detail/tree_value_compare.hpp index c8f596fc96..f6dd01dc25 100644 --- a/boost/intrusive/detail/tree_value_compare.hpp +++ b/boost/intrusive/detail/tree_value_compare.hpp @@ -37,7 +37,8 @@ struct disable_if_smartref_to || detail::is_same <From, typename pointer_traits < typename pointer_rebind - <ValuePtr, const typename pointer_element<ValuePtr>::type>::type> + < ValuePtr + , const typename boost::movelib::pointer_element<ValuePtr>::type>::type> ::reference>::value > {}; @@ -45,11 +46,13 @@ struct disable_if_smartref_to //This function object takes a KeyCompare function object //and compares values that contains keys using KeyOfValue template< class ValuePtr, class KeyCompare, class KeyOfValue - , bool = boost::intrusive::detail::is_same<typename pointer_element<ValuePtr>::type, typename KeyOfValue::type>::value > + , bool = boost::intrusive::detail::is_same + <typename boost::movelib::pointer_element<ValuePtr>::type, typename KeyOfValue::type>::value > struct tree_value_compare : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> { - typedef typename pointer_element<ValuePtr>::type value_type; + typedef typename + boost::movelib::pointer_element<ValuePtr>::type value_type; typedef KeyCompare key_compare; typedef KeyOfValue key_of_value; typedef typename KeyOfValue::type key_type; @@ -114,7 +117,8 @@ template<class ValuePtr, class KeyCompare, class KeyOfValue> struct tree_value_compare<ValuePtr, KeyCompare, KeyOfValue, true> : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> { - typedef typename pointer_element<ValuePtr>::type value_type; + typedef typename + boost::movelib::pointer_element<ValuePtr>::type value_type; typedef KeyCompare key_compare; typedef KeyOfValue key_of_value; typedef typename KeyOfValue::type key_type; diff --git a/boost/intrusive/hashtable.hpp b/boost/intrusive/hashtable.hpp index 313da829d3..bae9d52485 100644 --- a/boost/intrusive/hashtable.hpp +++ b/boost/intrusive/hashtable.hpp @@ -117,6 +117,24 @@ struct prime_list_holder { static const std::size_t prime_list[]; static const std::size_t prime_list_size; + + static std::size_t suggested_upper_bucket_count(std::size_t n) + { + const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; + const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; + std::size_t const* bound = std::lower_bound(primes, primes_end, n); + bound -= (bound == primes_end); + return *bound; + } + + static std::size_t suggested_lower_bucket_count(std::size_t n) + { + const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; + const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; + std::size_t const* bound = std::upper_bound(primes, primes_end, n); + bound -= (bound != primes); + return *bound; + } }; #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) @@ -588,7 +606,6 @@ struct bucket_plus_vtraits typedef typename value_traits::node_traits node_traits; typedef unordered_group_adapter<node_traits> group_traits; typedef typename slist_impl::iterator siterator; - typedef typename slist_impl::size_type size_type; typedef detail::bucket_impl<slist_impl> bucket_type; typedef detail::group_functions<node_traits> group_functions_t; typedef typename slist_impl::node_algorithms node_algorithms; @@ -655,7 +672,7 @@ struct bucket_plus_vtraits BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_pointer() const { return this->priv_bucket_traits().bucket_begin(); } - typename slist_impl::size_type priv_bucket_count() const + std::size_t priv_bucket_count() const { return this->priv_bucket_traits().bucket_count(); } BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_invalid_bucket() const @@ -668,9 +685,9 @@ struct bucket_plus_vtraits { return this->priv_bucket_traits().bucket_begin()->before_begin(); } template<class NodeDisposer> - static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_) //optimize multikey + static std::size_t priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_) //optimize multikey { - size_type n = 0; + std::size_t n = 0; siterator const sfirst(++siterator(sbefore_first)); if(sfirst != slast){ node_ptr const nf = detail::dcast_bucket_ptr<node>(sfirst.pointed_node()); @@ -708,9 +725,9 @@ struct bucket_plus_vtraits } template<class NodeDisposer> - static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_) //optimize multikey + static std::size_t priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_) //optimize multikey { - size_type n = 0; + std::size_t n = 0; siterator it(++siterator(sbefore_first)); while(it != slast){ node_disposer((it++).pointed_node()); @@ -757,17 +774,17 @@ struct bucket_plus_vtraits { b.erase_after_and_dispose(b.previous(i), node_disposer); } template<class NodeDisposer, bool OptimizeMultikey> - size_type priv_erase_node_range( siterator const &before_first_it, size_type const first_bucket - , siterator const &last_it, size_type const last_bucket + std::size_t priv_erase_node_range( siterator const &before_first_it, std::size_t const first_bucket + , siterator const &last_it, std::size_t const last_bucket , NodeDisposer node_disposer, detail::bool_<OptimizeMultikey> optimize_multikey_tag) { - size_type num_erased(0); + std::size_t num_erased(0); siterator last_step_before_it; if(first_bucket != last_bucket){ bucket_type *b = (&this->priv_bucket_pointer()[0]); num_erased += this->priv_erase_from_single_bucket (b[first_bucket], before_first_it, b[first_bucket].end(), node_disposer, optimize_multikey_tag); - for(size_type i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){ + for(std::size_t i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){ num_erased += this->priv_erase_whole_bucket(b[first_bucket+i+1], node_disposer); } last_step_before_it = b[last_bucket].before_begin(); @@ -797,9 +814,9 @@ struct bucket_plus_vtraits } template<class NodeDisposer> - size_type priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer) + std::size_t priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer) { - size_type num_erased = 0; + std::size_t num_erased = 0; siterator b_begin(b.before_begin()); siterator nxt(b_begin); ++nxt; @@ -841,7 +858,7 @@ struct bucket_plus_vtraits const bucket_type &b = static_cast<const bucket_type&> (bucket_type::slist_type::container_from_end_iterator(bucket_type::s_iterator_to(*bb))); //Now just calculate the index b has in the bucket array - return static_cast<size_type>(&b - &*f); + return static_cast<std::size_t>(&b - &*f); } std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::false_) //NO optimize multikey @@ -881,10 +898,10 @@ struct bucket_plus_vtraits BOOST_INTRUSIVE_FORCEINLINE const_reference priv_value_from_slist_node(slist_node_ptr n) const { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); } - void priv_clear_buckets(const bucket_ptr buckets_ptr, const size_type bucket_cnt) + void priv_clear_buckets(const bucket_ptr buckets_ptr, const std::size_t bucket_cnt) { bucket_ptr buckets_it = buckets_ptr; - for(size_type bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){ + for(std::size_t bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){ if(safemode_or_autounlink){ buckets_it->clear_and_dispose(detail::init_disposer<node_algorithms>()); } @@ -909,24 +926,6 @@ struct bucket_plus_vtraits BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const { return const_iterator(this->priv_invalid_local_it(), 0); } - static size_type suggested_upper_bucket_count(size_type n) - { - const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; - const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; - std::size_t const* bound = std::lower_bound(primes, primes_end, n); - bound -= (bound == primes_end); - return size_type(*bound); - } - - static size_type suggested_lower_bucket_count(size_type n) - { - const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; - const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; - size_type const* bound = std::upper_bound(primes, primes_end, n); - bound -= (bound != primes); - return size_type(*bound); - } - //Public functions: struct data_type : public ValueTraits { @@ -1072,7 +1071,6 @@ struct bucket_hash_equal_t typedef typename bucket_hash_type::hasher hasher; typedef BucketTraits bucket_traits; typedef typename bucket_plus_vtraits_t::slist_impl slist_impl; - typedef typename slist_impl::size_type size_type; typedef typename slist_impl::iterator siterator; typedef detail::bucket_impl<slist_impl> bucket_type; typedef typename detail::unordered_bucket_ptr_impl<value_traits>::type bucket_ptr; @@ -1089,7 +1087,7 @@ struct bucket_hash_equal_t BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &) {} - BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_cache_bucket_num() + BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num() { return 0u; } BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache() @@ -1100,8 +1098,8 @@ struct bucket_hash_equal_t siterator priv_begin() const { - size_type n = 0; - size_type bucket_cnt = this->bucket_hash_type::priv_bucket_count(); + std::size_t n = 0; + std::size_t bucket_cnt = this->bucket_hash_type::priv_bucket_count(); for (n = 0; n < bucket_cnt; ++n){ bucket_type &b = this->bucket_hash_type::priv_bucket_pointer()[n]; if(!b.empty()){ @@ -1111,10 +1109,10 @@ struct bucket_hash_equal_t return this->bucket_hash_type::priv_invalid_local_it(); } - BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(size_type) + BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(std::size_t) {} - BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(size_type, size_type) + BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(std::size_t, std::size_t) {} BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache() @@ -1145,7 +1143,6 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type; typedef typename bucket_hash_type::hasher hasher; typedef BucketTraits bucket_traits; - typedef typename bucket_plus_vtraits_t::slist_impl::size_type size_type; typedef typename bucket_plus_vtraits_t::slist_impl::iterator siterator; template<class BucketTraitsType> @@ -1187,7 +1184,7 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK } } - void priv_insertion_update_cache(size_type insertion_bucket) + void priv_insertion_update_cache(std::size_t insertion_bucket) { bucket_ptr p = this->bucket_hash_type::priv_bucket_pointer() + insertion_bucket; if(p < this->cached_begin_){ @@ -1201,7 +1198,7 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal() { return this->equal_holder_t::get(); } - void priv_erasure_update_cache_range(size_type first_bucket_num, size_type last_bucket_num) + void priv_erasure_update_cache_range(std::size_t first_bucket_num, std::size_t last_bucket_num) { //If the last bucket is the end, the cache must be updated //to the last position if all @@ -1215,8 +1212,8 @@ struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrK void priv_erasure_update_cache() { if(this->cached_begin_ != this->bucket_hash_type::priv_invalid_bucket()){ - size_type current_n = this->priv_get_cache() - this->bucket_hash_type::priv_bucket_pointer(); - for( const size_type num_buckets = this->bucket_hash_type::priv_bucket_count() + std::size_t current_n = this->priv_get_cache() - this->bucket_hash_type::priv_bucket_pointer(); + for( const std::size_t num_buckets = this->bucket_hash_type::priv_bucket_count() ; current_n < num_buckets ; ++current_n, ++this->priv_get_cache()){ if(!this->priv_get_cache()->empty()){ @@ -1307,7 +1304,7 @@ struct hashdata_internal typedef typename internal_type::key_equal key_equal; typedef typename internal_type::hasher hasher; typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; - typedef typename bucket_plus_vtraits_t::size_type size_type; + typedef SizeType size_type; typedef typename internal_type::size_traits split_traits; typedef typename bucket_plus_vtraits_t::bucket_ptr bucket_ptr; typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr; @@ -1459,7 +1456,11 @@ struct hashdata_internal } BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const - { return this->priv_bucket_count(); } + { + const std::size_t bc = this->priv_bucket_count(); + BOOST_INTRUSIVE_INVARIANT_ASSERT(sizeof(size_type) >= sizeof(std::size_t) || bc <= size_type(-1)); + return static_cast<size_type>(bc); + } BOOST_INTRUSIVE_FORCEINLINE size_type bucket_size(size_type n) const { return this->priv_bucket_pointer()[n].size(); } @@ -1473,6 +1474,20 @@ struct hashdata_internal BOOST_INTRUSIVE_FORCEINLINE const_local_iterator begin(size_type n) const { return this->cbegin(n); } + static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_upper_bucket_count(size_type n) + { + std::size_t c = prime_list_holder<0>::suggested_upper_bucket_count + (sizeof(size_type) > sizeof(std::size_t) && n > std::size_t(-1) ? std::size_t(-1) : static_cast<std::size_t>(n)); + return sizeof(size_type) < sizeof(std::size_t) && c > size_type(-1) ? size_type(-1) : static_cast<size_type>(c); + } + + static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_lower_bucket_count(size_type n) + { + std::size_t c = prime_list_holder<0>::suggested_lower_bucket_count + (sizeof(size_type) > sizeof(std::size_t) && n > std::size_t(-1) ? std::size_t(-1) : static_cast<std::size_t>(n)); + return sizeof(size_type) < sizeof(std::size_t) && c > size_type(-1) ? size_type(-1) : static_cast<size_type>(c); + } + const_local_iterator cbegin(size_type n) const { return const_local_iterator @@ -1737,7 +1752,7 @@ class hashtable_impl { this->priv_initialize_buckets_and_cache(); this->priv_size_traits().set_size(size_type(0)); - size_type bucket_sz = this->priv_bucket_count(); + size_type bucket_sz = this->bucket_count(); BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); //Check power of two bucket array if the option is activated BOOST_INTRUSIVE_INVARIANT_ASSERT @@ -1770,7 +1785,7 @@ class hashtable_impl { this->priv_initialize_buckets_and_cache(); this->priv_size_traits().set_size(size_type(0)); - size_type bucket_sz = this->priv_bucket_count(); + size_type bucket_sz = this->bucket_count(); BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); //Check power of two bucket array if the option is activated BOOST_INTRUSIVE_INVARIANT_ASSERT @@ -1894,8 +1909,8 @@ class hashtable_impl return this->begin() == this->end(); } else{ - size_type bucket_cnt = this->priv_bucket_count(); - const bucket_type *b = boost::intrusive::detail::to_raw_pointer(this->priv_bucket_pointer()); + size_type bucket_cnt = this->bucket_count(); + const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer()); for (size_type n = 0; n < bucket_cnt; ++n, ++b){ if(!b->empty()){ return false; @@ -1917,8 +1932,8 @@ class hashtable_impl return this->priv_size_traits().get_size(); else{ size_type len = 0; - size_type bucket_cnt = this->priv_bucket_count(); - const bucket_type *b = boost::intrusive::detail::to_raw_pointer(this->priv_bucket_pointer()); + size_type bucket_cnt = this->bucket_count(); + const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer()); for (size_type n = 0; n < bucket_cnt; ++n, ++b){ len += b->size(); } @@ -2898,7 +2913,7 @@ class hashtable_impl //This function is only available for containers with incremental hashing BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); const size_type split_idx = this->priv_split_traits().get_size(); - const size_type bucket_cnt = this->priv_bucket_count(); + const size_type bucket_cnt = this->bucket_count(); const bucket_ptr buck_ptr = this->priv_bucket_pointer(); bool ret = false; @@ -2961,7 +2976,7 @@ class hashtable_impl //This function is only available for containers with incremental hashing BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); size_type const new_bucket_traits_size = new_bucket_traits.bucket_count(); - size_type const cur_bucket_traits = this->priv_bucket_count(); + size_type const cur_bucket_traits = this->bucket_count(); const size_type split_idx = this->split_count(); //Test new bucket size is consistent with internal bucket size and split count @@ -3071,7 +3086,7 @@ class hashtable_impl const bucket_ptr new_buckets = new_bucket_traits.bucket_begin(); size_type new_bucket_count = new_bucket_traits.bucket_count(); const bucket_ptr old_buckets = this->priv_bucket_pointer(); - size_type old_bucket_count = this->priv_bucket_count(); + size_type old_bucket_count = this->bucket_count(); //Check power of two bucket array if the option is activated BOOST_INTRUSIVE_INVARIANT_ASSERT @@ -3400,7 +3415,7 @@ class hashtable_impl to_return.second == bp[n_bucket].end()){ to_return.second = this->priv_invalid_local_it(); ++n_bucket; - for( const size_type max_bucket = this->priv_bucket_count() + for( const size_type max_bucket = this->bucket_count() ; n_bucket != max_bucket ; ++n_bucket){ bucket_type &b = bp[n_bucket]; diff --git a/boost/intrusive/member_value_traits.hpp b/boost/intrusive/member_value_traits.hpp index 4efe79ebdb..0ab7ffb112 100644 --- a/boost/intrusive/member_value_traits.hpp +++ b/boost/intrusive/member_value_traits.hpp @@ -18,7 +18,7 @@ #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/detail/parent_from_member.hpp> -#include <boost/intrusive/detail/to_raw_pointer.hpp> +#include <boost/move/detail/to_raw_pointer.hpp> #include <boost/intrusive/pointer_traits.hpp> #if defined(BOOST_HAS_PRAGMA_ONCE) @@ -66,13 +66,13 @@ struct member_value_traits BOOST_INTRUSIVE_FORCEINLINE static pointer to_value_ptr(const node_ptr &n) { return pointer_traits<pointer>::pointer_to(*detail::parent_from_member<value_type, node> - (boost::intrusive::detail::to_raw_pointer(n), PtrToMember)); + (boost::movelib::to_raw_pointer(n), PtrToMember)); } BOOST_INTRUSIVE_FORCEINLINE static const_pointer to_value_ptr(const const_node_ptr &n) { return pointer_traits<const_pointer>::pointer_to(*detail::parent_from_member<value_type, node> - (boost::intrusive::detail::to_raw_pointer(n), PtrToMember)); + (boost::movelib::to_raw_pointer(n), PtrToMember)); } }; diff --git a/boost/intrusive/pointer_traits.hpp b/boost/intrusive/pointer_traits.hpp index 5baf5e807c..4216c7ee9c 100644 --- a/boost/intrusive/pointer_traits.hpp +++ b/boost/intrusive/pointer_traits.hpp @@ -20,7 +20,7 @@ #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/pointer_rebind.hpp> -#include <boost/intrusive/detail/pointer_element.hpp> +#include <boost/move/detail/pointer_element.hpp> #include <boost/intrusive/detail/mpl.hpp> #include <cstddef> @@ -97,7 +97,7 @@ struct pointer_traits // typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_EVAL_DEFAULT ( boost::intrusive::detail::, Ptr, element_type - , boost::intrusive::detail::first_param<Ptr>) element_type; + , boost::movelib::detail::first_param<Ptr>) element_type; // typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT (boost::intrusive::detail::, Ptr, difference_type, std::ptrdiff_t) difference_type; |