diff options
Diffstat (limited to 'boost/multi_index/detail')
-rw-r--r-- | boost/multi_index/detail/bidir_node_iterator.hpp | 3 | ||||
-rw-r--r-- | boost/multi_index/detail/hash_index_iterator.hpp | 1 | ||||
-rw-r--r-- | boost/multi_index/detail/is_transparent.hpp | 135 | ||||
-rw-r--r-- | boost/multi_index/detail/ord_index_ops.hpp | 125 | ||||
-rw-r--r-- | boost/multi_index/detail/promotes_arg.hpp | 83 | ||||
-rw-r--r-- | boost/multi_index/detail/rnd_index_node.hpp | 6 | ||||
-rw-r--r-- | boost/multi_index/detail/rnd_index_ops.hpp | 3 | ||||
-rw-r--r-- | boost/multi_index/detail/rnd_node_iterator.hpp | 3 |
8 files changed, 349 insertions, 10 deletions
diff --git a/boost/multi_index/detail/bidir_node_iterator.hpp b/boost/multi_index/detail/bidir_node_iterator.hpp index 9bb04701f4..9be5ec84b4 100644 --- a/boost/multi_index/detail/bidir_node_iterator.hpp +++ b/boost/multi_index/detail/bidir_node_iterator.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* 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) @@ -41,6 +41,7 @@ class bidir_node_iterator: const typename Node::value_type&> { public: + /* coverity[uninit_ctor]: suppress warning */ bidir_node_iterator(){} explicit bidir_node_iterator(Node* node_):node(node_){} diff --git a/boost/multi_index/detail/hash_index_iterator.hpp b/boost/multi_index/detail/hash_index_iterator.hpp index f8e983dbb4..8d063002a1 100644 --- a/boost/multi_index/detail/hash_index_iterator.hpp +++ b/boost/multi_index/detail/hash_index_iterator.hpp @@ -44,6 +44,7 @@ class hashed_index_iterator: const typename Node::value_type&> { public: + /* coverity[uninit_ctor]: suppress warning */ hashed_index_iterator(){} hashed_index_iterator(Node* node_):node(node_){} diff --git a/boost/multi_index/detail/is_transparent.hpp b/boost/multi_index/detail/is_transparent.hpp new file mode 100644 index 0000000000..72036d257e --- /dev/null +++ b/boost/multi_index/detail/is_transparent.hpp @@ -0,0 +1,135 @@ +/* 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_IS_TRANSPARENT_HPP +#define BOOST_MULTI_INDEX_DETAIL_IS_TRANSPARENT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/bool.hpp> +#include <boost/type_traits/intrinsics.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Metafunction that checks if f(arg,arg2) executes without argument type + * conversion. By default (i.e. when it cannot be determined) it evaluates to + * true. + */ + +template<typename F,typename Arg1,typename Arg2,typename=void> +struct is_transparent:mpl::true_{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#if !defined(BOOST_NO_SFINAE)&&!defined(BOOST_NO_SFINAE_EXPR)&& \ + !defined(BOOST_NO_CXX11_DECLTYPE)&& \ + (defined(BOOST_NO_CXX11_FINAL)||defined(BOOST_IS_FINAL)) + +#include <boost/mpl/and.hpp> +#include <boost/mpl/not.hpp> +#include <boost/mpl/or.hpp> +#include <boost/type_traits/function_traits.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/type_traits/is_final.hpp> +#include <boost/type_traits/is_function.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/remove_pointer.hpp> +#include <boost/utility/declval.hpp> +#include <boost/utility/enable_if.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +struct not_is_transparent_result_type{}; + +template<typename F,typename Arg1,typename Arg2> +struct is_transparent_class_helper:F +{ + using F::operator(); + template<typename T,typename Q> + not_is_transparent_result_type operator()(const T&,const Q&)const; +}; + +template<typename F,typename Arg1,typename Arg2,typename=void> +struct is_transparent_class:mpl::true_{}; + +template<typename F,typename Arg1,typename Arg2> +struct is_transparent_class< + F,Arg1,Arg2, + typename enable_if< + is_same< + decltype( + declval<const is_transparent_class_helper<F,Arg1,Arg2> >()( + declval<const Arg1&>(),declval<const Arg2&>()) + ), + not_is_transparent_result_type + > + >::type +>:mpl::false_{}; + +template<typename F,typename Arg1,typename Arg2> +struct is_transparent< + F,Arg1,Arg2, + typename enable_if< + mpl::and_< + is_class<F>, + mpl::not_<is_final<F> > /* is_transparent_class_helper derives from F */ + > + >::type +>:is_transparent_class<F,Arg1,Arg2>{}; + +template<typename F,typename Arg1,typename Arg2,typename=void> +struct is_transparent_function:mpl::true_{}; + +template<typename F,typename Arg1,typename Arg2> +struct is_transparent_function< + F,Arg1,Arg2, + typename enable_if< + mpl::or_< + mpl::not_<mpl::or_< + is_same<typename function_traits<F>::arg1_type,const Arg1&>, + is_same<typename function_traits<F>::arg1_type,Arg1> + > >, + mpl::not_<mpl::or_< + is_same<typename function_traits<F>::arg2_type,const Arg2&>, + is_same<typename function_traits<F>::arg2_type,Arg2> + > > + > + >::type +>:mpl::false_{}; + +template<typename F,typename Arg1,typename Arg2> +struct is_transparent< + F,Arg1,Arg2, + typename enable_if< + is_function<typename remove_pointer<F>::type> + >::type +>:is_transparent_function<typename remove_pointer<F>::type,Arg1,Arg2>{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif +#endif diff --git a/boost/multi_index/detail/ord_index_ops.hpp b/boost/multi_index/detail/ord_index_ops.hpp index d42f5f1a29..84d5cacae1 100644 --- a/boost/multi_index/detail/ord_index_ops.hpp +++ b/boost/multi_index/detail/ord_index_ops.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* 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) @@ -41,6 +41,8 @@ #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/and.hpp> +#include <boost/multi_index/detail/promotes_arg.hpp> #include <utility> namespace boost{ @@ -51,6 +53,9 @@ namespace detail{ /* Common code for index memfuns having templatized and * non-templatized versions. + * Implementation note: When CompatibleKey is consistently promoted to + * KeyFromValue::result_type for comparison, the promotion is made once in + * advance to increase efficiency. */ template< @@ -61,6 +66,35 @@ inline Node* ordered_index_find( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_find( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_find(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ Node* y0=y; while (top){ @@ -82,6 +116,33 @@ inline Node* ordered_index_lower_bound( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_lower_bound( + top,y,key,x,comp, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(!comp(key(top->value()),x)){ y=top; @@ -101,6 +162,33 @@ inline Node* ordered_index_upper_bound( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_upper_bound( + top,y,key,x,comp, + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(comp(x,key(top->value()))){ y=top; @@ -120,6 +208,35 @@ inline std::pair<Node*,Node*> ordered_index_equal_range( Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, const CompatibleCompare& comp) { + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_equal_range( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_equal_range(top,y,key,x,comp,mpl::false_()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp,mpl::false_) +{ while(top){ if(comp(key(top->value()),x)){ top=Node::from_impl(top->right()); @@ -130,8 +247,10 @@ inline std::pair<Node*,Node*> ordered_index_equal_range( } else{ return std::pair<Node*,Node*>( - ordered_index_lower_bound(Node::from_impl(top->left()),top,key,x,comp), - ordered_index_upper_bound(Node::from_impl(top->right()),y,key,x,comp)); + ordered_index_lower_bound( + Node::from_impl(top->left()),top,key,x,comp,mpl::false_()), + ordered_index_upper_bound( + Node::from_impl(top->right()),y,key,x,comp,mpl::false_())); } } diff --git a/boost/multi_index/detail/promotes_arg.hpp b/boost/multi_index/detail/promotes_arg.hpp new file mode 100644 index 0000000000..75cf4368cf --- /dev/null +++ b/boost/multi_index/detail/promotes_arg.hpp @@ -0,0 +1,83 @@ +/* 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_PROMOTES_ARG_HPP +#define BOOST_MULTI_INDEX_DETAIL_PROMOTES_ARG_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/bool.hpp> +#include <boost/type_traits/intrinsics.hpp> + +/* Metafunctions to check if f(arg1,arg2) promotes either arg1 to the type of + * arg2 or viceversa. By default, (i.e. if it cannot be determined), no + * promotion is assumed. + */ + +#if !defined(BOOST_IS_CONVERTIBLE) + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename F,typename Arg1,typename Arg2> +struct promotes_1st_arg:mpl::false_{}; + +template<typename F,typename Arg1,typename Arg2> +struct promotes_2nd_arg:mpl::false_{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#else + +#include <boost/mpl/and.hpp> +#include <boost/mpl/not.hpp> +#include <boost/multi_index/detail/is_transparent.hpp> +#include <boost/type_traits/is_convertible.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename F,typename Arg1,typename Arg2> +struct promotes_1st_arg: + mpl::and_< + mpl::not_<is_transparent<F,Arg1,Arg2> >, + is_convertible<const Arg1,Arg2>, + is_transparent<F,Arg2,Arg2> + > +{}; + +template<typename F,typename Arg1,typename Arg2> +struct promotes_2nd_arg: + mpl::and_< + mpl::not_<is_transparent<F,Arg1,Arg2> >, + is_convertible<const Arg2,Arg1>, + is_transparent<F,Arg1,Arg1> + > +{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif /* defined(BOOST_IS_CONVERTIBLE) */ +#endif diff --git a/boost/multi_index/detail/rnd_index_node.hpp b/boost/multi_index/detail/rnd_index_node.hpp index 991f6dab80..def057583a 100644 --- a/boost/multi_index/detail/rnd_index_node.hpp +++ b/boost/multi_index/detail/rnd_index_node.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2015 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) @@ -16,7 +16,7 @@ #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> #include <boost/detail/allocator_utilities.hpp> -#include <boost/math/common_factor_rt.hpp> +#include <boost/integer/common_factor_rt.hpp> #include <cstddef> #include <functional> @@ -105,7 +105,7 @@ struct random_access_index_node_impl std::ptrdiff_t n=end-begin; std::ptrdiff_t m=middle-begin; std::ptrdiff_t n_m=n-m; - std::ptrdiff_t p=math::gcd(n,m); + std::ptrdiff_t p=integer::gcd(n,m); for(std::ptrdiff_t i=0;i<p;++i){ pointer tmp=begin[i]; diff --git a/boost/multi_index/detail/rnd_index_ops.hpp b/boost/multi_index/detail/rnd_index_ops.hpp index 6cb030fbc7..d05386d747 100644 --- a/boost/multi_index/detail/rnd_index_ops.hpp +++ b/boost/multi_index/detail/rnd_index_ops.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* Copyright 2003-2015 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) @@ -172,7 +172,6 @@ void random_access_index_sort( if(ptrs.size()<=1)return; - typedef typename Node::value_type value_type; typedef typename Node::impl_pointer impl_pointer; typedef typename Node::impl_ptr_pointer impl_ptr_pointer; typedef random_access_index_sort_compare< diff --git a/boost/multi_index/detail/rnd_node_iterator.hpp b/boost/multi_index/detail/rnd_node_iterator.hpp index 65bf5e8e03..48026132fb 100644 --- a/boost/multi_index/detail/rnd_node_iterator.hpp +++ b/boost/multi_index/detail/rnd_node_iterator.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2013 Joaquin M Lopez Munoz. +/* 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) @@ -39,6 +39,7 @@ class rnd_node_iterator: const typename Node::value_type&> { public: + /* coverity[uninit_ctor]: suppress warning */ rnd_node_iterator(){} explicit rnd_node_iterator(Node* node_):node(node_){} |