diff options
| author | robot-contrib <robot-contrib@yandex-team.com> | 2022-09-15 22:06:51 +0300 |
|---|---|---|
| committer | robot-contrib <robot-contrib@yandex-team.com> | 2022-09-15 22:06:51 +0300 |
| commit | e2586739fd69a82509aa56e6723bdeaca6e24966 (patch) | |
| tree | 5f00a60db1d4a7ccaae49c406e542b907482d7ef | |
| parent | 66b777879cc0f9bba996c4271f8b5d37e9e2c913 (diff) | |
| download | ydb-e2586739fd69a82509aa56e6723bdeaca6e24966.tar.gz | |
Update contrib/restricted/boost/multi_index to 1.80.0
35 files changed, 2687 insertions, 1194 deletions
diff --git a/contrib/restricted/boost/detail/include/boost/detail/allocator_utilities.hpp b/contrib/restricted/boost/detail/include/boost/detail/allocator_utilities.hpp deleted file mode 100644 index 056ba37e2ce..00000000000 --- a/contrib/restricted/boost/detail/include/boost/detail/allocator_utilities.hpp +++ /dev/null @@ -1,193 +0,0 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. - * 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 Boost website at http://www.boost.org/ - */ - -#ifndef BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP -#define BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP - -#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <boost/detail/workaround.hpp> -#include <boost/detail/select_type.hpp> -#include <boost/type_traits/is_same.hpp> -#include <cstddef> -#include <memory> -#include <new> - -namespace boost{ - -namespace detail{ - -/* Allocator adaption layer. Some stdlibs provide allocators without rebind - * and template ctors. These facilities are simulated with the external - * template class rebind_to and the aid of partial_std_allocator_wrapper. - */ - -namespace allocator{ - -/* partial_std_allocator_wrapper inherits the functionality of a std - * allocator while providing a templatized ctor and other bits missing - * in some stdlib implementation or another. - */ - -template<typename Type> -class partial_std_allocator_wrapper:public std::allocator<Type> -{ -public: - /* Oddly enough, STLport does not define std::allocator<void>::value_type - * when configured to work without partial template specialization. - * No harm in supplying the definition here unconditionally. - */ - - typedef Type value_type; - - partial_std_allocator_wrapper(){} - - template<typename Other> - partial_std_allocator_wrapper(const partial_std_allocator_wrapper<Other>&){} - - partial_std_allocator_wrapper(const std::allocator<Type>& x): - std::allocator<Type>(x) - { - } - -#if defined(BOOST_DINKUMWARE_STDLIB) - /* Dinkumware guys didn't provide a means to call allocate() without - * supplying a hint, in disagreement with the standard. - */ - - Type* allocate(std::size_t n,const void* hint=0) - { - std::allocator<Type>& a=*this; - return a.allocate(n,hint); - } -#endif - -}; - -/* Detects whether a given allocator belongs to a defective stdlib not - * having the required member templates. - * Note that it does not suffice to check the Boost.Config stdlib - * macros, as the user might have passed a custom, compliant allocator. - * The checks also considers partial_std_allocator_wrapper to be - * a standard defective allocator. - */ - -#if defined(BOOST_NO_STD_ALLOCATOR)&&\ - (defined(BOOST_HAS_PARTIAL_STD_ALLOCATOR)||defined(BOOST_DINKUMWARE_STDLIB)) - -template<typename Allocator> -struct is_partial_std_allocator -{ - BOOST_STATIC_CONSTANT(bool, - value= - (is_same< - std::allocator<BOOST_DEDUCED_TYPENAME Allocator::value_type>, - Allocator - >::value)|| - (is_same< - partial_std_allocator_wrapper< - BOOST_DEDUCED_TYPENAME Allocator::value_type>, - Allocator - >::value)); -}; - -#else - -template<typename Allocator> -struct is_partial_std_allocator -{ - BOOST_STATIC_CONSTANT(bool,value=false); -}; - -#endif - -/* rebind operations for defective std allocators */ - -template<typename Allocator,typename Type> -struct partial_std_allocator_rebind_to -{ - typedef partial_std_allocator_wrapper<Type> type; -}; - -/* rebind operation in all other cases */ - -template<typename Allocator> -struct rebinder -{ - template<typename Type> - struct result - { -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename Allocator::BOOST_NESTED_TEMPLATE - rebind<Type>::other other; -#else - typedef typename std::allocator_traits<Allocator>::BOOST_NESTED_TEMPLATE - rebind_alloc<Type> other; -#endif - }; -}; - -template<typename Allocator,typename Type> -struct compliant_allocator_rebind_to -{ - typedef typename rebinder<Allocator>:: - BOOST_NESTED_TEMPLATE result<Type>::other type; -}; - -/* rebind front-end */ - -template<typename Allocator,typename Type> -struct rebind_to: - boost::detail::if_true< - is_partial_std_allocator<Allocator>::value - >::template then< - partial_std_allocator_rebind_to<Allocator,Type>, - compliant_allocator_rebind_to<Allocator,Type> - >::type -{ -}; - -/* allocator-independent versions of construct and destroy */ - -template<typename Type> -void construct(void* p,const Type& t) -{ - new (p) Type(t); -} - -#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) -/* MSVC++ issues spurious warnings about unreferencend formal parameters - * in destroy<Type> when Type is a class with trivial dtor. - */ - -#pragma warning(push) -#pragma warning(disable:4100) -#endif - -template<typename Type> -void destroy(const Type* p) -{ - -#if BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590)) - const_cast<Type*>(p)->~Type(); -#else - p->~Type(); -#endif - -} - -#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) -#pragma warning(pop) -#endif - -} /* namespace boost::detail::allocator */ - -} /* namespace boost::detail */ - -} /* namespace boost */ - -#endif diff --git a/contrib/restricted/boost/multi_index/README.md b/contrib/restricted/boost/multi_index/README.md new file mode 100644 index 00000000000..60038d7894a --- /dev/null +++ b/contrib/restricted/boost/multi_index/README.md @@ -0,0 +1,10 @@ +# Boost Multi-index Containers Library + +Branch | Travis | Drone | GitHub Actions | AppVeyor | Regression tests +---------|--------|-------|----------------|----------|----------------- +develop | [](https://travis-ci.com/boostorg/multi_index) | [](https://drone.cpp.al/boostorg/multi_index) | [](https://github.com/boostorg/multi_index/actions/workflows/ci.yml?query=branch:develop) | [](https://ci.appveyor.com/project/joaquintides/multi-index) | [](https://www.boost.org/development/tests/develop/developer/multi_index.html) +master | [](https://travis-ci.com/boostorg/multi_index) | [](https://drone.cpp.al/boostorg/multi_index) | [](https://github.com/boostorg/multi_index/actions/workflows/ci.yml?query=branch:master) | [](https://ci.appveyor.com/project/joaquintides/multi-index) | [](https://www.boost.org/development/tests/master/developer/multi_index.html) + +[Boost.MultiIndex](http://boost.org/libs/multi_index) provides a class template +named `multi_index_container` which enables the construction of containers +maintaining one or more indices with different sorting and access semantics. diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/allocator_traits.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/allocator_traits.hpp new file mode 100644 index 00000000000..45903b75f08 --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/allocator_traits.hpp @@ -0,0 +1,173 @@ +/* Copyright 2003-2020 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ALLOCATOR_TRAITS_HPP +#define BOOST_MULTI_INDEX_DETAIL_ALLOCATOR_TRAITS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ + +#if !defined(BOOST_NO_CXX11_ALLOCATOR) +#include <boost/type_traits/is_empty.hpp> +#include <memory> +#else +#include <boost/detail/workaround.hpp> +#include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/multi_index/detail/vartempl_support.hpp> +#include <boost/type_traits/integral_constant.hpp> +#include <boost/type_traits/is_empty.hpp> +#include <new> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* poor man's replacement of std::allocator_traits */ + +#if !defined(BOOST_NO_CXX11_ALLOCATOR) + +template<typename T> struct void_helper{typedef void type;}; + +template<typename Allocator,typename=void> +struct allocator_is_always_equal:boost::is_empty<Allocator>{}; + +template<typename Allocator> +struct allocator_is_always_equal< + Allocator, + typename void_helper< + typename std::allocator_traits<Allocator>::is_always_equal + >::type +>:std::allocator_traits<Allocator>::is_always_equal{}; + +template<typename Allocator> +struct allocator_traits:std::allocator_traits<Allocator> +{ + /* wrap std::allocator_traits alias templates for use in C++03 codebase */ + + typedef std::allocator_traits<Allocator> super; + + /* pre-C++17 compatibilty */ + + typedef allocator_is_always_equal<Allocator> is_always_equal; + + template<typename T> + struct rebind_alloc + { + typedef typename super::template rebind_alloc<T> type; + }; + + template<typename T> + struct rebind_traits + { + typedef typename super::template rebind_traits<T> type; + }; +}; + +#else + +/* not a full std::allocator_traits rewrite (not needed) */ + +template<typename Allocator> +struct allocator_traits +{ + typedef Allocator allocator_type; + typedef typename Allocator::value_type value_type; + typedef typename Allocator::pointer pointer; + typedef typename Allocator::const_pointer const_pointer; + + /* [const_]void_pointer not provided as boost::pointer_traits's + * rebind_to has been seen to fail with things like + * boost::interprocess::offset_ptr in relatively old environments. + */ + + typedef typename Allocator::difference_type difference_type; + typedef typename Allocator::size_type size_type; + + typedef boost::false_type propagate_on_container_copy_assignment; + typedef boost::false_type propagate_on_container_move_assignment; + typedef boost::false_type propagate_on_container_swap; + typedef boost::is_empty<Allocator> is_always_equal; + + template<typename T> + struct rebind_alloc + { + typedef typename Allocator::template rebind<T>::other type; + }; + + template<typename T> + struct rebind_traits + { + typedef allocator_traits<typename rebind_alloc<T>::type> type; + }; + + static pointer allocate(Allocator& a,size_type n){return a.allocate(n);} + static pointer allocate(Allocator& a,size_type n,const_pointer p) + /* should've been const_void_pointer p */ + {return a.allocate(n,p);} + static void deallocate(Allocator& a,pointer p,size_type n) + {a.deallocate(p,n);} + template<typename T> + static void construct(Allocator&,T* p,const T& x) + {::new (static_cast<void*>(p)) T(x);} + template<typename T> + static void construct(Allocator&,T* p,BOOST_RV_REF(T) x) + {::new (static_cast<void*>(p)) T(boost::move(x));} + + template<typename T,BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> + static void construct(Allocator&,T* p,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + vartempl_placement_new(p,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +/* MSVC issues spurious warnings about unreferencend formal parameters in + * destroy<T> when T is a class with trivial dtor. + */ + +#pragma warning(push) +#pragma warning(disable:4100) +#endif + + template<typename T> + static void destroy(Allocator&,T* p){p->~T();} + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +#pragma warning(pop) +#endif + + static size_type max_size(Allocator& a)BOOST_NOEXCEPT{return a.max_size();} + + static Allocator select_on_container_copy_construction(const Allocator& a) + { + return a; + } +}; + +#endif + +template<typename Allocator,typename T> +struct rebind_alloc_for +{ + typedef typename allocator_traits<Allocator>:: + template rebind_alloc<T>::type type; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/any_container_view.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/any_container_view.hpp new file mode 100644 index 00000000000..6432b35ffa3 --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/any_container_view.hpp @@ -0,0 +1,76 @@ +/* Copyright 2003-2021 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ANY_CONTAINER_VIEW_HPP +#define BOOST_MULTI_INDEX_DETAIL_ANY_CONTAINER_VIEW_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* type-erased, non-owning view over a ConstIterator-container's range */ + +template<typename ConstIterator> +class any_container_view +{ +public: + template<typename Container> + any_container_view(const Container& x):px(&x),pt(vtable_for<Container>()){} + + const void* container()const{return px;} + ConstIterator begin()const{return pt->begin(px);} + ConstIterator end()const{return pt->end(px);} + +private: + struct vtable + { + ConstIterator (*begin)(const void*); + ConstIterator (*end)(const void*); + }; + + template<typename Container> + static ConstIterator begin_for(const void* px) + { + return static_cast<const Container*>(px)->begin(); + } + + template<typename Container> + static ConstIterator end_for(const void* px) + { + return static_cast<const Container*>(px)->end(); + } + + template<typename Container> + vtable* vtable_for() + { + static vtable v= + { + &begin_for<Container>, + &end_for<Container> + }; + + return &v; + } + + const void* px; + vtable* pt; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/archive_constructed.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/archive_constructed.hpp index 0a7a26e0d4e..43d3687e1a2 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/archive_constructed.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/archive_constructed.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2016 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -14,8 +14,8 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <boost/detail/no_exceptions_support.hpp> -#include <boost/noncopyable.hpp> +#include <boost/core/no_exceptions_support.hpp> +#include <boost/core/noncopyable.hpp> #include <boost/serialization/serialization.hpp> #include <boost/type_traits/aligned_storage.hpp> #include <boost/type_traits/alignment_of.hpp> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/auto_space.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/auto_space.hpp index 911f810f8fa..449456372bf 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/auto_space.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/auto_space.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -15,9 +15,10 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> -#include <boost/detail/allocator_utilities.hpp> +#include <boost/core/noncopyable.hpp> #include <boost/multi_index/detail/adl_swap.hpp> -#include <boost/noncopyable.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> +#include <boost/type_traits/integral_constant.hpp> #include <memory> namespace boost{ @@ -45,34 +46,18 @@ namespace detail{ template<typename T,typename Allocator=std::allocator<T> > struct auto_space:private noncopyable { - typedef typename boost::detail::allocator::rebind_to< - Allocator,T - >::type allocator; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator::pointer pointer; -#else - typedef std::allocator_traits<allocator> traits; - typedef typename traits::pointer pointer; -#endif - - explicit auto_space(const Allocator& al=Allocator(),std::size_t n=1): - al_(al),n_(n), -#ifdef BOOST_NO_CXX11_ALLOCATOR - data_(n_?al_.allocate(n_):pointer(0)) -#else - data_(n_?traits::allocate(al_,n_):pointer(0)) -#endif + typedef typename rebind_alloc_for< + Allocator,T> + ::type allocator; + typedef allocator_traits<allocator> alloc_traits; + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::size_type size_type; + + explicit auto_space(const Allocator& al=Allocator(),size_type n=1): + al_(al),n_(n),data_(n_?alloc_traits::allocate(al_,n_):pointer(0)) {} - ~auto_space() - { - if(n_) -#ifdef BOOST_NO_CXX11_ALLOCATOR - al_.deallocate(data_,n_); -#else - traits::deallocate(al_,data_,n_); -#endif - } + ~auto_space(){if(n_)alloc_traits::deallocate(al_,data_,n_);} Allocator get_allocator()const{return al_;} @@ -80,15 +65,29 @@ struct auto_space:private noncopyable void swap(auto_space& x) { - if(al_!=x.al_)adl_swap(al_,x.al_); + swap( + x, + boost::integral_constant< + bool,alloc_traits::propagate_on_container_swap::value>()); + } + + void swap(auto_space& x,boost::true_type /* swap_allocators */) + { + adl_swap(al_,x.al_); std::swap(n_,x.n_); std::swap(data_,x.data_); } + void swap(auto_space& x,boost::false_type /* swap_allocators */) + { + std::swap(n_,x.n_); + std::swap(data_,x.data_); + } + private: - allocator al_; - std::size_t n_; - pointer data_; + allocator al_; + size_type n_; + pointer data_; }; template<typename T,typename Allocator> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bidir_node_iterator.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bidir_node_iterator.hpp index 9be5ec84b43..adfb77de6d1 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bidir_node_iterator.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bidir_node_iterator.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2014 Joaquin M Lopez Munoz. +/* Copyright 2003-2018 Joaquin M Lopez Munoz. * 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) @@ -36,7 +36,7 @@ class bidir_node_iterator: public bidirectional_iterator_helper< bidir_node_iterator<Node>, typename Node::value_type, - std::ptrdiff_t, + typename Node::difference_type, const typename Node::value_type*, const typename Node::value_type&> { diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bucket_array.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bucket_array.hpp index d9fa434d9a9..04392d18999 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bucket_array.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/bucket_array.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2015 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -15,9 +15,10 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> +#include <boost/core/noncopyable.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/auto_space.hpp> #include <boost/multi_index/detail/hash_index_node.hpp> -#include <boost/noncopyable.hpp> #include <boost/preprocessor/repetition/repeat.hpp> #include <boost/preprocessor/seq/elem.hpp> #include <boost/preprocessor/seq/enum.hpp> @@ -128,7 +129,7 @@ class bucket_array:bucket_array_base<> { typedef bucket_array_base<> super; typedef hashed_index_base_node_impl< - typename boost::detail::allocator::rebind_to< + typename rebind_alloc_for< Allocator, char >::type @@ -140,7 +141,7 @@ public: bucket_array(const Allocator& al,pointer end_,std::size_t size_): size_index_(super::size_index(size_)), - spc(al,super::sizes[size_index_]+1) + spc(al,static_cast<auto_space_size_type>(super::sizes[size_index_]+1)) { clear(end_); } @@ -172,9 +173,19 @@ public: spc.swap(x.spc); } + template<typename BoolConstant> + void swap(bucket_array& x,BoolConstant swap_allocators) + { + std::swap(size_index_,x.size_index_); + spc.swap(x.spc,swap_allocators); + } + private: - std::size_t size_index_; - auto_space<base_node_impl_type,Allocator> spc; + typedef auto_space<base_node_impl_type,Allocator> auto_space_type; + typedef typename auto_space_type::size_type auto_space_size_type; + + std::size_t size_index_; + auto_space_type spc; base_pointer buckets()const { diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/converter.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/converter.hpp index 3e04a3e8295..02e1994d4a4 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/converter.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/converter.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -31,13 +31,15 @@ struct converter static Index& index(MultiIndexContainer& x){return x;} static typename Index::const_iterator const_iterator( - const MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + const MultiIndexContainer& x, + typename MultiIndexContainer::final_node_type* node) { return x.Index::make_iterator(node); } static typename Index::iterator iterator( - MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + MultiIndexContainer& x, + typename MultiIndexContainer::final_node_type* node) { return x.Index::make_iterator(node); } diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/copy_map.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/copy_map.hpp index 1ab2bf00433..4e79697aa80 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/copy_map.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/copy_map.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -16,13 +16,14 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> #include <boost/core/addressof.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> +#include <boost/core/noncopyable.hpp> +#include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/auto_space.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> -#include <boost/noncopyable.hpp> -#include <cstddef> #include <functional> -#include <memory> namespace boost{ @@ -56,14 +57,33 @@ struct copy_map_entry } }; +struct copy_map_value_copier +{ + template<typename Value> + const Value& operator()(Value& x)const{return x;} +}; + +struct copy_map_value_mover +{ + template<typename Value> + BOOST_RV_REF(Value) operator()(Value& x)const{return boost::move(x);} +}; + template <typename Node,typename Allocator> class copy_map:private noncopyable { + typedef typename rebind_alloc_for< + Allocator,Node + >::type allocator_type; + typedef allocator_traits<allocator_type> alloc_traits; + typedef typename alloc_traits::pointer pointer; + public: - typedef const copy_map_entry<Node>* const_iterator; + typedef const copy_map_entry<Node>* const_iterator; + typedef typename alloc_traits::size_type size_type; copy_map( - const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy): + const Allocator& al,size_type size,Node* header_org,Node* header_cpy): al_(al),size_(size),spc(al_,size_),n(0), header_org_(header_org),header_cpy_(header_cpy),released(false) {} @@ -71,9 +91,9 @@ public: ~copy_map() { if(!released){ - for(std::size_t i=0;i<n;++i){ - boost::detail::allocator::destroy( - boost::addressof((spc.data()+i)->second->value())); + for(size_type i=0;i<n;++i){ + alloc_traits::destroy( + al_,boost::addressof((spc.data()+i)->second->value())); deallocate((spc.data()+i)->second); } } @@ -82,27 +102,8 @@ public: const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());} const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);} - void clone(Node* node) - { - (spc.data()+n)->first=node; - (spc.data()+n)->second=raw_ptr<Node*>(allocate()); - BOOST_TRY{ - boost::detail::allocator::construct( - boost::addressof((spc.data()+n)->second->value()),node->value()); - } - BOOST_CATCH(...){ - deallocate((spc.data()+n)->second); - BOOST_RETHROW; - } - BOOST_CATCH_END - ++n; - - if(n==size_){ - std::sort( - raw_ptr<copy_map_entry<Node>*>(spc.data()), - raw_ptr<copy_map_entry<Node>*>(spc.data())+size_); - } - } + void copy_clone(Node* node){clone(node,copy_map_value_copier());} + void move_clone(Node* node){clone(node,copy_map_value_mover());} Node* find(Node* node)const { @@ -117,40 +118,46 @@ public: } private: - typedef typename boost::detail::allocator::rebind_to< - Allocator,Node - >::type allocator_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::pointer allocator_pointer; -#else - typedef std::allocator_traits<allocator_type> allocator_traits; - typedef typename allocator_traits::pointer allocator_pointer; -#endif - - allocator_type al_; - std::size_t size_; - auto_space<copy_map_entry<Node>,Allocator> spc; - std::size_t n; - Node* header_org_; - Node* header_cpy_; - bool released; - - allocator_pointer allocate() + allocator_type al_; + size_type size_; + auto_space<copy_map_entry<Node>,Allocator> spc; + size_type n; + Node* header_org_; + Node* header_cpy_; + bool released; + + pointer allocate() { -#ifdef BOOST_NO_CXX11_ALLOCATOR - return al_.allocate(1); -#else - return allocator_traits::allocate(al_,1); -#endif + return alloc_traits::allocate(al_,1); } void deallocate(Node* node) { -#ifdef BOOST_NO_CXX11_ALLOCATOR - al_.deallocate(static_cast<allocator_pointer>(node),1); -#else - allocator_traits::deallocate(al_,static_cast<allocator_pointer>(node),1); -#endif + alloc_traits::deallocate(al_,static_cast<pointer>(node),1); + } + + template<typename ValueAccess> + void clone(Node* node,ValueAccess access) + { + (spc.data()+n)->first=node; + (spc.data()+n)->second=raw_ptr<Node*>(allocate()); + BOOST_TRY{ + alloc_traits::construct( + al_,boost::addressof((spc.data()+n)->second->value()), + access(node->value())); + } + BOOST_CATCH(...){ + deallocate((spc.data()+n)->second); + BOOST_RETHROW; + } + BOOST_CATCH_END + ++n; + + if(n==size_){ + std::sort( + raw_ptr<copy_map_entry<Node>*>(spc.data()), + raw_ptr<copy_map_entry<Node>*>(spc.data())+size_); + } } }; diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/define_if_constexpr_macro.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/define_if_constexpr_macro.hpp new file mode 100644 index 00000000000..52df93c570c --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/define_if_constexpr_macro.hpp @@ -0,0 +1,32 @@ +/* Copyright 2003-2020 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#include <boost/config.hpp> + +#if !defined(BOOST_MULTI_INDEX_DETAIL_UNDEF_IF_CONSTEXPR_MACRO) + +#if !defined(BOOST_NO_CXX17_IF_CONSTEXPR) +#define BOOST_MULTI_INDEX_IF_CONSTEXPR if constexpr +#else +#define BOOST_MULTI_INDEX_IF_CONSTEXPR if +#if defined(BOOST_MSVC) +#define BOOST_MULTI_INDEX_DETAIL_C4127_DISABLED +#pragma warning(push) +#pragma warning(disable:4127) /* conditional expression is constant */ +#endif +#endif + +#else + +#undef BOOST_MULTI_INDEX_IF_CONSTEXPR +#if defined(BOOST_MULTI_INDEX_DETAIL_C4127_DISABLED) +#pragma warning(pop) +#undef BOOST_MULTI_INDEX_DETAIL_C4127_DISABLED +#endif + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/duplicates_iterator.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/duplicates_iterator.hpp index cbebf264045..bfba2320c5a 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/duplicates_iterator.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/duplicates_iterator.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2018 Joaquin M Lopez Munoz. * 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) @@ -14,7 +14,6 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <cstddef> #include <iterator> namespace boost{ @@ -32,7 +31,7 @@ class duplicates_iterator { public: typedef typename Node::value_type value_type; - typedef std::ptrdiff_t difference_type; + typedef typename Node::difference_type difference_type; typedef const typename Node::value_type* pointer; typedef const typename Node::value_type& reference; typedef std::forward_iterator_tag iterator_category; diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_iterator.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_iterator.hpp index 8d063002a1d..f5b0d0e379a 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_iterator.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_iterator.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2014 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -34,12 +34,15 @@ namespace detail{ struct hashed_index_global_iterator_tag{}; struct hashed_index_local_iterator_tag{}; -template<typename Node,typename BucketArray,typename Category> +template< + typename Node,typename BucketArray, + typename IndexCategory,typename IteratorCategory +> class hashed_index_iterator: public forward_iterator_helper< - hashed_index_iterator<Node,BucketArray,Category>, + hashed_index_iterator<Node,BucketArray,IndexCategory,IteratorCategory>, typename Node::value_type, - std::ptrdiff_t, + typename Node::difference_type, const typename Node::value_type*, const typename Node::value_type&> { @@ -55,7 +58,7 @@ public: hashed_index_iterator& operator++() { - this->increment(Category()); + this->increment(IteratorCategory()); return *this; } @@ -78,7 +81,7 @@ public: template<class Archive> void load(Archive& ar,const unsigned int version) { - load(ar,version,Category()); + load(ar,version,IteratorCategory()); } template<class Archive> @@ -122,21 +125,26 @@ private: void increment(hashed_index_global_iterator_tag) { - Node::increment(node); + Node::template increment<IndexCategory>(node); } void increment(hashed_index_local_iterator_tag) { - Node::increment_local(node); + Node::template increment_local<IndexCategory>(node); } Node* node; }; -template<typename Node,typename BucketArray,typename Category> +template< + typename Node,typename BucketArray, + typename IndexCategory,typename IteratorCategory +> bool operator==( - const hashed_index_iterator<Node,BucketArray,Category>& x, - const hashed_index_iterator<Node,BucketArray,Category>& y) + const hashed_index_iterator< + Node,BucketArray,IndexCategory,IteratorCategory>& x, + const hashed_index_iterator< + Node,BucketArray,IndexCategory,IteratorCategory>& y) { return x.get_node()==y.get_node(); } @@ -151,9 +159,14 @@ bool operator==( */ namespace serialization { -template<typename Node,typename BucketArray,typename Category> +template< + typename Node,typename BucketArray, + typename IndexCategory,typename IteratorCategory +> struct version< - boost::multi_index::detail::hashed_index_iterator<Node,BucketArray,Category> + boost::multi_index::detail::hashed_index_iterator< + Node,BucketArray,IndexCategory,IteratorCategory + > > { BOOST_STATIC_CONSTANT(int,value=1); diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_node.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_node.hpp index 2be575b4693..bcb4745ea9c 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_node.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/hash_index_node.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -14,10 +14,9 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <boost/detail/allocator_utilities.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> #include <utility> -#include <memory> namespace boost{ @@ -100,34 +99,19 @@ struct hashed_index_node_impl; template<typename Allocator> struct hashed_index_base_node_impl { - typedef typename - boost::detail::allocator::rebind_to< + typedef typename rebind_alloc_for< Allocator,hashed_index_base_node_impl - >::type base_allocator; - typedef typename - boost::detail::allocator::rebind_to< - Allocator, - hashed_index_node_impl<Allocator> - >::type node_allocator; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename base_allocator::pointer base_pointer; - typedef typename base_allocator::const_pointer const_base_pointer; - typedef typename node_allocator::pointer pointer; - typedef typename node_allocator::const_pointer const_pointer; -#else - typedef typename std::allocator_traits< - base_allocator - >::pointer base_pointer; - typedef typename std::allocator_traits< - base_allocator - >::const_pointer const_base_pointer; - typedef typename std::allocator_traits< - node_allocator - >::pointer pointer; - typedef typename std::allocator_traits< - node_allocator - >::const_pointer const_pointer; -#endif + >::type base_allocator; + typedef typename rebind_alloc_for< + Allocator,hashed_index_node_impl<Allocator> + >::type node_allocator; + typedef allocator_traits<base_allocator> base_alloc_traits; + typedef allocator_traits<node_allocator> node_alloc_traits; + typedef typename base_alloc_traits::pointer base_pointer; + typedef typename base_alloc_traits::const_pointer const_base_pointer; + typedef typename node_alloc_traits::pointer pointer; + typedef typename node_alloc_traits::const_pointer const_pointer; + typedef typename node_alloc_traits::difference_type difference_type; pointer& prior(){return prior_;} pointer prior()const{return prior_;} @@ -424,7 +408,7 @@ struct hashed_index_node_alg<Node,hashed_non_unique_tag> buc->prior()=x; x->next()->prior()=x; } - }; + } static void link(pointer x,pointer first,pointer last) { @@ -705,20 +689,18 @@ private: template<typename Super> struct hashed_index_node_trampoline: hashed_index_node_impl< - typename boost::detail::allocator::rebind_to< - typename Super::allocator_type, - char + typename rebind_alloc_for< + typename Super::allocator_type,char >::type > { - typedef typename boost::detail::allocator::rebind_to< - typename Super::allocator_type, - char - >::type impl_allocator_type; - typedef hashed_index_node_impl<impl_allocator_type> impl_type; + typedef typename rebind_alloc_for< + typename Super::allocator_type,char + >::type impl_allocator_type; + typedef hashed_index_node_impl<impl_allocator_type> impl_type; }; -template<typename Super,typename Category> +template<typename Super> struct hashed_index_node: Super,hashed_index_node_trampoline<Super> { @@ -727,12 +709,16 @@ private: public: typedef typename trampoline::impl_type impl_type; - typedef hashed_index_node_alg< - impl_type,Category> node_alg; typedef typename trampoline::base_pointer impl_base_pointer; typedef typename trampoline::const_base_pointer const_impl_base_pointer; typedef typename trampoline::pointer impl_pointer; typedef typename trampoline::const_pointer const_impl_pointer; + typedef typename trampoline::difference_type difference_type; + + template<typename Category> + struct node_alg{ + typedef hashed_index_node_alg<impl_type,Category> type; + }; impl_pointer& prior(){return trampoline::prior();} impl_pointer prior()const{return trampoline::prior();} @@ -769,14 +755,16 @@ public: /* interoperability with hashed_index_iterator */ + template<typename Category> static void increment(hashed_index_node*& x) { - x=from_impl(node_alg::after(x->impl())); + x=from_impl(node_alg<Category>::type::after(x->impl())); } + template<typename Category> static void increment_local(hashed_index_node*& x) { - x=from_impl(node_alg::after_local(x->impl())); + x=from_impl(node_alg<Category>::type::after_local(x->impl())); } }; diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/header_holder.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/header_holder.hpp index ca8a9b2edb1..297c67318fc 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/header_holder.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/header_holder.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2008 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -13,7 +13,7 @@ #pragma once #endif -#include <boost/noncopyable.hpp> +#include <boost/core/noncopyable.hpp> namespace boost{ diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_access_sequence.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_access_sequence.hpp new file mode 100644 index 00000000000..773a9aef0ae --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_access_sequence.hpp @@ -0,0 +1,80 @@ +/* Copyright 2003-2021 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_ACCESS_SEQUENCE_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_ACCESS_SEQUENCE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/if.hpp> +#include <boost/mpl/size.hpp> +#include <boost/multi_index_container_fwd.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Successive access to the indices of a multi_index_container. Used as dst in + * backbone function extract_(x,dst) to retrieve the destination indices + * where iterators referring to x must be transferred to (in merging + * operations). + */ + +template<typename MultiIndexContainer,int N=0> +struct index_access_sequence; + +struct index_access_sequence_terminal +{ + index_access_sequence_terminal(void*){} +}; + +template<typename MultiIndexContainer,int N> +struct index_access_sequence_normal +{ + MultiIndexContainer* p; + + index_access_sequence_normal(MultiIndexContainer* p_):p(p_){} + + typename nth_index<MultiIndexContainer,N>::type& + get(){return p->template get<N>();} + + index_access_sequence<MultiIndexContainer,N+1> + next(){return index_access_sequence<MultiIndexContainer,N+1>(p);} +}; + +template<typename MultiIndexContainer,int N> +struct index_access_sequence_base: + mpl::if_c< + N<mpl::size<typename MultiIndexContainer::index_type_list>::type::value, + index_access_sequence_normal<MultiIndexContainer,N>, + index_access_sequence_terminal + > +{}; + +template<typename MultiIndexContainer,int N> +struct index_access_sequence: + index_access_sequence_base<MultiIndexContainer,N>::type +{ + typedef typename index_access_sequence_base< + MultiIndexContainer,N>::type super; + + index_access_sequence(MultiIndexContainer* p):super(p){} +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_base.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_base.hpp index 22cf0f14027..ede5a30566a 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_base.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_base.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2017 Joaquin M Lopez Munoz. +/* Copyright 2003-2021 Joaquin M Lopez Munoz. * 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) @@ -15,14 +15,15 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <boost/core/addressof.hpp> -#include <boost/detail/allocator_utilities.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/detail/workaround.hpp> -#include <boost/move/core.hpp> -#include <boost/move/utility.hpp> +#include <boost/move/utility_core.hpp> #include <boost/mpl/vector.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/copy_map.hpp> #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> +#include <boost/multi_index/detail/index_access_sequence.hpp> +#include <boost/multi_index/detail/node_handle.hpp> #include <boost/multi_index/detail/node_type.hpp> #include <boost/multi_index/detail/vartempl_support.hpp> #include <boost/multi_index_container_fwd.hpp> @@ -56,17 +57,17 @@ template<typename Value,typename IndexSpecifierList,typename Allocator> class index_base { protected: - typedef index_node_base<Value,Allocator> node_type; + typedef index_node_base<Value,Allocator> index_node_type; typedef typename multi_index_node_type< Value,IndexSpecifierList,Allocator>::type final_node_type; typedef multi_index_container< Value,IndexSpecifierList,Allocator> final_type; typedef tuples::null_type ctor_args_list; - typedef typename - boost::detail::allocator::rebind_to< - Allocator, - typename Allocator::value_type + typedef typename rebind_alloc_for< + Allocator,typename Allocator::value_type >::type final_allocator_type; + typedef node_handle< + final_node_type,final_allocator_type> final_node_handle_type; typedef mpl::vector0<> index_type_list; typedef mpl::vector0<> iterator_type_list; typedef mpl::vector0<> const_iterator_type_list; @@ -76,16 +77,18 @@ protected: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) typedef index_saver< - node_type, + index_node_type, final_allocator_type> index_saver_type; typedef index_loader< - node_type, + index_node_type, final_node_type, final_allocator_type> index_loader_type; #endif private: typedef Value value_type; + typedef allocator_traits<Allocator> alloc_traits; + typedef typename alloc_traits::size_type size_type; protected: explicit index_base(const ctor_args_list&,const Allocator&){} @@ -103,7 +106,7 @@ protected: { x=final().allocate_node(); BOOST_TRY{ - boost::detail::allocator::construct(boost::addressof(x->value()),v); + final().construct_value(x,v); } BOOST_CATCH(...){ final().deallocate_node(x); @@ -117,15 +120,7 @@ protected: { x=final().allocate_node(); BOOST_TRY{ - /* This shoud have used a modified, T&&-compatible version of - * boost::detail::allocator::construct, but - * <boost/detail/allocator_utilities.hpp> is too old and venerable to - * mess with; besides, it is a general internal utility and the imperfect - * perfect forwarding emulation of Boost.Move might break other libs. - */ - - new (boost::addressof(x->value())) - value_type(boost::move(const_cast<value_type&>(v))); + final().construct_value(x,boost::move(const_cast<value_type&>(v))); } BOOST_CATCH(...){ final().deallocate_node(x); @@ -140,57 +135,63 @@ protected: return x; } + template<typename MultiIndexContainer> final_node_type* insert_( - const value_type& v,node_type*,final_node_type*& x,lvalue_tag) + const value_type&,final_node_type*& x,MultiIndexContainer* p) { - return insert_(v,x,lvalue_tag()); + p->final_extract_for_transfer_( + x,index_access_sequence<final_type>(&final())); + return x; } final_node_type* insert_( - const value_type& v,node_type*,final_node_type*& x,rvalue_tag) + const value_type& v,index_node_type*,final_node_type*& x,lvalue_tag) { - return insert_(v,x,rvalue_tag()); + return insert_(v,x,lvalue_tag()); } final_node_type* insert_( - const value_type&,node_type*,final_node_type*& x,emplaced_tag) + const value_type& v,index_node_type*,final_node_type*& x,rvalue_tag) { - return x; + return insert_(v,x,rvalue_tag()); } - void erase_(node_type* x) + final_node_type* insert_( + const value_type&,index_node_type*,final_node_type*& x,emplaced_tag) { - boost::detail::allocator::destroy(boost::addressof(x->value())); + return x; } - void delete_node_(node_type* x) - { - boost::detail::allocator::destroy(boost::addressof(x->value())); - } + template<typename Dst> + void extract_(index_node_type*,Dst){} void clear_(){} - void swap_(index_base<Value,IndexSpecifierList,Allocator>&){} + template<typename BoolConstant> + void swap_( + index_base<Value,IndexSpecifierList,Allocator>&, + BoolConstant /* swap_allocators */) + {} void swap_elements_(index_base<Value,IndexSpecifierList,Allocator>&){} - bool replace_(const value_type& v,node_type* x,lvalue_tag) + bool replace_(const value_type& v,index_node_type* x,lvalue_tag) { x->value()=v; return true; } - bool replace_(const value_type& v,node_type* x,rvalue_tag) + bool replace_(const value_type& v,index_node_type* x,rvalue_tag) { x->value()=boost::move(const_cast<value_type&>(v)); return true; } - bool modify_(node_type*){return true;} + bool modify_(index_node_type*){return true;} - bool modify_rollback_(node_type*){return true;} + bool modify_rollback_(index_node_type*){return true;} - bool check_rollback_(node_type*)const{return true;} + bool check_rollback_(index_node_type*)const{return true;} #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) /* serialization */ @@ -213,11 +214,15 @@ protected: final_type& final(){return *static_cast<final_type*>(this);} const final_type& final()const{return *static_cast<const final_type*>(this);} + template<typename Index> + static typename Index::final_type& final(Index& x) /* cross-index access */ + {return static_cast<typename Index::final_type&>(x);} + final_node_type* final_header()const{return final().header();} - bool final_empty_()const{return final().empty_();} - std::size_t final_size_()const{return final().size_();} - std::size_t final_max_size_()const{return final().max_size_();} + bool final_empty_()const{return final().empty_();} + size_type final_size_()const{return final().size_();} + size_type final_max_size_()const{return final().max_size_();} std::pair<final_node_type*,bool> final_insert_(const value_type& x) {return final().insert_(x);} @@ -229,6 +234,12 @@ protected: template<typename T> std::pair<final_node_type*,bool> final_insert_ref_(T& t) {return final().insert_ref_(t);} + std::pair<final_node_type*,bool> final_insert_nh_(final_node_handle_type& nh) + {return final().insert_nh_(nh);} + + template<typename Index> + std::pair<final_node_type*,bool> final_transfer_(Index& x,final_node_type* n) + {return final().transfer_(x,n);} template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> std::pair<final_node_type*,bool> final_emplace_( @@ -251,6 +262,9 @@ protected: std::pair<final_node_type*,bool> final_insert_ref_( T& t,final_node_type* position) {return final().insert_ref_(t,position);} + std::pair<final_node_type*,bool> final_insert_nh_( + final_node_handle_type& nh,final_node_type* position) + {return final().insert_nh_(nh,position);} template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> std::pair<final_node_type*,bool> final_emplace_hint_( @@ -260,12 +274,30 @@ protected: position,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); } + final_node_handle_type final_extract_(final_node_type* x) + { + return final().extract_(x); + } + + template<typename Dst> + void final_extract_for_transfer_(final_node_type* x,Dst dst) + { + final().extract_for_transfer_(x,dst); + } + void final_erase_(final_node_type* x){final().erase_(x);} void final_delete_node_(final_node_type* x){final().delete_node_(x);} void final_delete_all_nodes_(){final().delete_all_nodes_();} void final_clear_(){final().clear_();} + template<typename Index> + void final_transfer_range_( + Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + {final().transfer_range_(x,first,last);} + void final_swap_(final_type& x){final().swap_(x);} bool final_replace_( diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_loader.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_loader.hpp index 71418a10e19..cab79f0a786 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_loader.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_loader.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2015 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -16,7 +16,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> #include <boost/archive/archive_exception.hpp> -#include <boost/noncopyable.hpp> +#include <boost/core/noncopyable.hpp> #include <boost/multi_index/detail/auto_space.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> #include <boost/serialization/nvp.hpp> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_matcher.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_matcher.hpp index 34d1f9d5a8d..37a41197967 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_matcher.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_matcher.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2015 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -15,7 +15,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> -#include <boost/noncopyable.hpp> +#include <boost/core/noncopyable.hpp> #include <boost/multi_index/detail/auto_space.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> #include <cstddef> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_saver.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_saver.hpp index ae09d4eba4f..0f7b6efef15 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_saver.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/index_saver.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -15,7 +15,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <boost/multi_index/detail/index_matcher.hpp> -#include <boost/noncopyable.hpp> +#include <boost/core/noncopyable.hpp> #include <boost/serialization/nvp.hpp> #include <cstddef> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/invalidate_iterators.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/invalidate_iterators.hpp new file mode 100644 index 00000000000..8d6ed85d6e7 --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/invalidate_iterators.hpp @@ -0,0 +1,44 @@ +/* Copyright 2003-2021 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INVALIDATE_ITERATORS_HPP +#define BOOST_MULTI_INDEX_DETAIL_INVALIDATE_ITERATORS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* invalidate_iterators mimics the interface of index_access_sequence (see + * index_access_sequence.hpp) but returns dummy indices whose iterator type + * won't ever match those of the source: the net effect is that safe iterator + * transfer resolves to iterator invalidation, so backbone function invocation + * extract_(x,invalidate_iterators()) is used in extraction scenarios other + * than merging. + */ + +struct invalidate_iterators +{ + typedef void iterator; + + invalidate_iterators& get(){return *this;} + invalidate_iterators& next(){return *this;} +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/node_handle.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/node_handle.hpp new file mode 100644 index 00000000000..bd2427499d4 --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/node_handle.hpp @@ -0,0 +1,267 @@ +/* Copyright 2003-2021 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_NODE_HANDLE_HPP +#define BOOST_MULTI_INDEX_DETAIL_NODE_HANDLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <algorithm> +#include <boost/core/addressof.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/multi_index_container_fwd.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <new> + +#if !defined(BOOST_NO_SFINAE) +#include <boost/type_traits/is_const.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/utility/enable_if.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Node handle template class following [container.node] specs. + */ + +#include <boost/multi_index/detail/define_if_constexpr_macro.hpp> + +template<typename Node,typename Allocator> +class node_handle +{ +public: + typedef typename Node::value_type value_type; + typedef Allocator allocator_type; + +private: + typedef allocator_traits<allocator_type> alloc_traits; + +public: + node_handle()BOOST_NOEXCEPT:node(0){} + + node_handle(BOOST_RV_REF(node_handle) x)BOOST_NOEXCEPT:node(x.node) + { + if(!x.empty()){ + move_construct_allocator(boost::move(x)); + x.destroy_allocator(); + x.node=0; + } + } + + ~node_handle() + { + if(!empty()){ + delete_node(); + destroy_allocator(); + } + } + + node_handle& operator=(BOOST_RV_REF(node_handle) x) + { + if(this!=&x){ + if(!empty()){ + delete_node(); + if(!x.empty()){ + BOOST_MULTI_INDEX_IF_CONSTEXPR( + alloc_traits::propagate_on_container_move_assignment::value){ + move_assign_allocator(boost::move(x)); + } + x.destroy_allocator(); + } + else{ + destroy_allocator(); + } + } + else if(!x.empty()){ + move_construct_allocator(boost::move(x)); + x.destroy_allocator(); + } + node=x.node; + x.node=0; + } + return *this; + } + + value_type& value()const{return node->value();} + allocator_type get_allocator()const{return *allocator_ptr();} + +#if !defined(BOOST_NO_CXX11_EXPLICIT_CONVERSION_OPERATORS) + explicit +#endif + operator bool()const BOOST_NOEXCEPT{return (node!=0);} + +#if BOOST_WORKAROUND(BOOST_GCC_VERSION,>=70000)&&__cplusplus<201103L + /* https://github.com/boostorg/config/issues/336 */ +#else + BOOST_ATTRIBUTE_NODISCARD +#endif + bool empty()const BOOST_NOEXCEPT{return (node==0);} + + void swap(node_handle& x) + BOOST_NOEXCEPT_IF( + alloc_traits::propagate_on_container_swap::value|| + alloc_traits::is_always_equal::value) + { + if(!empty()){ + if(!x.empty()){ + BOOST_MULTI_INDEX_IF_CONSTEXPR( + alloc_traits::propagate_on_container_swap::value){ + using std::swap; + swap(*allocator_ptr(),*x.allocator_ptr()); + } + } + else{ + x.move_construct_allocator(boost::move(*this)); + destroy_allocator(); + } + } + else if(!x.empty()){ + move_construct_allocator(boost::move(x)); + x.destroy_allocator(); + } + std::swap(node,x.node); + } + + friend void swap(node_handle& x,node_handle& y) + BOOST_NOEXCEPT_IF(noexcept(x.swap(y))) + { + x.swap(y); + } + +private: + BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle) + + template <typename,typename,typename> + friend class boost::multi_index::multi_index_container; + + node_handle(Node* node_,const allocator_type& al):node(node_) + { + ::new (static_cast<void*>(allocator_ptr())) allocator_type(al); + } + + void release_node() + { + if(!empty()){ + node=0; + destroy_allocator(); + } + } + +#include <boost/multi_index/detail/ignore_wstrict_aliasing.hpp> + + const allocator_type* allocator_ptr()const + { + return reinterpret_cast<const allocator_type*>(&space); + } + + allocator_type* allocator_ptr() + { + return reinterpret_cast<allocator_type*>(&space); + } + +#include <boost/multi_index/detail/restore_wstrict_aliasing.hpp> + + void move_construct_allocator(BOOST_RV_REF(node_handle) x) + { + ::new (static_cast<void*>(allocator_ptr())) + allocator_type(boost::move(*x.allocator_ptr())); + } + + void move_assign_allocator(BOOST_RV_REF(node_handle) x) + { + *allocator_ptr()=boost::move(*x.allocator_ptr()); + } + + void destroy_allocator(){allocator_ptr()->~allocator_type();} + + void delete_node() + { + typedef typename rebind_alloc_for< + allocator_type,Node + >::type node_allocator; + typedef detail::allocator_traits<node_allocator> node_alloc_traits; + typedef typename node_alloc_traits::pointer node_pointer; + + alloc_traits::destroy(*allocator_ptr(),boost::addressof(node->value())); + node_allocator nal(*allocator_ptr()); + node_alloc_traits::deallocate(nal,static_cast<node_pointer>(node),1); + } + + Node* node; + typename aligned_storage< + sizeof(allocator_type), + alignment_of<allocator_type>::value + >::type space; +}; + +#include <boost/multi_index/detail/undef_if_constexpr_macro.hpp> + +/* node handle insert return type template class following + * [container.insert.return] specs. + */ + +template<typename Iterator,typename NodeHandle> +struct insert_return_type +{ + insert_return_type( + Iterator position_,bool inserted_,BOOST_RV_REF(NodeHandle) node_): + position(position_),inserted(inserted_),node(boost::move(node_)){} + insert_return_type(BOOST_RV_REF(insert_return_type) x): + position(x.position),inserted(x.inserted),node(boost::move(x.node)){} + + insert_return_type& operator=(BOOST_RV_REF(insert_return_type) x) + { + position=x.position; + inserted=x.inserted; + node=boost::move(x.node); + return *this; + } + + Iterator position; + bool inserted; + NodeHandle node; + +private: + BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type) +}; + +/* utility for SFINAEing merge and related operations */ + +#if !defined(BOOST_NO_SFINAE) + +#define BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(Dst,Src,T) \ +typename enable_if_c< \ + !is_const< Dst >::value&&!is_const< Src >::value&& \ + is_same<typename Dst::node_type,typename Src::node_type>::value, \ + T \ +>::type + +#else + +#define BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(Dst,Src,T) T + +#endif + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_impl.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_impl.hpp index 1093b87c99e..93d47df018f 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_impl.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_impl.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -44,19 +44,25 @@ #include <algorithm> #include <boost/call_traits.hpp> #include <boost/core/addressof.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> +#include <boost/core/ref.hpp> #include <boost/detail/workaround.hpp> #include <boost/foreach_fwd.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/push_front.hpp> #include <boost/multi_index/detail/access_specifier.hpp> +#include <boost/multi_index/detail/adl_swap.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/bidir_node_iterator.hpp> #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> #include <boost/multi_index/detail/index_node_base.hpp> +#include <boost/multi_index/detail/invalidate_iterators.hpp> #include <boost/multi_index/detail/modify_key_adaptor.hpp> +#include <boost/multi_index/detail/node_handle.hpp> #include <boost/multi_index/detail/ord_index_node.hpp> #include <boost/multi_index/detail/ord_index_ops.hpp> #include <boost/multi_index/detail/safe_mode.hpp> @@ -65,11 +71,9 @@ #include <boost/multi_index/detail/value_compare.hpp> #include <boost/multi_index/detail/vartempl_support.hpp> #include <boost/multi_index/detail/ord_index_impl_fwd.hpp> -#include <boost/ref.hpp> #include <boost/tuple/tuple.hpp> #include <boost/type_traits/is_same.hpp> #include <utility> -#include <memory> #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> @@ -77,7 +81,7 @@ #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) #include <boost/archive/archive_exception.hpp> -#include <boost/bind.hpp> +#include <boost/bind/bind.hpp> #include <boost/multi_index/detail/duplicates_iterator.hpp> #include <boost/throw_exception.hpp> #endif @@ -112,6 +116,11 @@ namespace detail{ struct ordered_unique_tag{}; struct ordered_non_unique_tag{}; +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4355) /* this used in base member initializer list */ +#endif + template< typename KeyFromValue,typename Compare, typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy @@ -124,13 +133,6 @@ template< > class ordered_index_impl: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - ,public safe_mode::safe_container< - ordered_index_impl< - KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy> > -#endif - { #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) @@ -142,59 +144,60 @@ class ordered_index_impl: #pragma parse_mfunc_templ off #endif +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + /* cross-index access */ + + template <typename,typename,typename> friend class index_base; +#endif + typedef typename SuperMeta::type super; protected: typedef ordered_index_node< - AugmentPolicy,typename super::node_type> node_type; + AugmentPolicy,typename super::index_node_type> index_node_type; protected: /* for the benefit of AugmentPolicy::augmented_interface */ - typedef typename node_type::impl_type node_impl_type; + typedef typename index_node_type::impl_type node_impl_type; typedef typename node_impl_type::pointer node_impl_pointer; public: /* types */ typedef typename KeyFromValue::result_type key_type; - typedef typename node_type::value_type value_type; + typedef typename index_node_type::value_type value_type; typedef KeyFromValue key_from_value; typedef Compare key_compare; typedef value_comparison< value_type,KeyFromValue,Compare> value_compare; typedef tuple<key_from_value,key_compare> ctor_args; typedef typename super::final_allocator_type allocator_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::reference reference; - typedef typename allocator_type::const_reference const_reference; -#else typedef value_type& reference; typedef const value_type& const_reference; -#endif #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) typedef safe_mode::safe_iterator< - bidir_node_iterator<node_type>, - ordered_index_impl> iterator; + bidir_node_iterator<index_node_type> > iterator; #else - typedef bidir_node_iterator<node_type> iterator; + typedef bidir_node_iterator<index_node_type> iterator; #endif typedef iterator const_iterator; - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::pointer pointer; - typedef typename allocator_type::const_pointer const_pointer; -#else - typedef std::allocator_traits<allocator_type> allocator_traits; - typedef typename allocator_traits::pointer pointer; - typedef typename allocator_traits::const_pointer const_pointer; -#endif +private: + typedef allocator_traits<allocator_type> alloc_traits; + +public: + typedef typename alloc_traits::size_type size_type; + typedef typename alloc_traits::difference_type difference_type; + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::const_pointer const_pointer; typedef typename boost::reverse_iterator<iterator> reverse_iterator; typedef typename boost::reverse_iterator<const_iterator> const_reverse_iterator; + typedef typename super::final_node_handle_type node_type; + typedef detail::insert_return_type< + iterator,node_type> insert_return_type; typedef TagList tag_list; protected: @@ -223,8 +226,7 @@ protected: protected: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef safe_mode::safe_container< - ordered_index_impl> safe_super; + typedef safe_mode::safe_container<iterator> safe_container; #endif typedef typename call_traits< @@ -232,11 +234,9 @@ protected: typedef typename call_traits< key_type>::param_type key_param_type; - /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL - * expansion. - */ + /* needed to avoid commas in some macros */ - typedef std::pair<iterator,bool> emplace_return_type; + typedef std::pair<iterator,bool> pair_return_type; public: @@ -280,12 +280,14 @@ public: iterator iterator_to(const value_type& x) { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } const_iterator iterator_to(const value_type& x)const { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } /* capacity */ @@ -297,7 +299,7 @@ public: /* modifiers */ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( - emplace_return_type,emplace,emplace_impl) + pair_return_type,emplace,emplace_impl) BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( iterator,emplace_hint,emplace_hint_impl,iterator,position) @@ -340,11 +342,11 @@ public: void insert(InputIterator first,InputIterator last) { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; - node_type* hint=header(); /* end() */ + index_node_type* hint=header(); /* end() */ for(;first!=last;++first){ hint=this->final_insert_ref_( *first,static_cast<final_node_type*>(hint)).first; - node_type::increment(hint); + index_node_type::increment(hint); } } @@ -355,6 +357,42 @@ public: } #endif + insert_return_type insert(BOOST_RV_REF(node_type) nh) + { + if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh); + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh); + return insert_return_type(make_iterator(p.first),p.second,boost::move(nh)); + } + + iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh); + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_nh_( + nh,static_cast<final_node_type*>(position.get_node())); + return make_iterator(p.first); + } + + node_type extract(const_iterator position) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; + return this->final_extract_( + static_cast<final_node_type*>(position.get_node())); + } + + node_type extract(key_param_type x) + { + iterator position=lower_bound(x); + if(position==end()||comp_(x,key(*position)))return node_type(); + else return extract(position); + } + iterator erase(iterator position) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); @@ -492,6 +530,75 @@ public: this->final_clear_(); } + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void) + merge(Index& x) + { + merge(x,x.begin(),x.end()); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void) + merge(BOOST_RV_REF(Index) x){merge(static_cast<Index&>(x));} + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE( + ordered_index_impl,Index,pair_return_type) + merge(Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; + if(x.end().get_node()==this->header()){ /* same container */ + return std::pair<iterator,bool>( + make_iterator(static_cast<final_node_type*>(i.get_node())),true); + } + else{ + std::pair<final_node_type*,bool> p=this->final_transfer_( + x,static_cast<final_node_type*>(i.get_node())); + return std::pair<iterator,bool>(make_iterator(p.first),p.second); + } + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE( + ordered_index_impl,Index,pair_return_type) + merge(BOOST_RV_REF(Index) x,BOOST_DEDUCED_TYPENAME Index::iterator i) + { + return merge(static_cast<Index&>(x),i); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void) + merge( + Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; + if(x.end().get_node()!=this->header()){ /* different containers */ + this->final_transfer_range_(x,first,last); + } + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void) + merge( + BOOST_RV_REF(Index) x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + { + merge(static_cast<Index&>(x),first,last); + } + /* observers */ key_from_value key_extractor()const{return key;} @@ -527,11 +634,24 @@ public: size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const { std::pair<iterator,iterator> p=equal_range(x,comp); - size_type n=std::distance(p.first,p.second); + size_type n=static_cast<size_type>(std::distance(p.first,p.second)); return n; } template<typename CompatibleKey> + bool contains(const CompatibleKey& x)const + { + return contains(x,comp_); + } + + template<typename CompatibleKey,typename CompatibleCompare> + bool contains( + const CompatibleKey& x,const CompatibleCompare& comp)const + { + return find(x,comp)!=end(); + } + + template<typename CompatibleKey> iterator lower_bound(const CompatibleKey& x)const { return make_iterator( @@ -565,7 +685,7 @@ public: std::pair<iterator,iterator> equal_range( const CompatibleKey& x)const { - std::pair<node_type*,node_type*> p= + std::pair<index_node_type*,index_node_type*> p= ordered_index_equal_range(root(),header(),key,x,comp_); return std::pair<iterator,iterator>( make_iterator(p.first),make_iterator(p.second)); @@ -575,7 +695,7 @@ public: std::pair<iterator,iterator> equal_range( const CompatibleKey& x,const CompatibleCompare& comp)const { - std::pair<node_type*,node_type*> p= + std::pair<index_node_type*,index_node_type*> p= ordered_index_equal_range(root(),header(),key,x,comp); return std::pair<iterator,iterator>( make_iterator(p.first),make_iterator(p.second)); @@ -609,6 +729,11 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: super(args_list.get_tail(),al), key(tuples::get<0>(args_list.get_head())), comp_(tuples::get<1>(args_list.get_head())) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe(*this) +#endif + { empty_initialize(); } @@ -617,13 +742,13 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: const ordered_index_impl< KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x): super(x), + key(x.key), + comp_(x.comp_) #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super(), + ,safe(*this) #endif - key(x.key), - comp_(x.comp_) { /* Copy ctor just takes the key and compare objects from x. The rest is * done in a subsequent call to copy_(). @@ -635,13 +760,13 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, do_not_copy_elements_tag): super(x,do_not_copy_elements_tag()), + key(x.key), + comp_(x.comp_) #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super(), + ,safe(*this) #endif - key(x.key), - comp_(x.comp_) { empty_initialize(); } @@ -652,12 +777,13 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - iterator make_iterator(node_type* node){return iterator(node,this);} - const_iterator make_iterator(node_type* node)const - {return const_iterator(node,const_cast<ordered_index_impl*>(this));} + iterator make_iterator(index_node_type* node) + {return iterator(node,&safe);} + const_iterator make_iterator(index_node_type* node)const + {return const_iterator(node,const_cast<safe_container*>(&safe));} #else - iterator make_iterator(node_type* node){return iterator(node);} - const_iterator make_iterator(node_type* node)const + iterator make_iterator(index_node_type* node){return iterator(node);} + const_iterator make_iterator(index_node_type* node)const {return const_iterator(node);} #endif @@ -673,21 +799,22 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: header()->color()=x.header()->color(); AugmentPolicy::copy(x.header()->impl(),header()->impl()); - node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root())); + index_node_type* root_cpy=map.find( + static_cast<final_node_type*>(x.root())); header()->parent()=root_cpy->impl(); - node_type* leftmost_cpy=map.find( + index_node_type* leftmost_cpy=map.find( static_cast<final_node_type*>(x.leftmost())); header()->left()=leftmost_cpy->impl(); - node_type* rightmost_cpy=map.find( + index_node_type* rightmost_cpy=map.find( static_cast<final_node_type*>(x.rightmost())); header()->right()=rightmost_cpy->impl(); typedef typename copy_map_type::const_iterator copy_map_iterator; for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){ - node_type* org=it->first; - node_type* cpy=it->second; + index_node_type* org=it->first; + index_node_type* cpy=it->second; cpy->color()=org->color(); AugmentPolicy::copy(org->impl(),cpy->impl()); @@ -695,8 +822,9 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: node_impl_pointer parent_org=org->parent(); if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0); else{ - node_type* parent_cpy=map.find( - static_cast<final_node_type*>(node_type::from_impl(parent_org))); + index_node_type* parent_cpy=map.find( + static_cast<final_node_type*>( + index_node_type::from_impl(parent_org))); cpy->parent()=parent_cpy->impl(); if(parent_org->left()==org->impl()){ parent_cpy->left()=cpy->impl(); @@ -723,42 +851,48 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: { link_info inf; if(!link_point(key(v),inf,Category())){ - return static_cast<final_node_type*>(node_type::from_impl(inf.pos)); + return static_cast<final_node_type*>( + index_node_type::from_impl(inf.pos)); } final_node_type* res=super::insert_(v,x,variant); if(res==x){ node_impl_type::link( - static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl()); + static_cast<index_node_type*>(x)->impl(), + inf.side,inf.pos,header()->impl()); } return res; } template<typename Variant> final_node_type* insert_( - value_param_type v,node_type* position,final_node_type*& x,Variant variant) + value_param_type v,index_node_type* position, + final_node_type*& x,Variant variant) { link_info inf; if(!hinted_link_point(key(v),position,inf,Category())){ - return static_cast<final_node_type*>(node_type::from_impl(inf.pos)); + return static_cast<final_node_type*>( + index_node_type::from_impl(inf.pos)); } final_node_type* res=super::insert_(v,position,x,variant); if(res==x){ node_impl_type::link( - static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl()); + static_cast<index_node_type*>(x)->impl(), + inf.side,inf.pos,header()->impl()); } return res; } - void erase_(node_type* x) + template<typename Dst> + void extract_(index_node_type* x,Dst dst) { - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); - super::erase_(x); + super::extract_(x,dst.next()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - detach_iterators(x); + transfer_iterators(dst.get(),x); #endif } @@ -773,22 +907,24 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: empty_initialize(); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::detach_dereferenceable_iterators(); + safe.detach_dereferenceable_iterators(); #endif } + template<typename BoolConstant> void swap_( ordered_index_impl< - KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x) + KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x, + BoolConstant swap_allocators) { - std::swap(key,x.key); - std::swap(comp_,x.comp_); + adl_swap(key,x.key); + adl_swap(comp_,x.comp_); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif - super::swap_(x); + super::swap_(x,swap_allocators); } void swap_elements_( @@ -796,23 +932,23 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x) { #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif super::swap_elements_(x); } template<typename Variant> - bool replace_(value_param_type v,node_type* x,Variant variant) + bool replace_(value_param_type v,index_node_type* x,Variant variant) { if(in_place(v,x,Category())){ return super::replace_(v,x,variant); } - node_type* next=x; - node_type::increment(next); + index_node_type* next=x; + index_node_type::increment(next); - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ @@ -831,24 +967,24 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool modify_(node_type* x) + bool modify_(index_node_type* x) { bool b; BOOST_TRY{ b=in_place(x->value(),x,Category()); } BOOST_CATCH(...){ - erase_(x); + extract_(x,invalidate_iterators()); BOOST_RETHROW; } BOOST_CATCH_END if(!b){ - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ link_info inf; if(!link_point(key(x->value()),inf,Category())){ - super::erase_(x); + super::extract_(x,invalidate_iterators()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); @@ -858,7 +994,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); } BOOST_CATCH(...){ - super::erase_(x); + super::extract_(x,invalidate_iterators()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); @@ -871,7 +1007,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_TRY{ if(!super::modify_(x)){ - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) @@ -883,7 +1019,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: else return true; } BOOST_CATCH(...){ - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) @@ -895,16 +1031,16 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool modify_rollback_(node_type* x) + bool modify_rollback_(index_node_type* x) { if(in_place(x->value(),x,Category())){ return super::modify_rollback_(x); } - node_type* next=x; - node_type::increment(next); + index_node_type* next=x; + index_node_type::increment(next); - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ @@ -924,7 +1060,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool check_rollback_(node_type* x)const + bool check_rollback_(index_node_type* x)const { return in_place(x->value(),x,Category())&&super::check_rollback_(x); } @@ -962,9 +1098,9 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: std::size_t len=node_impl_type::black_count( leftmost()->impl(),root()->impl()); for(const_iterator it=begin(),it_end=end();it!=it_end;++it){ - node_type* x=it.get_node(); - node_type* left_x=node_type::from_impl(x->left()); - node_type* right_x=node_type::from_impl(x->right()); + index_node_type* x=it.get_node(); + index_node_type* left_x=index_node_type::from_impl(x->left()); + index_node_type* right_x=index_node_type::from_impl(x->right()); if(x->color()==red){ if((left_x&&left_x->color()==red)|| @@ -997,10 +1133,14 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #endif protected: /* for the benefit of AugmentPolicy::augmented_interface */ - node_type* header()const{return this->final_header();} - node_type* root()const{return node_type::from_impl(header()->parent());} - node_type* leftmost()const{return node_type::from_impl(header()->left());} - node_type* rightmost()const{return node_type::from_impl(header()->right());} + index_node_type* header()const + {return this->final_header();} + index_node_type* root()const + {return index_node_type::from_impl(header()->parent());} + index_node_type* leftmost()const + {return index_node_type::from_impl(header()->left());} + index_node_type* rightmost()const + {return index_node_type::from_impl(header()->right());} private: void empty_initialize() @@ -1024,22 +1164,22 @@ private: bool link_point(key_param_type k,link_info& inf,ordered_unique_tag) { - node_type* y=header(); - node_type* x=root(); + index_node_type* y=header(); + index_node_type* x=root(); bool c=true; while(x){ y=x; c=comp_(k,key(x->value())); - x=node_type::from_impl(c?x->left():x->right()); + x=index_node_type::from_impl(c?x->left():x->right()); } - node_type* yy=y; + index_node_type* yy=y; if(c){ if(yy==leftmost()){ inf.side=to_left; inf.pos=y->impl(); return true; } - else node_type::decrement(yy); + else index_node_type::decrement(yy); } if(comp_(key(yy->value()),k)){ @@ -1055,13 +1195,13 @@ private: bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) { - node_type* y=header(); - node_type* x=root(); + index_node_type* y=header(); + index_node_type* x=root(); bool c=true; while (x){ y=x; c=comp_(k,key(x->value())); - x=node_type::from_impl(c?x->left():x->right()); + x=index_node_type::from_impl(c?x->left():x->right()); } inf.side=c?to_left:to_right; inf.pos=y->impl(); @@ -1070,13 +1210,13 @@ private: bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) { - node_type* y=header(); - node_type* x=root(); + index_node_type* y=header(); + index_node_type* x=root(); bool c=false; while (x){ y=x; c=comp_(key(x->value()),k); - x=node_type::from_impl(c?x->right():x->left()); + x=index_node_type::from_impl(c?x->right():x->left()); } inf.side=c?to_right:to_left; inf.pos=y->impl(); @@ -1084,7 +1224,8 @@ private: } bool hinted_link_point( - key_param_type k,node_type* position,link_info& inf,ordered_unique_tag) + key_param_type k,index_node_type* position, + link_info& inf,ordered_unique_tag) { if(position->impl()==header()->left()){ if(size()>0&&comp_(k,key(position->value()))){ @@ -1103,8 +1244,8 @@ private: else return link_point(k,inf,ordered_unique_tag()); } else{ - node_type* before=position; - node_type::decrement(before); + index_node_type* before=position; + index_node_type::decrement(before); if(comp_(key(before->value()),k)&&comp_(k,key(position->value()))){ if(before->right()==node_impl_pointer(0)){ inf.side=to_right; @@ -1122,7 +1263,8 @@ private: } bool hinted_link_point( - key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag) + key_param_type k,index_node_type* position, + link_info& inf,ordered_non_unique_tag) { if(position->impl()==header()->left()){ if(size()>0&&!comp_(key(position->value()),k)){ @@ -1141,8 +1283,8 @@ private: else return link_point(k,inf,ordered_non_unique_tag()); } else{ - node_type* before=position; - node_type::decrement(before); + index_node_type* before=position; + index_node_type::decrement(before); if(!comp_(k,key(before->value()))){ if(!comp_(key(position->value()),k)){ if(before->right()==node_impl_pointer(0)){ @@ -1162,49 +1304,57 @@ private: } } - void delete_all_nodes(node_type* x) + void delete_all_nodes(index_node_type* x) { if(!x)return; - delete_all_nodes(node_type::from_impl(x->left())); - delete_all_nodes(node_type::from_impl(x->right())); + delete_all_nodes(index_node_type::from_impl(x->left())); + delete_all_nodes(index_node_type::from_impl(x->right())); this->final_delete_node_(static_cast<final_node_type*>(x)); } - bool in_place(value_param_type v,node_type* x,ordered_unique_tag)const + bool in_place(value_param_type v,index_node_type* x,ordered_unique_tag)const { - node_type* y; + index_node_type* y; if(x!=leftmost()){ y=x; - node_type::decrement(y); + index_node_type::decrement(y); if(!comp_(key(y->value()),key(v)))return false; } y=x; - node_type::increment(y); + index_node_type::increment(y); return y==header()||comp_(key(v),key(y->value())); } - bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)const + bool in_place( + value_param_type v,index_node_type* x,ordered_non_unique_tag)const { - node_type* y; + index_node_type* y; if(x!=leftmost()){ y=x; - node_type::decrement(y); + index_node_type::decrement(y); if(comp_(key(v),key(y->value())))return false; } y=x; - node_type::increment(y); + index_node_type::increment(y); return y==header()||!comp_(key(y->value()),key(v)); } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - void detach_iterators(node_type* x) + void detach_iterators(index_node_type* x) { iterator it=make_iterator(x); safe_mode::detach_equivalent_iterators(it); } + + template<typename Dst> + void transfer_iterators(Dst& dst,index_node_type* x) + { + iterator it=make_iterator(x); + safe_mode::transfer_equivalent_iterators(dst,it); + } #endif template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> @@ -1234,23 +1384,23 @@ private: std::pair<iterator,iterator> range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const { - node_type* y=header(); - node_type* z=root(); + index_node_type* y=header(); + index_node_type* z=root(); while(z){ if(!lower(key(z->value()))){ - z=node_type::from_impl(z->right()); + z=index_node_type::from_impl(z->right()); } else if(!upper(key(z->value()))){ y=z; - z=node_type::from_impl(z->left()); + z=index_node_type::from_impl(z->left()); } else{ return std::pair<iterator,iterator>( make_iterator( - lower_range(node_type::from_impl(z->left()),z,lower)), + lower_range(index_node_type::from_impl(z->left()),z,lower)), make_iterator( - upper_range(node_type::from_impl(z->right()),y,upper))); + upper_range(index_node_type::from_impl(z->right()),y,upper))); } } @@ -1283,28 +1433,30 @@ private: } template<typename LowerBounder> - node_type * lower_range(node_type* top,node_type* y,LowerBounder lower)const + index_node_type * lower_range( + index_node_type* top,index_node_type* y,LowerBounder lower)const { while(top){ if(lower(key(top->value()))){ y=top; - top=node_type::from_impl(top->left()); + top=index_node_type::from_impl(top->left()); } - else top=node_type::from_impl(top->right()); + else top=index_node_type::from_impl(top->right()); } return y; } template<typename UpperBounder> - node_type * upper_range(node_type* top,node_type* y,UpperBounder upper)const + index_node_type * upper_range( + index_node_type* top,index_node_type* y,UpperBounder upper)const { while(top){ if(!upper(key(top->value()))){ y=top; - top=node_type::from_impl(top->left()); + top=index_node_type::from_impl(top->left()); } - else top=node_type::from_impl(top->right()); + else top=index_node_type::from_impl(top->right()); } return y; @@ -1332,7 +1484,7 @@ private: Archive& ar,const unsigned int version,const index_saver_type& sm, ordered_non_unique_tag)const { - typedef duplicates_iterator<node_type,value_compare> dup_iterator; + typedef duplicates_iterator<index_node_type,value_compare> dup_iterator; sm.save( dup_iterator(begin().get_node(),end().get_node(),value_comp()), @@ -1354,7 +1506,7 @@ private: super::load_(ar,version,lm); } - void rearranger(node_type* position,node_type *x) + void rearranger(index_node_type* position,index_node_type *x) { if(!position||comp_(key(position->value()),key(x->value()))){ position=lower_bound(key(x->value())).get_node(); @@ -1365,10 +1517,10 @@ private: archive::archive_exception( archive::archive_exception::other_exception)); } - else node_type::increment(position); + else index_node_type::increment(position); if(position!=x){ - node_impl_type::rebalance_for_erase( + node_impl_type::rebalance_for_extract( x->impl(),header()->parent(),header()->left(),header()->right()); node_impl_type::restore( x->impl(),position->impl(),header()->impl()); @@ -1380,6 +1532,10 @@ protected: /* for the benefit of AugmentPolicy::augmented_interface */ key_from_value key; key_compare comp_; +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_container safe; +#endif + #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) #pragma parse_mfunc_templ reset @@ -1434,12 +1590,16 @@ protected: const ctor_args_list& args_list,const allocator_type& al): super(args_list,al){} - ordered_index(const ordered_index& x):super(x){}; + ordered_index(const ordered_index& x):super(x){} ordered_index(const ordered_index& x,do_not_copy_elements_tag): - super(x,do_not_copy_elements_tag()){}; + super(x,do_not_copy_elements_tag()){} }; +#if defined(BOOST_MSVC) +#pragma warning(pop) /* C4355 */ +#endif + /* comparison */ template< diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_node.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_node.hpp index b4ed3ea3adc..72bffe33cca 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_node.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/ord_index_node.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -42,8 +42,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <cstddef> -#include <memory> -#include <boost/detail/allocator_utilities.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES) @@ -71,31 +70,29 @@ struct ordered_index_node_impl; /* fwd decl. */ template<typename AugmentPolicy,typename Allocator> struct ordered_index_node_traits { - typedef typename - boost::detail::allocator::rebind_to< + typedef typename rebind_alloc_for< Allocator, ordered_index_node_impl<AugmentPolicy,Allocator> >::type allocator; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator::pointer pointer; - typedef typename allocator::const_pointer const_pointer; -#else - typedef std::allocator_traits<allocator> allocator_traits; - typedef typename allocator_traits::pointer pointer; - typedef typename allocator_traits::const_pointer const_pointer; -#endif + typedef allocator_traits<allocator> alloc_traits; + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::const_pointer const_pointer; + typedef typename alloc_traits::difference_type difference_type; + typedef typename alloc_traits::size_type size_type; }; template<typename AugmentPolicy,typename Allocator> struct ordered_index_node_std_base { typedef ordered_index_node_traits< - AugmentPolicy,Allocator> node_traits; - typedef typename node_traits::allocator node_allocator; - typedef typename node_traits::pointer pointer; - typedef typename node_traits::const_pointer const_pointer; - typedef ordered_index_color& color_ref; - typedef pointer& parent_ref; + AugmentPolicy,Allocator> node_traits; + typedef typename node_traits::allocator node_allocator; + typedef typename node_traits::pointer pointer; + typedef typename node_traits::const_pointer const_pointer; + typedef typename node_traits::difference_type difference_type; + typedef typename node_traits::size_type size_type; + typedef ordered_index_color& color_ref; + typedef pointer& parent_ref; ordered_index_color& color(){return color_;} ordered_index_color color()const{return color_;} @@ -134,16 +131,19 @@ private: template<typename AugmentPolicy,typename Allocator> struct ordered_index_node_compressed_base { + typedef ordered_index_node_traits< + AugmentPolicy,Allocator> node_traits; typedef ordered_index_node_impl< - AugmentPolicy,Allocator>* pointer; + AugmentPolicy,Allocator>* pointer; typedef const ordered_index_node_impl< - AugmentPolicy,Allocator>* const_pointer; + AugmentPolicy,Allocator>* const_pointer; + typedef typename node_traits::difference_type difference_type; + typedef typename node_traits::size_type size_type; struct color_ref { color_ref(uintptr_type* r_):r(r_){} - - color_ref(color_ref const& x):r(x.r){} + color_ref(const color_ref& x):r(x.r){} operator ordered_index_color()const { @@ -169,8 +169,7 @@ struct ordered_index_node_compressed_base struct parent_ref { parent_ref(uintptr_type* r_):r(r_){} - - parent_ref(parent_ref const& x):r(x.r){} + parent_ref(const parent_ref& x):r(x.r){} operator pointer()const { @@ -413,7 +412,7 @@ public: ordered_index_node_impl::rebalance(x,header->parent()); } - static pointer rebalance_for_erase( + static pointer rebalance_for_extract( pointer z,parent_ref root,pointer& leftmost,pointer& rightmost) { pointer y=z; @@ -581,7 +580,7 @@ template<typename AugmentPolicy,typename Super> struct ordered_index_node_trampoline: ordered_index_node_impl< AugmentPolicy, - typename boost::detail::allocator::rebind_to< + typename rebind_alloc_for< typename Super::allocator_type, char >::type @@ -589,7 +588,7 @@ struct ordered_index_node_trampoline: { typedef ordered_index_node_impl< AugmentPolicy, - typename boost::detail::allocator::rebind_to< + typename rebind_alloc_for< typename Super::allocator_type, char >::type @@ -604,11 +603,13 @@ private: typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline; public: - typedef typename trampoline::impl_type impl_type; - typedef typename trampoline::color_ref impl_color_ref; - typedef typename trampoline::parent_ref impl_parent_ref; - typedef typename trampoline::pointer impl_pointer; - typedef typename trampoline::const_pointer const_impl_pointer; + typedef typename trampoline::impl_type impl_type; + typedef typename trampoline::color_ref impl_color_ref; + typedef typename trampoline::parent_ref impl_parent_ref; + typedef typename trampoline::pointer impl_pointer; + typedef typename trampoline::const_pointer const_impl_pointer; + typedef typename trampoline::difference_type difference_type; + typedef typename trampoline::size_type size_type; impl_color_ref color(){return trampoline::color();} ordered_index_color color()const{return trampoline::color();} diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/safe_mode.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/safe_mode.hpp index 905270e9fb3..0ba6b44835c 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/safe_mode.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/safe_mode.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2022 Joaquin M Lopez Munoz. * 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) @@ -15,9 +15,9 @@ /* Safe mode machinery, in the spirit of Cay Hortmann's "Safe STL" * (http://www.horstmann.com/safestl.html). - * In this mode, containers of type Container are derived from - * safe_container<Container>, and their corresponding iterators - * are wrapped with safe_iterator. These classes provide + * In this mode, containers have to redefine their iterators as + * safe_iterator<base_iterator> and keep a tracking object member of + * type safe_container<safe_iterator<base_iterator> >. These classes provide * an internal record of which iterators are at a given moment associated * to a given container, and properly mark the iterators as invalid * when the container gets destroyed. @@ -80,6 +80,11 @@ safe_mode::check_is_owner(it,cont), \ safe_mode::not_owner); +#define BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,cont) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_belongs_in_some_index(it,cont), \ + safe_mode::not_owner); + #define BOOST_MULTI_INDEX_CHECK_SAME_OWNER(it0,it1) \ BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ safe_mode::check_same_owner(it0,it1), \ @@ -105,14 +110,21 @@ safe_mode::check_different_container(cont0,cont1), \ safe_mode::same_container); +#define BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(cont0,cont1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_equal_allocators(cont0,cont1), \ + safe_mode::unequal_allocators); + #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> -#include <boost/detail/iterator.hpp> +#include <boost/core/addressof.hpp> + #include <boost/core/noncopyable.hpp> #include <boost/multi_index/detail/access_specifier.hpp> +#include <boost/multi_index/detail/any_container_view.hpp> #include <boost/multi_index/detail/iter_adaptor.hpp> #include <boost/multi_index/safe_mode_errors.hpp> -#include <boost/noncopyable.hpp> +#include <boost/type_traits/is_same.hpp> #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) #include <boost/serialization/split_member.hpp> @@ -121,6 +133,7 @@ #if defined(BOOST_HAS_THREADS) #include <boost/detail/lightweight_mutex.hpp> +#include <boost/multi_index/detail/scoped_bilock.hpp> #endif namespace boost{ @@ -158,18 +171,29 @@ inline bool check_decrementable_iterator(const Iterator& it) return (it.valid()&&it!=it.owner()->begin())||it.unchecked(); } -template<typename Iterator> +template<typename Iterator,typename Container> inline bool check_is_owner( - const Iterator& it,const typename Iterator::container_type& cont) + const Iterator& it,const Container& cont) { - return (it.valid()&&it.owner()==&cont)||it.unchecked(); + return (it.valid()&& + it.owner()->container()==cont.end().owner()->container()) + ||it.unchecked(); } +template<typename Iterator,typename MultiIndexContainer> +inline bool check_belongs_in_some_index( + const Iterator& it,const MultiIndexContainer& cont) +{ + return (it.valid()&&it.owner()->end().get_node()==cont.end().get_node()) + ||it.unchecked(); +} + template<typename Iterator> inline bool check_same_owner(const Iterator& it0,const Iterator& it1) { - return (it0.valid()&&it1.valid()&&it0.owner()==it1.owner())|| - it0.unchecked()||it1.unchecked(); + return (it0.valid()&&it1.valid()&& + it0.owner()->container()==it1.owner()->container()) + ||it0.unchecked()||it1.unchecked(); } template<typename Iterator> @@ -213,6 +237,28 @@ inline bool check_outside_range( return true; } +template<typename Iterator1,typename Iterator2> +inline bool check_outside_range( + const Iterator1& it,const Iterator2& it0,const Iterator2& it1) +{ + if(it.valid()&&it!=it.owner()->end()&&it0.valid()){ + Iterator2 last=it0.owner()->end(); + bool found=false; + + Iterator2 first=it0; + for(;first!=last;++first){ + if(first==it1)break; + + /* crucial that this check goes after previous break */ + + if(boost::addressof(*first)==boost::addressof(*it))found=true; + } + if(first!=it1)return false; + return !found; + } + return true; +} + template<typename Iterator,typename Difference> inline bool check_in_bounds(const Iterator& it,Difference n) { @@ -229,42 +275,33 @@ inline bool check_different_container( return &cont0!=&cont1; } -/* Invalidates all iterators equivalent to that given. Safe containers - * must call this when deleting elements: the safe mode framework cannot - * perform this operation automatically without outside help. - */ - -template<typename Iterator> -inline void detach_equivalent_iterators(Iterator& it) +template<typename Container1,typename Container2> +inline bool check_different_container(const Container1&,const Container2&) { - if(it.valid()){ - { -#if defined(BOOST_HAS_THREADS) - boost::detail::lightweight_mutex::scoped_lock lock(it.cont->mutex); -#endif + return true; +} - Iterator *prev_,*next_; - for( - prev_=static_cast<Iterator*>(&it.cont->header); - (next_=static_cast<Iterator*>(prev_->next))!=0;){ - if(next_!=&it&&*next_==it){ - prev_->next=next_->next; - next_->cont=0; - } - else prev_=next_; - } - } - it.detach(); - } +template<typename Container0,typename Container1> +inline bool check_equal_allocators( + const Container0& cont0,const Container1& cont1) +{ + return cont0.get_allocator()==cont1.get_allocator(); } -template<typename Container> class safe_container; /* fwd decl. */ +/* fwd decls */ -} /* namespace multi_index::safe_mode */ +template<typename Container> class safe_container; +template<typename Iterator> void detach_equivalent_iterators(Iterator&); -namespace detail{ +namespace safe_mode_detail{ -class safe_container_base; /* fwd decl. */ +/* fwd decls */ + +class safe_container_base; +template<typename Dst,typename Iterator> +void transfer_equivalent_iterators(Dst&,Iterator,boost::true_type); +template<typename Dst,typename Iterator> +inline void transfer_equivalent_iterators(Dst&,Iterator&,boost::false_type); class safe_iterator_base { @@ -314,12 +351,16 @@ protected: const safe_container_base* owner()const{return cont;} BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS: - friend class safe_container_base; #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template<typename> friend class safe_mode::safe_container; - template<typename Iterator> friend - void safe_mode::detach_equivalent_iterators(Iterator&); + friend class safe_container_base; + template<typename> + friend class safe_mode::safe_container; + template<typename Iterator> + friend void safe_mode::detach_equivalent_iterators(Iterator&); + template<typename Dst,typename Iterator> + friend void safe_mode_detail::transfer_equivalent_iterators( + Dst&,Iterator,boost::true_type); #endif inline void attach(safe_container_base* cont_); @@ -335,11 +376,14 @@ public: safe_container_base(){} BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: - friend class safe_iterator_base; #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template<typename Iterator> friend - void safe_mode::detach_equivalent_iterators(Iterator&); + friend class safe_iterator_base; + template<typename Iterator> + friend void safe_mode::detach_equivalent_iterators(Iterator&); + template<typename Dst,typename Iterator> + friend void safe_mode_detail::transfer_equivalent_iterators( + Dst&,Iterator,boost::true_type); #endif ~safe_container_base() @@ -394,42 +438,38 @@ void safe_iterator_base::detach() } } -} /* namespace multi_index::detail */ - -namespace safe_mode{ +} /* namespace multi_index::safe_mode::safe_mode_detail */ /* In order to enable safe mode on a container: - * - The container must derive from safe_container<container_type>, + * - The container must keep a member of type safe_container<iterator>, * - iterators must be generated via safe_iterator, which adapts a - * preexistent unsafe iterator class. + * preexistent unsafe iterator class. safe_iterators are passed the + * address of the previous safe_container member at construction time. */ -template<typename Container> -class safe_container; - -template<typename Iterator,typename Container> +template<typename Iterator> class safe_iterator: - public detail::iter_adaptor<safe_iterator<Iterator,Container>,Iterator>, - public detail::safe_iterator_base + public detail::iter_adaptor<safe_iterator<Iterator>,Iterator>, + public safe_mode_detail::safe_iterator_base { typedef detail::iter_adaptor<safe_iterator,Iterator> super; - typedef detail::safe_iterator_base safe_super; + typedef safe_mode_detail::safe_iterator_base safe_super; public: - typedef Container container_type; typedef typename Iterator::reference reference; typedef typename Iterator::difference_type difference_type; safe_iterator(){} - explicit safe_iterator(safe_container<container_type>* cont_): + explicit safe_iterator(safe_container<safe_iterator>* cont_): safe_super(cont_){} template<typename T0> - safe_iterator(const T0& t0,safe_container<container_type>* cont_): + safe_iterator(const T0& t0,safe_container<safe_iterator>* cont_): super(Iterator(t0)),safe_super(cont_){} template<typename T0,typename T1> safe_iterator( - const T0& t0,const T1& t1,safe_container<container_type>* cont_): + const T0& t0,const T1& t1,safe_container<safe_iterator>* cont_): super(Iterator(t0,t1)),safe_super(cont_){} + safe_iterator(const safe_iterator& x):super(x),safe_super(x){} safe_iterator& operator=(const safe_iterator& x) { @@ -439,12 +479,11 @@ public: return *this; } - const container_type* owner()const + const safe_container<safe_iterator>* owner()const { return - static_cast<const container_type*>( - static_cast<const safe_container<container_type>*>( - this->safe_super::owner())); + static_cast<const safe_container<safe_iterator>*>( + this->safe_super::owner()); } /* get_node is not to be used by the user */ @@ -535,21 +574,28 @@ private: #endif }; -template<typename Container> -class safe_container:public detail::safe_container_base +template<typename Iterator> +class safe_container:public safe_mode_detail::safe_container_base { - typedef detail::safe_container_base super; + typedef safe_mode_detail::safe_container_base super; + + detail::any_container_view<Iterator> view; public: + template<typename Container> + safe_container(const Container& c):view(c){} + + const void* container()const{return view.container();} + Iterator begin()const{return view.begin();} + Iterator end()const{return view.end();} + void detach_dereferenceable_iterators() { - typedef typename Container::iterator iterator; - - iterator end_=static_cast<Container*>(this)->end(); - iterator *prev_,*next_; + Iterator end_=view.end(); + Iterator *prev_,*next_; for( - prev_=static_cast<iterator*>(&this->header); - (next_=static_cast<iterator*>(prev_->next))!=0;){ + prev_=static_cast<Iterator*>(&this->header); + (next_=static_cast<Iterator*>(prev_->next))!=0;){ if(*next_!=end_){ prev_->next=next_->next; next_->cont=0; @@ -558,21 +604,102 @@ public: } } - void swap(safe_container<Container>& x) + void swap(safe_container<Iterator>& x) { super::swap(x); } }; +/* Invalidates all iterators equivalent to that given. Safe containers + * must call this when deleting elements: the safe mode framework cannot + * perform this operation automatically without outside help. + */ + +template<typename Iterator> +inline void detach_equivalent_iterators(Iterator& it) +{ + if(it.valid()){ + { +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(it.cont->mutex); +#endif + + Iterator *prev_,*next_; + for( + prev_=static_cast<Iterator*>(&it.cont->header); + (next_=static_cast<Iterator*>(prev_->next))!=0;){ + if(next_!=&it&&*next_==it){ + prev_->next=next_->next; + next_->cont=0; + } + else prev_=next_; + } + } + it.detach(); + } +} + +/* Transfers iterators equivalent to that given to Dst, if that container has + * the same iterator type; otherwise, detaches them. + */ + +template<typename Dst,typename Iterator> +inline void transfer_equivalent_iterators(Dst& dst,Iterator& i) +{ + safe_mode_detail::transfer_equivalent_iterators( + dst,i,boost::is_same<Iterator,typename Dst::iterator>()); +} + +namespace safe_mode_detail{ + +template<typename Dst,typename Iterator> +inline void transfer_equivalent_iterators( + Dst& dst,Iterator it,boost::true_type /* same iterator type */) +{ + if(it.valid()){ + { + safe_container_base* cont_=dst.end().cont; + +#if defined(BOOST_HAS_THREADS) + detail::scoped_bilock<boost::detail::lightweight_mutex> + scoped_bilock(it.cont->mutex,cont_->mutex); +#endif + + Iterator *prev_,*next_; + for( + prev_=static_cast<Iterator*>(&it.cont->header); + (next_=static_cast<Iterator*>(prev_->next))!=0;){ + if(next_!=&it&&*next_==it){ + prev_->next=next_->next; + next_->cont=cont_; + next_->next=cont_->header.next; + cont_->header.next=next_; + } + else prev_=next_; + } + } + /* nothing to do with it, was passed by value and will die now */ + } +} + +template<typename Dst,typename Iterator> +inline void transfer_equivalent_iterators( + Dst&,Iterator& it,boost::false_type /* same iterator type */) +{ + detach_equivalent_iterators(it); +} + +} /* namespace multi_index::safe_mode::safe_mode_detail */ + } /* namespace multi_index::safe_mode */ } /* namespace multi_index */ #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) namespace serialization{ -template<typename Iterator,typename Container> +template<typename Iterator> struct version< - boost::multi_index::safe_mode::safe_iterator<Iterator,Container> + boost::multi_index::safe_mode::safe_iterator<Iterator> > { BOOST_STATIC_CONSTANT( diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scope_guard.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scope_guard.hpp index 116f8f50415..23c53637460 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scope_guard.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scope_guard.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -13,7 +13,7 @@ #pragma once #endif -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/mpl/if.hpp> namespace boost{ diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scoped_bilock.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scoped_bilock.hpp new file mode 100644 index 00000000000..6937ddf3f9a --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/scoped_bilock.hpp @@ -0,0 +1,70 @@ +/* Copyright 2003-2022 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SCOPED_BILOCK_HPP +#define BOOST_MULTI_INDEX_DETAIL_SCOPED_BILOCK_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/core/noncopyable.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <functional> +#include <new> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Locks/unlocks two RAII-lockable mutexes taking care that locking is done in + * a deadlock-avoiding global order and no double locking happens when the two + * mutexes are the same. + */ + +template<typename Mutex> +class scoped_bilock:private noncopyable +{ +public: + scoped_bilock(Mutex& mutex1,Mutex& mutex2):mutex_eq(&mutex1==&mutex2) + { + bool mutex_lt=std::less<Mutex*>()(&mutex1,&mutex2); + + ::new (static_cast<void*>(&lock1)) scoped_lock(mutex_lt?mutex1:mutex2); + if(!mutex_eq) + ::new (static_cast<void*>(&lock2)) scoped_lock(mutex_lt?mutex2:mutex1); + } + + ~scoped_bilock() + { + reinterpret_cast<scoped_lock*>(&lock1)->~scoped_lock(); + if(!mutex_eq) + reinterpret_cast<scoped_lock*>(&lock2)->~scoped_lock(); + } + +private: + typedef typename Mutex::scoped_lock scoped_lock; + typedef typename aligned_storage< + sizeof(scoped_lock), + alignment_of<scoped_lock>::value + >::type scoped_lock_space; + + bool mutex_eq; + scoped_lock_space lock1,lock2; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_node.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_node.hpp index abbe4e5795f..626d8d6dcd2 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_node.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_node.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2019 Joaquin M Lopez Munoz. * 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) @@ -15,8 +15,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> -#include <memory> -#include <boost/detail/allocator_utilities.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/raw_ptr.hpp> namespace boost{ @@ -30,18 +29,14 @@ namespace detail{ template<typename Allocator> struct sequenced_index_node_impl { - typedef typename - boost::detail::allocator::rebind_to< + typedef typename rebind_alloc_for< Allocator,sequenced_index_node_impl - >::type node_allocator; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename node_allocator::pointer pointer; - typedef typename node_allocator::const_pointer const_pointer; -#else - typedef std::allocator_traits<node_allocator> allocator_traits; - typedef typename allocator_traits::pointer pointer; - typedef typename allocator_traits::const_pointer const_pointer; -#endif + >::type node_allocator; + typedef allocator_traits<node_allocator> alloc_traits; + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::const_pointer const_pointer; + typedef typename alloc_traits::difference_type difference_type; + pointer& prior(){return prior_;} pointer prior()const{return prior_;} pointer& next(){return next_;} @@ -59,7 +54,7 @@ struct sequenced_index_node_impl x->prior()=header->prior(); x->next()=header; x->prior()->next()=x->next()->prior()=x; - }; + } static void unlink(pointer x) { @@ -137,14 +132,14 @@ private: template<typename Super> struct sequenced_index_node_trampoline: sequenced_index_node_impl< - typename boost::detail::allocator::rebind_to< + typename rebind_alloc_for< typename Super::allocator_type, char >::type > { typedef sequenced_index_node_impl< - typename boost::detail::allocator::rebind_to< + typename rebind_alloc_for< typename Super::allocator_type, char >::type @@ -158,9 +153,10 @@ private: typedef sequenced_index_node_trampoline<Super> trampoline; public: - typedef typename trampoline::impl_type impl_type; - typedef typename trampoline::pointer impl_pointer; - typedef typename trampoline::const_pointer const_impl_pointer; + typedef typename trampoline::impl_type impl_type; + typedef typename trampoline::pointer impl_pointer; + typedef typename trampoline::const_pointer const_impl_pointer; + typedef typename trampoline::difference_type difference_type; impl_pointer& prior(){return trampoline::prior();} impl_pointer prior()const{return trampoline::prior();} diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_ops.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_ops.hpp index 142bdd9dd9a..b12cc321a52 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_ops.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/seq_index_ops.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2016 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -14,7 +14,7 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/multi_index/detail/seq_index_node.hpp> #include <boost/limits.hpp> #include <boost/type_traits/aligned_storage.hpp> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/undef_if_constexpr_macro.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/undef_if_constexpr_macro.hpp new file mode 100644 index 00000000000..956a20de247 --- /dev/null +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/detail/undef_if_constexpr_macro.hpp @@ -0,0 +1,11 @@ +/* Copyright 2003-2020 Joaquin M Lopez Munoz. + * 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/multi_index for library home page. + */ + +#define BOOST_MULTI_INDEX_DETAIL_UNDEF_IF_CONSTEXPR_MACRO +#include <boost/multi_index/detail/define_if_constexpr_macro.hpp> +#undef BOOST_MULTI_INDEX_DETAIL_UNDEF_IF_CONSTEXPR_MACRO diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/hashed_index.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/hashed_index.hpp index 7b142223742..71543d0c794 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/hashed_index.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/hashed_index.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2021 Joaquin M Lopez Munoz. * 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) @@ -17,22 +17,26 @@ #include <algorithm> #include <boost/call_traits.hpp> #include <boost/core/addressof.hpp> -#include <boost/detail/allocator_utilities.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/detail/workaround.hpp> #include <boost/foreach_fwd.hpp> #include <boost/limits.hpp> #include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/push_front.hpp> #include <boost/multi_index/detail/access_specifier.hpp> +#include <boost/multi_index/detail/adl_swap.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/auto_space.hpp> #include <boost/multi_index/detail/bucket_array.hpp> #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> #include <boost/multi_index/detail/hash_index_iterator.hpp> #include <boost/multi_index/detail/index_node_base.hpp> +#include <boost/multi_index/detail/invalidate_iterators.hpp> #include <boost/multi_index/detail/modify_key_adaptor.hpp> +#include <boost/multi_index/detail/node_handle.hpp> #include <boost/multi_index/detail/promotes_arg.hpp> #include <boost/multi_index/detail/safe_mode.hpp> #include <boost/multi_index/detail/scope_guard.hpp> @@ -45,7 +49,6 @@ #include <functional> #include <iterator> #include <utility> -#include <memory> #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> @@ -80,18 +83,17 @@ namespace detail{ * Category tags defined in hash_index_node.hpp. */ +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4355) /* this used in base member initializer list */ +#endif + template< typename KeyFromValue,typename Hash,typename Pred, typename SuperMeta,typename TagList,typename Category > class hashed_index: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - ,public safe_mode::safe_container< - hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> > -#endif - { #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) @@ -103,66 +105,73 @@ class hashed_index: #pragma parse_mfunc_templ off #endif - typedef typename SuperMeta::type super; +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + /* cross-index access */ + + template <typename,typename,typename> friend class index_base; +#endif + + typedef typename SuperMeta::type super; protected: typedef hashed_index_node< - typename super::node_type,Category> node_type; + typename super::index_node_type> index_node_type; private: - typedef typename node_type::node_alg node_alg; - typedef typename node_type::impl_type node_impl_type; - typedef typename node_impl_type::pointer node_impl_pointer; - typedef typename node_impl_type::base_pointer node_impl_base_pointer; + typedef typename index_node_type:: + template node_alg<Category>::type node_alg; + typedef typename index_node_type::impl_type node_impl_type; + typedef typename node_impl_type::pointer node_impl_pointer; + typedef typename node_impl_type::base_pointer node_impl_base_pointer; typedef bucket_array< - typename super::final_allocator_type> bucket_array_type; + typename super::final_allocator_type> bucket_array_type; public: /* types */ - typedef typename KeyFromValue::result_type key_type; - typedef typename node_type::value_type value_type; - typedef KeyFromValue key_from_value; - typedef Hash hasher; - typedef Pred key_equal; - typedef tuple<std::size_t, - key_from_value,hasher,key_equal> ctor_args; - typedef typename super::final_allocator_type allocator_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::pointer pointer; - typedef typename allocator_type::const_pointer const_pointer; - typedef typename allocator_type::reference reference; - typedef typename allocator_type::const_reference const_reference; -#else - typedef std::allocator_traits<allocator_type> allocator_traits; - typedef typename allocator_traits::pointer pointer; - typedef typename allocator_traits::const_pointer const_pointer; - typedef value_type& reference; - typedef const value_type& const_reference; -#endif - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; + typedef typename KeyFromValue::result_type key_type; + typedef typename index_node_type::value_type value_type; + typedef KeyFromValue key_from_value; + typedef Hash hasher; + typedef Pred key_equal; + typedef typename super::final_allocator_type allocator_type; + +private: + typedef allocator_traits<allocator_type> alloc_traits; + +public: + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::const_pointer const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename alloc_traits::size_type size_type; + typedef typename alloc_traits::difference_type difference_type; + typedef tuple<size_type, + key_from_value,hasher,key_equal> ctor_args; #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) typedef safe_mode::safe_iterator< hashed_index_iterator< - node_type,bucket_array_type, - hashed_index_global_iterator_tag>, - hashed_index> iterator; + index_node_type,bucket_array_type, + Category, + hashed_index_global_iterator_tag> > iterator; #else typedef hashed_index_iterator< - node_type,bucket_array_type, - hashed_index_global_iterator_tag> iterator; + index_node_type,bucket_array_type, + Category,hashed_index_global_iterator_tag> iterator; #endif - typedef iterator const_iterator; + typedef iterator const_iterator; typedef hashed_index_iterator< - node_type,bucket_array_type, - hashed_index_local_iterator_tag> local_iterator; - typedef local_iterator const_local_iterator; + index_node_type,bucket_array_type, + Category,hashed_index_local_iterator_tag> local_iterator; + typedef local_iterator const_local_iterator; - typedef TagList tag_list; + typedef typename super::final_node_handle_type node_type; + typedef detail::insert_return_type< + iterator,node_type> insert_return_type; + typedef TagList tag_list; protected: typedef typename super::final_node_type final_node_type; @@ -187,19 +196,16 @@ protected: private: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef safe_mode::safe_container< - hashed_index> safe_super; + typedef safe_mode::safe_container<iterator> safe_container; #endif typedef typename call_traits<value_type>::param_type value_param_type; typedef typename call_traits< key_type>::param_type key_param_type; - /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL - * expansion. - */ + /* needed to avoid commas in some macros */ - typedef std::pair<iterator,bool> emplace_return_type; + typedef std::pair<iterator,bool> pair_return_type; public: @@ -238,9 +244,17 @@ public: /* iterators */ iterator begin()BOOST_NOEXCEPT - {return make_iterator(node_type::from_impl(header()->next()->prior()));} + { + return make_iterator( + index_node_type::from_impl(header()->next()->prior())); + + } const_iterator begin()const BOOST_NOEXCEPT - {return make_iterator(node_type::from_impl(header()->next()->prior()));} + { + return make_iterator( + index_node_type::from_impl(header()->next()->prior())); + } + iterator end()BOOST_NOEXCEPT{return make_iterator(header());} const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());} const_iterator cbegin()const BOOST_NOEXCEPT{return begin();} @@ -248,18 +262,20 @@ public: iterator iterator_to(const value_type& x) { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } const_iterator iterator_to(const value_type& x)const { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } /* modifiers */ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( - emplace_return_type,emplace,emplace_impl) + pair_return_type,emplace,emplace_impl) BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( iterator,emplace_hint,emplace_hint_impl,iterator,position) @@ -312,6 +328,42 @@ public: } #endif + insert_return_type insert(BOOST_RV_REF(node_type) nh) + { + if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh); + return insert_return_type(make_iterator(p.first),p.second,boost::move(nh)); + } + + iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_nh_( + nh,static_cast<final_node_type*>(position.get_node())); + return make_iterator(p.first); + } + + node_type extract(const_iterator position) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + return this->final_extract_( + static_cast<final_node_type*>(position.get_node())); + } + + node_type extract(key_param_type x) + { + iterator position=find(x); + if(position==end())return node_type(); + else return extract(position); + } + iterator erase(iterator position) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); @@ -329,13 +381,13 @@ public: std::size_t buc=buckets.position(hash_(k)); for(node_impl_pointer x=buckets.at(buc)->prior(); x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq_(k,key(node_type::from_impl(x)->value()))){ + if(eq_(k,key(index_node_type::from_impl(x)->value()))){ node_impl_pointer y=end_of_range(x); size_type s=0; do{ node_impl_pointer z=node_alg::after(x); this->final_erase_( - static_cast<final_node_type*>(node_type::from_impl(x))); + static_cast<final_node_type*>(index_node_type::from_impl(x))); x=z; ++s; }while(x!=y); @@ -458,6 +510,73 @@ public: this->final_swap_(x.final()); } + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void) + merge(Index& x) + { + merge(x,x.begin(),x.end()); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void) + merge(BOOST_RV_REF(Index) x){merge(static_cast<Index&>(x));} + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type) + merge(Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + if(x.end().get_node()==this->header()){ /* same container */ + return std::pair<iterator,bool>( + make_iterator(static_cast<final_node_type*>(i.get_node())),true); + } + else{ + std::pair<final_node_type*,bool> p=this->final_transfer_( + x,static_cast<final_node_type*>(i.get_node())); + return std::pair<iterator,bool>(make_iterator(p.first),p.second); + } + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type) + merge(BOOST_RV_REF(Index) x,BOOST_DEDUCED_TYPENAME Index::iterator i) + { + return merge(static_cast<Index&>(x),i); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void) + merge( + Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + if(x.end().get_node()!=this->header()){ /* different containers */ + this->final_transfer_range_(x,first,last); + } + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void) + merge( + BOOST_RV_REF(Index) x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + { + merge(static_cast<Index&>(x),first,last); + } + /* observers */ key_from_value key_extractor()const{return key;} @@ -510,6 +629,22 @@ public: } template<typename CompatibleKey> + bool contains(const CompatibleKey& k)const + { + return contains(k,hash_,eq_); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + bool contains( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq)const + { + return find(k,hash,eq)!=end(); + } + + template<typename CompatibleKey> std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const { return equal_range(k,hash_,eq_); @@ -528,7 +663,11 @@ public: /* bucket interface */ - size_type bucket_count()const BOOST_NOEXCEPT{return buckets.size();} + size_type bucket_count()const BOOST_NOEXCEPT + { + return static_cast<size_type>(buckets.size()); + } + size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);} size_type bucket_size(size_type n)const @@ -543,7 +682,7 @@ public: size_type bucket(key_param_type k)const { - return buckets.position(hash_(k)); + return static_cast<size_type>(buckets.position(hash_(k))); } local_iterator begin(size_type n) @@ -555,7 +694,7 @@ public: { node_impl_pointer x=buckets.at(n)->prior(); if(x==node_impl_pointer(0))return end(n); - return make_local_iterator(node_type::from_impl(x)); + return make_local_iterator(index_node_type::from_impl(x)); } local_iterator end(size_type n) @@ -574,13 +713,13 @@ public: local_iterator local_iterator_to(const value_type& x) { return make_local_iterator( - node_from_value<node_type>(boost::addressof(x))); + node_from_value<index_node_type>(boost::addressof(x))); } const_local_iterator local_iterator_to(const value_type& x)const { return make_local_iterator( - node_from_value<node_type>(boost::addressof(x))); + node_from_value<index_node_type>(boost::addressof(x))); } /* hash policy */ @@ -617,6 +756,11 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: eq_(tuples::get<3>(args_list.get_head())), buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())), mlf(1.0f) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe(*this) +#endif + { calculate_max_load(); } @@ -624,17 +768,17 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: hashed_index( const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x): super(x), - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super(), -#endif - key(x.key), hash_(x.hash_), eq_(x.eq_), buckets(x.get_allocator(),header()->impl(),x.buckets.size()), mlf(x.mlf), max_load(x.max_load) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe(*this) +#endif + { /* Copy ctor just takes the internal configuration objects from x. The rest * is done in subsequent call to copy_(). @@ -645,16 +789,16 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, do_not_copy_elements_tag): super(x,do_not_copy_elements_tag()), - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super(), -#endif - key(x.key), hash_(x.hash_), eq_(x.eq_), buckets(x.get_allocator(),header()->impl(),0), mlf(1.0f) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe(*this) +#endif + { calculate_max_load(); } @@ -665,33 +809,33 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - iterator make_iterator(node_type* node) + iterator make_iterator(index_node_type* node) { - return iterator(node,this); + return iterator(node,&safe); } - const_iterator make_iterator(node_type* node)const + const_iterator make_iterator(index_node_type* node)const { - return const_iterator(node,const_cast<hashed_index*>(this)); + return const_iterator(node,const_cast<safe_container*>(&safe)); } #else - iterator make_iterator(node_type* node) + iterator make_iterator(index_node_type* node) { return iterator(node); } - const_iterator make_iterator(node_type* node)const + const_iterator make_iterator(index_node_type* node)const { return const_iterator(node); } #endif - local_iterator make_local_iterator(node_type* node) + local_iterator make_local_iterator(index_node_type* node) { return local_iterator(node); } - const_local_iterator make_local_iterator(node_type* node)const + const_local_iterator make_local_iterator(index_node_type* node)const { return const_local_iterator(node); } @@ -714,8 +858,8 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: do{ node_impl_pointer prev_org=org->prior(), prev_cpy= - static_cast<node_type*>(map.find(static_cast<final_node_type*>( - node_type::from_impl(prev_org))))->impl(); + static_cast<index_node_type*>(map.find(static_cast<final_node_type*>( + index_node_type::from_impl(prev_org))))->impl(); cpy->prior()=prev_cpy; if(node_alg::is_first_of_bucket(org)){ node_impl_base_pointer buc_org=prev_org->next(), @@ -746,8 +890,8 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: do{ node_impl_pointer next_org=node_alg::after(org), next_cpy= - static_cast<node_type*>(map.find(static_cast<final_node_type*>( - node_type::from_impl(next_org))))->impl(); + static_cast<index_node_type*>(map.find(static_cast<final_node_type*>( + index_node_type::from_impl(next_org))))->impl(); if(node_alg::is_first_of_bucket(next_org)){ node_impl_base_pointer buc_org=org->next(), buc_cpy= @@ -763,15 +907,17 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: else{ cpy->next()= node_impl_type::base_pointer_from( - static_cast<node_type*>(map.find(static_cast<final_node_type*>( - node_type::from_impl( - node_impl_type::pointer_from(org->next())))))->impl()); + static_cast<index_node_type*>( + map.find(static_cast<final_node_type*>( + index_node_type::from_impl( + node_impl_type::pointer_from(org->next())))))->impl()); } if(next_org->prior()!=org){ next_cpy->prior()= - static_cast<node_type*>(map.find(static_cast<final_node_type*>( - node_type::from_impl(next_org->prior()))))->impl(); + static_cast<index_node_type*>( + map.find(static_cast<final_node_type*>( + index_node_type::from_impl(next_org->prior()))))->impl(); } else{ next_cpy->prior()=cpy; @@ -795,17 +941,18 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: link_info pos(buckets.at(buc)); if(!link_point(v,pos)){ return static_cast<final_node_type*>( - node_type::from_impl(node_impl_type::pointer_from(pos))); + index_node_type::from_impl(node_impl_type::pointer_from(pos))); } final_node_type* res=super::insert_(v,x,variant); - if(res==x)link(static_cast<node_type*>(x),pos); + if(res==x)link(static_cast<index_node_type*>(x),pos); return res; } template<typename Variant> final_node_type* insert_( - value_param_type v,node_type* position,final_node_type*& x,Variant variant) + value_param_type v,index_node_type* position, + final_node_type*& x,Variant variant) { reserve_for_insert(size()+1); @@ -813,21 +960,22 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: link_info pos(buckets.at(buc)); if(!link_point(v,pos)){ return static_cast<final_node_type*>( - node_type::from_impl(node_impl_type::pointer_from(pos))); + index_node_type::from_impl(node_impl_type::pointer_from(pos))); } final_node_type* res=super::insert_(v,position,x,variant); - if(res==x)link(static_cast<node_type*>(x),pos); + if(res==x)link(static_cast<index_node_type*>(x),pos); return res; } - void erase_(node_type* x) + template<typename Dst> + void extract_(index_node_type* x,Dst dst) { unlink(x); - super::erase_(x); + super::extract_(x,dst.next()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - detach_iterators(x); + transfer_iterators(dst.get(),x); #endif } @@ -841,7 +989,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){ node_impl_pointer y=x->prior(); this->final_delete_node_( - static_cast<final_node_type*>(node_type::from_impl(x))); + static_cast<final_node_type*>(index_node_type::from_impl(x))); x=y; } } @@ -860,7 +1008,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: first->next()->prior()=first; } this->final_delete_node_( - static_cast<final_node_type*>(node_type::from_impl(x))); + static_cast<final_node_type*>(index_node_type::from_impl(x))); x=y; } } @@ -871,25 +1019,27 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: buckets.clear(header()->impl()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::detach_dereferenceable_iterators(); + safe.detach_dereferenceable_iterators(); #endif } + template<typename BoolConstant> void swap_( - hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x) + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + BoolConstant swap_allocators) { - std::swap(key,x.key); - std::swap(hash_,x.hash_); - std::swap(eq_,x.eq_); - buckets.swap(x.buckets); + adl_swap(key,x.key); + adl_swap(hash_,x.hash_); + adl_swap(eq_,x.eq_); + buckets.swap(x.buckets,swap_allocators); std::swap(mlf,x.mlf); std::swap(max_load,x.max_load); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif - super::swap_(x); + super::swap_(x,swap_allocators); } void swap_elements_( @@ -900,14 +1050,14 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: std::swap(max_load,x.max_load); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif super::swap_elements_(x); } template<typename Variant> - bool replace_(value_param_type v,node_type* x,Variant variant) + bool replace_(value_param_type v,index_node_type* x,Variant variant) { if(eq_(key(v),key(x->value()))){ return super::replace_(v,x,variant); @@ -933,7 +1083,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool modify_(node_type* x) + bool modify_(index_node_type* x) { std::size_t buc; bool b; @@ -942,7 +1092,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: b=in_place(x->impl(),key(x->value()),buc); } BOOST_CATCH(...){ - erase_(x); + extract_(x,invalidate_iterators()); BOOST_RETHROW; } BOOST_CATCH_END @@ -951,7 +1101,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_TRY{ link_info pos(buckets.at(buc)); if(!link_point(x->value(),pos)){ - super::erase_(x); + super::extract_(x,invalidate_iterators()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); @@ -961,7 +1111,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: link(x,pos); } BOOST_CATCH(...){ - super::erase_(x); + super::extract_(x,invalidate_iterators()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); @@ -995,7 +1145,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool modify_rollback_(node_type* x) + bool modify_rollback_(index_node_type* x) { std::size_t buc=find_bucket(x->value()); if(in_place(x->impl(),key(x->value()),buc)){ @@ -1021,7 +1171,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool check_rollback_(node_type* x)const + bool check_rollback_(index_node_type* x)const { std::size_t buc=find_bucket(x->value()); return in_place(x->impl(),key(x->value()),buc)&&super::check_rollback_(x); @@ -1059,7 +1209,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: if(it2==it2_last)return false; const_iterator it_last=make_iterator( - node_type::from_impl(end_of_range(it.get_node()->impl()))); + index_node_type::from_impl(end_of_range(it.get_node()->impl()))); if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false; /* From is_permutation code in @@ -1072,7 +1222,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: if(it!=it_last){ for(const_iterator scan=it;scan!=it_last;++scan){ if(std::find(it,scan,*scan)!=scan)continue; - std::ptrdiff_t matches=std::count(it2,it2_last,*scan); + difference_type matches=std::count(it2,it2_last,*scan); if(matches==0||matches!=std::count(scan,it_last,*scan))return false; } it=it_last; @@ -1137,7 +1287,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #endif private: - node_type* header()const{return this->final_header();} + index_node_type* header()const{return this->final_header();} std::size_t find_bucket(value_param_type v)const { @@ -1170,7 +1320,7 @@ private: { for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0); x=node_alg::after_local(x)){ - if(eq_(key(v),key(node_type::from_impl(x)->value()))){ + if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){ pos=node_impl_type::base_pointer_from(x); return false; } @@ -1183,7 +1333,7 @@ private: { for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0); x=node_alg::next_to_inspect(x)){ - if(eq_(key(v),key(node_type::from_impl(x)->value()))){ + if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){ pos.first=node_impl_type::base_pointer_from(x); pos.last=node_impl_type::base_pointer_from(last_of_range(x)); return true; @@ -1211,8 +1361,8 @@ private: node_impl_pointer yy=node_impl_type::pointer_from(y); return eq_( - key(node_type::from_impl(x)->value()), - key(node_type::from_impl(yy)->value()))?yy:x; + key(index_node_type::from_impl(x)->value()), + key(index_node_type::from_impl(yy)->value()))?yy:x; } else if(z->prior()==x) /* last of bucket */ return x; @@ -1238,8 +1388,8 @@ private: if(z==x){ /* range of size 1 or 2 */ node_impl_pointer yy=node_impl_type::pointer_from(y); if(!eq_( - key(node_type::from_impl(x)->value()), - key(node_type::from_impl(yy)->value())))yy=x; + key(index_node_type::from_impl(x)->value()), + key(index_node_type::from_impl(yy)->value())))yy=x; return yy->next()->prior()==yy? node_impl_type::pointer_from(yy->next()): yy->next()->prior(); @@ -1252,17 +1402,18 @@ private: z->next()->prior(); } - void link(node_type* x,const link_info& pos) + void link(index_node_type* x,const link_info& pos) { link(x,pos,Category()); } - void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag) + void link(index_node_type* x,node_impl_base_pointer pos,hashed_unique_tag) { node_alg::link(x->impl(),pos,header()->impl()); } - void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag) + void link( + index_node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag) { if(pos.last==node_impl_base_pointer(0)){ node_alg::link(x->impl(),pos.first,header()->impl()); @@ -1275,14 +1426,14 @@ private: } } - void unlink(node_type* x) + void unlink(index_node_type* x) { node_alg::unlink(x->impl()); } typedef typename node_alg::unlink_undo unlink_undo; - void unlink(node_type* x,unlink_undo& undo) + void unlink(index_node_type* x,unlink_undo& undo) { node_alg::unlink(x->impl(),undo); } @@ -1325,7 +1476,7 @@ private: node_impl_pointer x=end_->prior(); /* only this can possibly throw */ - std::size_t h=hash_(key(node_type::from_impl(x)->value())); + std::size_t h=hash_(key(index_node_type::from_impl(x)->value())); hashes.data()[i]=h; node_ptrs.data()[i]=x; @@ -1378,7 +1529,7 @@ private: if(x==end_)break; /* only this can possibly throw */ - std::size_t h=hash_(key(node_type::from_impl(x)->value())); + std::size_t h=hash_(key(index_node_type::from_impl(x)->value())); hashes.data()[i]=h; node_ptrs.data()[i]=x; @@ -1432,7 +1583,7 @@ private: for(node_impl_pointer y=buckets.at(buc)->prior(); y!=node_impl_pointer(0);y=node_alg::after_local(y)){ if(y==x)found=true; - else if(eq_(k,key(node_type::from_impl(y)->value())))return false; + else if(eq_(k,key(index_node_type::from_impl(y)->value())))return false; } return found; } @@ -1449,13 +1600,13 @@ private: /* in place <-> equal to some other member of the group */ return eq_( k, - key(node_type::from_impl( + key(index_node_type::from_impl( node_impl_type::pointer_from(y->next()))->value())); } else{ node_impl_pointer z= node_alg::after_local(y->next()->prior()); /* end of range */ - if(eq_(k,key(node_type::from_impl(y)->value()))){ + if(eq_(k,key(index_node_type::from_impl(y)->value()))){ if(found)return false; /* x lies outside */ do{ if(y==x)return true; @@ -1477,7 +1628,7 @@ private: range_size=1; found=true; } - else if(eq_(k,key(node_type::from_impl(y)->value()))){ + else if(eq_(k,key(index_node_type::from_impl(y)->value()))){ if(range_size==0&&found)return false; if(range_size==1&&!found)return false; if(range_size==2)return false; @@ -1495,11 +1646,18 @@ private: } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - void detach_iterators(node_type* x) + void detach_iterators(index_node_type* x) { iterator it=make_iterator(x); safe_mode::detach_equivalent_iterators(it); } + + template<typename Dst> + void transfer_iterators(Dst& dst,index_node_type* x) + { + iterator it=make_iterator(x); + safe_mode::transfer_equivalent_iterators(dst,it); + } #endif template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> @@ -1545,8 +1703,8 @@ private: std::size_t buc=buckets.position(hash(k)); for(node_impl_pointer x=buckets.at(buc)->prior(); x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ - return make_iterator(node_type::from_impl(x)); + if(eq(k,key(index_node_type::from_impl(x)->value()))){ + return make_iterator(index_node_type::from_impl(x)); } } return end(); @@ -1572,7 +1730,7 @@ private: std::size_t buc=buckets.position(hash(k)); for(node_impl_pointer x=buckets.at(buc)->prior(); x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ + if(eq(k,key(index_node_type::from_impl(x)->value()))){ size_type res=0; node_impl_pointer y=end_of_range(x); do{ @@ -1605,10 +1763,10 @@ private: std::size_t buc=buckets.position(hash(k)); for(node_impl_pointer x=buckets.at(buc)->prior(); x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ + if(eq(k,key(index_node_type::from_impl(x)->value()))){ return std::pair<iterator,iterator>( - make_iterator(node_type::from_impl(x)), - make_iterator(node_type::from_impl(end_of_range(x)))); + make_iterator(index_node_type::from_impl(x)), + make_iterator(index_node_type::from_impl(end_of_range(x)))); } } return std::pair<iterator,iterator>(end(),end()); @@ -1620,13 +1778,21 @@ private: bucket_array_type buckets; float mlf; size_type max_load; - + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_container safe; +#endif + #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) #pragma parse_mfunc_templ reset #endif }; +#if defined(BOOST_MSVC) +#pragma warning(pop) /* C4355 */ +#endif + /* comparison */ template< @@ -1681,7 +1847,7 @@ struct hashed_unique template<typename Super> struct node_class { - typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type; + typedef detail::hashed_index_node<Super> type; }; template<typename SuperMeta> @@ -1706,8 +1872,7 @@ struct hashed_non_unique template<typename Super> struct node_class { - typedef detail::hashed_index_node< - Super,detail::hashed_non_unique_tag> type; + typedef detail::hashed_index_node<Super> type; }; template<typename SuperMeta> diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/mem_fun.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/mem_fun.hpp index 111c386c5f5..aa116f0379e 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/mem_fun.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/mem_fun.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2015 Joaquin M Lopez Munoz. +/* Copyright 2003-2019 Joaquin M Lopez Munoz. * 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) @@ -30,17 +30,30 @@ namespace multi_index{ /* mem_fun implements a read-only key extractor based on a given non-const * member function of a class. - * const_mem_fun does the same for const member functions. - * Additionally, mem_fun and const_mem_fun are overloaded to support - * referece_wrappers of T and "chained pointers" to T's. By chained pointer - * to T we mean a type P such that, given a p of Type P + * Also, the following variations are provided: + * const_mem_fun: const member functions + * volatile_mem_fun: volatile member functions + * cv_mem_fun: const volatile member functions + * ref_mem_fun: ref-qualifed member functions (C++11) + * cref_mem_fun: const ref-qualifed member functions (C++11) + * vref_mem_fun: volatile ref-qualifed member functions (C++11) + * cvref_mem_fun: const volatile ref-qualifed member functions (C++11) + * + * All of these classes are overloaded to support boost::referece_wrappers + * of T and "chained pointers" to T's. By chained pointer to T we mean a type + * P such that, given a p of Type P * *...n...*x is convertible to T&, for some n>=1. * Examples of chained pointers are raw and smart pointers, iterators and * arbitrary combinations of these (vg. T** or unique_ptr<T*>.) */ -template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()const> -struct const_mem_fun +namespace detail{ + +template< + class Class,typename Type, + typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction +> +struct const_mem_fun_impl { typedef typename remove_reference<Type>::type result_type; @@ -74,8 +87,11 @@ struct const_mem_fun } }; -template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()> -struct mem_fun +template< + class Class,typename Type, + typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction +> +struct mem_fun_impl { typedef typename remove_reference<Type>::type result_type; @@ -104,6 +120,62 @@ struct mem_fun } }; +} /* namespace multi_index::detail */ + +template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()const> +struct const_mem_fun:detail::const_mem_fun_impl< + Class,Type,Type (Class::*)()const,PtrToMemberFunction +>{}; + +template< + class Class,typename Type, + Type (Class::*PtrToMemberFunction)()const volatile +> +struct cv_mem_fun:detail::const_mem_fun_impl< + Class,Type,Type (Class::*)()const volatile,PtrToMemberFunction +>{}; + +template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()> +struct mem_fun: + detail::mem_fun_impl<Class,Type,Type (Class::*)(),PtrToMemberFunction>{}; + +template< + class Class,typename Type,Type (Class::*PtrToMemberFunction)()volatile +> +struct volatile_mem_fun:detail::mem_fun_impl< + Class,Type,Type (Class::*)()volatile,PtrToMemberFunction +>{}; + +#if !defined(BOOST_NO_CXX11_REF_QUALIFIERS) + +template< + class Class,typename Type,Type (Class::*PtrToMemberFunction)()const& +> +struct cref_mem_fun:detail::const_mem_fun_impl< + Class,Type,Type (Class::*)()const&,PtrToMemberFunction +>{}; + +template< + class Class,typename Type, + Type (Class::*PtrToMemberFunction)()const volatile& +> +struct cvref_mem_fun:detail::const_mem_fun_impl< + Class,Type,Type (Class::*)()const volatile&,PtrToMemberFunction +>{}; + +template<class Class,typename Type,Type (Class::*PtrToMemberFunction)()&> +struct ref_mem_fun: + detail::mem_fun_impl<Class,Type,Type (Class::*)()&,PtrToMemberFunction>{}; + +template< + class Class,typename Type,Type (Class::*PtrToMemberFunction)()volatile& +> +struct vref_mem_fun:detail::mem_fun_impl< + Class,Type,Type (Class::*)()volatile&,PtrToMemberFunction +>{}; + +#endif + /* MSVC++ 6.0 has problems with const member functions as non-type template * parameters, somehow it takes them as non-const. const_mem_fun_explicit * workarounds this deficiency by accepting an extra type parameter that @@ -119,7 +191,8 @@ struct mem_fun template< class Class,typename Type, - typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction> + typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction +> struct const_mem_fun_explicit { typedef typename remove_reference<Type>::type result_type; @@ -156,7 +229,8 @@ struct const_mem_fun_explicit template< class Class,typename Type, - typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction> + typename PtrToMemberFunctionType,PtrToMemberFunctionType PtrToMemberFunction +> struct mem_fun_explicit { typedef typename remove_reference<Type>::type result_type; diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/safe_mode_errors.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/safe_mode_errors.hpp index 1904706edec..65aba892ddd 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/safe_mode_errors.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/safe_mode_errors.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2020 Joaquin M Lopez Munoz. * 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) @@ -36,7 +36,8 @@ enum error_code invalid_range, inside_range, out_of_bounds, - same_container + same_container, + unequal_allocators }; } /* namespace multi_index::safe_mode */ diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index/sequenced_index.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index/sequenced_index.hpp index ad538e0c4b5..f12213e6720 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index/sequenced_index.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index/sequenced_index.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2018 Joaquin M Lopez Munoz. +/* Copyright 2003-2021 Joaquin M Lopez Munoz. * 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) @@ -14,23 +14,24 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ -#include <boost/bind.hpp> +#include <boost/bind/bind.hpp> #include <boost/call_traits.hpp> #include <boost/core/addressof.hpp> -#include <boost/detail/allocator_utilities.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/detail/workaround.hpp> #include <boost/foreach_fwd.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/move/core.hpp> -#include <boost/move/utility.hpp> +#include <boost/move/utility_core.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/not.hpp> #include <boost/mpl/push_front.hpp> #include <boost/multi_index/detail/access_specifier.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/bidir_node_iterator.hpp> #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> #include <boost/multi_index/detail/index_node_base.hpp> +#include <boost/multi_index/detail/node_handle.hpp> #include <boost/multi_index/detail/safe_mode.hpp> #include <boost/multi_index/detail/scope_guard.hpp> #include <boost/multi_index/detail/seq_index_node.hpp> @@ -38,20 +39,15 @@ #include <boost/multi_index/detail/vartempl_support.hpp> #include <boost/multi_index/sequenced_index_fwd.hpp> #include <boost/tuple/tuple.hpp> +#include <boost/type_traits/is_copy_constructible.hpp> #include <boost/type_traits/is_integral.hpp> -#include <cstddef> #include <functional> #include <utility> -#include <memory> #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include<initializer_list> #endif -#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) -#include <boost/bind.hpp> -#endif - #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x) \ detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ @@ -72,15 +68,14 @@ namespace detail{ /* sequenced_index adds a layer of sequenced indexing to a given Super */ +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4355) /* this used in base member initializer list */ +#endif + template<typename SuperMeta,typename TagList> class sequenced_index: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - ,public safe_mode::safe_container< - sequenced_index<SuperMeta,TagList> > -#endif - { #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) @@ -92,54 +87,55 @@ class sequenced_index: #pragma parse_mfunc_templ off #endif - typedef typename SuperMeta::type super; +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + /* cross-index access */ + + template <typename,typename,typename> friend class index_base; +#endif + + typedef typename SuperMeta::type super; protected: typedef sequenced_index_node< - typename super::node_type> node_type; + typename super::index_node_type> index_node_type; private: - typedef typename node_type::impl_type node_impl_type; + typedef typename index_node_type::impl_type node_impl_type; public: /* types */ - typedef typename node_type::value_type value_type; - typedef tuples::null_type ctor_args; - typedef typename super::final_allocator_type allocator_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::reference reference; - typedef typename allocator_type::const_reference const_reference; -#else - typedef value_type& reference; - typedef const value_type& const_reference; -#endif + typedef typename index_node_type::value_type value_type; + typedef tuples::null_type ctor_args; + typedef typename super::final_allocator_type allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) typedef safe_mode::safe_iterator< - bidir_node_iterator<node_type>, - sequenced_index> iterator; + bidir_node_iterator<index_node_type> > iterator; #else - typedef bidir_node_iterator<node_type> iterator; + typedef bidir_node_iterator<index_node_type> iterator; #endif - typedef iterator const_iterator; + typedef iterator const_iterator; - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename allocator_type::pointer pointer; - typedef typename allocator_type::const_pointer const_pointer; -#else - typedef std::allocator_traits<allocator_type> allocator_traits; - typedef typename allocator_traits::pointer pointer; - typedef typename allocator_traits::const_pointer const_pointer; -#endif +private: + typedef allocator_traits<allocator_type> alloc_traits; + +public: + typedef typename alloc_traits::pointer pointer; + typedef typename alloc_traits::const_pointer const_pointer; + typedef typename alloc_traits::size_type size_type; + typedef typename alloc_traits::difference_type difference_type; typedef typename - boost::reverse_iterator<iterator> reverse_iterator; + boost::reverse_iterator<iterator> reverse_iterator; typedef typename - boost::reverse_iterator<const_iterator> const_reverse_iterator; - typedef TagList tag_list; + boost::reverse_iterator<const_iterator> const_reverse_iterator; + typedef typename super::final_node_handle_type node_type; + typedef detail::insert_return_type< + iterator,node_type> insert_return_type; + typedef TagList tag_list; protected: typedef typename super::final_node_type final_node_type; @@ -164,17 +160,14 @@ protected: private: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef safe_mode::safe_container< - sequenced_index> safe_super; + typedef safe_mode::safe_container<iterator> safe_container; #endif typedef typename call_traits<value_type>::param_type value_param_type; - /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL - * expansion. - */ + /* needed to avoid commas in some macros */ - typedef std::pair<iterator,bool> emplace_return_type; + typedef std::pair<iterator,bool> pair_return_type; public: @@ -227,9 +220,9 @@ public: /* iterators */ iterator begin()BOOST_NOEXCEPT - {return make_iterator(node_type::from_impl(header()->next()));} + {return make_iterator(index_node_type::from_impl(header()->next()));} const_iterator begin()const BOOST_NOEXCEPT - {return make_iterator(node_type::from_impl(header()->next()));} + {return make_iterator(index_node_type::from_impl(header()->next()));} iterator end()BOOST_NOEXCEPT{return make_iterator(header());} const_iterator @@ -253,12 +246,14 @@ public: iterator iterator_to(const value_type& x) { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } const_iterator iterator_to(const value_type& x)const { - return make_iterator(node_from_value<node_type>(boost::addressof(x))); + return make_iterator( + node_from_value<index_node_type>(boost::addressof(x))); } /* capacity */ @@ -280,7 +275,7 @@ public: void resize(size_type n,value_param_type x) { BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - if(n>size())insert(end(),n-size(),x); + if(n>size())insert(end(),static_cast<size_type>(n-size()),x); else if(n<size())for(size_type m=size()-n;m--;)pop_back(); } @@ -294,7 +289,7 @@ public: /* modifiers */ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( - emplace_return_type,emplace_front,emplace_front_impl) + pair_return_type,emplace_front,emplace_front_impl) std::pair<iterator,bool> push_front(const value_type& x) {return insert(begin(),x);} @@ -303,7 +298,7 @@ public: void pop_front(){erase(begin());} BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( - emplace_return_type,emplace_back,emplace_back_impl) + pair_return_type,emplace_back,emplace_back_impl) std::pair<iterator,bool> push_back(const value_type& x) {return insert(end(),x);} @@ -312,7 +307,7 @@ public: void pop_back(){erase(--end());} BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( - emplace_return_type,emplace,emplace_impl,iterator,position) + pair_return_type,emplace,emplace_impl,iterator,position) std::pair<iterator,bool> insert(iterator position,const value_type& x) { @@ -359,6 +354,29 @@ public: } #endif + insert_return_type insert(const_iterator position,BOOST_RV_REF(node_type) nh) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return insert_return_type(make_iterator(p.first),p.second,boost::move(nh)); + } + + node_type extract(const_iterator position) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + return this->final_extract_( + static_cast<final_node_type*>(position.get_node())); + } + iterator erase(iterator position) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); @@ -460,20 +478,36 @@ public: /* list operations */ - void splice(iterator position,sequenced_index<SuperMeta,TagList>& x) + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(sequenced_index,Index,void) + splice(iterator position,Index& x) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); - BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x); BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - iterator first=x.begin(),last=x.end(); - while(first!=last){ - if(insert(position,*first).second)first=x.erase(first); - else ++first; + if(x.end().get_node()==this->header()){ /* same container */ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( + position==end(),safe_mode::inside_range); + } + else{ + external_splice( + position,x,x.begin(),x.end(), + boost::is_copy_constructible<value_type>()); } } - void splice(iterator position,sequenced_index<SuperMeta,TagList>& x,iterator i) + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(sequenced_index,Index,void) + splice(iterator position,BOOST_RV_REF(Index) x) + { + splice(position,static_cast<Index&>(x)); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE( + sequenced_index,Index,pair_return_type) + splice( + iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); @@ -481,30 +515,36 @@ public: BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - if(&x==this){ - if(position!=i)relink(position.get_node(),i.get_node()); + if(x.end().get_node()==this->header()){ /* same container */ + index_node_type* pn=position.get_node(); + index_node_type* in=static_cast<index_node_type*>(i.get_node()); + if(pn!=in)relink(pn,in); + return std::pair<iterator,bool>(make_iterator(in),true); } else{ - if(insert(position,*i).second){ - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following - * workaround is needed. Left it for all compilers as it does no - * harm. - */ - i.detach(); - x.erase(x.make_iterator(i.get_node())); -#else - x.erase(i); -#endif - - } + std::pair<final_node_type*,bool> p= + external_splice( + position,x,i,boost::is_copy_constructible<value_type>()); + return std::pair<iterator,bool>(make_iterator(p.first),p.second); } } - void splice( - iterator position,sequenced_index<SuperMeta,TagList>& x, - iterator first,iterator last) + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE( + sequenced_index,Index,pair_return_type) + splice( + iterator position,BOOST_RV_REF(Index) x, + BOOST_DEDUCED_TYPENAME Index::iterator i) + { + return splice(position,static_cast<Index&>(x),i); + } + + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(sequenced_index,Index,void) + splice( + iterator position,Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); @@ -514,24 +554,32 @@ public: BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - if(&x==this){ + if(x.end().get_node()==this->header()){ /* same container */ BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); - if(position!=last)relink( - position.get_node(),first.get_node(),last.get_node()); + internal_splice(position,first,last); } else{ - while(first!=last){ - if(insert(position,*first).second)first=x.erase(first); - else ++first; - } + external_splice( + position,x,first,last,boost::is_copy_constructible<value_type>()); } } + template<typename Index> + BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(sequenced_index,Index,void) + splice( + iterator position,BOOST_RV_REF(Index) x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) + { + splice(position,static_cast<Index&>(x),first,last); + } + void remove(value_param_type value) { sequenced_index_remove( *this, - ::boost::bind(std::equal_to<value_type>(),::boost::arg<1>(),value)); + ::boost::bind<bool>( + std::equal_to<value_type>(),::boost::arg<1>(),value)); } template<typename Predicate> @@ -613,16 +661,21 @@ public: void rearrange(InputIterator first) { BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - node_type* pos=header(); + index_node_type* pos=header(); for(size_type s=size();s--;){ const value_type& v=*first++; - relink(pos,node_from_value<node_type>(&v)); + relink(pos,node_from_value<index_node_type>(&v)); } } BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: sequenced_index(const ctor_args_list& args_list,const allocator_type& al): super(args_list.get_tail(),al) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe(*this) +#endif + { empty_initialize(); } @@ -631,7 +684,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: super(x) #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - ,safe_super() + ,safe(*this) #endif { @@ -643,7 +696,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: super(x,do_not_copy_elements_tag()) #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - ,safe_super() + ,safe(*this) #endif { @@ -656,23 +709,25 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - iterator make_iterator(node_type* node){return iterator(node,this);} - const_iterator make_iterator(node_type* node)const - {return const_iterator(node,const_cast<sequenced_index*>(this));} + iterator make_iterator(index_node_type* node) + {return iterator(node,&safe);} + const_iterator make_iterator(index_node_type* node)const + {return const_iterator(node,const_cast<safe_container*>(&safe));} #else - iterator make_iterator(node_type* node){return iterator(node);} - const_iterator make_iterator(node_type* node)const + iterator make_iterator(index_node_type* node){return iterator(node);} + const_iterator make_iterator(index_node_type* node)const {return const_iterator(node);} #endif void copy_( const sequenced_index<SuperMeta,TagList>& x,const copy_map_type& map) { - node_type* org=x.header(); - node_type* cpy=header(); + index_node_type* org=x.header(); + index_node_type* cpy=header(); do{ - node_type* next_org=node_type::from_impl(org->next()); - node_type* next_cpy=map.find(static_cast<final_node_type*>(next_org)); + index_node_type* next_org=index_node_type::from_impl(org->next()); + index_node_type* next_cpy=map.find( + static_cast<final_node_type*>(next_org)); cpy->next()=next_cpy->impl(); next_cpy->prior()=cpy->impl(); org=next_org; @@ -687,33 +742,36 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: value_param_type v,final_node_type*& x,Variant variant) { final_node_type* res=super::insert_(v,x,variant); - if(res==x)link(static_cast<node_type*>(x)); + if(res==x)link(static_cast<index_node_type*>(x)); return res; } template<typename Variant> final_node_type* insert_( - value_param_type v,node_type* position,final_node_type*& x,Variant variant) + value_param_type v,index_node_type* position, + final_node_type*& x,Variant variant) { final_node_type* res=super::insert_(v,position,x,variant); - if(res==x)link(static_cast<node_type*>(x)); + if(res==x)link(static_cast<index_node_type*>(x)); return res; } - void erase_(node_type* x) + template<typename Dst> + void extract_(index_node_type* x,Dst dst) { unlink(x); - super::erase_(x); + super::extract_(x,dst.next()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - detach_iterators(x); + transfer_iterators(dst.get(),x); #endif } void delete_all_nodes_() { - for(node_type* x=node_type::from_impl(header()->next());x!=header();){ - node_type* y=node_type::from_impl(x->next()); + for(index_node_type* x=index_node_type::from_impl(header()->next()); + x!=header();){ + index_node_type* y=index_node_type::from_impl(x->next()); this->final_delete_node_(static_cast<final_node_type*>(x)); x=y; } @@ -725,35 +783,37 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: empty_initialize(); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::detach_dereferenceable_iterators(); + safe.detach_dereferenceable_iterators(); #endif } - void swap_(sequenced_index<SuperMeta,TagList>& x) + template<typename BoolConstant> + void swap_( + sequenced_index<SuperMeta,TagList>& x,BoolConstant swap_allocators) { #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif - super::swap_(x); + super::swap_(x,swap_allocators); } void swap_elements_(sequenced_index<SuperMeta,TagList>& x) { #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - safe_super::swap(x); + safe.swap(x.safe); #endif super::swap_elements_(x); } template<typename Variant> - bool replace_(value_param_type v,node_type* x,Variant variant) + bool replace_(value_param_type v,index_node_type* x,Variant variant) { return super::replace_(v,x,variant); } - bool modify_(node_type* x) + bool modify_(index_node_type* x) { BOOST_TRY{ if(!super::modify_(x)){ @@ -779,12 +839,12 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - bool modify_rollback_(node_type* x) + bool modify_rollback_(index_node_type* x) { return super::modify_rollback_(x); } - bool check_rollback_(node_type* x)const + bool check_rollback_(index_node_type* x)const { return super::check_rollback_(x); } @@ -842,49 +902,57 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #endif private: - node_type* header()const{return this->final_header();} + index_node_type* header()const{return this->final_header();} void empty_initialize() { header()->prior()=header()->next()=header()->impl(); } - void link(node_type* x) + void link(index_node_type* x) { node_impl_type::link(x->impl(),header()->impl()); - }; + } - static void unlink(node_type* x) + static void unlink(index_node_type* x) { node_impl_type::unlink(x->impl()); } - static void relink(node_type* position,node_type* x) + static void relink(index_node_type* position,index_node_type* x) { node_impl_type::relink(position->impl(),x->impl()); } - static void relink(node_type* position,node_type* first,node_type* last) + static void relink( + index_node_type* position,index_node_type* first,index_node_type* last) { node_impl_type::relink( position->impl(),first->impl(),last->impl()); } #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) - void rearranger(node_type* position,node_type *x) + void rearranger(index_node_type* position,index_node_type *x) { if(!position)position=header(); - node_type::increment(position); + index_node_type::increment(position); if(position!=x)relink(position,x); } #endif #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - void detach_iterators(node_type* x) + void detach_iterators(index_node_type* x) { iterator it=make_iterator(x); safe_mode::detach_equivalent_iterators(it); } + + template<typename Dst> + void transfer_iterators(Dst& dst,index_node_type* x) + { + iterator it=make_iterator(x); + safe_mode::transfer_equivalent_iterators(dst,it); + } #endif template <class InputIterator> @@ -954,12 +1022,116 @@ private: return std::pair<iterator,bool>(make_iterator(p.first),p.second); } + template<typename Index> + std::pair<final_node_type*,bool> external_splice( + iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i, + boost::true_type /* copy-constructible value */) + { + if(get_allocator()==x.get_allocator()){ + return external_splice(position,x,i,boost::false_type()); + } + else{ + /* backwards compatibility with old, non-transfer-based splice */ + + std::pair<iterator,bool> p=insert(position,*i); + if(p.second)x.erase(i); + return std::pair<final_node_type*,bool>( + static_cast<final_node_type*>(p.first.get_node()),p.second); + } + } + + template<typename Index> + std::pair<final_node_type*,bool> external_splice( + iterator position,Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i, + boost::false_type /* copy-constructible value */) + { + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + std::pair<final_node_type*,bool> p=this->final_transfer_( + x,static_cast<final_node_type*>(i.get_node())); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return p; + } + + template<typename Iterator> + void internal_splice(iterator position,Iterator first,Iterator last) + { + index_node_type* pn=position.get_node(); + while(first!=last){ + relink(pn,static_cast<index_node_type*>((first++).get_node())); + } + } + + void internal_splice(iterator position,iterator first,iterator last) + { + index_node_type* pn=position.get_node(); + index_node_type* fn=static_cast<index_node_type*>(first.get_node()); + index_node_type* ln=static_cast<index_node_type*>(last.get_node()); + if(pn!=ln)relink(pn,fn,ln); + } + + template<typename Index> + void external_splice( + iterator position,Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last, + boost::true_type /* copy-constructible value */) + { + if(get_allocator()==x.get_allocator()){ + external_splice(position,x,first,last,boost::false_type()); + } + else{ + /* backwards compatibility with old, non-transfer-based splice */ + + while(first!=last){ + if(insert(position,*first).second)first=x.erase(first); + else ++first; + } + } + } + + template<typename Index> + void external_splice( + iterator position,Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last, + boost::false_type /* copy-constructible value */) + { + BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x); + if(position==end()){ + this->final_transfer_range_(x,first,last); + } + else{ + iterator first_to_relink=end(); + --first_to_relink; + BOOST_TRY{ + this->final_transfer_range_(x,first,last); + } + BOOST_CATCH(...){ + ++first_to_relink; + relink(position.get_node(),first_to_relink.get_node(),header()); + } + BOOST_CATCH_END + ++first_to_relink; + relink(position.get_node(),first_to_relink.get_node(),header()); + } + } + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_container safe; +#endif + #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) #pragma parse_mfunc_templ reset #endif }; +#if defined(BOOST_MSVC) +#pragma warning(pop) /* C4355 */ +#endif + /* comparison */ template< diff --git a/contrib/restricted/boost/multi_index/include/boost/multi_index_container.hpp b/contrib/restricted/boost/multi_index/include/boost/multi_index_container.hpp index f0190d5ff77..9840a65ef01 100644 --- a/contrib/restricted/boost/multi_index/include/boost/multi_index_container.hpp +++ b/contrib/restricted/boost/multi_index/include/boost/multi_index_container.hpp @@ -1,6 +1,6 @@ /* Multiply indexed container. * - * Copyright 2003-2018 Joaquin M Lopez Munoz. + * Copyright 2003-2021 Joaquin M Lopez Munoz. * 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) @@ -17,12 +17,11 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> -#include <memory> #include <boost/core/addressof.hpp> -#include <boost/detail/allocator_utilities.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <boost/detail/workaround.hpp> #include <boost/move/core.hpp> +#include <boost/move/utility_core.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/contains.hpp> #include <boost/mpl/find_if.hpp> @@ -33,16 +32,19 @@ #include <boost/multi_index_container_fwd.hpp> #include <boost/multi_index/detail/access_specifier.hpp> #include <boost/multi_index/detail/adl_swap.hpp> +#include <boost/multi_index/detail/allocator_traits.hpp> #include <boost/multi_index/detail/base_type.hpp> #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp> #include <boost/multi_index/detail/converter.hpp> #include <boost/multi_index/detail/header_holder.hpp> #include <boost/multi_index/detail/has_tag.hpp> +#include <boost/multi_index/detail/invalidate_iterators.hpp> #include <boost/multi_index/detail/no_duplicate_tags.hpp> #include <boost/multi_index/detail/safe_mode.hpp> #include <boost/multi_index/detail/scope_guard.hpp> #include <boost/multi_index/detail/vartempl_support.hpp> #include <boost/static_assert.hpp> +#include <boost/type_traits/integral_constant.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/utility/base_from_member.hpp> @@ -77,6 +79,12 @@ namespace boost{ namespace multi_index{ +namespace detail{ + +struct unequal_alloc_move_ctor_tag{}; + +} /* namespace multi_index::detail */ + #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) #pragma warning(push) #pragma warning(disable:4522) /* spurious warning on multiple operator=()'s */ @@ -85,25 +93,20 @@ namespace multi_index{ template<typename Value,typename IndexSpecifierList,typename Allocator> class multi_index_container: private ::boost::base_from_member< - typename boost::detail::allocator::rebind_to< + typename detail::rebind_alloc_for< Allocator, typename detail::multi_index_node_type< Value,IndexSpecifierList,Allocator>::type - >::type>, + >::type + >, BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder< -#ifndef BOOST_NO_CXX11_ALLOCATOR - typename std::allocator_traits< -#endif - typename boost::detail::allocator::rebind_to< + typename detail::allocator_traits< + typename detail::rebind_alloc_for< Allocator, typename detail::multi_index_node_type< Value,IndexSpecifierList,Allocator>::type >::type -#ifdef BOOST_NO_CXX11_ALLOCATOR - ::pointer, -#else >::pointer, -#endif multi_index_container<Value,IndexSpecifierList,Allocator> >, public detail::multi_index_base_type< Value,IndexSpecifierList,Allocator>::type @@ -128,23 +131,18 @@ private: #endif typedef typename detail::multi_index_base_type< - Value,IndexSpecifierList,Allocator>::type super; - typedef typename - boost::detail::allocator::rebind_to< + Value,IndexSpecifierList,Allocator>::type super; + typedef typename detail::rebind_alloc_for< Allocator, - typename super::node_type - >::type node_allocator; -#ifdef BOOST_NO_CXX11_ALLOCATOR - typedef typename node_allocator::pointer node_pointer; -#else - typedef std::allocator_traits<node_allocator> node_allocator_traits; - typedef typename node_allocator_traits::pointer node_pointer; -#endif + typename super::index_node_type + >::type node_allocator; + typedef detail::allocator_traits<node_allocator> node_alloc_traits; + typedef typename node_alloc_traits::pointer node_pointer; typedef ::boost::base_from_member< - node_allocator> bfm_allocator; + node_allocator> bfm_allocator; typedef detail::header_holder< node_pointer, - multi_index_container> bfm_header; + multi_index_container> bfm_header; public: /* All types are inherited from super, a few are explicitly @@ -160,6 +158,7 @@ public: typedef typename super::const_iterator_type_list const_iterator_type_list; typedef typename super::value_type value_type; typedef typename super::final_allocator_type allocator_type; + typedef typename super::size_type size_type; typedef typename super::iterator iterator; typedef typename super::const_iterator const_iterator; @@ -168,25 +167,30 @@ public: /* global project() needs to see this publicly */ - typedef typename super::node_type node_type; + typedef typename super::final_node_type final_node_type; /* construct/copy/destroy */ + multi_index_container(): + bfm_allocator(allocator_type()), + super(ctor_args_list(),bfm_allocator::member), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } + explicit multi_index_container( + const ctor_args_list& args_list, #if BOOST_WORKAROUND(__IBMCPP__,<=600) - /* VisualAge seems to have an ETI issue with the default values - * for arguments args_list and al. + /* VisualAge seems to have an ETI issue with the default value for + * argument al. */ - const ctor_args_list& args_list= - typename mpl::identity<multi_index_container>::type:: - ctor_args_list(), const allocator_type& al= typename mpl::identity<multi_index_container>::type:: allocator_type()): #else - const ctor_args_list& args_list=ctor_args_list(), const allocator_type& al=allocator_type()): #endif @@ -275,28 +279,18 @@ public: multi_index_container( const multi_index_container<Value,IndexSpecifierList,Allocator>& x): - bfm_allocator(x.bfm_allocator::member), + bfm_allocator( + node_alloc_traits::select_on_container_copy_construction( + x.bfm_allocator::member)), bfm_header(), super(x), node_count(0) { - copy_map_type map(bfm_allocator::member,x.size(),x.header(),header()); - for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){ - map.clone(it.get_node()); - } - super::copy_(x,map); - map.release(); - node_count=x.size(); - - /* Not until this point are the indices required to be consistent, - * hence the position of the invariant checker. - */ - - BOOST_MULTI_INDEX_CHECK_INVARIANT; + copy_construct_from(x); } multi_index_container(BOOST_RV_REF(multi_index_container) x): - bfm_allocator(x.bfm_allocator::member), + bfm_allocator(boost::move(x.bfm_allocator::member)), bfm_header(), super(x,detail::do_not_copy_elements_tag()), node_count(0) @@ -306,6 +300,36 @@ public: swap_elements_(x); } + multi_index_container( + const multi_index_container<Value,IndexSpecifierList,Allocator>& x, + const allocator_type& al): + bfm_allocator(al), + bfm_header(), + super(x), + node_count(0) + { + copy_construct_from(x); + } + + multi_index_container( + BOOST_RV_REF(multi_index_container) x,const allocator_type& al): + bfm_allocator(al), + bfm_header(), + super(x,detail::do_not_copy_elements_tag()), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x); + + if(al==x.get_allocator()){ + swap_elements_(x); + } + else{ + multi_index_container y(x,al,detail::unequal_alloc_move_ctor_tag()); + swap_elements_(y); + } + } + ~multi_index_container() { delete_all_nodes_(); @@ -319,8 +343,11 @@ public: multi_index_container<Value,IndexSpecifierList,Allocator>& operator=( const multi_index_container<Value,IndexSpecifierList,Allocator>& x) { - multi_index_container y(x); - this->swap(y); + multi_index_container y( + x, + node_alloc_traits::propagate_on_container_copy_assignment::value? + x.get_allocator():this->get_allocator()); + swap_(y,boost::true_type() /* swap_allocators */); return *this; } #endif @@ -328,16 +355,33 @@ public: multi_index_container<Value,IndexSpecifierList,Allocator>& operator=( BOOST_COPY_ASSIGN_REF(multi_index_container) x) { - multi_index_container y(x); - this->swap(y); + multi_index_container y( + x, + node_alloc_traits::propagate_on_container_copy_assignment::value? + x.get_allocator():this->get_allocator()); + swap_(y,boost::true_type() /* swap_allocators */); return *this; } multi_index_container<Value,IndexSpecifierList,Allocator>& operator=( BOOST_RV_REF(multi_index_container) x) { - this->swap(x); +#include <boost/multi_index/detail/define_if_constexpr_macro.hpp> + + BOOST_MULTI_INDEX_IF_CONSTEXPR( + node_alloc_traits::propagate_on_container_move_assignment::value){ + swap_(x,boost::true_type() /* swap_allocators */); + } + else if(this->get_allocator()==x.get_allocator()){ + swap_(x,boost::false_type() /* swap_allocators */); + } + else{ + multi_index_container y(boost::move(x),this->get_allocator()); + swap_(y,boost::false_type() /* swap_allocators */); + } return *this; + +#include <boost/multi_index/detail/undef_if_constexpr_macro.hpp> } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) @@ -446,10 +490,9 @@ public: #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - BOOST_MULTI_INDEX_CHECK_IS_OWNER( - it,static_cast<typename IteratorType::container_type&>(*this)); - - return index_type::make_iterator(static_cast<node_type*>(it.get_node())); + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this); + return index_type::make_iterator( + static_cast<final_node_type*>(it.get_node())); } template<int N,typename IteratorType> @@ -464,9 +507,9 @@ public: #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - BOOST_MULTI_INDEX_CHECK_IS_OWNER( - it,static_cast<const typename IteratorType::container_type&>(*this)); - return index_type::make_iterator(static_cast<node_type*>(it.get_node())); + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this); + return index_type::make_iterator( + static_cast<final_node_type*>(it.get_node())); } #endif @@ -496,9 +539,9 @@ public: #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - BOOST_MULTI_INDEX_CHECK_IS_OWNER( - it,static_cast<typename IteratorType::container_type&>(*this)); - return index_type::make_iterator(static_cast<node_type*>(it.get_node())); + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this); + return index_type::make_iterator( + static_cast<final_node_type*>(it.get_node())); } template<typename Tag,typename IteratorType> @@ -513,14 +556,48 @@ public: #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - BOOST_MULTI_INDEX_CHECK_IS_OWNER( - it,static_cast<const typename IteratorType::container_type&>(*this)); - return index_type::make_iterator(static_cast<node_type*>(it.get_node())); + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this); + return index_type::make_iterator( + static_cast<final_node_type*>(it.get_node())); } #endif BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: - typedef typename super::copy_map_type copy_map_type; + typedef typename super::final_node_handle_type final_node_handle_type; + typedef typename super::copy_map_type copy_map_type; + + multi_index_container( + multi_index_container<Value,IndexSpecifierList,Allocator>& x, + const allocator_type& al, + detail::unequal_alloc_move_ctor_tag): + bfm_allocator(al), + bfm_header(), + super(x), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x); + BOOST_TRY{ + copy_map_type map(bfm_allocator::member,x.size(),x.header(),header()); + for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){ + map.move_clone(it.get_node()); + } + super::copy_(x,map); + map.release(); + node_count=x.size(); + x.clear(); + } + BOOST_CATCH(...){ + x.clear(); + BOOST_RETHROW; + } + BOOST_CATCH_END + + /* Not until this point are the indices required to be consistent, + * hence the position of the invariant checker. + */ + + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) multi_index_container( @@ -535,27 +612,59 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } #endif - node_type* header()const + void copy_construct_from( + const multi_index_container<Value,IndexSpecifierList,Allocator>& x) + { + copy_map_type map(bfm_allocator::member,x.size(),x.header(),header()); + for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){ + map.copy_clone(it.get_node()); + } + super::copy_(x,map); + map.release(); + node_count=x.size(); + + /* Not until this point are the indices required to be consistent, + * hence the position of the invariant checker. + */ + + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } + + final_node_type* header()const { return &*bfm_header::member; } - node_type* allocate_node() + final_node_type* allocate_node() { -#ifdef BOOST_NO_CXX11_ALLOCATOR - return &*bfm_allocator::member.allocate(1); -#else - return &*node_allocator_traits::allocate(bfm_allocator::member,1); -#endif + return &*node_alloc_traits::allocate(bfm_allocator::member,1); } - void deallocate_node(node_type* x) + void deallocate_node(final_node_type* x) { -#ifdef BOOST_NO_CXX11_ALLOCATOR - bfm_allocator::member.deallocate(static_cast<node_pointer>(x),1); -#else - node_allocator_traits::deallocate(bfm_allocator::member,static_cast<node_pointer>(x),1); -#endif + node_alloc_traits::deallocate( + bfm_allocator::member,static_cast<node_pointer>(x),1); + } + + void construct_value(final_node_type* x,const Value& v) + { + node_alloc_traits::construct( + bfm_allocator::member,boost::addressof(x->value()),v); + } + + void construct_value(final_node_type* x,BOOST_RV_REF(Value) v) + { + node_alloc_traits::construct( + bfm_allocator::member,boost::addressof(x->value()),boost::move(v)); + } + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( + void,construct_value,vartempl_construct_value_impl,final_node_type*,x) + + void destroy_value(final_node_type* x) + { + node_alloc_traits::destroy( + bfm_allocator::member,boost::addressof(x->value())); } bool empty_()const @@ -563,60 +672,60 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: return node_count==0; } - std::size_t size_()const + size_type size_()const { return node_count; } - std::size_t max_size_()const + size_type max_size_()const { - return static_cast<std::size_t >(-1); + return static_cast<size_type>(-1); } template<typename Variant> - std::pair<node_type*,bool> insert_(const Value& v,Variant variant) + std::pair<final_node_type*,bool> insert_(const Value& v,Variant variant) { - node_type* x=0; - node_type* res=super::insert_(v,x,variant); + final_node_type* x=0; + final_node_type* res=super::insert_(v,x,variant); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - return std::pair<node_type*,bool>(res,false); + return std::pair<final_node_type*,bool>(res,false); } } - std::pair<node_type*,bool> insert_(const Value& v) + std::pair<final_node_type*,bool> insert_(const Value& v) { return insert_(v,detail::lvalue_tag()); } - std::pair<node_type*,bool> insert_rv_(const Value& v) + std::pair<final_node_type*,bool> insert_rv_(const Value& v) { return insert_(v,detail::rvalue_tag()); } template<typename T> - std::pair<node_type*,bool> insert_ref_(T& t) + std::pair<final_node_type*,bool> insert_ref_(T& t) { - node_type* x=allocate_node(); + final_node_type* x=allocate_node(); BOOST_TRY{ - new(boost::addressof(x->value())) value_type(t); + construct_value(x,t); BOOST_TRY{ - node_type* res=super::insert_(x->value(),x,detail::emplaced_tag()); + final_node_type* res=super::insert_( + x->value(),x,detail::emplaced_tag()); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - boost::detail::allocator::destroy(boost::addressof(x->value())); - deallocate_node(x); - return std::pair<node_type*,bool>(res,false); + delete_node_(x); + return std::pair<final_node_type*,bool>(res,false); } } BOOST_CATCH(...){ - boost::detail::allocator::destroy(boost::addressof(x->value())); + destroy_value(x); BOOST_RETHROW; } BOOST_CATCH_END @@ -628,38 +737,66 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - std::pair<node_type*,bool> insert_ref_(const value_type& x) + std::pair<final_node_type*,bool> insert_ref_(const value_type& x) { return insert_(x); } - std::pair<node_type*,bool> insert_ref_(value_type& x) + std::pair<final_node_type*,bool> insert_ref_(value_type& x) { return insert_(x); } + std::pair<final_node_type*,bool> insert_nh_(final_node_handle_type& nh) + { + if(!nh)return std::pair<final_node_type*,bool>(header(),false); + else{ + final_node_type* x=nh.node; + final_node_type* res=super::insert_( + x->value(),x,detail::emplaced_tag()); + if(res==x){ + nh.release_node(); + ++node_count; + return std::pair<final_node_type*,bool>(res,true); + } + else return std::pair<final_node_type*,bool>(res,false); + } + } + + template<typename Index> + std::pair<final_node_type*,bool> transfer_(Index& x,final_node_type* n) + { + final_node_type* res=super::insert_(n->value(),n,&super::final(x)); + if(res==n){ + ++node_count; + return std::pair<final_node_type*,bool>(res,true); + } + else{ + return std::pair<final_node_type*,bool>(res,false); + } + } + template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> - std::pair<node_type*,bool> emplace_( + std::pair<final_node_type*,bool> emplace_( BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) { - node_type* x=allocate_node(); + final_node_type* x=allocate_node(); BOOST_TRY{ - detail::vartempl_placement_new( - boost::addressof(x->value()),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); BOOST_TRY{ - node_type* res=super::insert_(x->value(),x,detail::emplaced_tag()); + final_node_type* res=super::insert_( + x->value(),x,detail::emplaced_tag()); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - boost::detail::allocator::destroy(boost::addressof(x->value())); - deallocate_node(x); - return std::pair<node_type*,bool>(res,false); + delete_node_(x); + return std::pair<final_node_type*,bool>(res,false); } } BOOST_CATCH(...){ - boost::detail::allocator::destroy(boost::addressof(x->value())); + destroy_value(x); BOOST_RETHROW; } BOOST_CATCH_END @@ -672,52 +809,53 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } template<typename Variant> - std::pair<node_type*,bool> insert_( - const Value& v,node_type* position,Variant variant) + std::pair<final_node_type*,bool> insert_( + const Value& v,final_node_type* position,Variant variant) { - node_type* x=0; - node_type* res=super::insert_(v,position,x,variant); + final_node_type* x=0; + final_node_type* res=super::insert_(v,position,x,variant); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - return std::pair<node_type*,bool>(res,false); + return std::pair<final_node_type*,bool>(res,false); } } - std::pair<node_type*,bool> insert_(const Value& v,node_type* position) + std::pair<final_node_type*,bool> insert_( + const Value& v,final_node_type* position) { return insert_(v,position,detail::lvalue_tag()); } - std::pair<node_type*,bool> insert_rv_(const Value& v,node_type* position) + std::pair<final_node_type*,bool> insert_rv_( + const Value& v,final_node_type* position) { return insert_(v,position,detail::rvalue_tag()); } template<typename T> - std::pair<node_type*,bool> insert_ref_( - T& t,node_type* position) + std::pair<final_node_type*,bool> insert_ref_( + T& t,final_node_type* position) { - node_type* x=allocate_node(); + final_node_type* x=allocate_node(); BOOST_TRY{ - new(boost::addressof(x->value())) value_type(t); + construct_value(x,t); BOOST_TRY{ - node_type* res=super::insert_( + final_node_type* res=super::insert_( x->value(),position,x,detail::emplaced_tag()); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - boost::detail::allocator::destroy(boost::addressof(x->value())); - deallocate_node(x); - return std::pair<node_type*,bool>(res,false); + delete_node_(x); + return std::pair<final_node_type*,bool>(res,false); } } BOOST_CATCH(...){ - boost::detail::allocator::destroy(boost::addressof(x->value())); + destroy_value(x); BOOST_RETHROW; } BOOST_CATCH_END @@ -729,42 +867,57 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - std::pair<node_type*,bool> insert_ref_( - const value_type& x,node_type* position) + std::pair<final_node_type*,bool> insert_ref_( + const value_type& x,final_node_type* position) { return insert_(x,position); } - std::pair<node_type*,bool> insert_ref_( - value_type& x,node_type* position) + std::pair<final_node_type*,bool> insert_ref_( + value_type& x,final_node_type* position) { return insert_(x,position); } + std::pair<final_node_type*,bool> insert_nh_( + final_node_handle_type& nh,final_node_type* position) + { + if(!nh)return std::pair<final_node_type*,bool>(header(),false); + else{ + final_node_type* x=nh.node; + final_node_type* res=super::insert_( + x->value(),position,x,detail::emplaced_tag()); + if(res==x){ + nh.release_node(); + ++node_count; + return std::pair<final_node_type*,bool>(res,true); + } + else return std::pair<final_node_type*,bool>(res,false); + } + } + template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> - std::pair<node_type*,bool> emplace_hint_( - node_type* position, + std::pair<final_node_type*,bool> emplace_hint_( + final_node_type* position, BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) { - node_type* x=allocate_node(); + final_node_type* x=allocate_node(); BOOST_TRY{ - detail::vartempl_placement_new( - boost::addressof(x->value()),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); BOOST_TRY{ - node_type* res=super::insert_( + final_node_type* res=super::insert_( x->value(),position,x,detail::emplaced_tag()); if(res==x){ ++node_count; - return std::pair<node_type*,bool>(res,true); + return std::pair<final_node_type*,bool>(res,true); } else{ - boost::detail::allocator::destroy(boost::addressof(x->value())); - deallocate_node(x); - return std::pair<node_type*,bool>(res,false); + delete_node_(x); + return std::pair<final_node_type*,bool>(res,false); } } BOOST_CATCH(...){ - boost::detail::allocator::destroy(boost::addressof(x->value())); + destroy_value(x); BOOST_RETHROW; } BOOST_CATCH_END @@ -776,16 +929,30 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_CATCH_END } - void erase_(node_type* x) + final_node_handle_type extract_(final_node_type* x) { --node_count; - super::erase_(x); - deallocate_node(x); + super::extract_(x,detail::invalidate_iterators()); + return final_node_handle_type(x,get_allocator()); + } + + template<typename Dst> + void extract_for_transfer_(final_node_type* x,Dst dst) + { + --node_count; + super::extract_(x,dst); + } + + void erase_(final_node_type* x) + { + --node_count; + super::extract_(x,detail::invalidate_iterators()); + delete_node_(x); } - void delete_node_(node_type* x) + void delete_node_(final_node_type* x) { - super::delete_node_(x); + destroy_value(x); deallocate_node(x); } @@ -801,13 +968,41 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: node_count=0; } - void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x) + template<typename Index> + void transfer_range_( + Index& x, + BOOST_DEDUCED_TYPENAME Index::iterator first, + BOOST_DEDUCED_TYPENAME Index::iterator last) { - if(bfm_allocator::member!=x.bfm_allocator::member){ - detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member); + while(first!=last){ + transfer_(x,static_cast<final_node_type*>((first++).get_node())); } + } + + void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x) + { + swap_( + x, + boost::integral_constant< + bool,node_alloc_traits::propagate_on_container_swap::value>()); + } + + void swap_( + multi_index_container<Value,IndexSpecifierList,Allocator>& x, + boost::true_type swap_allocators) + { + detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member); std::swap(bfm_header::member,x.bfm_header::member); - super::swap_(x); + super::swap_(x,swap_allocators); + std::swap(node_count,x.node_count); + } + + void swap_( + multi_index_container<Value,IndexSpecifierList,Allocator>& x, + boost::false_type swap_allocators) + { + std::swap(bfm_header::member,x.bfm_header::member); + super::swap_(x,swap_allocators); std::swap(node_count,x.node_count); } @@ -819,18 +1014,18 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: std::swap(node_count,x.node_count); } - bool replace_(const Value& k,node_type* x) + bool replace_(const Value& k,final_node_type* x) { return super::replace_(k,x,detail::lvalue_tag()); } - bool replace_rv_(const Value& k,node_type* x) + bool replace_rv_(const Value& k,final_node_type* x) { return super::replace_(k,x,detail::rvalue_tag()); } template<typename Modifier> - bool modify_(Modifier& mod,node_type* x) + bool modify_(Modifier& mod,final_node_type* x) { BOOST_TRY{ mod(const_cast<value_type&>(x->value())); @@ -843,14 +1038,14 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_TRY{ if(!super::modify_(x)){ - deallocate_node(x); + delete_node_(x); --node_count; return false; } else return true; } BOOST_CATCH(...){ - deallocate_node(x); + delete_node_(x); --node_count; BOOST_RETHROW; } @@ -858,7 +1053,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } template<typename Modifier,typename Rollback> - bool modify_(Modifier& mod,Rollback& back_,node_type* x) + bool modify_(Modifier& mod,Rollback& back_,final_node_type* x) { BOOST_TRY{ mod(const_cast<value_type&>(x->value())); @@ -960,7 +1155,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: for(std::size_t n=0;n<s;++n){ detail::archive_constructed<Value> value("item",ar,value_version); - std::pair<node_type*,bool> p=insert_( + std::pair<final_node_type*,bool> p=insert_rv_( value.get(),super::end().get_node()); if(!p.second)throw_exception( archive::archive_exception( @@ -990,7 +1185,16 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #endif private: - std::size_t node_count; + template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> + void vartempl_construct_value_impl( + final_node_type* x,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + node_alloc_traits::construct( + bfm_allocator::member,boost::addressof(x->value()), + BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + + size_type node_count; #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) @@ -1155,16 +1359,9 @@ project( #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef detail::converter< - multi_index_type, - BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter; - BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m)); -#endif - + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m); return detail::converter<multi_index_type,index_type>::iterator( - m,static_cast<typename multi_index_type::node_type*>(it.get_node())); + m,static_cast<typename multi_index_type::final_node_type*>(it.get_node())); } template< @@ -1191,16 +1388,9 @@ project( #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef detail::converter< - multi_index_type, - BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter; - BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m)); -#endif - + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m); return detail::converter<multi_index_type,index_type>::const_iterator( - m,static_cast<typename multi_index_type::node_type*>(it.get_node())); + m,static_cast<typename multi_index_type::final_node_type*>(it.get_node())); } /* projection of iterators by tag */ @@ -1241,16 +1431,9 @@ project( #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef detail::converter< - multi_index_type, - BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter; - BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m)); -#endif - + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m); return detail::converter<multi_index_type,index_type>::iterator( - m,static_cast<typename multi_index_type::node_type*>(it.get_node())); + m,static_cast<typename multi_index_type::final_node_type*>(it.get_node())); } template< @@ -1278,16 +1461,9 @@ project( #endif BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); - -#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) - typedef detail::converter< - multi_index_type, - BOOST_DEDUCED_TYPENAME IteratorType::container_type> converter; - BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,converter::index(m)); -#endif - + BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m); return detail::converter<multi_index_type,index_type>::const_iterator( - m,static_cast<typename multi_index_type::node_type*>(it.get_node())); + m,static_cast<typename multi_index_type::final_node_type*>(it.get_node())); } /* Comparison. Simple forward to first index. */ |