From eea861301be0bf3e3f5db6cfc3cada38d133fef2 Mon Sep 17 00:00:00 2001 From: Tobias Markmann Date: Fri, 17 Feb 2017 18:15:41 +0100 Subject: Add LRUCache utility class to Swiften This implements a simple lookup cache with least recently used replacement strategy. This also adds Boost.MultiIndex from version 1.56 to 3rdParty. Test-Information: Added some unit tests for LRUCache, which pass on macOS 10.12.3 with clang-5.0 Change-Id: I0567945b1197d3fe786bf9d82fdb5e755743b975 diff --git a/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp new file mode 100644 index 0000000..ed3de84 --- /dev/null +++ b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp @@ -0,0 +1,187 @@ +/* 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 /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include + +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 +class partial_std_allocator_wrapper:public std::allocator +{ +public: + /* Oddly enough, STLport does not define std::allocator::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 + partial_std_allocator_wrapper(const partial_std_allocator_wrapper&){} + + partial_std_allocator_wrapper(const std::allocator& x): + std::allocator(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& 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 +struct is_partial_std_allocator +{ + BOOST_STATIC_CONSTANT(bool, + value= + (is_same< + std::allocator, + Allocator + >::value)|| + (is_same< + partial_std_allocator_wrapper< + BOOST_DEDUCED_TYPENAME Allocator::value_type>, + Allocator + >::value)); +}; + +#else + +template +struct is_partial_std_allocator +{ + BOOST_STATIC_CONSTANT(bool,value=false); +}; + +#endif + +/* rebind operations for defective std allocators */ + +template +struct partial_std_allocator_rebind_to +{ + typedef partial_std_allocator_wrapper type; +}; + +/* rebind operation in all other cases */ + +template +struct rebinder +{ + template + struct result + { + typedef typename Allocator::BOOST_NESTED_TEMPLATE + rebind::other other; + }; +}; + +template +struct compliant_allocator_rebind_to +{ + typedef typename rebinder:: + BOOST_NESTED_TEMPLATE result::other type; +}; + +/* rebind front-end */ + +template +struct rebind_to: + mpl::eval_if_c< + is_partial_std_allocator::value, + partial_std_allocator_rebind_to, + compliant_allocator_rebind_to + > +{ +}; + +/* allocator-independent versions of construct and destroy */ + +template +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 when Type is a class with trivial dtor. + */ + +#pragma warning(push) +#pragma warning(disable:4100) +#endif + +template +void destroy(const Type* p) +{ + +#if BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590)) + const_cast(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/3rdParty/Boost/src/boost/mpl/aux_/reverse_iter_fold_impl.hpp b/3rdParty/Boost/src/boost/mpl/aux_/reverse_iter_fold_impl.hpp new file mode 100644 index 0000000..83182a2 --- /dev/null +++ b/3rdParty/Boost/src/boost/mpl/aux_/reverse_iter_fold_impl.hpp @@ -0,0 +1,43 @@ + +#ifndef BOOST_MPL_AUX_ITER_FOLD_BACKWARD_IMPL_HPP_INCLUDED +#define BOOST_MPL_AUX_ITER_FOLD_BACKWARD_IMPL_HPP_INCLUDED + +// Copyright Aleksey Gurtovoy 2000-2004 +// +// 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/mpl for documentation. + +// $Id$ +// $Date$ +// $Revision$ + +#if !defined(BOOST_MPL_PREPROCESSING_MODE) +# include +# include +# include +# if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ + || defined(BOOST_MPL_CFG_NO_NONTYPE_TEMPLATE_PARTIAL_SPEC) +# include +# include +# endif +#endif + +#include + +#if !defined(BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS) \ + && !defined(BOOST_MPL_PREPROCESSING_MODE) + +# define BOOST_MPL_PREPROCESSED_HEADER reverse_iter_fold_impl.hpp +# include + +#else + +# define AUX778076_FOLD_IMPL_OP(iter) iter +# define AUX778076_FOLD_IMPL_NAME_PREFIX reverse_iter_fold +# include + +#endif // BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS +#endif // BOOST_MPL_AUX_ITER_FOLD_BACKWARD_IMPL_HPP_INCLUDED diff --git a/3rdParty/Boost/src/boost/mpl/reverse_iter_fold.hpp b/3rdParty/Boost/src/boost/mpl/reverse_iter_fold.hpp new file mode 100644 index 0000000..348f295 --- /dev/null +++ b/3rdParty/Boost/src/boost/mpl/reverse_iter_fold.hpp @@ -0,0 +1,56 @@ + +#ifndef BOOST_MPL_ITER_FOLD_BACKWARD_HPP_INCLUDED +#define BOOST_MPL_ITER_FOLD_BACKWARD_HPP_INCLUDED + +// Copyright Aleksey Gurtovoy 2001-2004 +// Copyright Dave Abrahams 2001-2002 +// +// 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/mpl for documentation. + +// $Id$ +// $Date$ +// $Revision$ + +#include +#include +#include +#include +#include +#include +#include + +namespace boost { namespace mpl { + +template< + typename BOOST_MPL_AUX_NA_PARAM(Sequence) + , typename BOOST_MPL_AUX_NA_PARAM(State) + , typename BOOST_MPL_AUX_NA_PARAM(BackwardOp) + , typename ForwardOp = arg<1> + > +struct reverse_iter_fold +{ + typedef typename aux::reverse_iter_fold_impl< + ::boost::mpl::O1_size::value + , typename begin::type + , typename end::type + , State + , typename lambda::type + , typename lambda::type + >::state type; + + BOOST_MPL_AUX_LAMBDA_SUPPORT( + 4 + , reverse_iter_fold + , (Sequence,State,BackwardOp,ForwardOp) + ) +}; + +BOOST_MPL_AUX_NA_SPEC(3, reverse_iter_fold) + +}} + +#endif // BOOST_MPL_ITER_FOLD_BACKWARD_HPP_INCLUDED diff --git a/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp b/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp new file mode 100644 index 0000000..f3346e8 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp @@ -0,0 +1,54 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ACCESS_SPECIFIER_HPP +#define BOOST_MULTI_INDEX_DETAIL_ACCESS_SPECIFIER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include +#include + +/* In those compilers that do not accept the member template friend syntax, + * some protected and private sections might need to be specified as + * public. + */ + +#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) +#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS public +#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS public +#else +#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS protected +#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS private +#endif + +/* GCC does not correctly support in-class using declarations for template + * functions. See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9810 + * MSVC 7.1/8.0 seem to have a similar problem, though the conditions in + * which the error happens are not that simple. I have yet to isolate this + * into a snippet suitable for bug reporting. + * Sun Studio also has this problem, which might be related, from the + * information gathered at Sun forums, with a known issue notified at the + * internal bug report 6421933. The bug is present up to Studio Express 2, + * the latest preview version of the future Sun Studio 12. As of this writing + * (October 2006) it is not known whether a fix will finally make it into the + * official Sun Studio 12. + */ + +#if BOOST_WORKAROUND(__GNUC__,==3)&&(__GNUC_MINOR__<4)||\ + BOOST_WORKAROUND(BOOST_MSVC,==1310)||\ + BOOST_WORKAROUND(BOOST_MSVC,==1400)||\ + BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590)) +#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS public +#else +#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS private +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp b/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp new file mode 100644 index 0000000..02b0644 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp @@ -0,0 +1,44 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ADL_SWAP_HPP +#define BOOST_MULTI_INDEX_DETAIL_ADL_SWAP_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template +void adl_swap(T& x,T& y) +{ + +#if !defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL) + using std::swap; + swap(x,y); +#else + std::swap(x,y); +#endif + +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp b/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp new file mode 100644 index 0000000..0cf7991 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp @@ -0,0 +1,79 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ARCHIVE_CONSTRUCTED_HPP +#define BOOST_MULTI_INDEX_DETAIL_ARCHIVE_CONSTRUCTED_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* constructs a stack-based object from a serialization archive */ + +template +struct archive_constructed:private noncopyable +{ + template + archive_constructed(Archive& ar,const unsigned int version) + { + serialization::load_construct_data_adl(ar,&get(),version); + BOOST_TRY{ + ar>>get(); + } + BOOST_CATCH(...){ + (&get())->~T(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + template + archive_constructed(const char* name,Archive& ar,const unsigned int version) + { + serialization::load_construct_data_adl(ar,&get(),version); + BOOST_TRY{ + ar>>serialization::make_nvp(name,get()); + } + BOOST_CATCH(...){ + (&get())->~T(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + ~archive_constructed() + { + (&get())->~T(); + } + + T& get(){return *static_cast(static_cast(&space));} + +private: + typename aligned_storage::value>::type space; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp b/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp new file mode 100644 index 0000000..9d78c3a --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp @@ -0,0 +1,91 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_AUTO_SPACE_HPP +#define BOOST_MULTI_INDEX_DETAIL_AUTO_SPACE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* auto_space provides uninitialized space suitably to store + * a given number of elements of a given type. + */ + +/* NB: it is not clear whether using an allocator to handle + * zero-sized arrays of elements is conformant or not. GCC 3.3.1 + * and prior fail here, other stdlibs handle the issue gracefully. + * To be on the safe side, the case n==0 is given special treatment. + * References: + * GCC Bugzilla, "standard allocator crashes when deallocating segment + * "of zero length", http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14176 + * C++ Standard Library Defect Report List (Revision 28), issue 199 + * "What does allocate(0) return?", + * http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#199 + */ + +template > +struct auto_space:private noncopyable +{ + typedef typename boost::detail::allocator::rebind_to< + Allocator,T + >::type::pointer pointer; + + explicit auto_space(const Allocator& al=Allocator(),std::size_t n=1): + al_(al),n_(n),data_(n_?al_.allocate(n_):pointer(0)) + {} + + ~auto_space() + { + if(n_)al_.deallocate(data_,n_); + } + + Allocator get_allocator()const{return al_;} + + pointer data()const{return data_;} + + void swap(auto_space& x) + { + if(al_!=x.al_)adl_swap(al_,x.al_); + std::swap(n_,x.n_); + std::swap(data_,x.data_); + } + +private: + typename boost::detail::allocator::rebind_to< + Allocator,T>::type al_; + std::size_t n_; + pointer data_; +}; + +template +void swap(auto_space& x,auto_space& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp b/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp new file mode 100644 index 0000000..8c9b62b --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp @@ -0,0 +1,74 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_BASE_TYPE_HPP +#define BOOST_MULTI_INDEX_DETAIL_BASE_TYPE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* MPL machinery to construct a linear hierarchy of indices out of + * a index list. + */ + +struct index_applier +{ + template + struct apply + { + typedef typename IndexSpecifierMeta::type index_specifier; + typedef typename index_specifier:: + BOOST_NESTED_TEMPLATE index_class::type type; + }; +}; + +template +struct nth_layer +{ + BOOST_STATIC_CONSTANT(int,length=mpl::size::value); + + typedef typename mpl::eval_if_c< + N==length, + mpl::identity >, + mpl::apply2< + index_applier, + mpl::at_c, + nth_layer + > + >::type type; +}; + +template +struct multi_index_base_type:nth_layer<0,Value,IndexSpecifierList,Allocator> +{ + BOOST_STATIC_ASSERT(detail::is_index_list::value); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp b/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp new file mode 100644 index 0000000..9bb0470 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp @@ -0,0 +1,113 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_BIDIR_NODE_ITERATOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_BIDIR_NODE_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Iterator class for node-based indices with bidirectional + * iterators (ordered and sequenced indices.) + */ + +template +class bidir_node_iterator: + public bidirectional_iterator_helper< + bidir_node_iterator, + typename Node::value_type, + std::ptrdiff_t, + const typename Node::value_type*, + const typename Node::value_type&> +{ +public: + bidir_node_iterator(){} + explicit bidir_node_iterator(Node* node_):node(node_){} + + const typename Node::value_type& operator*()const + { + return node->value(); + } + + bidir_node_iterator& operator++() + { + Node::increment(node); + return *this; + } + + bidir_node_iterator& operator--() + { + Node::decrement(node); + return *this; + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* Serialization. As for why the following is public, + * see explanation in safe_mode_iterator notes in safe_mode.hpp. + */ + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + typedef typename Node::base_type node_base_type; + + template + void save(Archive& ar,const unsigned int)const + { + node_base_type* bnode=node; + ar< + void load(Archive& ar,const unsigned int) + { + node_base_type* bnode; + ar>>serialization::make_nvp("pointer",bnode); + node=static_cast(bnode); + } +#endif + + /* get_node is not to be used by the user */ + + typedef Node node_type; + + Node* get_node()const{return node;} + +private: + Node* node; +}; + +template +bool operator==( + const bidir_node_iterator& x, + const bidir_node_iterator& y) +{ + return x.get_node()==y.get_node(); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/bucket_array.hpp b/3rdParty/Boost/src/boost/multi_index/detail/bucket_array.hpp new file mode 100644 index 0000000..f688ba1 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/bucket_array.hpp @@ -0,0 +1,242 @@ +/* Copyright 2003-2014 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_BUCKET_ARRAY_HPP +#define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* bucket structure for use by hashed indices */ + +#define BOOST_MULTI_INDEX_BA_SIZES_32BIT \ +(53ul)(97ul)(193ul)(389ul)(769ul) \ +(1543ul)(3079ul)(6151ul)(12289ul)(24593ul) \ +(49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ +(1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ +(50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ +(1610612741ul)(3221225473ul) + +#if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */ +#define BOOST_MULTI_INDEX_BA_SIZES \ +BOOST_MULTI_INDEX_BA_SIZES_32BIT \ +(4294967291ul) +#else + /* obtained with aid from + * http://javaboutique.internet.com/prime_numb/ + * http://www.rsok.com/~jrm/next_ten_primes.html + * and verified with + * http://www.alpertron.com.ar/ECM.HTM + */ + +#define BOOST_MULTI_INDEX_BA_SIZES \ +BOOST_MULTI_INDEX_BA_SIZES_32BIT \ +(6442450939ul)(12884901893ul)(25769803751ul)(51539607551ul) \ +(103079215111ul)(206158430209ul)(412316860441ul)(824633720831ul) \ +(1649267441651ul)(3298534883309ul)(6597069766657ul)(13194139533299ul) \ +(26388279066623ul)(52776558133303ul)(105553116266489ul)(211106232532969ul) \ +(422212465066001ul)(844424930131963ul)(1688849860263953ul) \ +(3377699720527861ul)(6755399441055731ul)(13510798882111483ul) \ +(27021597764222939ul)(54043195528445957ul)(108086391056891903ul) \ +(216172782113783843ul)(432345564227567621ul)(864691128455135207ul) \ +(1729382256910270481ul)(3458764513820540933ul)(6917529027641081903ul) \ +(13835058055282163729ul)(18446744073709551557ul) +#endif + +template /* templatized to have in-header static var defs */ +class bucket_array_base:private noncopyable +{ +protected: + static const std::size_t sizes[]; + + static std::size_t size_index(std::size_t n) + { + const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n); + if(bound==sizes+sizes_length)--bound; + return bound-sizes; + } + +#define BOOST_MULTI_INDEX_BA_POSITION_CASE(z,n,_) \ + case n:return hash%BOOST_PP_SEQ_ELEM(n,BOOST_MULTI_INDEX_BA_SIZES); + + static std::size_t position(std::size_t hash,std::size_t size_index_) + { + /* Accelerate hash%sizes[size_index_] by replacing with a switch on + * hash%Ci expressions, each Ci a compile-time constant, which the + * compiler can implement without using integer division. + */ + + switch(size_index_){ + default: /* never used */ + BOOST_PP_REPEAT( + BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES), + BOOST_MULTI_INDEX_BA_POSITION_CASE,~) + } + } + +private: + static const std::size_t sizes_length; +}; + +template +const std::size_t bucket_array_base<_>::sizes[]={ + BOOST_PP_SEQ_ENUM(BOOST_MULTI_INDEX_BA_SIZES) +}; + +template +const std::size_t bucket_array_base<_>::sizes_length= + sizeof(bucket_array_base<_>::sizes)/ + sizeof(bucket_array_base<_>::sizes[0]); + +#undef BOOST_MULTI_INDEX_BA_POSITION_CASE +#undef BOOST_MULTI_INDEX_BA_SIZES +#undef BOOST_MULTI_INDEX_BA_SIZES_32BIT + +template +class bucket_array:bucket_array_base<> +{ + typedef bucket_array_base<> super; + typedef hashed_index_base_node_impl< + typename boost::detail::allocator::rebind_to< + Allocator, + char + >::type + > base_node_impl_type; + +public: + typedef typename base_node_impl_type::base_pointer base_pointer; + typedef typename base_node_impl_type::pointer pointer; + + bucket_array(const Allocator& al,pointer end_,std::size_t size_): + size_index_(super::size_index(size_)), + spc(al,super::sizes[size_index_]+1) + { + clear(end_); + } + + std::size_t size()const + { + return super::sizes[size_index_]; + } + + std::size_t position(std::size_t hash)const + { + return super::position(hash,size_index_); + } + + base_pointer begin()const{return buckets();} + base_pointer end()const{return buckets()+size();} + base_pointer at(std::size_t n)const{return buckets()+n;} + + void clear(pointer end_) + { + for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0); + end()->prior()=end_->prior()=end_; + end_->next()=end(); + } + + void swap(bucket_array& x) + { + std::swap(size_index_,x.size_index_); + spc.swap(x.spc); + } + +private: + std::size_t size_index_; + auto_space spc; + + base_pointer buckets()const + { + return spc.data(); + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + friend class boost::serialization::access; + + /* bucket_arrays do not emit any kind of serialization info. They are + * fed to Boost.Serialization as hashed index iterators need to track + * them during serialization. + */ + + template + void serialize(Archive&,const unsigned int) + { + } +#endif +}; + +template +void swap(bucket_array& x,bucket_array& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +/* bucket_arrays never get constructed directly by Boost.Serialization, + * as archives are always fed pointers to previously existent + * arrays. So, if this is called it means we are dealing with a + * somehow invalid archive. + */ + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +namespace serialization{ +#else +namespace multi_index{ +namespace detail{ +#endif + +template +inline void load_construct_data( + Archive&,boost::multi_index::detail::bucket_array*, + const unsigned int) +{ + throw_exception( + archive::archive_exception(archive::archive_exception::other_exception)); +} + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +} /* namespace serialization */ +#else +} /* namespace multi_index::detail */ +} /* namespace multi_index */ +#endif + +#endif + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp b/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp new file mode 100644 index 0000000..3e04a3e --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp @@ -0,0 +1,52 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_CONVERTER_HPP +#define BOOST_MULTI_INDEX_DETAIL_CONVERTER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* converter offers means to access indices of a given multi_index_container + * and for convertibilty between index iterators, so providing a + * localized access point for get() and project() functions. + */ + +template +struct converter +{ + static const Index& index(const MultiIndexContainer& x){return x;} + static Index& index(MultiIndexContainer& x){return x;} + + static typename Index::const_iterator const_iterator( + const MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + { + return x.Index::make_iterator(node); + } + + static typename Index::iterator iterator( + MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + { + return x.Index::make_iterator(node); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp b/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp new file mode 100644 index 0000000..a0b6cad --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp @@ -0,0 +1,137 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP +#define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* copy_map is used as an auxiliary structure during copy_() operations. + * When a container with n nodes is replicated, node_map holds the pairings + * between original and copied nodes, and provides a fast way to find a + * copied node from an original one. + * The semantics of the class are not simple, and no attempt has been made + * to enforce it: multi_index_container handles it right. On the other hand, + * the const interface, which is the one provided to index implementations, + * only allows for: + * - Enumeration of pairs of (original,copied) nodes (excluding the headers), + * - fast retrieval of copied nodes (including the headers.) + */ + +template +struct copy_map_entry +{ + copy_map_entry(Node* f,Node* s):first(f),second(s){} + + Node* first; + Node* second; + + bool operator<(const copy_map_entry& x)const + { + return std::less()(first,x.first); + } +}; + +template +class copy_map:private noncopyable +{ +public: + typedef const copy_map_entry* const_iterator; + + copy_map( + const Allocator& al,std::size_t 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) + {} + + ~copy_map() + { + if(!released){ + for(std::size_t i=0;isecond->value()); + deallocate((spc.data()+i)->second); + } + } + } + + const_iterator begin()const{return &*spc.data();} + const_iterator end()const{return &*(spc.data()+n);} + + void clone(Node* node) + { + (spc.data()+n)->first=node; + (spc.data()+n)->second=&*al_.allocate(1); + BOOST_TRY{ + boost::detail::allocator::construct( + &(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(&*spc.data(),&*spc.data()+size_); + } + + Node* find(Node* node)const + { + if(node==header_org_)return header_cpy_; + return std::lower_bound( + begin(),end(),copy_map_entry(node,0))->second; + } + + void release() + { + released=true; + } + +private: + typedef typename boost::detail::allocator::rebind_to< + Allocator,Node + >::type allocator_type; + typedef typename allocator_type::pointer allocator_pointer; + + allocator_type al_; + std::size_t size_; + auto_space,Allocator> spc; + std::size_t n; + Node* header_org_; + Node* header_cpy_; + bool released; + + void deallocate(Node* node) + { + al_.deallocate(static_cast(node),1); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/do_not_copy_elements_tag.hpp b/3rdParty/Boost/src/boost/multi_index/detail/do_not_copy_elements_tag.hpp new file mode 100644 index 0000000..f0fa730 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/do_not_copy_elements_tag.hpp @@ -0,0 +1,34 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_DO_NOT_COPY_ELEMENTS_TAG_HPP +#define BOOST_MULTI_INDEX_DETAIL_DO_NOT_COPY_ELEMENTS_TAG_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Used to mark a special ctor variant that copies the internal objects of + * a container but not its elements. + */ + +struct do_not_copy_elements_tag{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp b/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp new file mode 100644 index 0000000..217b611 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp @@ -0,0 +1,42 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_HAS_TAG_HPP +#define BOOST_MULTI_INDEX_DETAIL_HAS_TAG_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* determines whether an index type has a given tag in its tag list */ + +template +struct has_tag +{ + template + struct apply:mpl::contains + { + }; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/hash_index_args.hpp b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_args.hpp new file mode 100644 index 0000000..81902f5 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_args.hpp @@ -0,0 +1,105 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_ARGS_HPP +#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_ARGS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Hashed index specifiers can be instantiated in two forms: + * + * (hashed_unique|hashed_non_unique)< + * KeyFromValue, + * Hash=boost::hash, + * Pred=std::equal_to > + * (hashed_unique|hashed_non_unique)< + * TagList, + * KeyFromValue, + * Hash=boost::hash, + * Pred=std::equal_to > + * + * hashed_index_args implements the machinery to accept this + * argument-dependent polymorphism. + */ + +template +struct index_args_default_hash +{ + typedef ::boost::hash type; +}; + +template +struct index_args_default_pred +{ + typedef std::equal_to type; +}; + +template +struct hashed_index_args +{ + typedef is_tag full_form; + + typedef typename mpl::if_< + full_form, + Arg1, + tag< > >::type tag_list_type; + typedef typename mpl::if_< + full_form, + Arg2, + Arg1>::type key_from_value_type; + typedef typename mpl::if_< + full_form, + Arg3, + Arg2>::type supplied_hash_type; + typedef typename mpl::eval_if< + mpl::is_na, + index_args_default_hash, + mpl::identity + >::type hash_type; + typedef typename mpl::if_< + full_form, + Arg4, + Arg3>::type supplied_pred_type; + typedef typename mpl::eval_if< + mpl::is_na, + index_args_default_pred, + mpl::identity + >::type pred_type; + + BOOST_STATIC_ASSERT(is_tag::value); + BOOST_STATIC_ASSERT(!mpl::is_na::value); + BOOST_STATIC_ASSERT(!mpl::is_na::value); + BOOST_STATIC_ASSERT(!mpl::is_na::value); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/hash_index_iterator.hpp b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_iterator.hpp new file mode 100644 index 0000000..f8e983d --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_iterator.hpp @@ -0,0 +1,165 @@ +/* Copyright 2003-2014 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_HASH_INDEX_ITERATOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Iterator class for hashed indices. + */ + +struct hashed_index_global_iterator_tag{}; +struct hashed_index_local_iterator_tag{}; + +template +class hashed_index_iterator: + public forward_iterator_helper< + hashed_index_iterator, + typename Node::value_type, + std::ptrdiff_t, + const typename Node::value_type*, + const typename Node::value_type&> +{ +public: + hashed_index_iterator(){} + hashed_index_iterator(Node* node_):node(node_){} + + const typename Node::value_type& operator*()const + { + return node->value(); + } + + hashed_index_iterator& operator++() + { + this->increment(Category()); + return *this; + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* Serialization. As for why the following is public, + * see explanation in safe_mode_iterator notes in safe_mode.hpp. + */ + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + typedef typename Node::base_type node_base_type; + + template + void save(Archive& ar,const unsigned int)const + { + node_base_type* bnode=node; + ar< + void load(Archive& ar,const unsigned int version) + { + load(ar,version,Category()); + } + + template + void load( + Archive& ar,const unsigned int version,hashed_index_global_iterator_tag) + { + node_base_type* bnode; + ar>>serialization::make_nvp("pointer",bnode); + node=static_cast(bnode); + if(version<1){ + BucketArray* throw_away; /* consume unused ptr */ + ar>>serialization::make_nvp("pointer",throw_away); + } + } + + template + void load( + Archive& ar,const unsigned int version,hashed_index_local_iterator_tag) + { + node_base_type* bnode; + ar>>serialization::make_nvp("pointer",bnode); + node=static_cast(bnode); + if(version<1){ + BucketArray* buckets; + ar>>serialization::make_nvp("pointer",buckets); + if(buckets&&node&&node->impl()==buckets->end()->prior()){ + /* end local_iterators used to point to end node, now they are null */ + node=0; + } + } + } +#endif + + /* get_node is not to be used by the user */ + + typedef Node node_type; + + Node* get_node()const{return node;} + +private: + + void increment(hashed_index_global_iterator_tag) + { + Node::increment(node); + } + + void increment(hashed_index_local_iterator_tag) + { + Node::increment_local(node); + } + + Node* node; +}; + +template +bool operator==( + const hashed_index_iterator& x, + const hashed_index_iterator& y) +{ + return x.get_node()==y.get_node(); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +/* class version = 1 : hashed_index_iterator does no longer serialize a bucket + * array pointer. + */ + +namespace serialization { +template +struct version< + boost::multi_index::detail::hashed_index_iterator +> +{ + BOOST_STATIC_CONSTANT(int,value=1); +}; +} /* namespace serialization */ +#endif + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/hash_index_node.hpp b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_node.hpp new file mode 100644 index 0000000..cfc60f6 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/hash_index_node.hpp @@ -0,0 +1,770 @@ +/* Copyright 2003-2014 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_HASH_INDEX_NODE_HPP +#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Certain C++ requirements on unordered associative containers (see LWG issue + * #579) imply a data structure where nodes are linked in a single list, which + * in its turn forces implementors to add additional overhed per node to + * associate each with its corresponding bucket. Others resort to storing hash + * values, we use an alternative structure providing unconditional O(1) + * manipulation, even in situations of unfair hash distribution, plus some + * lookup speedups. For unique indices we maintain a doubly linked list of + * nodes except that if N is the first node of a bucket its associated + * bucket node is embedded between N and the preceding node in the following + * manner: + * + * +---+ +---+ +---+ +---+ + * <--+ |<--+ | <--+ |<--+ | + * ... | B0| | B1| ... | B1| | B2| ... + * | |-+ | +--> | |-+ | +--> + * +-+-+ | +---+ +-+-+ | +---+ + * | ^ | ^ + * | | | | + * | +-+ | +-+ + * | | | | + * v | v | + * --+---+---+---+-- --+---+---+---+-- + * ... | | B1| | ... | | B2| | ... + * --+---+---+---+-- --+---+---+---+-- + * + * + * The fist and last nodes of buckets can be checked with + * + * first node of a bucket: Npn != N + * last node of a bucket: Nnp != N + * + * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers + * only). Pure insert and erase (without lookup) can be unconditionally done + * in O(1). + * For non-unique indices we add the following additional complexity: when + * there is a group of 3 or more equivalent elements, they are linked as + * follows: + * + * +-----------------------+ + * | v + * +---+ | +---+ +---+ +---+ + * | | +-+ | | |<--+ | + * | F | | S | ... | P | | L | + * | +-->| | | +-+ | | + * +---+ +---+ +---+ | +---+ + * ^ | + * +-----------------------+ + * + * F, S, P and L are the first, second, penultimate and last node in the + * group, respectively (S and P can coincide if the group has size 3.) This + * arrangement is used to skip equivalent elements in O(1) when doing lookup, + * while preserving O(1) insert/erase. The following invariants identify + * special positions (some of the operations have to be carefully implemented + * as Xnn is not valid if Xn points to a bucket): + * + * first node of a bucket: Npnp == N + * last node of a bucket: Nnpp == N + * first node of a group: Nnp != N && Nnppn == N + * second node of a group: Npn != N && Nppnn == N + * n-1 node of a group: Nnp != N && Nnnpp == N + * last node of a group: Npn != N && Npnnp == N + * + * The memory overhead is one pointer per bucket plus two pointers per node, + * probably unbeatable. The resulting structure is bidirectonally traversable, + * though currently we are just providing forward iteration. + */ + +template +struct hashed_index_node_impl; + +/* half-header (only prior() pointer) to use for the bucket array */ + +template +struct hashed_index_base_node_impl +{ + typedef typename + boost::detail::allocator::rebind_to< + Allocator,hashed_index_base_node_impl + >::type::pointer base_pointer; + typedef typename + boost::detail::allocator::rebind_to< + Allocator,hashed_index_base_node_impl + >::type::const_pointer const_base_pointer; + typedef typename + boost::detail::allocator::rebind_to< + Allocator, + hashed_index_node_impl + >::type::pointer pointer; + typedef typename + boost::detail::allocator::rebind_to< + Allocator, + hashed_index_node_impl + >::type::const_pointer const_pointer; + + pointer& prior(){return prior_;} + pointer prior()const{return prior_;} + +private: + pointer prior_; +}; + +/* full header (prior() and next()) for the nodes */ + +template +struct hashed_index_node_impl:hashed_index_base_node_impl +{ +private: + typedef hashed_index_base_node_impl super; + +public: + typedef typename super::base_pointer base_pointer; + typedef typename super::const_base_pointer const_base_pointer; + typedef typename super::pointer pointer; + typedef typename super::const_pointer const_pointer; + + base_pointer& next(){return next_;} + base_pointer next()const{return next_;} + + static pointer pointer_from(base_pointer x) + { + return static_cast(static_cast(&*x)); + } + + static base_pointer base_pointer_from(pointer x) + { + return static_cast(&*x); + } + +private: + base_pointer next_; +}; + +/* Boost.MultiIndex requires machinery to reverse unlink operations. A simple + * way to make a pointer-manipulation function undoable is to templatize + * its internal pointer assignments with a functor that, besides doing the + * assignment, keeps track of the original pointer values and can later undo + * the operations in reverse order. + */ + +struct default_assigner +{ + template void operator()(T& x,const T& val){x=val;} +}; + +template +struct unlink_undo_assigner +{ + typedef typename Node::base_pointer base_pointer; + typedef typename Node::pointer pointer; + + unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){} + + void operator()(pointer& x,pointer val) + { + pointer_tracks[pointer_track_count].x=&x; + pointer_tracks[pointer_track_count++].val=x; + x=val; + } + + void operator()(base_pointer& x,base_pointer val) + { + base_pointer_tracks[base_pointer_track_count].x=&x; + base_pointer_tracks[base_pointer_track_count++].val=x; + x=val; + } + + void operator()() /* undo op */ + { + /* in the absence of aliasing, restitution order is immaterial */ + + while(pointer_track_count--){ + *(pointer_tracks[pointer_track_count].x)= + pointer_tracks[pointer_track_count].val; + } + while(base_pointer_track_count--){ + *(base_pointer_tracks[base_pointer_track_count].x)= + base_pointer_tracks[base_pointer_track_count].val; + } + } + + struct pointer_track {pointer* x; pointer val;}; + struct base_pointer_track{base_pointer* x; base_pointer val;}; + + /* We know the maximum number of pointer and base pointer assignments that + * the two unlink versions do, so we can statically reserve the needed + * storage. + */ + + pointer_track pointer_tracks[3]; + int pointer_track_count; + base_pointer_track base_pointer_tracks[2]; + int base_pointer_track_count; +}; + +/* algorithmic stuff for unique and non-unique variants */ + +struct hashed_unique_tag{}; +struct hashed_non_unique_tag{}; + +template +struct hashed_index_node_alg; + +template +struct hashed_index_node_alg +{ + typedef typename Node::base_pointer base_pointer; + typedef typename Node::const_base_pointer const_base_pointer; + typedef typename Node::pointer pointer; + typedef typename Node::const_pointer const_pointer; + + static bool is_first_of_bucket(pointer x) + { + return x->prior()->next()!=base_pointer_from(x); + } + + static pointer after(pointer x) + { + return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next()); + } + + static pointer after_local(pointer x) + { + return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); + } + + static pointer next_to_inspect(pointer x) + { + return is_last_of_bucket(x)?pointer(0):pointer_from(x->next()); + } + + static void link(pointer x,base_pointer buc,pointer end) + { + if(buc->prior()==pointer(0)){ /* empty bucket */ + x->prior()=end->prior(); + x->next()=end->prior()->next(); + x->prior()->next()=buc; + buc->prior()=x; + end->prior()=x; + } + else{ + x->prior()=buc->prior()->prior(); + x->next()=base_pointer_from(buc->prior()); + buc->prior()=x; + x->next()->prior()=x; + } + } + + static void unlink(pointer x) + { + default_assigner assign; + unlink(x,assign); + } + + typedef unlink_undo_assigner unlink_undo; + + template + static void unlink(pointer x,Assigner& assign) + { + if(is_first_of_bucket(x)){ + if(is_last_of_bucket(x)){ + assign(x->prior()->next()->prior(),pointer(0)); + assign(x->prior()->next(),x->next()); + assign(x->next()->prior()->prior(),x->prior()); + } + else{ + assign(x->prior()->next()->prior(),pointer_from(x->next())); + assign(x->next()->prior(),x->prior()); + } + } + else if(is_last_of_bucket(x)){ + assign(x->prior()->next(),x->next()); + assign(x->next()->prior()->prior(),x->prior()); + } + else{ + assign(x->prior()->next(),x->next()); + assign(x->next()->prior(),x->prior()); + } + } + + /* used only at rehashing */ + + static void append(pointer x,pointer end) + { + x->prior()=end->prior(); + x->next()=end->prior()->next(); + x->prior()->next()=base_pointer_from(x); + end->prior()=x; + } + + static bool unlink_last(pointer end) + { + /* returns true iff bucket is emptied */ + + pointer x=end->prior(); + if(x->prior()->next()==base_pointer_from(x)){ + x->prior()->next()=x->next(); + end->prior()=x->prior(); + return false; + } + else{ + x->prior()->next()->prior()=pointer(0); + x->prior()->next()=x->next(); + end->prior()=x->prior(); + return true; + } + } + +private: + static pointer pointer_from(base_pointer x) + { + return Node::pointer_from(x); + } + + static base_pointer base_pointer_from(pointer x) + { + return Node::base_pointer_from(x); + } + + static bool is_last_of_bucket(pointer x) + { + return x->next()->prior()!=x; + } +}; + +template +struct hashed_index_node_alg +{ + typedef typename Node::base_pointer base_pointer; + typedef typename Node::const_base_pointer const_base_pointer; + typedef typename Node::pointer pointer; + typedef typename Node::const_pointer const_pointer; + + static bool is_first_of_bucket(pointer x) + { + return x->prior()->next()->prior()==x; + } + + static bool is_first_of_group(pointer x) + { + return + x->next()->prior()!=x&& + x->next()->prior()->prior()->next()==base_pointer_from(x); + } + + static pointer after(pointer x) + { + if(x->next()->prior()==x)return pointer_from(x->next()); + if(x->next()->prior()->prior()==x)return x->next()->prior(); + if(x->next()->prior()->prior()->next()==base_pointer_from(x)) + return pointer_from(x->next()); + return pointer_from(x->next())->next()->prior(); + } + + static pointer after_local(pointer x) + { + if(x->next()->prior()==x)return pointer_from(x->next()); + if(x->next()->prior()->prior()==x)return pointer(0); + if(x->next()->prior()->prior()->next()==base_pointer_from(x)) + return pointer_from(x->next()); + return pointer_from(x->next())->next()->prior(); + } + + static pointer next_to_inspect(pointer x) + { + if(x->next()->prior()==x)return pointer_from(x->next()); + if(x->next()->prior()->prior()==x)return pointer(0); + if(x->next()->prior()->next()->prior()!=x->next()->prior()) + return pointer(0); + return pointer_from(x->next()->prior()->next()); + } + + static void link(pointer x,base_pointer buc,pointer end) + { + if(buc->prior()==pointer(0)){ /* empty bucket */ + x->prior()=end->prior(); + x->next()=end->prior()->next(); + x->prior()->next()=buc; + buc->prior()=x; + end->prior()=x; + } + else{ + x->prior()=buc->prior()->prior(); + x->next()=base_pointer_from(buc->prior()); + buc->prior()=x; + x->next()->prior()=x; + } + }; + + static void link(pointer x,pointer first,pointer last) + { + x->prior()=first->prior(); + x->next()=base_pointer_from(first); + if(is_first_of_bucket(first)){ + x->prior()->next()->prior()=x; + } + else{ + x->prior()->next()=base_pointer_from(x); + } + + if(first==last){ + last->prior()=x; + } + else if(first->next()==base_pointer_from(last)){ + first->prior()=last; + first->next()=base_pointer_from(x); + } + else{ + pointer second=pointer_from(first->next()), + lastbutone=last->prior(); + second->prior()=first; + first->prior()=last; + lastbutone->next()=base_pointer_from(x); + } + } + + static void unlink(pointer x) + { + default_assigner assign; + unlink(x,assign); + } + + typedef unlink_undo_assigner unlink_undo; + + template + static void unlink(pointer x,Assigner& assign) + { + if(x->prior()->next()==base_pointer_from(x)){ + if(x->next()->prior()==x){ + left_unlink(x,assign); + right_unlink(x,assign); + } + else if(x->next()->prior()->prior()==x){ /* last of bucket */ + left_unlink(x,assign); + right_unlink_last_of_bucket(x,assign); + } + else if(x->next()->prior()->prior()->next()== + base_pointer_from(x)){ /* first of group size */ + left_unlink(x,assign); + right_unlink_first_of_group(x,assign); + } + else{ /* n-1 of group */ + unlink_last_but_one_of_group(x,assign); + } + } + else if(x->prior()->next()->prior()==x){ /* first of bucket */ + if(x->next()->prior()==x){ + left_unlink_first_of_bucket(x,assign); + right_unlink(x,assign); + } + else if(x->next()->prior()->prior()==x){ /* last of bucket */ + assign(x->prior()->next()->prior(),pointer(0)); + assign(x->prior()->next(),x->next()); + assign(x->next()->prior()->prior(),x->prior()); + } + else{ /* first of group */ + left_unlink_first_of_bucket(x,assign); + right_unlink_first_of_group(x,assign); + } + } + else if(x->next()->prior()->prior()==x){ /* last of group and bucket */ + left_unlink_last_of_group(x,assign); + right_unlink_last_of_bucket(x,assign); + } + else if(pointer_from(x->prior()->prior()->next()) + ->next()==base_pointer_from(x)){ /* second of group */ + unlink_second_of_group(x,assign); + } + else{ /* last of group, ~(last of bucket) */ + left_unlink_last_of_group(x,assign); + right_unlink(x,assign); + } + } + + /* used only at rehashing */ + + static void link_range( + pointer first,pointer last,base_pointer buc,pointer cend) + { + if(buc->prior()==pointer(0)){ /* empty bucket */ + first->prior()=cend->prior(); + last->next()=cend->prior()->next(); + first->prior()->next()=buc; + buc->prior()=first; + cend->prior()=last; + } + else{ + first->prior()=buc->prior()->prior(); + last->next()=base_pointer_from(buc->prior()); + buc->prior()=first; + last->next()->prior()=last; + } + } + + static void append_range(pointer first,pointer last,pointer cend) + { + first->prior()=cend->prior(); + last->next()=cend->prior()->next(); + first->prior()->next()=base_pointer_from(first); + cend->prior()=last; + } + + static std::pair unlink_last_group(pointer end) + { + /* returns first of group true iff bucket is emptied */ + + pointer x=end->prior(); + if(x->prior()->next()==base_pointer_from(x)){ + x->prior()->next()=x->next(); + end->prior()=x->prior(); + return std::make_pair(x,false); + } + else if(x->prior()->next()->prior()==x){ + x->prior()->next()->prior()=pointer(0); + x->prior()->next()=x->next(); + end->prior()=x->prior(); + return std::make_pair(x,true); + } + else{ + pointer y=pointer_from(x->prior()->next()); + + if(y->prior()->next()==base_pointer_from(y)){ + y->prior()->next()=x->next(); + end->prior()=y->prior(); + return std::make_pair(y,false); + } + else{ + y->prior()->next()->prior()=pointer(0); + y->prior()->next()=x->next(); + end->prior()=y->prior(); + return std::make_pair(y,true); + } + } + } + + static void unlink_range(pointer first,pointer last) + { + if(is_first_of_bucket(first)){ + if(is_last_of_bucket(last)){ + first->prior()->next()->prior()=pointer(0); + first->prior()->next()=last->next(); + last->next()->prior()->prior()=first->prior(); + } + else{ + first->prior()->next()->prior()=pointer_from(last->next()); + last->next()->prior()=first->prior(); + } + } + else if(is_last_of_bucket(last)){ + first->prior()->next()=last->next(); + last->next()->prior()->prior()=first->prior(); + } + else{ + first->prior()->next()=last->next(); + last->next()->prior()=first->prior(); + } + } + +private: + static pointer pointer_from(base_pointer x) + { + return Node::pointer_from(x); + } + + static base_pointer base_pointer_from(pointer x) + { + return Node::base_pointer_from(x); + } + + static bool is_last_of_bucket(pointer x) + { + return x->next()->prior()->prior()==x; + } + + template + static void left_unlink(pointer x,Assigner& assign) + { + assign(x->prior()->next(),x->next()); + } + + template + static void right_unlink(pointer x,Assigner& assign) + { + assign(x->next()->prior(),x->prior()); + } + + template + static void left_unlink_first_of_bucket(pointer x,Assigner& assign) + { + assign(x->prior()->next()->prior(),pointer_from(x->next())); + } + + template + static void right_unlink_last_of_bucket(pointer x,Assigner& assign) + { + assign(x->next()->prior()->prior(),x->prior()); + } + + template + static void right_unlink_first_of_group(pointer x,Assigner& assign) + { + pointer second=pointer_from(x->next()), + last=second->prior(), + lastbutone=last->prior(); + if(second==lastbutone){ + assign(second->next(),base_pointer_from(last)); + assign(second->prior(),x->prior()); + } + else{ + assign(lastbutone->next(),base_pointer_from(second)); + assign(second->next()->prior(),last); + assign(second->prior(),x->prior()); + } + } + + template + static void left_unlink_last_of_group(pointer x,Assigner& assign) + { + pointer lastbutone=x->prior(), + first=pointer_from(lastbutone->next()), + second=pointer_from(first->next()); + if(lastbutone==second){ + assign(lastbutone->prior(),first); + assign(lastbutone->next(),x->next()); + } + else{ + assign(second->prior(),lastbutone); + assign(lastbutone->prior()->next(),base_pointer_from(first)); + assign(lastbutone->next(),x->next()); + } + } + + template + static void unlink_last_but_one_of_group(pointer x,Assigner& assign) + { + pointer first=pointer_from(x->next()), + second=pointer_from(first->next()), + last=second->prior(); + if(second==x){ + assign(last->prior(),first); + assign(first->next(),base_pointer_from(last)); + } + else{ + assign(last->prior(),x->prior()); + assign(x->prior()->next(),base_pointer_from(first)); + } + } + + template + static void unlink_second_of_group(pointer x,Assigner& assign) + { + pointer last=x->prior(), + lastbutone=last->prior(), + first=pointer_from(lastbutone->next()); + if(lastbutone==x){ + assign(first->next(),base_pointer_from(last)); + assign(last->prior(),first); + } + else{ + assign(first->next(),x->next()); + assign(x->next()->prior(),last); + } + } +}; + +template +struct hashed_index_node_trampoline: + hashed_index_node_impl< + typename boost::detail::allocator::rebind_to< + 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_type; +}; + +template +struct hashed_index_node: + Super,hashed_index_node_trampoline +{ +private: + typedef hashed_index_node_trampoline trampoline; + +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; + + impl_pointer& prior(){return trampoline::prior();} + impl_pointer prior()const{return trampoline::prior();} + impl_base_pointer& next(){return trampoline::next();} + impl_base_pointer next()const{return trampoline::next();} + + impl_pointer impl() + { + return static_cast( + static_cast(static_cast(this))); + } + + const_impl_pointer impl()const + { + return static_cast( + static_cast(static_cast(this))); + } + + static hashed_index_node* from_impl(impl_pointer x) + { + return static_cast( + static_cast(&*x)); + } + + static const hashed_index_node* from_impl(const_impl_pointer x) + { + return static_cast( + static_cast(&*x)); + } + + /* interoperability with hashed_index_iterator */ + + static void increment(hashed_index_node*& x) + { + x=from_impl(node_alg::after(x->impl())); + } + + static void increment_local(hashed_index_node*& x) + { + x=from_impl(node_alg::after_local(x->impl())); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp b/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp new file mode 100644 index 0000000..ca8a9b2 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp @@ -0,0 +1,50 @@ +/* Copyright 2003-2008 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_HEADER_HOLDER_HPP +#define BOOST_MULTI_INDEX_DETAIL_HEADER_HOLDER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* A utility class used to hold a pointer to the header node. + * The base from member idiom is used because index classes, which are + * superclasses of multi_index_container, need this header in construction + * time. The allocation is made by the allocator of the multi_index_container + * class --hence, this allocator needs also be stored resorting + * to the base from member trick. + */ + +template +struct header_holder:private noncopyable +{ + header_holder():member(final().allocate_node()){} + ~header_holder(){final().deallocate_node(&*member);} + + NodeTypePtr member; + +private: + Final& final(){return *static_cast(this);} +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp new file mode 100644 index 0000000..99000ed --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp @@ -0,0 +1,293 @@ +/* Copyright 2003-2014 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_BASE_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_BASE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* The role of this class is threefold: + * - tops the linear hierarchy of indices. + * - terminates some cascading backbone function calls (insert_, etc.), + * - grants access to the backbone functions of the final + * multi_index_container class (for access restriction reasons, these + * cannot be called directly from the index classes.) + */ + +struct lvalue_tag{}; +struct rvalue_tag{}; +struct emplaced_tag{}; + +template +class index_base +{ +protected: + typedef index_node_base 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 + >::type final_allocator_type; + typedef mpl::vector0<> index_type_list; + typedef mpl::vector0<> iterator_type_list; + typedef mpl::vector0<> const_iterator_type_list; + typedef copy_map< + final_node_type, + final_allocator_type> copy_map_type; + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + typedef index_saver< + node_type, + final_allocator_type> index_saver_type; + typedef index_loader< + node_type, + final_node_type, + final_allocator_type> index_loader_type; +#endif + +private: + typedef Value value_type; + +protected: + explicit index_base(const ctor_args_list&,const Allocator&){} + + index_base( + const index_base&, + do_not_copy_elements_tag) + {} + + void copy_( + const index_base&,const copy_map_type&) + {} + + final_node_type* insert_(const value_type& v,final_node_type*& x,lvalue_tag) + { + x=final().allocate_node(); + BOOST_TRY{ + boost::detail::allocator::construct(&x->value(),v); + } + BOOST_CATCH(...){ + final().deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + return x; + } + + final_node_type* insert_(const value_type& v,final_node_type*& x,rvalue_tag) + { + x=final().allocate_node(); + BOOST_TRY{ + /* This shoud have used a modified, T&&-compatible version of + * boost::detail::allocator::construct, but + * 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 (&x->value()) value_type(boost::move(const_cast(v))); + } + BOOST_CATCH(...){ + final().deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + return x; + } + + final_node_type* insert_(const value_type&,final_node_type*& x,emplaced_tag) + { + return x; + } + + final_node_type* insert_( + const value_type& v,node_type*,final_node_type*& x,lvalue_tag) + { + return insert_(v,x,lvalue_tag()); + } + + final_node_type* insert_( + const value_type& v,node_type*,final_node_type*& x,rvalue_tag) + { + return insert_(v,x,rvalue_tag()); + } + + final_node_type* insert_( + const value_type&,node_type*,final_node_type*& x,emplaced_tag) + { + return x; + } + + void erase_(node_type* x) + { + boost::detail::allocator::destroy(&x->value()); + } + + void delete_node_(node_type* x) + { + boost::detail::allocator::destroy(&x->value()); + } + + void clear_(){} + + void swap_(index_base&){} + + void swap_elements_(index_base&){} + + bool replace_(const value_type& v,node_type* x,lvalue_tag) + { + x->value()=v; + return true; + } + + bool replace_(const value_type& v,node_type* x,rvalue_tag) + { + x->value()=boost::move(const_cast(v)); + return true; + } + + bool modify_(node_type*){return true;} + + bool modify_rollback_(node_type*){return true;} + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* serialization */ + + template + void save_(Archive&,const unsigned int,const index_saver_type&)const{} + + template + void load_(Archive&,const unsigned int,const index_loader_type&){} +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + /* invariant stuff */ + + bool invariant_()const{return true;} +#endif + + /* access to backbone memfuns of Final class */ + + final_type& final(){return *static_cast(this);} + const final_type& final()const{return *static_cast(this);} + + 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_();} + + std::pair final_insert_(const value_type& x) + {return final().insert_(x);} + std::pair final_insert_rv_(const value_type& x) + {return final().insert_rv_(x);} + template + std::pair final_insert_ref_(const T& t) + {return final().insert_ref_(t);} + template + std::pair final_insert_ref_(T& t) + {return final().insert_ref_(t);} + + template + std::pair final_emplace_( + BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + return final().emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + + std::pair final_insert_( + const value_type& x,final_node_type* position) + {return final().insert_(x,position);} + std::pair final_insert_rv_( + const value_type& x,final_node_type* position) + {return final().insert_rv_(x,position);} + template + std::pair final_insert_ref_( + const T& t,final_node_type* position) + {return final().insert_ref_(t,position);} + template + std::pair final_insert_ref_( + T& t,final_node_type* position) + {return final().insert_ref_(t,position);} + + template + std::pair final_emplace_hint_( + final_node_type* position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + return final().emplace_hint_( + position,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + + 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_();} + + void final_swap_(final_type& x){final().swap_(x);} + + bool final_replace_( + const value_type& k,final_node_type* x) + {return final().replace_(k,x);} + bool final_replace_rv_( + const value_type& k,final_node_type* x) + {return final().replace_rv_(k,x);} + + template + bool final_modify_(Modifier& mod,final_node_type* x) + {return final().modify_(mod,x);} + + template + bool final_modify_(Modifier& mod,Rollback& back,final_node_type* x) + {return final().modify_(mod,back,x);} + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + void final_check_invariant_()const{final().check_invariant_();} +#endif +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp new file mode 100644 index 0000000..3f0428c --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp @@ -0,0 +1,138 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_LOADER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_LOADER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Counterpart of index_saver (check index_saver.hpp for serialization + * details.)* multi_index_container is in charge of supplying the info about + * the base sequence, and each index can subsequently load itself using the + * const interface of index_loader. + */ + +template +class index_loader:private noncopyable +{ +public: + index_loader(const Allocator& al,std::size_t size): + spc(al,size),size_(size),n(0),sorted(false) + { + } + + template + void add(Node* node,Archive& ar,const unsigned int) + { + ar>>serialization::make_nvp("position",*node); + entries()[n++]=node; + } + + template + void add_track(Node* node,Archive& ar,const unsigned int) + { + ar>>serialization::make_nvp("position",*node); + } + + /* A rearranger is passed two nodes, and is expected to + * reposition the second after the first. + * If the first node is 0, then the second should be moved + * to the beginning of the sequence. + */ + + template + void load(Rearranger r,Archive& ar,const unsigned int)const + { + FinalNode* prev=unchecked_load_node(ar); + if(!prev)return; + + if(!sorted){ + std::sort(entries(),entries()+size_); + sorted=true; + } + + check_node(prev); + + for(;;){ + for(;;){ + FinalNode* node=load_node(ar); + if(!node)break; + + if(node==prev)prev=0; + r(prev,node); + + prev=node; + } + prev=load_node(ar); + if(!prev)break; + } + } + +private: + Node** entries()const{return &*spc.data();} + + /* We try to delay sorting as much as possible just in case it + * is not necessary, hence this version of load_node. + */ + + template + FinalNode* unchecked_load_node(Archive& ar)const + { + Node* node=0; + ar>>serialization::make_nvp("pointer",node); + return static_cast(node); + } + + template + FinalNode* load_node(Archive& ar)const + { + Node* node=0; + ar>>serialization::make_nvp("pointer",node); + check_node(node); + return static_cast(node); + } + + void check_node(Node* node)const + { + if(node!=0&&!std::binary_search(entries(),entries()+size_,node)){ + throw_exception( + archive::archive_exception( + archive::archive_exception::other_exception)); + } + } + + auto_space spc; + std::size_t size_; + std::size_t n; + mutable bool sorted; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp new file mode 100644 index 0000000..f3675ac --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp @@ -0,0 +1,248 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_matcher compares a sequence of elements against a + * base sequence, identifying those elements that belong to the + * longest subsequence which is ordered with respect to the base. + * For instance, if the base sequence is: + * + * 0 1 2 3 4 5 6 7 8 9 + * + * and the compared sequence (not necesarilly the same length): + * + * 1 4 2 3 0 7 8 9 + * + * the elements of the longest ordered subsequence are: + * + * 1 2 3 7 8 9 + * + * The algorithm for obtaining such a subsequence is called + * Patience Sorting, described in ch. 1 of: + * Aldous, D., Diaconis, P.: "Longest increasing subsequences: from + * patience sorting to the Baik-Deift-Johansson Theorem", Bulletin + * of the American Mathematical Society, vol. 36, no 4, pp. 413-432, + * July 1999. + * http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/ + * S0273-0979-99-00796-X.pdf + * + * This implementation is not fully generic since it assumes that + * the sequences given are pointed to by index iterators (having a + * get_node() memfun.) + */ + +namespace index_matcher{ + +/* The algorithm stores the nodes of the base sequence and a number + * of "piles" that are dynamically updated during the calculation + * stage. From a logical point of view, nodes form an independent + * sequence from piles. They are stored together so as to minimize + * allocated memory. + */ + +struct entry +{ + entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){} + + /* node stuff */ + + void* node; + std::size_t pos; + entry* previous; + bool ordered; + + struct less_by_node + { + bool operator()( + const entry& x,const entry& y)const + { + return std::less()(x.node,y.node); + } + }; + + /* pile stuff */ + + std::size_t pile_top; + entry* pile_top_entry; + + struct less_by_pile_top + { + bool operator()( + const entry& x,const entry& y)const + { + return x.pile_top +class algorithm_base:private noncopyable +{ +protected: + algorithm_base(const Allocator& al,std::size_t size): + spc(al,size),size_(size),n_(0),sorted(false) + { + } + + void add(void* node) + { + entries()[n_]=entry(node,n_); + ++n_; + } + + void begin_algorithm()const + { + if(!sorted){ + std::sort(entries(),entries()+size_,entry::less_by_node()); + sorted=true; + } + num_piles=0; + } + + void add_node_to_algorithm(void* node)const + { + entry* ent= + std::lower_bound( + entries(),entries()+size_, + entry(node),entry::less_by_node()); /* localize entry */ + ent->ordered=false; + std::size_t n=ent->pos; /* get its position */ + + entry dummy(0); + dummy.pile_top=n; + + entry* pile_ent= /* find the first available pile */ + std::lower_bound( /* to stack the entry */ + entries(),entries()+num_piles, + dummy,entry::less_by_pile_top()); + + pile_ent->pile_top=n; /* stack the entry */ + pile_ent->pile_top_entry=ent; + + /* if not the first pile, link entry to top of the preceding pile */ + if(pile_ent>&entries()[0]){ + ent->previous=(pile_ent-1)->pile_top_entry; + } + + if(pile_ent==&entries()[num_piles]){ /* new pile? */ + ++num_piles; + } + } + + void finish_algorithm()const + { + if(num_piles>0){ + /* Mark those elements which are in their correct position, i.e. those + * belonging to the longest increasing subsequence. These are those + * elements linked from the top of the last pile. + */ + + entry* ent=entries()[num_piles-1].pile_top_entry; + for(std::size_t n=num_piles;n--;){ + ent->ordered=true; + ent=ent->previous; + } + } + } + + bool is_ordered(void * node)const + { + return std::lower_bound( + entries(),entries()+size_, + entry(node),entry::less_by_node())->ordered; + } + +private: + entry* entries()const{return &*spc.data();} + + auto_space spc; + std::size_t size_; + std::size_t n_; + mutable bool sorted; + mutable std::size_t num_piles; +}; + +/* The algorithm has three phases: + * - Initialization, during which the nodes of the base sequence are added. + * - Execution. + * - Results querying, through the is_ordered memfun. + */ + +template +class algorithm:private algorithm_base +{ + typedef algorithm_base super; + +public: + algorithm(const Allocator& al,std::size_t size):super(al,size){} + + void add(Node* node) + { + super::add(node); + } + + template + void execute(IndexIterator first,IndexIterator last)const + { + super::begin_algorithm(); + + for(IndexIterator it=first;it!=last;++it){ + add_node_to_algorithm(get_node(it)); + } + + super::finish_algorithm(); + } + + bool is_ordered(Node* node)const + { + return super::is_ordered(node); + } + +private: + void add_node_to_algorithm(Node* node)const + { + super::add_node_to_algorithm(node); + } + + template + static Node* get_node(IndexIterator it) + { + return static_cast(it.get_node()); + } +}; + +} /* namespace multi_index::detail::index_matcher */ + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp new file mode 100644 index 0000000..150eb75 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp @@ -0,0 +1,133 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_NODE_BASE_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_NODE_BASE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_node_base tops the node hierarchy of multi_index_container. It holds + * the value of the element contained. + */ + +template +struct pod_value_holder +{ + typename aligned_storage< + sizeof(Value), + alignment_of::value + >::type space; +}; + +template +struct index_node_base:private pod_value_holder +{ + typedef index_node_base base_type; /* used for serialization purposes */ + typedef Value value_type; + typedef Allocator allocator_type; + + value_type& value() + { + return *static_cast( + static_cast(&this->space)); + } + + const value_type& value()const + { + return *static_cast( + static_cast(&this->space)); + } + + static index_node_base* from_value(const value_type* p) + { + return static_cast( + reinterpret_cast*>( /* std 9.2.17 */ + const_cast(p))); + } + +private: +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + friend class boost::serialization::access; + + /* nodes do not emit any kind of serialization info. They are + * fed to Boost.Serialization so that pointers to nodes are + * tracked correctly. + */ + + template + void serialize(Archive&,const unsigned int) + { + } +#endif +}; + +template +Node* node_from_value(const Value* p) +{ + typedef typename Node::allocator_type allocator_type; + return static_cast( + index_node_base::from_value(p)); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +/* Index nodes never get constructed directly by Boost.Serialization, + * as archives are always fed pointers to previously existent + * nodes. So, if this is called it means we are dealing with a + * somehow invalid archive. + */ + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +namespace serialization{ +#else +namespace multi_index{ +namespace detail{ +#endif + +template +inline void load_construct_data( + Archive&,boost::multi_index::detail::index_node_base*, + const unsigned int) +{ + throw_exception( + archive::archive_exception(archive::archive_exception::other_exception)); +} + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +} /* namespace serialization */ +#else +} /* namespace multi_index::detail */ +} /* namespace multi_index */ +#endif + +#endif + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp new file mode 100644 index 0000000..ae09d4e --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp @@ -0,0 +1,135 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_saver accepts a base sequence of previously saved elements + * and saves a possibly reordered subsequence in an efficient manner, + * serializing only the information needed to rearrange the subsequence + * based on the original order of the base. + * multi_index_container is in charge of supplying the info about the + * base sequence, and each index can subsequently save itself using the + * const interface of index_saver. + */ + +template +class index_saver:private noncopyable +{ +public: + index_saver(const Allocator& al,std::size_t size):alg(al,size){} + + template + void add(Node* node,Archive& ar,const unsigned int) + { + ar< + void add_track(Node* node,Archive& ar,const unsigned int) + { + ar< + void save( + IndexIterator first,IndexIterator last,Archive& ar, + const unsigned int)const + { + /* calculate ordered positions */ + + alg.execute(first,last); + + /* Given a consecutive subsequence of displaced elements + * x1,...,xn, the following information is serialized: + * + * p0,p1,...,pn,0 + * + * where pi is a pointer to xi and p0 is a pointer to the element + * preceding x1. Crealy, from this information is possible to + * restore the original order on loading time. If x1 is the first + * element in the sequence, the following is serialized instead: + * + * p1,p1,...,pn,0 + * + * For each subsequence of n elements, n+2 pointers are serialized. + * An optimization policy is applied: consider for instance the + * sequence + * + * a,B,c,D + * + * where B and D are displaced, but c is in its correct position. + * Applying the schema described above we would serialize 6 pointers: + * + * p(a),p(B),0 + * p(c),p(D),0 + * + * but this can be reduced to 5 pointers by treating c as a displaced + * element: + * + * p(a),p(B),p(c),p(D),0 + */ + + std::size_t last_saved=3; /* distance to last pointer saved */ + for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){ + if(!alg.is_ordered(get_node(it))){ + if(last_saved>1)save_node(get_node(prev),ar); + save_node(get_node(it),ar); + last_saved=0; + } + else if(last_saved==2)save_node(null_node(),ar); + } + if(last_saved<=2)save_node(null_node(),ar); + + /* marks the end of the serialization info for [first,last) */ + + save_node(null_node(),ar); + } + +private: + template + static Node* get_node(IndexIterator it) + { + return it.get_node(); + } + + static Node* null_node(){return 0;} + + template + static void save_node(Node* node,Archive& ar) + { + ar< alg; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp b/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp new file mode 100644 index 0000000..c6c547c --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp @@ -0,0 +1,21 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INVARIANT_ASSERT_HPP +#define BOOST_MULTI_INDEX_DETAIL_INVARIANT_ASSERT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#if !defined(BOOST_MULTI_INDEX_INVARIANT_ASSERT) +#include +#define BOOST_MULTI_INDEX_INVARIANT_ASSERT BOOST_ASSERT +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp b/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp new file mode 100644 index 0000000..f6a2421 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp @@ -0,0 +1,40 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_IS_INDEX_LIST_HPP +#define BOOST_MULTI_INDEX_DETAIL_IS_INDEX_LIST_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template +struct is_index_list +{ + BOOST_STATIC_CONSTANT(bool,mpl_sequence=mpl::is_sequence::value); + BOOST_STATIC_CONSTANT(bool,non_empty=!mpl::empty::value); + BOOST_STATIC_CONSTANT(bool,value=mpl_sequence&&non_empty); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp b/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp new file mode 100644 index 0000000..7a03235 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp @@ -0,0 +1,321 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ITER_ADAPTOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_ITER_ADAPTOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Poor man's version of boost::iterator_adaptor. Used instead of the + * original as compile times for the latter are significantly higher. + * The interface is not replicated exactly, only to the extent necessary + * for internal consumption. + */ + +/* NB. The purpose of the (non-inclass) global operators ==, < and - defined + * above is to partially alleviate a problem of MSVC++ 6.0 by * which + * friend-injected operators on T are not visible if T is instantiated only + * in template code where T is a dependent type. + */ + +class iter_adaptor_access +{ +public: + template + static typename Class::reference dereference(const Class& x) + { + return x.dereference(); + } + + template + static bool equal(const Class& x,const Class& y) + { + return x.equal(y); + } + + template + static void increment(Class& x) + { + x.increment(); + } + + template + static void decrement(Class& x) + { + x.decrement(); + } + + template + static void advance(Class& x,typename Class::difference_type n) + { + x.advance(n); + } + + template + static typename Class::difference_type distance_to( + const Class& x,const Class& y) + { + return x.distance_to(y); + } +}; + +template +struct iter_adaptor_selector; + +template +class forward_iter_adaptor_base: + public forward_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + +private: + Derived& final(){return *static_cast(this);} + const Derived& final()const{return *static_cast(this);} +}; + +template +bool operator==( + const forward_iter_adaptor_base& x, + const forward_iter_adaptor_base& y) +{ + return iter_adaptor_access::equal( + static_cast(x),static_cast(y)); +} + +template<> +struct iter_adaptor_selector +{ + template + struct apply + { + typedef forward_iter_adaptor_base type; + }; +}; + +template +class bidirectional_iter_adaptor_base: + public bidirectional_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + + Derived& operator--() + { + iter_adaptor_access::decrement(final()); + return final(); + } + +private: + Derived& final(){return *static_cast(this);} + const Derived& final()const{return *static_cast(this);} +}; + +template +bool operator==( + const bidirectional_iter_adaptor_base& x, + const bidirectional_iter_adaptor_base& y) +{ + return iter_adaptor_access::equal( + static_cast(x),static_cast(y)); +} + +template<> +struct iter_adaptor_selector +{ + template + struct apply + { + typedef bidirectional_iter_adaptor_base type; + }; +}; + +template +class random_access_iter_adaptor_base: + public random_access_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + typedef typename Base::difference_type difference_type; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + friend bool operator<(const Derived& x,const Derived& y) + { + return iter_adaptor_access::distance_to(x,y)>0; + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + + Derived& operator--() + { + iter_adaptor_access::decrement(final()); + return final(); + } + + Derived& operator+=(difference_type n) + { + iter_adaptor_access::advance(final(),n); + return final(); + } + + Derived& operator-=(difference_type n) + { + iter_adaptor_access::advance(final(),-n); + return final(); + } + + friend difference_type operator-(const Derived& x,const Derived& y) + { + return iter_adaptor_access::distance_to(y,x); + } + +private: + Derived& final(){return *static_cast(this);} + const Derived& final()const{return *static_cast(this);} +}; + +template +bool operator==( + const random_access_iter_adaptor_base& x, + const random_access_iter_adaptor_base& y) +{ + return iter_adaptor_access::equal( + static_cast(x),static_cast(y)); +} + +template +bool operator<( + const random_access_iter_adaptor_base& x, + const random_access_iter_adaptor_base& y) +{ + return iter_adaptor_access::distance_to( + static_cast(x),static_cast(y))>0; +} + +template +typename random_access_iter_adaptor_base::difference_type +operator-( + const random_access_iter_adaptor_base& x, + const random_access_iter_adaptor_base& y) +{ + return iter_adaptor_access::distance_to( + static_cast(y),static_cast(x)); +} + +template<> +struct iter_adaptor_selector +{ + template + struct apply + { + typedef random_access_iter_adaptor_base type; + }; +}; + +template +struct iter_adaptor_base +{ + typedef iter_adaptor_selector< + typename Base::iterator_category> selector; + typedef typename mpl::apply2< + selector,Derived,Base>::type type; +}; + +template +class iter_adaptor:public iter_adaptor_base::type +{ +protected: + iter_adaptor(){} + explicit iter_adaptor(const Base& b_):b(b_){} + + const Base& base_reference()const{return b;} + Base& base_reference(){return b;} + +private: + Base b; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp b/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp new file mode 100644 index 0000000..6df89b1 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp @@ -0,0 +1,49 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_MODIFY_KEY_ADAPTOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_MODIFY_KEY_ADAPTOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Functional adaptor to resolve modify_key as a call to modify. + * Preferred over compose_f_gx and stuff cause it eliminates problems + * with references to references, dealing with function pointers, etc. + */ + +template +struct modify_key_adaptor +{ + + modify_key_adaptor(Fun f_,KeyFromValue kfv_):f(f_),kfv(kfv_){} + + void operator()(Value& x) + { + f(kfv(x)); + } + +private: + Fun f; + KeyFromValue kfv; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp b/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp new file mode 100644 index 0000000..ba216ed --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp @@ -0,0 +1,97 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_NO_DUPLICATE_TAGS_HPP +#define BOOST_MULTI_INDEX_DETAIL_NO_DUPLICATE_TAGS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* no_duplicate_tags check at compile-time that a tag list + * has no duplicate tags. + * The algorithm deserves some explanation: tags + * are sequentially inserted into a mpl::set if they were + * not already present. Due to the magic of mpl::set + * (mpl::has_key is contant time), this operation takes linear + * time, and even MSVC++ 6.5 handles it gracefully (other obvious + * solutions are quadratic.) + */ + +struct duplicate_tag_mark{}; + +struct duplicate_tag_marker +{ + template + struct apply + { + typedef mpl::s_item< + typename mpl::if_,duplicate_tag_mark,Tag>::type, + MplSet + > type; + }; +}; + +template +struct no_duplicate_tags +{ + typedef typename mpl::fold< + TagList, + mpl::set0<>, + duplicate_tag_marker + >::type aux; + + BOOST_STATIC_CONSTANT( + bool,value=!(mpl::has_key::value)); +}; + +/* Variant for an index list: duplication is checked + * across all the indices. + */ + +struct duplicate_tag_list_marker +{ + template + struct apply:mpl::fold< + BOOST_DEDUCED_TYPENAME Index::tag_list, + MplSet, + duplicate_tag_marker> + { + }; +}; + +template +struct no_duplicate_tags_in_index_list +{ + typedef typename mpl::fold< + IndexList, + mpl::set0<>, + duplicate_tag_list_marker + >::type aux; + + BOOST_STATIC_CONSTANT( + bool,value=!(mpl::has_key::value)); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp b/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp new file mode 100644 index 0000000..7fe85cf --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp @@ -0,0 +1,66 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_NODE_TYPE_HPP +#define BOOST_MULTI_INDEX_DETAIL_NODE_TYPE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* MPL machinery to construct the internal node type associated to an + * index list. + */ + +struct index_node_applier +{ + template + struct apply + { + typedef typename mpl::deref::type index_specifier; + typedef typename index_specifier:: + BOOST_NESTED_TEMPLATE node_class::type type; + }; +}; + +template +struct multi_index_node_type +{ + BOOST_STATIC_ASSERT(detail::is_index_list::value); + + typedef typename mpl::reverse_iter_fold< + IndexSpecifierList, + index_node_base, + mpl::bind2 + >::type type; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp new file mode 100644 index 0000000..3e2641f --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp @@ -0,0 +1,83 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_ARGS_HPP +#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_ARGS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Oredered index specifiers can be instantiated in two forms: + * + * (ordered_unique|ordered_non_unique)< + * KeyFromValue,Compare=std::less > + * (ordered_unique|ordered_non_unique)< + * TagList,KeyFromValue,Compare=std::less > + * + * index_args implements the machinery to accept this argument-dependent + * polymorphism. + */ + +template +struct index_args_default_compare +{ + typedef std::less type; +}; + +template +struct ordered_index_args +{ + typedef is_tag full_form; + + typedef typename mpl::if_< + full_form, + Arg1, + tag< > >::type tag_list_type; + typedef typename mpl::if_< + full_form, + Arg2, + Arg1>::type key_from_value_type; + typedef typename mpl::if_< + full_form, + Arg3, + Arg2>::type supplied_compare_type; + typedef typename mpl::eval_if< + mpl::is_na, + index_args_default_compare, + mpl::identity + >::type compare_type; + + BOOST_STATIC_ASSERT(is_tag::value); + BOOST_STATIC_ASSERT(!mpl::is_na::value); + BOOST_STATIC_ASSERT(!mpl::is_na::value); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp b/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp new file mode 100644 index 0000000..905270e --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp @@ -0,0 +1,588 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP +#define BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +/* 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, and their corresponding iterators + * are wrapped with safe_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. + * Iterators are chained in a single attached list, whose header is + * kept by the container. More elaborate data structures would yield better + * performance, but I decided to keep complexity to a minimum since + * speed is not an issue here. + * Safe mode iterators automatically check that only proper operations + * are performed on them: for instance, an invalid iterator cannot be + * dereferenced. Additionally, a set of utilty macros and functions are + * provided that serve to implement preconditions and cooperate with + * the framework within the container. + * Iterators can also be unchecked, i.e. they do not have info about + * which container they belong in. This situation arises when the iterator + * is restored from a serialization archive: only information on the node + * is available, and it is not possible to determine to which container + * the iterator is associated to. The only sensible policy is to assume + * unchecked iterators are valid, though this can certainly generate false + * positive safe mode checks. + * This is not a full-fledged safe mode framework, and is only intended + * for use within the limits of Boost.MultiIndex. + */ + +/* Assertion macros. These resolve to no-ops if + * !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE). + */ + +#if !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) +#undef BOOST_MULTI_INDEX_SAFE_MODE_ASSERT +#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) ((void)0) +#else +#if !defined(BOOST_MULTI_INDEX_SAFE_MODE_ASSERT) +#include +#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) BOOST_ASSERT(expr) +#endif +#endif + +#define BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_valid_iterator(it), \ + safe_mode::invalid_iterator); + +#define BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_dereferenceable_iterator(it), \ + safe_mode::not_dereferenceable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_incrementable_iterator(it), \ + safe_mode::not_incrementable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_decrementable_iterator(it), \ + safe_mode::not_decrementable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,cont) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_is_owner(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), \ + safe_mode::not_same_owner); + +#define BOOST_MULTI_INDEX_CHECK_VALID_RANGE(it0,it1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_valid_range(it0,it1), \ + safe_mode::invalid_range); + +#define BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(it,it0,it1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_outside_range(it,it0,it1), \ + safe_mode::inside_range); + +#define BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(it,n) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_in_bounds(it,n), \ + safe_mode::out_of_bounds); + +#define BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(cont0,cont1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_different_container(cont0,cont1), \ + safe_mode::same_container); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#endif + +#if defined(BOOST_HAS_THREADS) +#include +#endif + +namespace boost{ + +namespace multi_index{ + +namespace safe_mode{ + +/* Checking routines. Assume the best for unchecked iterators + * (i.e. they pass the checking when there is not enough info + * to know.) + */ + +template +inline bool check_valid_iterator(const Iterator& it) +{ + return it.valid()||it.unchecked(); +} + +template +inline bool check_dereferenceable_iterator(const Iterator& it) +{ + return (it.valid()&&it!=it.owner()->end())||it.unchecked(); +} + +template +inline bool check_incrementable_iterator(const Iterator& it) +{ + return (it.valid()&&it!=it.owner()->end())||it.unchecked(); +} + +template +inline bool check_decrementable_iterator(const Iterator& it) +{ + return (it.valid()&&it!=it.owner()->begin())||it.unchecked(); +} + +template +inline bool check_is_owner( + const Iterator& it,const typename Iterator::container_type& cont) +{ + return (it.valid()&&it.owner()==&cont)||it.unchecked(); +} + +template +inline bool check_same_owner(const Iterator& it0,const Iterator& it1) +{ + return (it0.valid()&&it1.valid()&&it0.owner()==it1.owner())|| + it0.unchecked()||it1.unchecked(); +} + +template +inline bool check_valid_range(const Iterator& it0,const Iterator& it1) +{ + if(!check_same_owner(it0,it1))return false; + + if(it0.valid()){ + Iterator last=it0.owner()->end(); + if(it1==last)return true; + + for(Iterator first=it0;first!=last;++first){ + if(first==it1)return true; + } + return false; + } + return true; +} + +template +inline bool check_outside_range( + const Iterator& it,const Iterator& it0,const Iterator& it1) +{ + if(!check_same_owner(it0,it1))return false; + + if(it0.valid()){ + Iterator last=it0.owner()->end(); + bool found=false; + + Iterator first=it0; + for(;first!=last;++first){ + if(first==it1)break; + + /* crucial that this check goes after previous break */ + + if(first==it)found=true; + } + if(first!=it1)return false; + return !found; + } + return true; +} + +template +inline bool check_in_bounds(const Iterator& it,Difference n) +{ + if(it.unchecked())return true; + if(!it.valid()) return false; + if(n>0) return it.owner()->end()-it>=n; + else return it.owner()->begin()-it<=n; +} + +template +inline bool check_different_container( + const Container& cont0,const Container& cont1) +{ + 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 +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(&it.cont->header); + (next_=static_cast(prev_->next))!=0;){ + if(next_!=&it&&*next_==it){ + prev_->next=next_->next; + next_->cont=0; + } + else prev_=next_; + } + } + it.detach(); + } +} + +template class safe_container; /* fwd decl. */ + +} /* namespace multi_index::safe_mode */ + +namespace detail{ + +class safe_container_base; /* fwd decl. */ + +class safe_iterator_base +{ +public: + bool valid()const{return cont!=0;} + bool unchecked()const{return unchecked_;} + + inline void detach(); + + void uncheck() + { + detach(); + unchecked_=true; + } + +protected: + safe_iterator_base():cont(0),next(0),unchecked_(false){} + + explicit safe_iterator_base(safe_container_base* cont_): + unchecked_(false) + { + attach(cont_); + } + + safe_iterator_base(const safe_iterator_base& it): + unchecked_(it.unchecked_) + { + attach(it.cont); + } + + safe_iterator_base& operator=(const safe_iterator_base& it) + { + unchecked_=it.unchecked_; + safe_container_base* new_cont=it.cont; + if(cont!=new_cont){ + detach(); + attach(new_cont); + } + return *this; + } + + ~safe_iterator_base() + { + detach(); + } + + 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 friend class safe_mode::safe_container; + template friend + void safe_mode::detach_equivalent_iterators(Iterator&); +#endif + + inline void attach(safe_container_base* cont_); + + safe_container_base* cont; + safe_iterator_base* next; + bool unchecked_; +}; + +class safe_container_base:private noncopyable +{ +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 friend + void safe_mode::detach_equivalent_iterators(Iterator&); +#endif + + ~safe_container_base() + { + /* Detaches all remaining iterators, which by now will + * be those pointing to the end of the container. + */ + + for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0; + header.next=0; + } + + void swap(safe_container_base& x) + { + for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x; + for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this; + std::swap(header.cont,x.header.cont); + std::swap(header.next,x.header.next); + } + + safe_iterator_base header; + +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex mutex; +#endif +}; + +void safe_iterator_base::attach(safe_container_base* cont_) +{ + cont=cont_; + if(cont){ +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); +#endif + + next=cont->header.next; + cont->header.next=this; + } +} + +void safe_iterator_base::detach() +{ + if(cont){ +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); +#endif + + safe_iterator_base *prev_,*next_; + for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){} + prev_->next=next; + cont=0; + } +} + +} /* namespace multi_index::detail */ + +namespace safe_mode{ + +/* In order to enable safe mode on a container: + * - The container must derive from safe_container, + * - iterators must be generated via safe_iterator, which adapts a + * preexistent unsafe iterator class. + */ + +template +class safe_container; + +template +class safe_iterator: + public detail::iter_adaptor,Iterator>, + public detail::safe_iterator_base +{ + typedef detail::iter_adaptor super; + typedef 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* cont_): + safe_super(cont_){} + template + safe_iterator(const T0& t0,safe_container* cont_): + super(Iterator(t0)),safe_super(cont_){} + template + safe_iterator( + const T0& t0,const T1& t1,safe_container* cont_): + super(Iterator(t0,t1)),safe_super(cont_){} + + safe_iterator& operator=(const safe_iterator& x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + this->base_reference()=x.base_reference(); + safe_super::operator=(x); + return *this; + } + + const container_type* owner()const + { + return + static_cast( + static_cast*>( + this->safe_super::owner())); + } + + /* get_node is not to be used by the user */ + + typedef typename Iterator::node_type node_type; + + node_type* get_node()const{return this->base_reference().get_node();} + +private: + friend class boost::multi_index::detail::iter_adaptor_access; + + reference dereference()const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this); + return *(this->base_reference()); + } + + bool equal(const safe_iterator& x)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); + return this->base_reference()==x.base_reference(); + } + + void increment() + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this); + ++(this->base_reference()); + } + + void decrement() + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this); + --(this->base_reference()); + } + + void advance(difference_type n) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n); + this->base_reference()+=n; + } + + difference_type distance_to(const safe_iterator& x)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); + return x.base_reference()-this->base_reference(); + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* Serialization. Note that Iterator::save and Iterator:load + * are assumed to be defined and public: at first sight it seems + * like we could have resorted to the public serialization interface + * for doing the forwarding to the adapted iterator class: + * ar<>base_reference(); + * but this would cause incompatibilities if a saving + * program is in safe mode and the loading program is not, or + * viceversa --in safe mode, the archived iterator data is one layer + * deeper, this is especially relevant with XML archives. + * It'd be nice if Boost.Serialization provided some forwarding + * facility for use by adaptor classes. + */ + + friend class boost::serialization::access; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + template + void save(Archive& ar,const unsigned int version)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + this->base_reference().save(ar,version); + } + + template + void load(Archive& ar,const unsigned int version) + { + this->base_reference().load(ar,version); + safe_super::uncheck(); + } +#endif +}; + +template +class safe_container:public detail::safe_container_base +{ + typedef detail::safe_container_base super; + +public: + void detach_dereferenceable_iterators() + { + typedef typename Container::iterator iterator; + + iterator end_=static_cast(this)->end(); + iterator *prev_,*next_; + for( + prev_=static_cast(&this->header); + (next_=static_cast(prev_->next))!=0;){ + if(*next_!=end_){ + prev_->next=next_->next; + next_->cont=0; + } + else prev_=next_; + } + } + + void swap(safe_container& x) + { + super::swap(x); + } +}; + +} /* namespace multi_index::safe_mode */ + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +namespace serialization{ +template +struct version< + boost::multi_index::safe_mode::safe_iterator +> +{ + BOOST_STATIC_CONSTANT( + int,value=boost::serialization::version::value); +}; +} /* namespace serialization */ +#endif + +} /* namespace boost */ + +#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp new file mode 100644 index 0000000..5cb4676 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp @@ -0,0 +1,212 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP +#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* doubly-linked node for use by sequenced_index */ + +template +struct sequenced_index_node_impl +{ + typedef typename + boost::detail::allocator::rebind_to< + Allocator,sequenced_index_node_impl + >::type::pointer pointer; + typedef typename + boost::detail::allocator::rebind_to< + Allocator,sequenced_index_node_impl + >::type::const_pointer const_pointer; + + pointer& prior(){return prior_;} + pointer prior()const{return prior_;} + pointer& next(){return next_;} + pointer next()const{return next_;} + + /* interoperability with bidir_node_iterator */ + + static void increment(pointer& x){x=x->next();} + static void decrement(pointer& x){x=x->prior();} + + /* algorithmic stuff */ + + static void link(pointer x,pointer header) + { + x->prior()=header->prior(); + x->next()=header; + x->prior()->next()=x->next()->prior()=x; + }; + + static void unlink(pointer x) + { + x->prior()->next()=x->next(); + x->next()->prior()=x->prior(); + } + + static void relink(pointer position,pointer x) + { + unlink(x); + x->prior()=position->prior(); + x->next()=position; + x->prior()->next()=x->next()->prior()=x; + } + + static void relink(pointer position,pointer x,pointer y) + { + /* position is assumed not to be in [x,y) */ + + if(x!=y){ + pointer z=y->prior(); + x->prior()->next()=y; + y->prior()=x->prior(); + x->prior()=position->prior(); + z->next()=position; + x->prior()->next()=x; + z->next()->prior()=z; + } + } + + static void reverse(pointer header) + { + pointer x=header; + do{ + pointer y=x->next(); + std::swap(x->prior(),x->next()); + x=y; + }while(x!=header); + } + + static void swap(pointer x,pointer y) + { + /* This swap function does not exchange the header nodes, + * but rather their pointers. This is *not* used for implementing + * sequenced_index::swap. + */ + + if(x->next()!=x){ + if(y->next()!=y){ + std::swap(x->next(),y->next()); + std::swap(x->prior(),y->prior()); + x->next()->prior()=x->prior()->next()=x; + y->next()->prior()=y->prior()->next()=y; + } + else{ + y->next()=x->next(); + y->prior()=x->prior(); + x->next()=x->prior()=x; + y->next()->prior()=y->prior()->next()=y; + } + } + else if(y->next()!=y){ + x->next()=y->next(); + x->prior()=y->prior(); + y->next()=y->prior()=y; + x->next()->prior()=x->prior()->next()=x; + } + } + +private: + pointer prior_; + pointer next_; +}; + +template +struct sequenced_index_node_trampoline: + sequenced_index_node_impl< + typename boost::detail::allocator::rebind_to< + typename Super::allocator_type, + char + >::type + > +{ + typedef sequenced_index_node_impl< + typename boost::detail::allocator::rebind_to< + typename Super::allocator_type, + char + >::type + > impl_type; +}; + +template +struct sequenced_index_node:Super,sequenced_index_node_trampoline +{ +private: + typedef sequenced_index_node_trampoline trampoline; + +public: + typedef typename trampoline::impl_type impl_type; + typedef typename trampoline::pointer impl_pointer; + typedef typename trampoline::const_pointer const_impl_pointer; + + impl_pointer& prior(){return trampoline::prior();} + impl_pointer prior()const{return trampoline::prior();} + impl_pointer& next(){return trampoline::next();} + impl_pointer next()const{return trampoline::next();} + + impl_pointer impl() + { + return static_cast( + static_cast(static_cast(this))); + } + + const_impl_pointer impl()const + { + return static_cast( + static_cast(static_cast(this))); + } + + static sequenced_index_node* from_impl(impl_pointer x) + { + return static_cast( + static_cast(&*x)); + } + + static const sequenced_index_node* from_impl(const_impl_pointer x) + { + return static_cast( + static_cast(&*x)); + } + + /* interoperability with bidir_node_iterator */ + + static void increment(sequenced_index_node*& x) + { + impl_pointer xi=x->impl(); + trampoline::increment(xi); + x=from_impl(xi); + } + + static void decrement(sequenced_index_node*& x) + { + impl_pointer xi=x->impl(); + trampoline::decrement(xi); + x=from_impl(xi); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp new file mode 100644 index 0000000..56da408 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp @@ -0,0 +1,199 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP +#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Common code for sequenced_index memfuns having templatized and + * non-templatized versions. + */ + +template +void sequenced_index_remove(SequencedIndex& x,Predicate pred) +{ + typedef typename SequencedIndex::iterator iterator; + iterator first=x.begin(),last=x.end(); + while(first!=last){ + if(pred(*first))x.erase(first++); + else ++first; + } +} + +template +void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred) +{ + typedef typename SequencedIndex::iterator iterator; + iterator first=x.begin(); + iterator last=x.end(); + if(first!=last){ + for(iterator middle=first;++middle!=last;middle=first){ + if(binary_pred(*middle,*first))x.erase(middle); + else first=middle; + } + } +} + +template +void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp) +{ + typedef typename SequencedIndex::iterator iterator; + if(&x!=&y){ + iterator first0=x.begin(),last0=x.end(); + iterator first1=y.begin(),last1=y.end(); + while(first0!=last0&&first1!=last1){ + if(comp(*first1,*first0))x.splice(first0,y,first1++); + else ++first0; + } + x.splice(last0,y,first1,last1); + } +} + +/* sorting */ + +/* auxiliary stuff */ + +template +void sequenced_index_collate( + BOOST_DEDUCED_TYPENAME Node::impl_type* x, + BOOST_DEDUCED_TYPENAME Node::impl_type* y, + Compare comp) +{ + typedef typename Node::impl_type impl_type; + typedef typename Node::impl_pointer impl_pointer; + + impl_pointer first0=x->next(); + impl_pointer last0=x; + impl_pointer first1=y->next(); + impl_pointer last1=y; + while(first0!=last0&&first1!=last1){ + if(comp( + Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){ + impl_pointer tmp=first1->next(); + impl_type::relink(first0,first1); + first1=tmp; + } + else first0=first0->next(); + } + impl_type::relink(last0,first1,last1); +} + +/* Some versions of CGG require a bogus typename in counter_spc + * inside sequenced_index_sort if the following is defined + * also inside sequenced_index_sort. + */ + +BOOST_STATIC_CONSTANT( + std::size_t, + sequenced_index_sort_max_fill= + (std::size_t)std::numeric_limits::digits+1); + +template +void sequenced_index_sort(Node* header,Compare comp) +{ + /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html. + * The implementation is a little convoluted: in the original code + * counter elements and carry are std::lists: here we do not want + * to use multi_index instead, so we do things at a lower level, managing + * directly the internal node representation. + * Incidentally, the implementations I've seen of this algorithm (SGI, + * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not + * use any dynamic storage. + */ + + if(header->next()==header->impl()|| + header->next()->next()==header->impl())return; + + typedef typename Node::impl_type impl_type; + typedef typename Node::impl_pointer impl_pointer; + + typedef typename aligned_storage< + sizeof(impl_type), + alignment_of::value + >::type carry_spc_type; + carry_spc_type carry_spc; + impl_type& carry= + *static_cast(static_cast(&carry_spc)); + typedef typename aligned_storage< + sizeof( + impl_type + [sequenced_index_sort_max_fill]), + alignment_of< + impl_type + [sequenced_index_sort_max_fill] + >::value + >::type counter_spc_type; + counter_spc_type counter_spc; + impl_type* counter= + static_cast(static_cast(&counter_spc)); + std::size_t fill=0; + + carry.prior()=carry.next()=static_cast(&carry); + counter[0].prior()=counter[0].next()=static_cast(&counter[0]); + + BOOST_TRY{ + while(header->next()!=header->impl()){ + impl_type::relink(carry.next(),header->next()); + std::size_t i=0; + while(i(&counter[i])){ + sequenced_index_collate(&carry,&counter[i++],comp); + } + impl_type::swap( + static_cast(&carry), + static_cast(&counter[i])); + if(i==fill){ + ++fill; + counter[fill].prior()=counter[fill].next()= + static_cast(&counter[fill]); + } + } + + for(std::size_t i=1;i(&counter[i],&counter[i-1],comp); + } + impl_type::swap( + header->impl(),static_cast(&counter[fill-1])); + } + BOOST_CATCH(...) + { + impl_type::relink( + header->impl(),carry.next(),static_cast(&carry)); + for(std::size_t i=0;i<=fill;++i){ + impl_type::relink( + header->impl(),counter[i].next(), + static_cast(&counter[i])); + } + BOOST_RETHROW; + } + BOOST_CATCH_END +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp b/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp new file mode 100644 index 0000000..ccd8bb4 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp @@ -0,0 +1,73 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SERIALIZATION_VERSION_HPP +#define BOOST_MULTI_INDEX_DETAIL_SERIALIZATION_VERSION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Helper class for storing and retrieving a given type serialization class + * version while avoiding saving the number multiple times in the same + * archive. + * Behavior undefined if template partial specialization is not supported. + */ + +template +struct serialization_version +{ + serialization_version(): + value(boost::serialization::version::value){} + + serialization_version& operator=(unsigned int x){value=x;return *this;}; + + operator unsigned int()const{return value;} + +private: + friend class boost::serialization::access; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + template + void save(Archive&,const unsigned int)const{} + + template + void load(Archive&,const unsigned int version) + { + this->value=version; + } + + unsigned int value; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +namespace serialization { +template +struct version > +{ + BOOST_STATIC_CONSTANT(int,value=version::value); +}; +} /* namespace serialization */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/vartempl_support.hpp b/3rdParty/Boost/src/boost/multi_index/detail/vartempl_support.hpp new file mode 100644 index 0000000..06ff430 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/vartempl_support.hpp @@ -0,0 +1,247 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_VARTEMPL_SUPPORT_HPP +#define BOOST_MULTI_INDEX_DETAIL_VARTEMPL_SUPPORT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +/* Utilities for emulation of variadic template functions. Variadic packs are + * replaced by lists of BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS parameters: + * + * - typename... Args --> BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK + * - Args&&... args --> BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK + * - std::forward(args)... --> BOOST_MULTI_INDEX_FORWARD_PARAM_PACK + * + * Forwarding emulated with Boost.Move. A template functions foo_imp + * defined in such way accepts *exactly* BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS + * arguments: variable number of arguments is emulated by providing a set of + * overloads foo forwarding to foo_impl with + * + * BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL + * BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG (initial extra arg) + * + * which fill the extra args with boost::multi_index::detail::noarg's. + * boost::multi_index::detail::vartempl_placement_new works the opposite + * way: it acceps a full a pointer x to Value and a + * BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK and forwards to + * new(x) Value(args) where args is the argument pack after discarding + * noarg's. + * + * Emulation decays to the real thing when the compiler supports variadic + * templates and move semantics natively. + */ + +#include + +#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)||\ + defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS) +#define BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS 5 +#endif + +#define BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK \ +BOOST_PP_ENUM_PARAMS( \ + BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,typename T) + +#define BOOST_MULTI_INDEX_VARTEMPL_ARG(z,n,_) \ +BOOST_FWD_REF(BOOST_PP_CAT(T,n)) BOOST_PP_CAT(t,n) + +#define BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK \ +BOOST_PP_ENUM( \ + BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS, \ + BOOST_MULTI_INDEX_VARTEMPL_ARG,~) + +#define BOOST_MULTI_INDEX_VARTEMPL_FORWARD_ARG(z,n,_) \ +boost::forward(BOOST_PP_CAT(t,n)) + +#define BOOST_MULTI_INDEX_FORWARD_PARAM_PACK \ +BOOST_PP_ENUM( \ + BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS, \ + BOOST_MULTI_INDEX_VARTEMPL_FORWARD_ARG,~) + +namespace boost{namespace multi_index{namespace detail{ +struct noarg{}; +}}} + +/* call vartempl function without args */ + +#define BOOST_MULTI_INDEX_NULL_PARAM_PACK \ +BOOST_PP_ENUM_PARAMS( \ + BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS, \ + boost::multi_index::detail::noarg() BOOST_PP_INTERCEPT) + +#define BOOST_MULTI_INDEX_TEMPLATE_N(n) \ +template + +#define BOOST_MULTI_INDEX_TEMPLATE_0(n) + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_AUX(z,n,data) \ +BOOST_PP_IF(n, \ + BOOST_MULTI_INDEX_TEMPLATE_N, \ + BOOST_MULTI_INDEX_TEMPLATE_0)(n) \ +BOOST_PP_SEQ_ELEM(0,data) /* ret */ \ +BOOST_PP_SEQ_ELEM(1,data) /* name_from */ ( \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_ARG,~)) \ +{ \ + return BOOST_PP_SEQ_ELEM(2,data) /* name_to */ ( \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_FORWARD_ARG,~) \ + BOOST_PP_COMMA_IF( \ + BOOST_PP_AND( \ + n,BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n))) \ + BOOST_PP_ENUM_PARAMS( \ + BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n), \ + boost::multi_index::detail::noarg() BOOST_PP_INTERCEPT) \ + ); \ +} + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( \ + ret,name_from,name_to) \ +BOOST_PP_REPEAT_FROM_TO( \ + 0,BOOST_PP_ADD(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,1), \ + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_AUX, \ + (ret)(name_from)(name_to)) + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG_AUX( \ + z,n,data) \ +BOOST_PP_IF(n, \ + BOOST_MULTI_INDEX_TEMPLATE_N, \ + BOOST_MULTI_INDEX_TEMPLATE_0)(n) \ +BOOST_PP_SEQ_ELEM(0,data) /* ret */ \ +BOOST_PP_SEQ_ELEM(1,data) /* name_from */ ( \ + BOOST_PP_SEQ_ELEM(3,data) BOOST_PP_SEQ_ELEM(4,data) /* extra arg */\ + BOOST_PP_COMMA_IF(n) \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_ARG,~)) \ +{ \ + return BOOST_PP_SEQ_ELEM(2,data) /* name_to */ ( \ + BOOST_PP_SEQ_ELEM(4,data) /* extra_arg_name */ \ + BOOST_PP_COMMA_IF(n) \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_FORWARD_ARG,~) \ + BOOST_PP_COMMA_IF( \ + BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n)) \ + BOOST_PP_ENUM_PARAMS( \ + BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n), \ + boost::multi_index::detail::noarg() BOOST_PP_INTERCEPT) \ + ); \ +} + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( \ + ret,name_from,name_to,extra_arg_type,extra_arg_name) \ +BOOST_PP_REPEAT_FROM_TO( \ + 0,BOOST_PP_ADD(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,1), \ + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG_AUX, \ + (ret)(name_from)(name_to)(extra_arg_type)(extra_arg_name)) + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +#define BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW_AUX(z,n,name) \ +template< \ + typename Value \ + BOOST_PP_COMMA_IF(n) \ + BOOST_PP_ENUM_PARAMS(n,typename T) \ +> \ +Value* name( \ + Value* x \ + BOOST_PP_COMMA_IF(n) \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_ARG,~) \ + BOOST_PP_COMMA_IF( \ + BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n)) \ + BOOST_PP_ENUM_PARAMS( \ + BOOST_PP_SUB(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,n), \ + BOOST_FWD_REF(noarg) BOOST_PP_INTERCEPT)) \ +{ \ + return new(x) Value( \ + BOOST_PP_ENUM(n,BOOST_MULTI_INDEX_VARTEMPL_FORWARD_ARG,~)); \ +} + +#define BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW(name) \ +BOOST_PP_REPEAT_FROM_TO( \ + 0,BOOST_PP_ADD(BOOST_MULTI_INDEX_LIMIT_VARTEMPL_ARGS,1), \ + BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW_AUX, \ + name) + +BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW(vartempl_placement_new) + +#undef BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW_AUX +#undef BOOST_MULTI_INDEX_VARTEMPL_TO_PLACEMENT_NEW + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#else + +/* native variadic templates support */ + +#include + +#define BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK typename... Args +#define BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK Args&&... args +#define BOOST_MULTI_INDEX_FORWARD_PARAM_PACK std::forward(args)... +#define BOOST_MULTI_INDEX_NULL_PARAM_PACK + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( \ + ret,name_from,name_to) \ +template ret name_from(Args&&... args) \ +{ \ + return name_to(std::forward(args)...); \ +} + +#define BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( \ + ret,name_from,name_to,extra_arg_type,extra_arg_name) \ +template ret name_from( \ + extra_arg_type extra_arg_name,Args&&... args) \ +{ \ + return name_to(extra_arg_name,std::forward(args)...); \ +} + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template +Value* vartempl_placement_new(Value*x,Args&&... args) +{ + return new(x) Value(std::forward(args)...); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/hashed_index.hpp b/3rdParty/Boost/src/boost/multi_index/hashed_index.hpp new file mode 100644 index 0000000..ebf55c9 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/hashed_index.hpp @@ -0,0 +1,1656 @@ +/* Copyright 2003-2014 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_HASHED_INDEX_HPP +#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include +#endif + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \ + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ + detail::make_obj_guard(x,&hashed_index::check_invariant_); \ + BOOST_JOIN(check_invariant_,__LINE__).touch(); +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \ + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this) +#else +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* hashed_index adds a layer of hashed indexing to a given Super */ + +/* Most of the implementation of unique and non-unique indices is + * shared. We tell from one another on instantiation time by using + * Category tags defined in hash_index_node.hpp. + */ + +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 > +#endif + +{ +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the + * lifetime of const references bound to temporaries --precisely what + * scopeguards are. + */ + +#pragma parse_mfunc_templ off +#endif + + typedef typename SuperMeta::type super; + +protected: + typedef hashed_index_node< + typename super::node_type,Category> 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 bucket_array< + 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 ctor_args; + typedef typename super::final_allocator_type allocator_type; + 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; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + +#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; +#else + typedef hashed_index_iterator< + node_type,bucket_array_type, + hashed_index_global_iterator_tag> iterator; +#endif + + 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; + + typedef TagList tag_list; + +protected: + typedef typename super::final_node_type final_node_type; + typedef tuples::cons< + ctor_args, + typename super::ctor_args_list> ctor_args_list; + typedef typename mpl::push_front< + typename super::index_type_list, + hashed_index>::type index_type_list; + typedef typename mpl::push_front< + typename super::iterator_type_list, + iterator>::type iterator_type_list; + typedef typename mpl::push_front< + typename super::const_iterator_type_list, + const_iterator>::type const_iterator_type_list; + typedef typename super::copy_map_type copy_map_type; + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + typedef typename super::index_saver_type index_saver_type; + typedef typename super::index_loader_type index_loader_type; +#endif + +private: +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + typedef safe_mode::safe_container< + hashed_index> safe_super; +#endif + + typedef typename call_traits::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. + */ + + typedef std::pair emplace_return_type; + +public: + + /* construct/destroy/copy + * Default and copy ctors are in the protected section as indices are + * not supposed to be created on their own. No range ctor either. + */ + + hashed_index& operator=( + const hashed_index& x) + { + this->final()=x.final(); + return *this; + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + hashed_index& operator=( + std::initializer_list list) + { + this->final()=list; + return *this; + } +#endif + + allocator_type get_allocator()const BOOST_NOEXCEPT + { + return this->final().get_allocator(); + } + + /* size and capacity */ + + bool empty()const BOOST_NOEXCEPT{return this->final_empty_();} + size_type size()const BOOST_NOEXCEPT{return this->final_size_();} + size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();} + + /* iterators */ + + iterator begin()BOOST_NOEXCEPT + {return make_iterator(node_type::from_impl(header()->next()->prior()));} + const_iterator begin()const BOOST_NOEXCEPT + {return make_iterator(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();} + const_iterator cend()const BOOST_NOEXCEPT{return end();} + + iterator iterator_to(const value_type& x) + { + return make_iterator(node_from_value(&x)); + } + + const_iterator iterator_to(const value_type& x)const + { + return make_iterator(node_from_value(&x)); + } + + /* modifiers */ + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( + emplace_return_type,emplace,emplace_impl) + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( + iterator,emplace_hint,emplace_hint_impl,iterator,position) + + std::pair insert(const value_type& x) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_(x); + return std::pair(make_iterator(p.first),p.second); + } + + std::pair insert(BOOST_RV_REF(value_type) x) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_rv_(x); + return std::pair(make_iterator(p.first),p.second); + } + + iterator insert(iterator position,const value_type& x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_( + x,static_cast(position.get_node())); + return make_iterator(p.first); + } + + iterator insert(iterator position,BOOST_RV_REF(value_type) x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_rv_( + x,static_cast(position.get_node())); + return make_iterator(p.first); + } + + template + void insert(InputIterator first,InputIterator last) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + for(;first!=last;++first)this->final_insert_ref_(*first); + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void insert(std::initializer_list list) + { + insert(list.begin(),list.end()); + } +#endif + + iterator erase(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; + this->final_erase_(static_cast(position++.get_node())); + return position; + } + + size_type erase(key_param_type k) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + + 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()))){ + 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(node_type::from_impl(x))); + x=z; + ++s; + }while(x!=y); + return s; + } + } + return 0; + } + + iterator erase(iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + while(first!=last){ + first=erase(first); + } + return first; + } + + bool replace(iterator position,const value_type& x) + { + 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_replace_( + x,static_cast(position.get_node())); + } + + bool replace(iterator position,BOOST_RV_REF(value_type) x) + { + 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_replace_rv_( + x,static_cast(position.get_node())); + } + + template + bool modify(iterator position,Modifier mod) + { + 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; + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + /* MSVC++ 6.0 optimizer on safe mode code chokes if this + * this is not added. Left it for all compilers as it does no + * harm. + */ + + position.detach(); +#endif + + return this->final_modify_( + mod,static_cast(position.get_node())); + } + + template + bool modify(iterator position,Modifier mod,Rollback back_) + { + 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; + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + /* MSVC++ 6.0 optimizer on safe mode code chokes if this + * this is not added. Left it for all compilers as it does no + * harm. + */ + + position.detach(); +#endif + + return this->final_modify_( + mod,back_,static_cast(position.get_node())); + } + + template + bool modify_key(iterator position,Modifier mod) + { + 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 modify( + position,modify_key_adaptor(mod,key)); + } + + template + bool modify_key(iterator position,Modifier mod,Rollback back_) + { + 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 modify( + position, + modify_key_adaptor(mod,key), + modify_key_adaptor(back_,key)); + } + + void clear()BOOST_NOEXCEPT + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + this->final_clear_(); + } + + void swap(hashed_index& x) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x); + this->final_swap_(x.final()); + } + + /* observers */ + + key_from_value key_extractor()const{return key;} + hasher hash_function()const{return hash_;} + key_equal key_eq()const{return eq_;} + + /* lookup */ + + /* Internally, these ops rely on const_iterator being the same + * type as iterator. + */ + + template + iterator find(const CompatibleKey& k)const + { + return find(k,hash_,eq_); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + iterator find( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq)const + { + 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)); + } + } + return end(); + } + + template + size_type count(const CompatibleKey& k)const + { + return count(k,hash_,eq_); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + size_type count( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq)const + { + 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()))){ + size_type res=0; + node_impl_pointer y=end_of_range(x); + do{ + ++res; + x=node_alg::after(x); + }while(x!=y); + return res; + } + } + return 0; + } + + template + std::pair equal_range(const CompatibleKey& k)const + { + return equal_range(k,hash_,eq_); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + std::pair equal_range( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq)const + { + 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 std::pair( + make_iterator(node_type::from_impl(x)), + make_iterator(node_type::from_impl(end_of_range(x)))); + } + } + return std::pair(end(),end()); + } + + /* bucket interface */ + + size_type bucket_count()const BOOST_NOEXCEPT{return buckets.size();} + size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast(-1);} + + size_type bucket_size(size_type n)const + { + size_type res=0; + for(node_impl_pointer x=buckets.at(n)->prior(); + x!=node_impl_pointer(0);x=node_alg::after_local(x)){ + ++res; + } + return res; + } + + size_type bucket(key_param_type k)const + { + return buckets.position(hash_(k)); + } + + local_iterator begin(size_type n) + { + return const_cast(this)->begin(n); + } + + const_local_iterator begin(size_type n)const + { + 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)); + } + + local_iterator end(size_type n) + { + return const_cast(this)->end(n); + } + + const_local_iterator end(size_type)const + { + return make_local_iterator(0); + } + + const_local_iterator cbegin(size_type n)const{return begin(n);} + const_local_iterator cend(size_type n)const{return end(n);} + + local_iterator local_iterator_to(const value_type& x) + { + return make_local_iterator(node_from_value(&x)); + } + + const_local_iterator local_iterator_to(const value_type& x)const + { + return make_local_iterator(node_from_value(&x)); + } + + /* hash policy */ + + float load_factor()const BOOST_NOEXCEPT + {return static_cast(size())/bucket_count();} + float max_load_factor()const BOOST_NOEXCEPT{return mlf;} + void max_load_factor(float z){mlf=z;calculate_max_load();} + + void rehash(size_type n) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + if(size()<=max_load&&n<=bucket_count())return; + + size_type bc =(std::numeric_limits::max)(); + float fbc=static_cast(1+size()/mlf); + if(bc>fbc){ + bc=static_cast(fbc); + if(bc(std::ceil(static_cast(n)/mlf))); + } + +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: + hashed_index(const ctor_args_list& args_list,const allocator_type& al): + super(args_list.get_tail(),al), + key(tuples::get<1>(args_list.get_head())), + hash_(tuples::get<2>(args_list.get_head())), + eq_(tuples::get<3>(args_list.get_head())), + buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())), + mlf(1.0f) + { + calculate_max_load(); + } + + hashed_index( + const hashed_index& 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) + { + /* Copy ctor just takes the internal configuration objects from x. The rest + * is done in subsequent call to copy_(). + */ + } + + hashed_index( + const hashed_index& 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) + { + calculate_max_load(); + } + + ~hashed_index() + { + /* the container is guaranteed to be empty by now */ + } + +#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(this)); + } +#else + iterator make_iterator(node_type* node) + { + return iterator(node); + } + + const_iterator make_iterator(node_type* node)const + { + return const_iterator(node); + } +#endif + + local_iterator make_local_iterator(node_type* node) + { + return local_iterator(node); + } + + const_local_iterator make_local_iterator(node_type* node)const + { + return const_local_iterator(node); + } + + void copy_( + const hashed_index& x, + const copy_map_type& map) + { + copy_(x,map,Category()); + } + + void copy_( + const hashed_index& x, + const copy_map_type& map,hashed_unique_tag) + { + if(x.size()!=0){ + node_impl_pointer end_org=x.header()->impl(), + org=end_org, + cpy=header()->impl(); + do{ + node_impl_pointer prev_org=org->prior(), + prev_cpy= + static_cast(map.find(static_cast( + 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(), + buc_cpy= + buckets.begin()+(buc_org-x.buckets.begin()); + prev_cpy->next()=buc_cpy; + buc_cpy->prior()=cpy; + } + else{ + prev_cpy->next()=node_impl_type::base_pointer_from(cpy); + } + org=prev_org; + cpy=prev_cpy; + }while(org!=end_org); + } + + super::copy_(x,map); + } + + void copy_( + const hashed_index& x, + const copy_map_type& map,hashed_non_unique_tag) + { + if(x.size()!=0){ + node_impl_pointer end_org=x.header()->impl(), + org=end_org, + cpy=header()->impl(); + do{ + node_impl_pointer next_org=node_alg::after(org), + next_cpy= + static_cast(map.find(static_cast( + 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= + buckets.begin()+(buc_org-x.buckets.begin()); + cpy->next()=buc_cpy; + buc_cpy->prior()=next_cpy; + next_cpy->prior()=cpy; + } + else{ + if(org->next()==node_impl_type::base_pointer_from(next_org)){ + cpy->next()=node_impl_type::base_pointer_from(next_cpy); + } + else{ + cpy->next()= + node_impl_type::base_pointer_from( + static_cast(map.find(static_cast( + node_type::from_impl( + node_impl_type::pointer_from(org->next())))))->impl()); + } + + if(next_org->prior()!=org){ + next_cpy->prior()= + static_cast(map.find(static_cast( + node_type::from_impl(next_org->prior()))))->impl(); + } + else{ + next_cpy->prior()=cpy; + } + } + org=next_org; + cpy=next_cpy; + }while(org!=end_org); + } + + super::copy_(x,map); + } + + template + final_node_type* insert_( + value_param_type v,final_node_type*& x,Variant variant) + { + reserve_for_insert(size()+1); + + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(!link_point(v,pos)){ + return static_cast( + 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(x),pos); + return res; + } + + template + final_node_type* insert_( + value_param_type v,node_type* position,final_node_type*& x,Variant variant) + { + reserve_for_insert(size()+1); + + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(!link_point(v,pos)){ + return static_cast( + 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(x),pos); + return res; + } + + void erase_(node_type* x) + { + unlink(x); + super::erase_(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + } + + void delete_all_nodes_() + { + delete_all_nodes_(Category()); + } + + void delete_all_nodes_(hashed_unique_tag) + { + 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(node_type::from_impl(x))); + x=y; + } + } + + void delete_all_nodes_(hashed_non_unique_tag) + { + for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){ + node_impl_pointer y=x->prior(); + if(y->next()!=node_impl_type::base_pointer_from(x)&& + y->next()->prior()!=x){ /* n-1 of group */ + /* Make the second node prior() pointer back-linked so that it won't + * refer to a deleted node when the time for its own destruction comes. + */ + + node_impl_pointer first=node_impl_type::pointer_from(y->next()); + first->next()->prior()=first; + } + this->final_delete_node_( + static_cast(node_type::from_impl(x))); + x=y; + } + } + + void clear_() + { + super::clear_(); + buckets.clear(header()->impl()); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::detach_dereferenceable_iterators(); +#endif + } + + void swap_( + hashed_index& x) + { + std::swap(key,x.key); + std::swap(hash_,x.hash_); + std::swap(eq_,x.eq_); + buckets.swap(x.buckets); + std::swap(mlf,x.mlf); + std::swap(max_load,x.max_load); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::swap(x); +#endif + + super::swap_(x); + } + + void swap_elements_( + hashed_index& x) + { + buckets.swap(x.buckets); + std::swap(mlf,x.mlf); + std::swap(max_load,x.max_load); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::swap(x); +#endif + + super::swap_elements_(x); + } + + template + bool replace_(value_param_type v,node_type* x,Variant variant) + { + if(eq_(key(v),key(x->value()))){ + return super::replace_(v,x,variant); + } + + unlink_undo undo; + unlink(x,undo); + + BOOST_TRY{ + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(link_point(v,pos)&&super::replace_(v,x,variant)){ + link(x,pos); + return true; + } + undo(); + return false; + } + BOOST_CATCH(...){ + undo(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + bool modify_(node_type* x) + { + std::size_t buc; + bool b; + BOOST_TRY{ + buc=find_bucket(x->value()); + b=in_place(x->impl(),key(x->value()),buc); + } + BOOST_CATCH(...){ + erase_(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + if(!b){ + unlink(x); + BOOST_TRY{ + link_info pos(buckets.at(buc)); + if(!link_point(x->value(),pos)){ + super::erase_(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + return false; + } + link(x,pos); + } + BOOST_CATCH(...){ + super::erase_(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + BOOST_TRY{ + if(!super::modify_(x)){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + return false; + } + else return true; + } + BOOST_CATCH(...){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + bool modify_rollback_(node_type* x) + { + std::size_t buc=find_bucket(x->value()); + if(in_place(x->impl(),key(x->value()),buc)){ + return super::modify_rollback_(x); + } + + unlink_undo undo; + unlink(x,undo); + + BOOST_TRY{ + link_info pos(buckets.at(buc)); + if(link_point(x->value(),pos)&&super::modify_rollback_(x)){ + link(x,pos); + return true; + } + undo(); + return false; + } + BOOST_CATCH(...){ + undo(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + /* comparison */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + /* defect macro refers to class, not function, templates, but anyway */ + + template + friend bool operator==( + const hashed_index&,const hashed_index& y); +#endif + + bool equals(const hashed_index& x)const{return equals(x,Category());} + + bool equals(const hashed_index& x,hashed_unique_tag)const + { + if(size()!=x.size())return false; + for(const_iterator it=begin(),it_end=end(),it2_end=x.end(); + it!=it_end;++it){ + const_iterator it2=x.find(key(*it)); + if(it2==it2_end||!(*it==*it2))return false; + } + return true; + } + + bool equals(const hashed_index& x,hashed_non_unique_tag)const + { + if(size()!=x.size())return false; + for(const_iterator it=begin(),it_end=end();it!=it_end;){ + const_iterator it2,it2_last; + boost::tie(it2,it2_last)=x.equal_range(key(*it)); + if(it2==it2_last)return false; + + const_iterator it_last=make_iterator( + 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 + * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf + */ + + for(;it!=it_last;++it,++it2){ + if(!(*it==*it2))break; + } + 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); + if(matches==0||matches!=std::count(scan,it_last,*scan))return false; + } + it=it_last; + } + } + return true; + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* serialization */ + + template + void save_( + Archive& ar,const unsigned int version,const index_saver_type& sm)const + { + ar< + void load_(Archive& ar,const unsigned int version,const index_loader_type& lm) + { + ar>>serialization::make_nvp("position",buckets); + super::load_(ar,version,lm); + } +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + /* invariant stuff */ + + bool invariant_()const + { + if(size()==0||begin()==end()){ + if(size()!=0||begin()!=end())return false; + } + else{ + size_type s0=0; + for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){} + if(s0!=size())return false; + + size_type s1=0; + for(size_type buc=0;bucfinal_check_invariant_();} +#endif + +private: + node_type* header()const{return this->final_header();} + + std::size_t find_bucket(value_param_type v)const + { + return bucket(key(v)); + } + + struct link_info_non_unique + { + link_info_non_unique(node_impl_base_pointer pos): + first(pos),last(node_impl_base_pointer(0)){} + + operator const node_impl_base_pointer&()const{return this->first;} + + node_impl_base_pointer first,last; + }; + + typedef typename mpl::if_< + is_same, + node_impl_base_pointer, + link_info_non_unique + >::type link_info; + + bool link_point(value_param_type v,link_info& pos) + { + return link_point(v,pos,Category()); + } + + bool link_point( + value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag) + { + 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()))){ + pos=node_impl_type::base_pointer_from(x); + return false; + } + } + return true; + } + + bool link_point( + value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag) + { + 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()))){ + pos.first=node_impl_type::base_pointer_from(x); + pos.last=node_impl_type::base_pointer_from(last_of_range(x)); + return true; + } + } + return true; + } + + node_impl_pointer last_of_range(node_impl_pointer x)const + { + return last_of_range(x,Category()); + } + + node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const + { + return x; + } + + node_impl_pointer last_of_range( + node_impl_pointer x,hashed_non_unique_tag)const + { + node_impl_base_pointer y=x->next(); + node_impl_pointer z=y->prior(); + if(z==x){ /* range of size 1 or 2 */ + 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; + } + else if(z->prior()==x) /* last of bucket */ + return x; + else /* group of size>2 */ + return z; + } + + node_impl_pointer end_of_range(node_impl_pointer x)const + { + return end_of_range(x,Category()); + } + + node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const + { + return node_alg::after(last_of_range(x)); + } + + node_impl_pointer end_of_range( + node_impl_pointer x,hashed_non_unique_tag)const + { + node_impl_base_pointer y=x->next(); + node_impl_pointer z=y->prior(); + 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; + return yy->next()->prior()==yy? + node_impl_type::pointer_from(yy->next()): + yy->next()->prior(); + } + else if(z->prior()==x) /* last of bucket */ + return z; + else /* group of size>2 */ + return z->next()->prior()==z? + node_impl_type::pointer_from(z->next()): + z->next()->prior(); + } + + void link(node_type* x,const link_info& pos) + { + link(x,pos,Category()); + } + + void link(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) + { + if(pos.last==node_impl_base_pointer(0)){ + node_alg::link(x->impl(),pos.first,header()->impl()); + } + else{ + node_alg::link( + x->impl(), + node_impl_type::pointer_from(pos.first), + node_impl_type::pointer_from(pos.last)); + } + } + + void unlink(node_type* x) + { + node_alg::unlink(x->impl()); + } + + typedef typename node_alg::unlink_undo unlink_undo; + + void unlink(node_type* x,unlink_undo& undo) + { + node_alg::unlink(x->impl(),undo); + } + + void calculate_max_load() + { + float fml=static_cast(mlf*bucket_count()); + max_load=(std::numeric_limits::max)(); + if(max_load>fml)max_load=static_cast(fml); + } + + void reserve_for_insert(size_type n) + { + if(n>max_load){ + size_type bc =(std::numeric_limits::max)(); + float fbc=static_cast(1+static_cast(n)/mlf); + if(bc>fbc)bc =static_cast(fbc); + unchecked_rehash(bc); + } + } + + void unchecked_rehash(size_type n){unchecked_rehash(n,Category());} + + void unchecked_rehash(size_type n,hashed_unique_tag) + { + node_impl_type cpy_end_node; + node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node), + end_=header()->impl(); + bucket_array_type buckets_cpy(get_allocator(),cpy_end,n); + + if(size()!=0){ + auto_space< + std::size_t,allocator_type> hashes(get_allocator(),size()); + auto_space< + node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size()); + std::size_t i=0,size_=size(); + bool within_bucket=false; + BOOST_TRY{ + for(;i!=size_;++i){ + node_impl_pointer x=end_->prior(); + + /* only this can possibly throw */ + std::size_t h=hash_(key(node_type::from_impl(x)->value())); + + hashes.data()[i]=h; + node_ptrs.data()[i]=x; + within_bucket=!node_alg::unlink_last(end_); + node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end); + } + } + BOOST_CATCH(...){ + if(i!=0){ + std::size_t prev_buc=buckets.position(hashes.data()[i-1]); + if(!within_bucket)prev_buc=~prev_buc; + + for(std::size_t j=i;j--;){ + std::size_t buc=buckets.position(hashes.data()[j]); + node_impl_pointer x=node_ptrs.data()[j]; + if(buc==prev_buc)node_alg::append(x,end_); + else node_alg::link(x,buckets.at(buc),end_); + prev_buc=buc; + } + } + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_; + end_->next()=cpy_end->next(); + end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_; + buckets.swap(buckets_cpy); + calculate_max_load(); + } + + void unchecked_rehash(size_type n,hashed_non_unique_tag) + { + node_impl_type cpy_end_node; + node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node), + end_=header()->impl(); + bucket_array_type buckets_cpy(get_allocator(),cpy_end,n); + + if(size()!=0){ + auto_space< + std::size_t,allocator_type> hashes(get_allocator(),size()); + auto_space< + node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size()); + std::size_t i=0; + bool within_bucket=false; + BOOST_TRY{ + for(;;++i){ + node_impl_pointer x=end_->prior(); + if(x==end_)break; + + /* only this can possibly throw */ + std::size_t h=hash_(key(node_type::from_impl(x)->value())); + + hashes.data()[i]=h; + node_ptrs.data()[i]=x; + std::pair p= + node_alg::unlink_last_group(end_); + node_alg::link_range( + p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end); + within_bucket=!(p.second); + } + } + BOOST_CATCH(...){ + if(i!=0){ + std::size_t prev_buc=buckets.position(hashes.data()[i-1]); + if(!within_bucket)prev_buc=~prev_buc; + + for(std::size_t j=i;j--;){ + std::size_t buc=buckets.position(hashes.data()[j]); + node_impl_pointer x=node_ptrs.data()[j], + y= + x->prior()->next()!=node_impl_type::base_pointer_from(x)&& + x->prior()->next()->prior()!=x? + node_impl_type::pointer_from(x->prior()->next()):x; + node_alg::unlink_range(y,x); + if(buc==prev_buc)node_alg::append_range(y,x,end_); + else node_alg::link_range(y,x,buckets.at(buc),end_); + prev_buc=buc; + } + } + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_; + end_->next()=cpy_end->next(); + end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_; + buckets.swap(buckets_cpy); + calculate_max_load(); + } + + bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const + { + return in_place(x,k,buc,Category()); + } + + bool in_place( + node_impl_pointer x,key_param_type k,std::size_t buc, + hashed_unique_tag)const + { + bool found=false; + 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; + } + return found; + } + + bool in_place( + node_impl_pointer x,key_param_type k,std::size_t buc, + hashed_non_unique_tag)const + { + bool found=false; + int range_size=0; + for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){ + if(node_alg::is_first_of_group(y)){ /* group of 3 or more */ + if(y==x){ + /* in place <-> equal to some other member of the group */ + return eq_( + k, + key(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(found)return false; /* x lies outside */ + do{ + if(y==x)return true; + y=node_alg::after_local(y); + }while(y!=z); + return false; /* x not found */ + } + else{ + if(range_size==1&&!found)return false; + if(range_size==2)return found; + range_size=0; + y=z; /* skip range (and potentially x, too, which is fine) */ + } + } + } + else{ /* group of 1 or 2 */ + if(y==x){ + if(range_size==1)return true; + range_size=1; + found=true; + } + else if(eq_(k,key(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; + ++range_size; + } + else{ + if(range_size==1&&!found)return false; + if(range_size==2)return found; + range_size=0; + } + y=node_alg::after_local(y); + } + } + return found; + } + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + void detach_iterators(node_type* x) + { + iterator it=make_iterator(x); + safe_mode::detach_equivalent_iterators(it); + } +#endif + + template + std::pair emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pairp= + this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + return std::pair(make_iterator(p.first),p.second); + } + + template + iterator emplace_hint_impl( + iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pairp= + this->final_emplace_hint_( + static_cast(position.get_node()), + BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + return make_iterator(p.first); + } + + key_from_value key; + hasher hash_; + key_equal eq_; + bucket_array_type buckets; + float mlf; + size_type max_load; + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +#pragma parse_mfunc_templ reset +#endif +}; + +/* comparison */ + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator==( + const hashed_index& x, + const hashed_index& y) +{ + return x.equals(y); +} + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator!=( + const hashed_index& x, + const hashed_index& y) +{ + return !(x==y); +} + +/* specialized algorithms */ + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +void swap( + hashed_index& x, + hashed_index& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +/* hashed index specifiers */ + +template +struct hashed_unique +{ + typedef typename detail::hashed_index_args< + Arg1,Arg2,Arg3,Arg4> index_args; + typedef typename index_args::tag_list_type::type tag_list_type; + typedef typename index_args::key_from_value_type key_from_value_type; + typedef typename index_args::hash_type hash_type; + typedef typename index_args::pred_type pred_type; + + template + struct node_class + { + typedef detail::hashed_index_node type; + }; + + template + struct index_class + { + typedef detail::hashed_index< + key_from_value_type,hash_type,pred_type, + SuperMeta,tag_list_type,detail::hashed_unique_tag> type; + }; +}; + +template +struct hashed_non_unique +{ + typedef typename detail::hashed_index_args< + Arg1,Arg2,Arg3,Arg4> index_args; + typedef typename index_args::tag_list_type::type tag_list_type; + typedef typename index_args::key_from_value_type key_from_value_type; + typedef typename index_args::hash_type hash_type; + typedef typename index_args::pred_type pred_type; + + template + struct node_class + { + typedef detail::hashed_index_node< + Super,detail::hashed_non_unique_tag> type; + }; + + template + struct index_class + { + typedef detail::hashed_index< + key_from_value_type,hash_type,pred_type, + SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type; + }; +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +/* Boost.Foreach compatibility */ + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +inline boost::mpl::true_* boost_foreach_is_noncopyable( + boost::multi_index::detail::hashed_index< + KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>*&, + boost::foreach::tag) +{ + return 0; +} + +#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT +#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/hashed_index_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/hashed_index_fwd.hpp new file mode 100644 index 0000000..d77e36c --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/hashed_index_fwd.hpp @@ -0,0 +1,74 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_HASHED_INDEX_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +class hashed_index; + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator==( + const hashed_index& x, + const hashed_index& y); + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator!=( + const hashed_index& x, + const hashed_index& y); + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +void swap( + hashed_index& x, + hashed_index& y); + +} /* namespace multi_index::detail */ + +/* hashed_index specifiers */ + +template< + typename Arg1,typename Arg2=mpl::na, + typename Arg3=mpl::na,typename Arg4=mpl::na +> +struct hashed_unique; + +template< + typename Arg1,typename Arg2=mpl::na, + typename Arg3=mpl::na,typename Arg4=mpl::na +> +struct hashed_non_unique; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/identity.hpp b/3rdParty/Boost/src/boost/multi_index/identity.hpp new file mode 100644 index 0000000..1dbaf3b --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/identity.hpp @@ -0,0 +1,137 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_IDENTITY_HPP +#define BOOST_MULTI_INDEX_IDENTITY_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_NO_SFINAE) +#include +#endif + +namespace boost{ + +template class reference_wrapper; /* fwd decl. */ + +namespace multi_index{ + +namespace detail{ + +/* identity is a do-nothing key extractor that returns the [const] Type& + * object passed. + * Additionally, identity is overloaded to support referece_wrappers + * of Type and "chained pointers" to Type's. By chained pointer to Type we + * mean a type P such that, given a p of type P + * *...n...*x is convertible to Type&, for some n>=1. + * Examples of chained pointers are raw and smart pointers, iterators and + * arbitrary combinations of these (vg. Type** or auto_ptr.) + */ + +template +struct const_identity_base +{ + typedef Type result_type; + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(Type& x)const + { + return x; + } + + Type& operator()(const reference_wrapper& x)const + { + return x.get(); + } + + Type& operator()( + const reference_wrapper::type>& x)const + { + return x.get(); + } +}; + +template +struct non_const_identity_base +{ + typedef Type result_type; + + /* templatized for pointer-like types */ + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Type& x)const + { + return x; + } + + Type& operator()(Type& x)const + { + return x; + } + + const Type& operator()(const reference_wrapper& x)const + { + return x.get(); + } + + Type& operator()(const reference_wrapper& x)const + { + return x.get(); + } +}; + +} /* namespace multi_index::detail */ + +template +struct identity: + mpl::if_c< + is_const::value, + detail::const_identity_base,detail::non_const_identity_base + >::type +{ +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp new file mode 100644 index 0000000..af6bd55 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp @@ -0,0 +1,26 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_IDENTITY_FWD_HPP +#define BOOST_MULTI_INDEX_IDENTITY_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +template struct identity; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp b/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp new file mode 100644 index 0000000..d2217e3 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp @@ -0,0 +1,68 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_INDEXED_BY_HPP +#define BOOST_MULTI_INDEX_INDEXED_BY_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include + +/* An alias to mpl::vector used to hide MPL from the user. + * indexed_by contains the index specifiers for instantiation + * of a multi_index_container. + */ + +/* This user_definable macro limits the number of elements of an index list; + * useful for shortening resulting symbol names (MSVC++ 6.0, for instance, + * has problems coping with very long symbol names.) + */ + +#if !defined(BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE) +#define BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif + +#if BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE +struct indexed_by: + mpl::vector +{ +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_INDEXED_BY_TEMPLATE_PARM +#undef BOOST_MULTI_INDEX_INDEXED_BY_SIZE + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/member.hpp b/3rdParty/Boost/src/boost/multi_index/member.hpp new file mode 100644 index 0000000..192cf1b --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/member.hpp @@ -0,0 +1,262 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_MEMBER_HPP +#define BOOST_MULTI_INDEX_MEMBER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include + +#if !defined(BOOST_NO_SFINAE) +#include +#endif + +namespace boost{ + +template class reference_wrapper; /* fwd decl. */ + +namespace multi_index{ + +namespace detail{ + +/* member is a read/write key extractor for accessing a given + * member of a class. + * Additionally, member is 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 + * *...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 auto_ptr.) + */ + +template +struct const_member_base +{ + typedef Type result_type; + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(const Class& x)const + { + return x.*PtrToMember; + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } +}; + +template +struct non_const_member_base +{ + typedef Type result_type; + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Class& x)const + { + return x.*PtrToMember; + } + + Type& operator()(Class& x)const + { + return x.*PtrToMember; + } + + const Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } +}; + +} /* namespace multi_index::detail */ + +template +struct member: + mpl::if_c< + is_const::value, + detail::const_member_base, + detail::non_const_member_base + >::type +{ +}; + +namespace detail{ + +/* MSVC++ 6.0 does not support properly pointers to members as + * non-type template arguments, as reported in + * http://support.microsoft.com/default.aspx?scid=kb;EN-US;249045 + * A similar problem (though not identical) is shown by MSVC++ 7.0. + * We provide an alternative to member<> accepting offsets instead + * of pointers to members. This happens to work even for non-POD + * types (although the standard forbids use of offsetof on these), + * so it serves as a workaround in this compiler for all practical + * purposes. + * Surprisingly enough, other compilers, like Intel C++ 7.0/7.1 and + * Visual Age 6.0, have similar bugs. This replacement of member<> + * can be used for them too. + * + * Support for such old compilers is dropped and + * [non_]const_member_offset_base is deprecated. + */ + +template +struct const_member_offset_base +{ + typedef Type result_type; + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(const Class& x)const + { + return *static_cast( + static_cast( + static_cast( + static_cast(&x))+OffsetOfMember)); + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } +}; + +template +struct non_const_member_offset_base +{ + typedef Type result_type; + + template + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Class& x)const + { + return *static_cast( + static_cast( + static_cast( + static_cast(&x))+OffsetOfMember)); + } + + Type& operator()(Class& x)const + { + return *static_cast( + static_cast( + static_cast(static_cast(&x))+OffsetOfMember)); + } + + const Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper& x)const + { + return operator()(x.get()); + } +}; + +} /* namespace multi_index::detail */ + +template +struct member_offset: + mpl::if_c< + is_const::value, + detail::const_member_offset_base, + detail::non_const_member_offset_base + >::type +{ +}; + +/* BOOST_MULTI_INDEX_MEMBER resolves to member in the normal cases, + * and to member_offset as a workaround in those defective compilers for + * which BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS is defined. + */ + +#if defined(BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS) +#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) \ +::boost::multi_index::member_offset< Class,Type,offsetof(Class,MemberName) > +#else +#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) \ +::boost::multi_index::member< Class,Type,&Class::MemberName > +#endif + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp new file mode 100644 index 0000000..dbd040f --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp @@ -0,0 +1,124 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_ORDERED_INDEX_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template< + typename KeyFromValue,typename Compare, + typename SuperMeta,typename TagList,typename Category +> +class ordered_index; + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator==( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator<( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator!=( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator>( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator>=( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue1,typename Compare1, + typename SuperMeta1,typename TagList1,typename Category1, + typename KeyFromValue2,typename Compare2, + typename SuperMeta2,typename TagList2,typename Category2 +> +bool operator<=( + const ordered_index< + KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, + const ordered_index< + KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y); + +template< + typename KeyFromValue,typename Compare, + typename SuperMeta,typename TagList,typename Category +> +void swap( + ordered_index& x, + ordered_index& y); + +} /* namespace multi_index::detail */ + +/* ordered_index specifiers */ + +template +struct ordered_unique; + +template +struct ordered_non_unique; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp b/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp new file mode 100644 index 0000000..1904706 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp @@ -0,0 +1,48 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_SAFE_MODE_ERRORS_HPP +#define BOOST_MULTI_INDEX_SAFE_MODE_ERRORS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace safe_mode{ + +/* Error codes for Boost.MultiIndex safe mode. These go in a separate + * header so that the user can include it when redefining + * BOOST_MULTI_INDEX_SAFE_MODE_ASSERT prior to the inclusion of + * any other header of Boost.MultiIndex. + */ + +enum error_code +{ + invalid_iterator=0, + not_dereferenceable_iterator, + not_incrementable_iterator, + not_decrementable_iterator, + not_owner, + not_same_owner, + invalid_range, + inside_range, + out_of_bounds, + same_container +}; + +} /* namespace multi_index::safe_mode */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp b/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp new file mode 100644 index 0000000..d56eddd --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp @@ -0,0 +1,1060 @@ +/* Copyright 2003-2014 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_SEQUENCED_INDEX_HPP +#define BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include +#endif + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#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__)= \ + detail::make_obj_guard(x,&sequenced_index::check_invariant_); \ + BOOST_JOIN(check_invariant_,__LINE__).touch(); +#define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT \ + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(*this) +#else +#define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x) +#define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* sequenced_index adds a layer of sequenced indexing to a given Super */ + +template +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 > +#endif + +{ +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the + * lifetime of const references bound to temporaries --precisely what + * scopeguards are. + */ + +#pragma parse_mfunc_templ off +#endif + + typedef typename SuperMeta::type super; + +protected: + typedef sequenced_index_node< + typename super::node_type> node_type; + +private: + typedef typename 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; + typedef typename allocator_type::reference reference; + typedef typename allocator_type::const_reference const_reference; + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + typedef safe_mode::safe_iterator< + bidir_node_iterator, + sequenced_index> iterator; +#else + typedef bidir_node_iterator iterator; +#endif + + typedef iterator const_iterator; + + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + typedef typename allocator_type::pointer pointer; + typedef typename allocator_type::const_pointer const_pointer; + typedef typename + boost::reverse_iterator reverse_iterator; + typedef typename + boost::reverse_iterator const_reverse_iterator; + typedef TagList tag_list; + +protected: + typedef typename super::final_node_type final_node_type; + typedef tuples::cons< + ctor_args, + typename super::ctor_args_list> ctor_args_list; + typedef typename mpl::push_front< + typename super::index_type_list, + sequenced_index>::type index_type_list; + typedef typename mpl::push_front< + typename super::iterator_type_list, + iterator>::type iterator_type_list; + typedef typename mpl::push_front< + typename super::const_iterator_type_list, + const_iterator>::type const_iterator_type_list; + typedef typename super::copy_map_type copy_map_type; + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + typedef typename super::index_saver_type index_saver_type; + typedef typename super::index_loader_type index_loader_type; +#endif + +private: +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + typedef safe_mode::safe_container< + sequenced_index> safe_super; +#endif + + typedef typename call_traits::param_type value_param_type; + + /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL + * expansion. + */ + + typedef std::pair emplace_return_type; + +public: + + /* construct/copy/destroy + * Default and copy ctors are in the protected section as indices are + * not supposed to be created on their own. No range ctor either. + */ + + sequenced_index& operator=( + const sequenced_index& x) + { + this->final()=x.final(); + return *this; + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + sequenced_index& operator=( + std::initializer_list list) + { + this->final()=list; + return *this; + } +#endif + + template + void assign(InputIterator first,InputIterator last) + { + assign_iter(first,last,mpl::not_ >()); + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void assign(std::initializer_list list) + { + assign(list.begin(),list.end()); + } +#endif + + void assign(size_type n,value_param_type value) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(size_type i=0;ifinal().get_allocator(); + } + + /* iterators */ + + iterator begin()BOOST_NOEXCEPT + {return make_iterator(node_type::from_impl(header()->next()));} + const_iterator begin()const BOOST_NOEXCEPT + {return make_iterator(node_type::from_impl(header()->next()));} + iterator + end()BOOST_NOEXCEPT{return make_iterator(header());} + const_iterator + end()const BOOST_NOEXCEPT{return make_iterator(header());} + reverse_iterator + rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());} + const_reverse_iterator + rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());} + reverse_iterator + rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());} + const_reverse_iterator + rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());} + const_iterator + cbegin()const BOOST_NOEXCEPT{return begin();} + const_iterator + cend()const BOOST_NOEXCEPT{return end();} + const_reverse_iterator + crbegin()const BOOST_NOEXCEPT{return rbegin();} + const_reverse_iterator + crend()const BOOST_NOEXCEPT{return rend();} + + iterator iterator_to(const value_type& x) + { + return make_iterator(node_from_value(&x)); + } + + const_iterator iterator_to(const value_type& x)const + { + return make_iterator(node_from_value(&x)); + } + + /* capacity */ + + bool empty()const BOOST_NOEXCEPT{return this->final_empty_();} + size_type size()const BOOST_NOEXCEPT{return this->final_size_();} + size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();} + + void resize(size_type n) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(n>size()){ + for(size_type m=n-size();m--;) + this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK); + } + else if(nsize())insert(end(),n-size(),x); + else if(n push_front(const value_type& x) + {return insert(begin(),x);} + std::pair push_front(BOOST_RV_REF(value_type) x) + {return insert(begin(),boost::move(x));} + void pop_front(){erase(begin());} + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( + emplace_return_type,emplace_back,emplace_back_impl) + + std::pair push_back(const value_type& x) + {return insert(end(),x);} + std::pair push_back(BOOST_RV_REF(value_type) x) + {return insert(end(),boost::move(x));} + void pop_back(){erase(--end());} + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( + emplace_return_type,emplace,emplace_impl,iterator,position) + + std::pair insert(iterator position,const value_type& x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_(x); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return std::pair(make_iterator(p.first),p.second); + } + + std::pair insert(iterator position,BOOST_RV_REF(value_type) x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + std::pair p=this->final_insert_rv_(x); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return std::pair(make_iterator(p.first),p.second); + } + + void insert(iterator position,size_type n,value_param_type x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(size_type i=0;i + void insert(iterator position,InputIterator first,InputIterator last) + { + insert_iter(position,first,last,mpl::not_ >()); + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void insert(iterator position,std::initializer_list list) + { + insert(position,list.begin(),list.end()); + } +#endif + + iterator erase(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; + this->final_erase_(static_cast(position++.get_node())); + return position; + } + + iterator erase(iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + while(first!=last){ + first=erase(first); + } + return first; + } + + bool replace(iterator position,const value_type& x) + { + 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_replace_( + x,static_cast(position.get_node())); + } + + bool replace(iterator position,BOOST_RV_REF(value_type) x) + { + 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_replace_rv_( + x,static_cast(position.get_node())); + } + + template + bool modify(iterator position,Modifier mod) + { + 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; + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + /* MSVC++ 6.0 optimizer on safe mode code chokes if this + * this is not added. Left it for all compilers as it does no + * harm. + */ + + position.detach(); +#endif + + return this->final_modify_( + mod,static_cast(position.get_node())); + } + + template + bool modify(iterator position,Modifier mod,Rollback back_) + { + 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; + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + /* MSVC++ 6.0 optimizer on safe mode code chokes if this + * this is not added. Left it for all compilers as it does no + * harm. + */ + + position.detach(); +#endif + + return this->final_modify_( + mod,back_,static_cast(position.get_node())); + } + + void swap(sequenced_index& x) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x); + this->final_swap_(x.final()); + } + + void clear()BOOST_NOEXCEPT + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + this->final_clear_(); + } + + /* list operations */ + + void splice(iterator position,sequenced_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; + } + } + + void splice(iterator position,sequenced_index& x,iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + 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_SEQ_INDEX_CHECK_INVARIANT; + if(&x==this){ + if(position!=i)relink(position.get_node(),i.get_node()); + } + 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 + + } + } + } + + void splice( + iterator position,sequenced_index& x, + iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + 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_SEQ_INDEX_CHECK_INVARIANT; + if(&x==this){ + BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); + if(position!=last)relink( + position.get_node(),first.get_node(),last.get_node()); + } + else{ + while(first!=last){ + if(insert(position,*first).second)first=x.erase(first); + else ++first; + } + } + } + + void remove(value_param_type value) + { + sequenced_index_remove( + *this,std::bind2nd(std::equal_to(),value)); + } + + template + void remove_if(Predicate pred) + { + sequenced_index_remove(*this,pred); + } + + void unique() + { + sequenced_index_unique(*this,std::equal_to()); + } + + template + void unique(BinaryPredicate binary_pred) + { + sequenced_index_unique(*this,binary_pred); + } + + void merge(sequenced_index& x) + { + sequenced_index_merge(*this,x,std::less()); + } + + template + void merge(sequenced_index& x,Compare comp) + { + sequenced_index_merge(*this,x,comp); + } + + void sort() + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + sequenced_index_sort(header(),std::less()); + } + + template + void sort(Compare comp) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + sequenced_index_sort(header(),comp); + } + + void reverse()BOOST_NOEXCEPT + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + node_impl_type::reverse(header()->impl()); + } + + /* rearrange operations */ + + void relocate(iterator position,iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(position!=i)relink(position.get_node(),i.get_node()); + } + + void relocate(iterator position,iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(position!=last)relink( + position.get_node(),first.get_node(),last.get_node()); + } + + template + void rearrange(InputIterator first) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + node_type* pos=header(); + for(size_type s=size();s--;){ + const value_type& v=*first++; + relink(pos,node_from_value(&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) + { + empty_initialize(); + } + + sequenced_index(const sequenced_index& x): + super(x) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe_super() +#endif + + { + /* the actual copying takes place in subsequent call to copy_() */ + } + + sequenced_index( + const sequenced_index& x,do_not_copy_elements_tag): + super(x,do_not_copy_elements_tag()) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe_super() +#endif + + { + empty_initialize(); + } + + ~sequenced_index() + { + /* the container is guaranteed to be empty by now */ + } + +#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(this));} +#else + iterator make_iterator(node_type* node){return iterator(node);} + const_iterator make_iterator(node_type* node)const + {return const_iterator(node);} +#endif + + void copy_( + const sequenced_index& x,const copy_map_type& map) + { + node_type* org=x.header(); + node_type* cpy=header(); + do{ + node_type* next_org=node_type::from_impl(org->next()); + node_type* next_cpy=map.find(static_cast(next_org)); + cpy->next()=next_cpy->impl(); + next_cpy->prior()=cpy->impl(); + org=next_org; + cpy=next_cpy; + }while(org!=x.header()); + + super::copy_(x,map); + } + + template + final_node_type* insert_( + 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(x)); + return res; + } + + template + final_node_type* insert_( + value_param_type v,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(x)); + return res; + } + + void erase_(node_type* x) + { + unlink(x); + super::erase_(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(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()); + this->final_delete_node_(static_cast(x)); + x=y; + } + } + + void clear_() + { + super::clear_(); + empty_initialize(); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::detach_dereferenceable_iterators(); +#endif + } + + void swap_(sequenced_index& x) + { +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::swap(x); +#endif + + super::swap_(x); + } + + void swap_elements_(sequenced_index& x) + { +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::swap(x); +#endif + + super::swap_elements_(x); + } + + template + bool replace_(value_param_type v,node_type* x,Variant variant) + { + return super::replace_(v,x,variant); + } + + bool modify_(node_type* x) + { + BOOST_TRY{ + if(!super::modify_(x)){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + return false; + } + else return true; + } + BOOST_CATCH(...){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + bool modify_rollback_(node_type* x) + { + return super::modify_rollback_(x); + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* serialization */ + + template + void save_( + Archive& ar,const unsigned int version,const index_saver_type& sm)const + { + sm.save(begin(),end(),ar,version); + super::save_(ar,version,sm); + } + + template + void load_( + Archive& ar,const unsigned int version,const index_loader_type& lm) + { + lm.load( + ::boost::bind( + &sequenced_index::rearranger,this,::boost::arg<1>(),::boost::arg<2>()), + ar,version); + super::load_(ar,version,lm); + } +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + /* invariant stuff */ + + bool invariant_()const + { + if(size()==0||begin()==end()){ + if(size()!=0||begin()!=end()|| + header()->next()!=header()->impl()|| + header()->prior()!=header()->impl())return false; + } + else{ + size_type s=0; + for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s){ + if(it.get_node()->next()->prior()!=it.get_node()->impl())return false; + if(it.get_node()->prior()->next()!=it.get_node()->impl())return false; + } + if(s!=size())return false; + } + + return super::invariant_(); + } + + /* This forwarding function eases things for the boost::mem_fn construct + * in BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT. Actually, + * final_check_invariant is already an inherited member function of index. + */ + void check_invariant_()const{this->final_check_invariant_();} +#endif + +private: + node_type* header()const{return this->final_header();} + + void empty_initialize() + { + header()->prior()=header()->next()=header()->impl(); + } + + void link(node_type* x) + { + node_impl_type::link(x->impl(),header()->impl()); + }; + + static void unlink(node_type* x) + { + node_impl_type::unlink(x->impl()); + } + + static void relink(node_type* position,node_type* x) + { + node_impl_type::relink(position->impl(),x->impl()); + } + + static void relink(node_type* position,node_type* first,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) + { + if(!position)position=header(); + 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) + { + iterator it=make_iterator(x); + safe_mode::detach_equivalent_iterators(it); + } +#endif + + template + void assign_iter(InputIterator first,InputIterator last,mpl::true_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(;first!=last;++first)this->final_insert_ref_(*first); + } + + void assign_iter(size_type n,value_param_type value,mpl::false_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(size_type i=0;i + void insert_iter( + iterator position,InputIterator first,InputIterator last,mpl::true_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(;first!=last;++first){ + std::pair p= + this->final_insert_ref_(*first); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + } + } + + void insert_iter( + iterator position,size_type n,value_param_type x,mpl::false_) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(size_type i=0;i + std::pair emplace_front_impl( + BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + + template + std::pair emplace_back_impl( + BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + } + + template + std::pair emplace_impl( + iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + std::pair p= + this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return std::pair(make_iterator(p.first),p.second); + } + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +#pragma parse_mfunc_templ reset +#endif +}; + +/* comparison */ + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator==( + const sequenced_index& x, + const sequenced_index& y) +{ + return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<( + const sequenced_index& x, + const sequenced_index& y) +{ + return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator!=( + const sequenced_index& x, + const sequenced_index& y) +{ + return !(x==y); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>( + const sequenced_index& x, + const sequenced_index& y) +{ + return y +bool operator>=( + const sequenced_index& x, + const sequenced_index& y) +{ + return !(x +bool operator<=( + const sequenced_index& x, + const sequenced_index& y) +{ + return !(x>y); +} + +/* specialized algorithms */ + +template +void swap( + sequenced_index& x, + sequenced_index& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +/* sequenced index specifier */ + +template +struct sequenced +{ + BOOST_STATIC_ASSERT(detail::is_tag::value); + + template + struct node_class + { + typedef detail::sequenced_index_node type; + }; + + template + struct index_class + { + typedef detail::sequenced_index type; + }; +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +/* Boost.Foreach compatibility */ + +template +inline boost::mpl::true_* boost_foreach_is_noncopyable( + boost::multi_index::detail::sequenced_index*&, + boost::foreach::tag) +{ + return 0; +} + +#undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT +#undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp new file mode 100644 index 0000000..a019f2a --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp @@ -0,0 +1,91 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_SEQUENCED_INDEX_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template +class sequenced_index; + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator==( + const sequenced_index& x, + const sequenced_index& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<( + const sequenced_index& x, + const sequenced_index& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator!=( + const sequenced_index& x, + const sequenced_index& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>( + const sequenced_index& x, + const sequenced_index& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>=( + const sequenced_index& x, + const sequenced_index& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<=( + const sequenced_index& x, + const sequenced_index& y); + +template +void swap( + sequenced_index& x, + sequenced_index& y); + +} /* namespace multi_index::detail */ + +/* index specifiers */ + +template > +struct sequenced; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/tag.hpp b/3rdParty/Boost/src/boost/multi_index/tag.hpp new file mode 100644 index 0000000..ce51f82 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/tag.hpp @@ -0,0 +1,88 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_TAG_HPP +#define BOOST_MULTI_INDEX_TAG_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* A wrapper of mpl::vector used to hide MPL from the user. + * tag contains types used as tag names for indices in get() functions. + */ + +/* This user_definable macro limits the number of elements of a tag; + * useful for shortening resulting symbol names (MSVC++ 6.0, for instance, + * has problems coping with very long symbol names.) + */ + +#if !defined(BOOST_MULTI_INDEX_LIMIT_TAG_SIZE) +#define BOOST_MULTI_INDEX_LIMIT_TAG_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif + +#if BOOST_MULTI_INDEX_LIMIT_TAG_SIZE +struct is_tag +{ + BOOST_STATIC_CONSTANT(bool,value=(is_base_and_derived::value)); +}; + +} /* namespace multi_index::detail */ + +template< + BOOST_PP_ENUM_BINARY_PARAMS( + BOOST_MULTI_INDEX_TAG_SIZE, + typename T, + =mpl::na BOOST_PP_INTERCEPT) +> +struct tag:private detail::tag_marker +{ + /* The mpl::transform pass produces shorter symbols (without + * trailing mpl::na's.) + */ + + typedef typename mpl::transform< + mpl::vector, + mpl::identity + >::type type; + + BOOST_STATIC_ASSERT(detail::no_duplicate_tags::value); +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_TAG_SIZE + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index_container.hpp b/3rdParty/Boost/src/boost/multi_index_container.hpp new file mode 100644 index 0000000..9993a8d --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index_container.hpp @@ -0,0 +1,1362 @@ +/* Multiply indexed container. + * + * Copyright 2003-2014 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_HPP +#define BOOST_MULTI_INDEX_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include +#endif + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include +#include +#include +#include +#include +#include +#include +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) +#include +#define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x) \ + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ + detail::make_obj_guard(x,&multi_index_container::check_invariant_); \ + BOOST_JOIN(check_invariant_,__LINE__).touch(); +#define BOOST_MULTI_INDEX_CHECK_INVARIANT \ + BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(*this) +#else +#define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x) +#define BOOST_MULTI_INDEX_CHECK_INVARIANT +#endif + +namespace boost{ + +namespace multi_index{ + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +#pragma warning(push) +#pragma warning(disable:4522) /* spurious warning on multiple operator=()'s */ +#endif + +template +class multi_index_container: + private ::boost::base_from_member< + typename boost::detail::allocator::rebind_to< + Allocator, + typename detail::multi_index_node_type< + Value,IndexSpecifierList,Allocator>::type + >::type>, + BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder< + typename boost::detail::allocator::rebind_to< + Allocator, + typename detail::multi_index_node_type< + Value,IndexSpecifierList,Allocator>::type + >::type::pointer, + multi_index_container >, + public detail::multi_index_base_type< + Value,IndexSpecifierList,Allocator>::type +{ +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the + * lifetime of const references bound to temporaries --precisely what + * scopeguards are. + */ + +#pragma parse_mfunc_templ off +#endif + +private: + BOOST_COPYABLE_AND_MOVABLE(multi_index_container) + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template friend class detail::index_base; + template friend struct detail::header_holder; + template friend struct detail::converter; +#endif + + typedef typename detail::multi_index_base_type< + Value,IndexSpecifierList,Allocator>::type super; + typedef typename + boost::detail::allocator::rebind_to< + Allocator, + typename super::node_type + >::type node_allocator; + typedef ::boost::base_from_member< + node_allocator> bfm_allocator; + typedef detail::header_holder< + typename node_allocator::pointer, + multi_index_container> bfm_header; + + +public: + /* All types are inherited from super, a few are explicitly + * brought forward here to save us some typename's. + */ + + typedef typename super::ctor_args_list ctor_args_list; + typedef IndexSpecifierList index_specifier_type_list; + + typedef typename super::index_type_list index_type_list; + + typedef typename super::iterator_type_list iterator_type_list; + 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::iterator iterator; + typedef typename super::const_iterator const_iterator; + + BOOST_STATIC_ASSERT( + detail::no_duplicate_tags_in_index_list::value); + + /* global project() needs to see this publicly */ + + typedef typename super::node_type node_type; + + /* construct/copy/destroy */ + + explicit multi_index_container( + +#if BOOST_WORKAROUND(__IBMCPP__,<=600) + /* VisualAge seems to have an ETI issue with the default values + * for arguments args_list and al. + */ + + const ctor_args_list& args_list= + typename mpl::identity::type:: + ctor_args_list(), + const allocator_type& al= + typename mpl::identity::type:: + allocator_type()): +#else + const ctor_args_list& args_list=ctor_args_list(), + const allocator_type& al=allocator_type()): +#endif + + bfm_allocator(al), + super(args_list,bfm_allocator::member), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } + + explicit multi_index_container(const allocator_type& al): + bfm_allocator(al), + super(ctor_args_list(),bfm_allocator::member), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } + + template + multi_index_container( + InputIterator first,InputIterator last, + +#if BOOST_WORKAROUND(__IBMCPP__,<=600) + /* VisualAge seems to have an ETI issue with the default values + * for arguments args_list and al. + */ + + const ctor_args_list& args_list= + typename mpl::identity::type:: + ctor_args_list(), + const allocator_type& al= + typename mpl::identity::type:: + allocator_type()): +#else + const ctor_args_list& args_list=ctor_args_list(), + const allocator_type& al=allocator_type()): +#endif + + bfm_allocator(al), + super(args_list,bfm_allocator::member), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + BOOST_TRY{ + iterator hint=super::end(); + for(;first!=last;++first){ + hint=super::make_iterator( + insert_ref_(*first,hint.get_node()).first); + ++hint; + } + } + BOOST_CATCH(...){ + clear_(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + multi_index_container( + std::initializer_list list, + const ctor_args_list& args_list=ctor_args_list(), + const allocator_type& al=allocator_type()): + bfm_allocator(al), + super(args_list,bfm_allocator::member), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + BOOST_TRY{ + typedef const Value* init_iterator; + + iterator hint=super::end(); + for(init_iterator first=list.begin(),last=list.end(); + first!=last;++first){ + hint=super::make_iterator(insert_(*first,hint.get_node()).first); + ++hint; + } + } + BOOST_CATCH(...){ + clear_(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } +#endif + + multi_index_container( + const multi_index_container& x): + bfm_allocator(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; + } + + multi_index_container(BOOST_RV_REF(multi_index_container) x): + bfm_allocator(x.bfm_allocator::member), + 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); + swap_elements_(x); + } + + ~multi_index_container() + { + delete_all_nodes_(); + } + +#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) + /* As per http://www.boost.org/doc/html/move/emulation_limitations.html + * #move.emulation_limitations.assignment_operator + */ + + multi_index_container& operator=( + const multi_index_container& x) + { + multi_index_container y(x); + this->swap(y); + return *this; + } +#endif + + multi_index_container& operator=( + BOOST_COPY_ASSIGN_REF(multi_index_container) x) + { + multi_index_container y(x); + this->swap(y); + return *this; + } + + multi_index_container& operator=( + BOOST_RV_REF(multi_index_container) x) + { + this->swap(x); + return *this; + } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + multi_index_container& operator=( + std::initializer_list list) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + typedef const Value* init_iterator; + + multi_index_container x(*this,detail::do_not_copy_elements_tag()); + iterator hint=x.end(); + for(init_iterator first=list.begin(),last=list.end(); + first!=last;++first){ + hint=x.make_iterator(x.insert_(*first,hint.get_node()).first); + ++hint; + } + x.swap_elements_(*this); + return*this; + } +#endif + + allocator_type get_allocator()const BOOST_NOEXCEPT + { + return allocator_type(bfm_allocator::member); + } + + /* retrieval of indices by number */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATES) + template + struct nth_index + { + BOOST_STATIC_ASSERT(N>=0&&N::type::value); + typedef typename mpl::at_c::type type; + }; + + template + typename nth_index::type& get()BOOST_NOEXCEPT + { + BOOST_STATIC_ASSERT(N>=0&&N::type::value); + return *this; + } + + template + const typename nth_index::type& get()const BOOST_NOEXCEPT + { + BOOST_STATIC_ASSERT(N>=0&&N::type::value); + return *this; + } +#endif + + /* retrieval of indices by tag */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATES) + template + struct index + { + typedef typename mpl::find_if< + index_type_list, + detail::has_tag + >::type iter; + + BOOST_STATIC_CONSTANT( + bool,index_found=!(is_same::type >::value)); + BOOST_STATIC_ASSERT(index_found); + + typedef typename mpl::deref::type type; + }; + + template + typename index::type& get()BOOST_NOEXCEPT + { + return *this; + } + + template + const typename index::type& get()const BOOST_NOEXCEPT + { + return *this; + } +#endif + + /* projection of iterators by number */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATES) + template + struct nth_index_iterator + { + typedef typename nth_index::type::iterator type; + }; + + template + struct nth_index_const_iterator + { + typedef typename nth_index::type::const_iterator type; + }; + + template + typename nth_index_iterator::type project(IteratorType it) + { + typedef typename nth_index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */ + BOOST_STATIC_ASSERT( + (mpl::contains::value)); +#endif + + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); + BOOST_MULTI_INDEX_CHECK_IS_OWNER( + it,static_cast(*this)); + + return index_type::make_iterator(static_cast(it.get_node())); + } + + template + typename nth_index_const_iterator::type project(IteratorType it)const + { + typedef typename nth_index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */ + BOOST_STATIC_ASSERT(( + mpl::contains::value|| + mpl::contains::value)); +#endif + + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); + BOOST_MULTI_INDEX_CHECK_IS_OWNER( + it,static_cast(*this)); + return index_type::make_iterator(static_cast(it.get_node())); + } +#endif + + /* projection of iterators by tag */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATES) + template + struct index_iterator + { + typedef typename index::type::iterator type; + }; + + template + struct index_const_iterator + { + typedef typename index::type::const_iterator type; + }; + + template + typename index_iterator::type project(IteratorType it) + { + typedef typename index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */ + BOOST_STATIC_ASSERT( + (mpl::contains::value)); +#endif + + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); + BOOST_MULTI_INDEX_CHECK_IS_OWNER( + it,static_cast(*this)); + return index_type::make_iterator(static_cast(it.get_node())); + } + + template + typename index_const_iterator::type project(IteratorType it)const + { + typedef typename index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */ + BOOST_STATIC_ASSERT(( + mpl::contains::value|| + mpl::contains::value)); +#endif + + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it); + BOOST_MULTI_INDEX_CHECK_IS_OWNER( + it,static_cast(*this)); + return index_type::make_iterator(static_cast(it.get_node())); + } +#endif + +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: + typedef typename super::copy_map_type copy_map_type; + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + multi_index_container( + const multi_index_container& x, + detail::do_not_copy_elements_tag): + bfm_allocator(x.bfm_allocator::member), + bfm_header(), + super(x,detail::do_not_copy_elements_tag()), + node_count(0) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + } +#endif + + node_type* header()const + { + return &*bfm_header::member; + } + + node_type* allocate_node() + { + return &*bfm_allocator::member.allocate(1); + } + + void deallocate_node(node_type* x) + { + typedef typename node_allocator::pointer node_pointer; + bfm_allocator::member.deallocate(static_cast(x),1); + } + + bool empty_()const + { + return node_count==0; + } + + std::size_t size_()const + { + return node_count; + } + + std::size_t max_size_()const + { + return static_cast(-1); + } + + template + std::pair insert_(const Value& v,Variant variant) + { + node_type* x=0; + node_type* res=super::insert_(v,x,variant); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + return std::pair(res,false); + } + } + + std::pair insert_(const Value& v) + { + return insert_(v,detail::lvalue_tag()); + } + + std::pair insert_rv_(const Value& v) + { + return insert_(v,detail::rvalue_tag()); + } + + template + std::pair insert_ref_(T& t) + { + node_type* x=allocate_node(); + BOOST_TRY{ + new(&x->value()) value_type(t); + BOOST_TRY{ + node_type* res=super::insert_(x->value(),x,detail::emplaced_tag()); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + boost::detail::allocator::destroy(&x->value()); + deallocate_node(x); + return std::pair(res,false); + } + } + BOOST_CATCH(...){ + boost::detail::allocator::destroy(&x->value()); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH(...){ + deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + std::pair insert_ref_(const value_type& x) + { + return insert_(x); + } + + std::pair insert_ref_(value_type& x) + { + return insert_(x); + } + + template + std::pair emplace_( + BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + node_type* x=allocate_node(); + BOOST_TRY{ + detail::vartempl_placement_new( + &x->value(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + BOOST_TRY{ + node_type* res=super::insert_(x->value(),x,detail::emplaced_tag()); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + boost::detail::allocator::destroy(&x->value()); + deallocate_node(x); + return std::pair(res,false); + } + } + BOOST_CATCH(...){ + boost::detail::allocator::destroy(&x->value()); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH(...){ + deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + template + std::pair insert_( + const Value& v,node_type* position,Variant variant) + { + node_type* x=0; + node_type* res=super::insert_(v,position,x,variant); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + return std::pair(res,false); + } + } + + std::pair insert_(const Value& v,node_type* position) + { + return insert_(v,position,detail::lvalue_tag()); + } + + std::pair insert_rv_(const Value& v,node_type* position) + { + return insert_(v,position,detail::rvalue_tag()); + } + + template + std::pair insert_ref_( + T& t,node_type* position) + { + node_type* x=allocate_node(); + BOOST_TRY{ + new(&x->value()) value_type(t); + BOOST_TRY{ + node_type* res=super::insert_( + x->value(),position,x,detail::emplaced_tag()); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + boost::detail::allocator::destroy(&x->value()); + deallocate_node(x); + return std::pair(res,false); + } + } + BOOST_CATCH(...){ + boost::detail::allocator::destroy(&x->value()); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH(...){ + deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + std::pair insert_ref_( + const value_type& x,node_type* position) + { + return insert_(x,position); + } + + std::pair insert_ref_( + value_type& x,node_type* position) + { + return insert_(x,position); + } + + template + std::pair emplace_hint_( + node_type* position, + BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + node_type* x=allocate_node(); + BOOST_TRY{ + detail::vartempl_placement_new( + &x->value(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + BOOST_TRY{ + node_type* res=super::insert_( + x->value(),position,x,detail::emplaced_tag()); + if(res==x){ + ++node_count; + return std::pair(res,true); + } + else{ + boost::detail::allocator::destroy(&x->value()); + deallocate_node(x); + return std::pair(res,false); + } + } + BOOST_CATCH(...){ + boost::detail::allocator::destroy(&x->value()); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH(...){ + deallocate_node(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + void erase_(node_type* x) + { + --node_count; + super::erase_(x); + deallocate_node(x); + } + + void delete_node_(node_type* x) + { + super::delete_node_(x); + deallocate_node(x); + } + + void delete_all_nodes_() + { + super::delete_all_nodes_(); + } + + void clear_() + { + delete_all_nodes_(); + super::clear_(); + node_count=0; + } + + void swap_(multi_index_container& x) + { + if(bfm_allocator::member!=x.bfm_allocator::member){ + detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member); + } + std::swap(bfm_header::member,x.bfm_header::member); + super::swap_(x); + std::swap(node_count,x.node_count); + } + + void swap_elements_( + multi_index_container& x) + { + std::swap(bfm_header::member,x.bfm_header::member); + super::swap_elements_(x); + std::swap(node_count,x.node_count); + } + + bool replace_(const Value& k,node_type* x) + { + return super::replace_(k,x,detail::lvalue_tag()); + } + + bool replace_rv_(const Value& k,node_type* x) + { + return super::replace_(k,x,detail::rvalue_tag()); + } + + template + bool modify_(Modifier& mod,node_type* x) + { + mod(const_cast(x->value())); + + BOOST_TRY{ + if(!super::modify_(x)){ + deallocate_node(x); + --node_count; + return false; + } + else return true; + } + BOOST_CATCH(...){ + deallocate_node(x); + --node_count; + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + template + bool modify_(Modifier& mod,Rollback& back_,node_type* x) + { + mod(const_cast(x->value())); + + bool b; + BOOST_TRY{ + b=super::modify_rollback_(x); + } + BOOST_CATCH(...){ + BOOST_TRY{ + back_(const_cast(x->value())); + BOOST_RETHROW; + } + BOOST_CATCH(...){ + this->erase_(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH_END + + BOOST_TRY{ + if(!b){ + back_(const_cast(x->value())); + return false; + } + else return true; + } + BOOST_CATCH(...){ + this->erase_(x); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* serialization */ + + friend class boost::serialization::access; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + typedef typename super::index_saver_type index_saver_type; + typedef typename super::index_loader_type index_loader_type; + + template + void save(Archive& ar,const unsigned int version)const + { + const serialization::collection_size_type s(size_()); + const detail::serialization_version value_version; + ar< + void load(Archive& ar,const unsigned int version) + { + BOOST_MULTI_INDEX_CHECK_INVARIANT; + + clear_(); + serialization::collection_size_type s; + detail::serialization_version value_version; + if(version<1){ + std::size_t sz; + ar>>serialization::make_nvp("count",sz); + s=static_cast(sz); + } + else{ + ar>>serialization::make_nvp("count",s); + } + if(version<2){ + value_version=0; + } + else{ + ar>>serialization::make_nvp("value_version",value_version); + } + + index_loader_type lm(bfm_allocator::member,s); + + for(std::size_t n=0;n value("item",ar,value_version); + std::pair p=insert_( + value.get(),super::end().get_node()); + if(!p.second)throw_exception( + archive::archive_exception( + archive::archive_exception::other_exception)); + ar.reset_object_address(&p.first->value(),&value.get()); + lm.add(p.first,ar,version); + } + lm.add_track(header(),ar,version); + + super::load_(ar,version,lm); + } +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + /* invariant stuff */ + + bool invariant_()const + { + return super::invariant_(); + } + + void check_invariant_()const + { + BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_()); + } +#endif + +private: + std::size_t node_count; + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +#pragma parse_mfunc_templ reset +#endif +}; + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +#pragma warning(pop) /* C4522 */ +#endif + +/* retrieval of indices by number */ + +template +struct nth_index +{ + BOOST_STATIC_CONSTANT( + int, + M=mpl::size::type::value); + BOOST_STATIC_ASSERT(N>=0&&N::type type; +}; + +template +typename nth_index< + multi_index_container,N>::type& +get( + multi_index_container& m)BOOST_NOEXCEPT +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename nth_index< + multi_index_container< + Value,IndexSpecifierList,Allocator>, + N + >::type index_type; + + BOOST_STATIC_ASSERT(N>=0&& + N< + mpl::size< + BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list + >::type::value); + + return detail::converter::index(m); +} + +template +const typename nth_index< + multi_index_container,N>::type& +get( + const multi_index_container& m +)BOOST_NOEXCEPT +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename nth_index< + multi_index_container< + Value,IndexSpecifierList,Allocator>, + N + >::type index_type; + + BOOST_STATIC_ASSERT(N>=0&& + N< + mpl::size< + BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list + >::type::value); + + return detail::converter::index(m); +} + +/* retrieval of indices by tag */ + +template +struct index +{ + typedef typename MultiIndexContainer::index_type_list index_type_list; + + typedef typename mpl::find_if< + index_type_list, + detail::has_tag + >::type iter; + + BOOST_STATIC_CONSTANT( + bool,index_found=!(is_same::type >::value)); + BOOST_STATIC_ASSERT(index_found); + + typedef typename mpl::deref::type type; +}; + +template< + typename Tag,typename Value,typename IndexSpecifierList,typename Allocator +> +typename ::boost::multi_index::index< + multi_index_container,Tag>::type& +get( + multi_index_container& m)BOOST_NOEXCEPT +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename ::boost::multi_index::index< + multi_index_container< + Value,IndexSpecifierList,Allocator>, + Tag + >::type index_type; + + return detail::converter::index(m); +} + +template< + typename Tag,typename Value,typename IndexSpecifierList,typename Allocator +> +const typename ::boost::multi_index::index< + multi_index_container,Tag>::type& +get( + const multi_index_container& m +)BOOST_NOEXCEPT +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename ::boost::multi_index::index< + multi_index_container< + Value,IndexSpecifierList,Allocator>, + Tag + >::type index_type; + + return detail::converter::index(m); +} + +/* projection of iterators by number */ + +template +struct nth_index_iterator +{ + typedef typename nth_index::type::iterator type; +}; + +template +struct nth_index_const_iterator +{ + typedef typename nth_index::type::const_iterator type; +}; + +template< + int N,typename IteratorType, + typename Value,typename IndexSpecifierList,typename Allocator> +typename nth_index_iterator< + multi_index_container,N>::type +project( + multi_index_container& m, + IteratorType it) +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename nth_index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */ + BOOST_STATIC_ASSERT(( + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list, + IteratorType>::value)); +#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 + + return detail::converter::iterator( + m,static_cast(it.get_node())); +} + +template< + int N,typename IteratorType, + typename Value,typename IndexSpecifierList,typename Allocator> +typename nth_index_const_iterator< + multi_index_container,N>::type +project( + const multi_index_container& m, + IteratorType it) +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename nth_index::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */ + BOOST_STATIC_ASSERT(( + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list, + IteratorType>::value|| + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list, + IteratorType>::value)); +#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 + + return detail::converter::const_iterator( + m,static_cast(it.get_node())); +} + +/* projection of iterators by tag */ + +template +struct index_iterator +{ + typedef typename ::boost::multi_index::index< + MultiIndexContainer,Tag>::type::iterator type; +}; + +template +struct index_const_iterator +{ + typedef typename ::boost::multi_index::index< + MultiIndexContainer,Tag>::type::const_iterator type; +}; + +template< + typename Tag,typename IteratorType, + typename Value,typename IndexSpecifierList,typename Allocator> +typename index_iterator< + multi_index_container,Tag>::type +project( + multi_index_container& m, + IteratorType it) +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename ::boost::multi_index::index< + multi_index_type,Tag>::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */ + BOOST_STATIC_ASSERT(( + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list, + IteratorType>::value)); +#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 + + return detail::converter::iterator( + m,static_cast(it.get_node())); +} + +template< + typename Tag,typename IteratorType, + typename Value,typename IndexSpecifierList,typename Allocator> +typename index_const_iterator< + multi_index_container,Tag>::type +project( + const multi_index_container& m, + IteratorType it) +{ + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> multi_index_type; + typedef typename ::boost::multi_index::index< + multi_index_type,Tag>::type index_type; + +#if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */ + BOOST_STATIC_ASSERT(( + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list, + IteratorType>::value|| + mpl::contains< + BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list, + IteratorType>::value)); +#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 + + return detail::converter::const_iterator( + m,static_cast(it.get_node())); +} + +/* Comparison. Simple forward to first index. */ + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator==( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)==get<0>(y); +} + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator<( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)(y); +} + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator!=( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)!=get<0>(y); +} + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator>( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)>get<0>(y); +} + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator>=( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)>=get<0>(y); +} + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator<=( + const multi_index_container& x, + const multi_index_container& y) +{ + return get<0>(x)<=get<0>(y); +} + +/* specialized algorithms */ + +template +void swap( + multi_index_container& x, + multi_index_container& y) +{ + x.swap(y); +} + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +/* class version = 1 : we now serialize the size through + * boost::serialization::collection_size_type. + * class version = 2 : proper use of {save|load}_construct_data. + */ + +namespace serialization { +template +struct version< + boost::multi_index_container +> +{ + BOOST_STATIC_CONSTANT(int,value=2); +}; +} /* namespace serialization */ +#endif + +/* Associated global functions are promoted to namespace boost, except + * comparison operators and swap, which are meant to be Koenig looked-up. + */ + +using multi_index::get; +using multi_index::project; + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_CHECK_INVARIANT +#undef BOOST_MULTI_INDEX_CHECK_INVARIANT_OF + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index_container_fwd.hpp b/3rdParty/Boost/src/boost/multi_index_container_fwd.hpp new file mode 100644 index 0000000..b35acad --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index_container_fwd.hpp @@ -0,0 +1,121 @@ +/* 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 http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include /* keep it first to prevent nasty warns in MSVC */ +#include +#include +#include +#include + +namespace boost{ + +namespace multi_index{ + +/* Default value for IndexSpecifierList specifies a container + * equivalent to std::set. + */ + +template< + typename Value, + typename IndexSpecifierList=indexed_by > >, + typename Allocator=std::allocator > +class multi_index_container; + +template +struct nth_index; + +template +struct index; + +template +struct nth_index_iterator; + +template +struct nth_index_const_iterator; + +template +struct index_iterator; + +template +struct index_const_iterator; + +/* get and project functions not fwd declared due to problems + * with dependent typenames + */ + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator==( + const multi_index_container& x, + const multi_index_container& y); + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator<( + const multi_index_container& x, + const multi_index_container& y); + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator!=( + const multi_index_container& x, + const multi_index_container& y); + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator>( + const multi_index_container& x, + const multi_index_container& y); + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator>=( + const multi_index_container& x, + const multi_index_container& y); + +template< + typename Value1,typename IndexSpecifierList1,typename Allocator1, + typename Value2,typename IndexSpecifierList2,typename Allocator2 +> +bool operator<=( + const multi_index_container& x, + const multi_index_container& y); + +template +void swap( + multi_index_container& x, + multi_index_container& y); + +} /* namespace multi_index */ + +/* multi_index_container, being the main type of this library, is promoted to + * namespace boost. + */ + +using multi_index::multi_index_container; + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/update.sh b/3rdParty/Boost/update.sh index afa7722..43a3cff 100755 --- a/3rdParty/Boost/update.sh +++ b/3rdParty/Boost/update.sh @@ -31,6 +31,10 @@ fi lambda/lambda.hpp \ lambda/bind.hpp \ logic/tribool.hpp \ + multi_index_container.hpp \ + multi_index/hashed_index.hpp \ + multi_index/member.hpp \ + multi_index/sequenced_index.hpp \ noncopyable.hpp \ numeric/conversion/cast.hpp \ optional.hpp \ @@ -70,7 +74,7 @@ cp $1/LICENSE_1_0.txt $TARGET_DIR rm -rf $TARGET_DIR/libs/config rm -rf $TARGET_DIR/libs/smart_ptr -LIBS="date_time regex system thread signals2 filesystem program_options serialization archive atomic" +LIBS="date_time regex system thread signals2 filesystem multi_index program_options serialization archive atomic" for lib in $LIBS; do rm -rf $TARGET_DIR/libs/$lib/build $TARGET_DIR/libs/$lib/*.doc $TARGET_DIR/libs/$lib/src/*.doc $TARGET_DIR/libs/$lib/src/CMakeLists.txt $TARGET_DIR/libs/$lib/test done diff --git a/Swiften/Base/LRUCache.h b/Swiften/Base/LRUCache.h new file mode 100644 index 0000000..e4e652f --- /dev/null +++ b/Swiften/Base/LRUCache.h @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2017 Isode Limited. + * All rights reserved. + * See the COPYING file for more information. + */ + +#pragma once + +#include +#include + +#include +#include +#include +#include +#include + +namespace Swift { + + +/** + * The \ref LRUCache templaged class implements a lookup cache which removes + * the least recently used cached item from the cache, if the cache size hits + * the \ref MAX_SIZE limit. + * + * An example use is a cache for entity capabilities hash to DiscoInfo. + */ +template +class LRUCache { +public: + using cacheMissFunction = std::function(const KEY_TYPE& )>; + +public: + /** + * Inserts the key/value pair in the front of the cache. If the \ref key + * already exists in the cache, it is moved to the front instead. If + * afterwards, the cahe size exceeds the \ref MAX_SIZE limit, the least + * recently item is removed from the cache. + */ + void insert(const KEY_TYPE& key, VALUE_TYPE value) { + auto pushResult = cache.push_front(entry_t(key, value)); + if (!pushResult.second) { + cache.relocate(cache.begin(), pushResult.first); + } + else if (cache.size() > MAX_SIZE) { + cache.pop_back(); + } + } + + /** + * Looks up a cache entry based on the provided \ref key and moves it back + * to the front of the cache. If there is no cache entry for the provided + * \ref key, an uninitialized \ref boost::optional is returned. + * If the optional \ref missFunction is provided, it is called on a cache miss. + * If the \ref missFunction returns an initialized \ref boost::optional, the + * value is inserted in the cache. + */ + boost::optional get(const KEY_TYPE& key, cacheMissFunction missFunction = cacheMissFunction()) { + boost::optional cachedValue; + auto cacheItemIterator = boost::multi_index::get<1>(cache).find(key); + if (cacheItemIterator != boost::multi_index::get<1>(cache).end()) { + cachedValue = cacheItemIterator->second; + cache.relocate(cache.begin(), cache.iterator_to(*cacheItemIterator)); + } + else if (missFunction && (cachedValue = missFunction(key))) { + insert(key, cachedValue.get()); + } + return cachedValue; + } + +private: + using entry_t = std::pair; + +private: + boost::multi_index_container< entry_t, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::hashed_unique< + BOOST_MULTI_INDEX_MEMBER(entry_t, KEY_TYPE, first)> > > cache; +}; + +} diff --git a/Swiften/Base/LogSerializers.cpp b/Swiften/Base/LogSerializers.cpp index ccc8437..5ac1e15 100644 --- a/Swiften/Base/LogSerializers.cpp +++ b/Swiften/Base/LogSerializers.cpp @@ -66,3 +66,13 @@ std::ostream& operator<<(std::ostream& stream, const Presence& presence) { } }; + +::std::ostream& operator<<(::std::ostream& os, const boost::optional& optStr) { + if (optStr.is_initialized()) { + return os << "boost::optional(\"" << optStr.get() << "\")"; + } + else { + return os << "boost::optional()"; + } +} + diff --git a/Swiften/Base/LogSerializers.h b/Swiften/Base/LogSerializers.h index 3d60426..be992bb 100644 --- a/Swiften/Base/LogSerializers.h +++ b/Swiften/Base/LogSerializers.h @@ -11,6 +11,8 @@ #include #include +#include + namespace Swift { class Presence; @@ -45,3 +47,6 @@ std::ostream& operator<<(std::ostream& stream, const std::vector& vec) { std::ostream& operator<<(std::ostream& stream, const Presence& presence); }; + +::std::ostream& operator<<(::std::ostream& os, const boost::optional& optStr); + diff --git a/Swiften/Base/UnitTest/LRUCacheTest.cpp b/Swiften/Base/UnitTest/LRUCacheTest.cpp new file mode 100644 index 0000000..7d54c5c --- /dev/null +++ b/Swiften/Base/UnitTest/LRUCacheTest.cpp @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2017 Isode Limited. + * All rights reserved. + * See the COPYING file for more information. + */ + +#include + +#include + +#include +#include + +#include // This has to go after Swiften/Base/LogSerializers.h. + +using namespace Swift; +namespace b = boost; + +TEST(LRUCacheTest, testCacheLimit) { + LRUCache testling; + + testling.insert("A", "AA"); + testling.insert("B", "BB"); + testling.insert("C", "CC"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional(), testling.get("D")); + + testling.insert("D", "DD"); + + ASSERT_EQ(b::optional(), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional("DD"), testling.get("D")); +} + +TEST(LRUCacheTest, testMoveRecentToFrontOnGet) { + LRUCache testling; + + testling.insert("A", "AA"); + testling.insert("B", "BB"); + testling.insert("C", "CC"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional(), testling.get("D")); + ASSERT_EQ(b::optional("AA"), testling.get("A")); + + testling.insert("D", "DD"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional(), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional("DD"), testling.get("D")); +} + +TEST(LRUCacheTest, testMoveRecentToFrontOnReinsert) { + LRUCache testling; + + testling.insert("A", "AA"); + testling.insert("B", "BB"); + testling.insert("C", "CC"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional(), testling.get("D")); + + testling.insert("B", "BB"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional(), testling.get("D")); + + testling.insert("D", "DD"); + + ASSERT_EQ(b::optional(), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + ASSERT_EQ(b::optional("DD"), testling.get("D")); +} + +TEST(LRUCacheTest, testCacheReturnsValuesPreviouslyInserted) { + LRUCache testling; + + testling.insert("A", "AA"); + testling.insert("B", "BB"); + testling.insert("C", "CC"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + ASSERT_EQ(b::optional("CC"), testling.get("C")); +} + +TEST(LRUCacheTest, testCacheMissFunctionIsUsedOnCacheMiss) { + LRUCache testling; + + testling.insert("A", "AA"); + testling.insert("B", "BB"); + + ASSERT_EQ(b::optional("AA"), testling.get("A")); + ASSERT_EQ(b::optional("BB"), testling.get("B")); + + ASSERT_EQ(b::optional("CC"), testling.get("C", [](const std::string&) { + return boost::optional(std::string("CC")); + })); + ASSERT_EQ(b::optional("CC"), testling.get("C")); + + ASSERT_EQ(b::optional(), testling.get("D", [](const std::string&) { + return boost::optional(); + })); + ASSERT_EQ(b::optional(), testling.get("D")); +} diff --git a/Swiften/SConscript b/Swiften/SConscript index a8fb88a..1103362 100644 --- a/Swiften/SConscript +++ b/Swiften/SConscript @@ -368,6 +368,7 @@ if env["SCONS_STAGE"] == "build" : File("Avatars/UnitTest/CombinedAvatarProviderTest.cpp"), File("Avatars/UnitTest/AvatarManagerImplTest.cpp"), File("Base/UnitTest/IDGeneratorTest.cpp"), + File("Base/UnitTest/LRUCacheTest.cpp"), File("Base/UnitTest/SimpleIDGeneratorTest.cpp"), File("Base/UnitTest/StringTest.cpp"), File("Base/UnitTest/DateTimeTest.cpp"), -- cgit v0.10.2-6-g49f6