boost/interprocess/containers/container/detail/algorithms.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2008.
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 // (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/container for documentation.
  10 //
  11 //////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_CONTAINERS_DETAIL_ALGORITHMS_HPP
  14 #define BOOST_CONTAINERS_DETAIL_ALGORITHMS_HPP
  15
  16 #if (defined _MSC_VER) && (_MSC_VER >= 1200)
  17 #  pragma once
  18 #endif
  19
  20 #include <boost/interprocess/containers/container/detail/config_begin.hpp>
  21 #include <boost/interprocess/containers/container/detail/workaround.hpp>
  22
  23 #include <boost/type_traits/has_trivial_copy.hpp>
  24 #include <boost/type_traits/has_trivial_assign.hpp>
  25 #include <boost/detail/no_exceptions_support.hpp>
  26 #include <boost/get_pointer.hpp>
  27
  28 #include <boost/interprocess/containers/container/detail/type_traits.hpp>
  29 #include <boost/interprocess/containers/container/detail/mpl.hpp>
  30 #include <boost/interprocess/containers/container/detail/iterators.hpp>
  31
  32
  33 #include <cstring>
  34
  35 namespace boost {
  36 namespace interprocess_container {
  37
  38 #if !defined(BOOST_HAS_RVALUE_REFS)
  39 template<class T>
  40 struct has_own_construct_from_it
  41 {
  42    static const bool value = false;
  43 };
  44
  45 namespace containers_detail  {
  46
  47 template<class T, class InpIt>
  48 inline void construct_in_place_impl(T* dest, const InpIt &source, containers_detail::true_)
  49 {
  50    T::construct(dest, *source);
  51 }
  52
  53 template<class T, class InpIt>
  54 inline void construct_in_place_impl(T* dest, const InpIt &source, containers_detail::false_)
  55 {
  56    new((void*)dest)T(*source);
  57 }
  58
  59 }  //namespace containers_detail   {
  60
  61 template<class T, class InpIt>
  62 inline void construct_in_place(T* dest, InpIt source)
  63 {
  64    typedef containers_detail::bool_<has_own_construct_from_it<T>::value> boolean_t;
  65    containers_detail::construct_in_place_impl(dest, source, boolean_t());
  66 }
  67
  68 #else
  69 template<class T, class InpIt>
  70 inline void construct_in_place(T* dest, InpIt source)
  71 {     ::new((void*)dest)T(*source);   }
  72 #endif
  73
  74 template<class T, class U, class D>
  75 inline void construct_in_place(T *dest, default_construct_iterator<U, D>)
  76 {
  77    ::new((void*)dest)T();
  78 }
  79
  80 template<class T, class U, class E>
  81 inline void construct_in_place(T *dest, emplace_iterator<U, E> ei)
  82 {
  83    ei.construct_in_place(dest);
  84 }
  85
  86 template<class InIt, class OutIt>
  87 struct optimize_assign
  88 {
  89    static const bool value = false;
  90 };
  91
  92 template<class T>
  93 struct optimize_assign<const T*, T*>
  94 {
  95    static const bool value = boost::has_trivial_assign<T>::value;
  96 };
  97
  98 template<class T>
  99 struct optimize_assign<T*, T*>
 100    :  public optimize_assign<const T*, T*>
 101 {};
 102
 103 template<class InIt, class OutIt>
 104 struct optimize_copy
 105 {
 106    static const bool value = false;
 107 };
 108
 109 template<class T>
 110 struct optimize_copy<const T*, T*>
 111 {
 112    static const bool value = boost::has_trivial_copy<T>::value;
 113 };
 114
 115 template<class T>
 116 struct optimize_copy<T*, T*>
 117    :  public optimize_copy<const T*, T*>
 118 {};
 119
 120 template<class InIt, class OutIt> inline
 121 OutIt copy_n_dispatch(InIt first, typename std::iterator_traits<InIt>::difference_type length, OutIt dest, containers_detail::bool_<false>)
 122 {
 123    for (; length--; ++dest, ++first)
 124       *dest = *first;
 125    return dest;
 126 }
 127
 128 template<class T> inline
 129 T *copy_n_dispatch(const T *first, typename std::iterator_traits<const T*>::difference_type length, T *dest, containers_detail::bool_<true>)
 130 {
 131    std::size_t size = length*sizeof(T);
 132    return (static_cast<T*>(std::memmove(dest, first, size))) + size;
 133 }
 134
 135 template<class InIt, class OutIt> inline
 136 OutIt copy_n(InIt first, typename std::iterator_traits<InIt>::difference_type length, OutIt dest)
 137 {
 138    const bool do_optimized_assign = optimize_assign<InIt, OutIt>::value;
 139    return copy_n_dispatch(first, length, dest, containers_detail::bool_<do_optimized_assign>());
 140 }
 141
 142 template<class InIt, class FwdIt> inline
 143 FwdIt uninitialized_copy_n_dispatch
 144    (InIt first,
 145     typename std::iterator_traits<InIt>::difference_type count,
 146     FwdIt dest, containers_detail::bool_<false>)
 147 {
 148    typedef typename std::iterator_traits<FwdIt>::value_type value_type;
 149    //Save initial destination position
 150    FwdIt dest_init = dest;
 151    typename std::iterator_traits<InIt>::difference_type new_count = count+1;
 152
 153    BOOST_TRY{
 154       //Try to build objects
 155       for (; --new_count; ++dest, ++first){
 156          construct_in_place(containers_detail::get_pointer(&*dest), first);
 157       }
 158    }
 159    BOOST_CATCH(...){
 160       //Call destructors
 161       new_count = count - new_count;
 162       for (; new_count--; ++dest_init){
 163          containers_detail::get_pointer(&*dest_init)->~value_type();
 164       }
 165       BOOST_RETHROW
 166    }
 167    BOOST_CATCH_END
 168    return dest;
 169 }
 170 template<class T> inline
 171 T *uninitialized_copy_n_dispatch(const T *first, typename std::iterator_traits<const T*>::difference_type length, T *dest, containers_detail::bool_<true>)
 172 {
 173    std::size_t size = length*sizeof(T);
 174    return (static_cast<T*>(std::memmove(dest, first, size))) + size;
 175 }
 176
 177 template<class InIt, class FwdIt> inline
 178 FwdIt uninitialized_copy_n
 179    (InIt first,
 180     typename std::iterator_traits<InIt>::difference_type count,
 181     FwdIt dest)
 182 {
 183    const bool do_optimized_copy = optimize_copy<InIt, FwdIt>::value;
 184    return uninitialized_copy_n_dispatch(first, count, dest, containers_detail::bool_<do_optimized_copy>());
 185 }
 186
 187 // uninitialized_copy_copy
 188 // Copies [first1, last1) into [result, result + (last1 - first1)), and
 189 // copies [first2, last2) into
 190 // [result + (last1 - first1), result + (last1 - first1) + (last2 - first2)).
 191 template <class InpIt1, class InpIt2, class FwdIt>
 192 FwdIt uninitialized_copy_copy
 193    (InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, FwdIt result)
 194 {
 195    typedef typename std::iterator_traits<FwdIt>::value_type value_type;
 196    FwdIt mid = std::uninitialized_copy(first1, last1, result);
 197    BOOST_TRY {
 198       return std::uninitialized_copy(first2, last2, mid);
 199    }
 200    BOOST_CATCH(...){
 201       for(;result != mid; ++result){
 202          containers_detail::get_pointer(&*result)->~value_type();
 203       }
 204       BOOST_RETHROW
 205    }
 206    BOOST_CATCH_END
 207 }
 208
 209 }  //namespace interprocess_container {
 210 }  //namespace boost {
 211
 212 #include <boost/interprocess/containers/container/detail/config_end.hpp>
 213
 214 #endif   //#ifndef BOOST_CONTAINERS_DETAIL_ALGORITHMS_HPP
 215