ceph/src/boost/boost/poly_collection/detail/packed_segment.hpp

   1 /* Copyright 2016-2017 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/poly_collection for library home page.
   7  */
   8
   9 #ifndef BOOST_POLY_COLLECTION_DETAIL_PACKED_SEGMENT_HPP
  10 #define BOOST_POLY_COLLECTION_DETAIL_PACKED_SEGMENT_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/detail/workaround.hpp>
  17 #include <boost/poly_collection/detail/newdelete_allocator.hpp>
  18 #include <boost/poly_collection/detail/segment_backend.hpp>
  19 #include <boost/poly_collection/detail/value_holder.hpp>
  20 #include <memory>
  21 #include <new>
  22 #include <vector>
  23 #include <utility>
  24
  25 namespace boost{
  26
  27 namespace poly_collection{
  28
  29 namespace detail{
  30
  31 /* segment_backend implementation where value_type& and Concrete& actually refer
  32  * to the same stored entity.
  33  *
  34  * Requires:
  35  *  - [const_]base_iterator is a stride iterator constructible from
  36  *    {value_type*,sizeof(store_value_type)}.
  37  *  - Model provides a function value_ptr for
  38  *    const Concrete* -> const value_type* conversion.
  39  */
  40
  41 template<typename Model,typename Concrete,typename Allocator>
  42 class packed_segment:public segment_backend<Model>
  43 {
  44   using value_type=typename Model::value_type;
  45   using store_value_type=value_holder<Concrete>;
  46   using store=std::vector<
  47     store_value_type,
  48     value_holder_allocator_adaptor<
  49       typename std::allocator_traits<Allocator>::
  50         template rebind_alloc<store_value_type>
  51     >
  52   >;
  53   using store_iterator=typename store::iterator;
  54   using const_store_iterator=typename store::const_iterator;
  55   using segment_backend=detail::segment_backend<Model>;
  56   using typename segment_backend::segment_backend_unique_ptr;
  57   using typename segment_backend::value_pointer;
  58   using typename segment_backend::const_value_pointer;
  59   using typename segment_backend::base_iterator;
  60   using typename segment_backend::const_base_iterator;
  61   using const_iterator=
  62     typename segment_backend::template const_iterator<Concrete>;
  63   using typename segment_backend::base_sentinel;
  64   using typename segment_backend::range;
  65   using segment_allocator_type=newdelete_allocator_adaptor<
  66     typename std::allocator_traits<Allocator>::
  67       template rebind_alloc<packed_segment>
  68   >;
  69 public:
  70   virtual ~packed_segment()=default;
  71
  72   virtual segment_backend_unique_ptr copy()const
  73   {
  74     return new_(s.get_allocator(),store{s});
  75   }
  76
  77   virtual segment_backend_unique_ptr empty_copy()const
  78   {
  79     return new_(s.get_allocator(),s.get_allocator());
  80   }
  81
  82   virtual bool equal(const segment_backend& x)const
  83   {
  84     return s==static_cast<const packed_segment&>(x).s;
  85   }
  86
  87   virtual base_iterator begin()const noexcept{return nv_begin();}
  88
  89   base_iterator nv_begin()const noexcept
  90   {
  91     return {value_ptr(s.data()),sizeof(store_value_type)};
  92   }
  93
  94   virtual base_iterator end()const noexcept{return nv_end();}
  95
  96   base_iterator nv_end()const noexcept
  97   {
  98     return {value_ptr(s.data()+s.size()),sizeof(store_value_type)};
  99   }
 100
 101   virtual bool          empty()const noexcept{return nv_empty();}
 102   bool                  nv_empty()const noexcept{return s.empty();}
 103   virtual std::size_t   size()const noexcept{return nv_size();}
 104   std::size_t           nv_size()const noexcept{return s.size();}
 105   virtual std::size_t   max_size()const noexcept{return nv_max_size();}
 106   std::size_t           nv_max_size()const noexcept{return s.max_size();}
 107   virtual std::size_t   capacity()const noexcept{return nv_capacity();}
 108   std::size_t           nv_capacity()const noexcept{return s.capacity();}
 109   virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);}
 110   base_sentinel         nv_reserve(std::size_t n)
 111                           {s.reserve(n);return sentinel();}
 112   virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();}
 113   base_sentinel         nv_shrink_to_fit()
 114                           {s.shrink_to_fit();return sentinel();}
 115
 116   template<typename Iterator,typename... Args>
 117   range nv_emplace(Iterator p,Args&&... args)
 118   {
 119     return range_from(
 120       s.emplace(
 121         iterator_from(p),
 122         value_holder_emplacing_ctor,std::forward<Args>(args)...));
 123   }
 124
 125   template<typename... Args>
 126   range nv_emplace_back(Args&&... args)
 127   {
 128     s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...);
 129     return range_from(s.size()-1);
 130   }
 131
 132   virtual range push_back(const_value_pointer x)
 133   {return nv_push_back(const_concrete_ref(x));}
 134
 135   range nv_push_back(const Concrete& x)
 136   {
 137     s.emplace_back(x);
 138     return range_from(s.size()-1);
 139   }
 140
 141   virtual range push_back_move(value_pointer x)
 142   {return nv_push_back(std::move(concrete_ref(x)));}
 143
 144   range nv_push_back(Concrete&& x)
 145   {
 146     s.emplace_back(std::move(x));
 147     return range_from(s.size()-1);
 148   }
 149
 150   virtual range insert(const_base_iterator p,const_value_pointer x)
 151   {return nv_insert(const_iterator(p),const_concrete_ref(x));}
 152
 153   range nv_insert(const_iterator p,const Concrete& x)
 154   {
 155     return range_from(s.emplace(iterator_from(p),x));
 156   }
 157
 158   virtual range insert_move(const_base_iterator p,value_pointer x)
 159   {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));}
 160
 161   range nv_insert(const_iterator p,Concrete&& x)
 162   {
 163     return range_from(s.emplace(iterator_from(p),std::move(x)));
 164   }
 165
 166   template<typename InputIterator>
 167   range nv_insert(InputIterator first,InputIterator last)
 168   {
 169     return nv_insert(
 170      const_iterator(concrete_ptr(s.data()+s.size())),first,last);
 171   }
 172
 173   template<typename InputIterator>
 174   range nv_insert(const_iterator p,InputIterator first,InputIterator last)
 175   {
 176 #if BOOST_WORKAROUND(BOOST_LIBSTDCXX_VERSION,<40900)
 177     /* std::vector::insert(pos,first,last) returns void rather than iterator */
 178
 179     auto n=const_store_value_type_ptr(p)-s.data();
 180     s.insert(s.begin()+n,first,last);
 181     return range_from(static_cast<std::size_t>(n));
 182 #else
 183     return range_from(s.insert(iterator_from(p),first,last));
 184 #endif
 185   }
 186
 187   virtual range erase(const_base_iterator p)
 188   {return nv_erase(const_iterator(p));}
 189
 190   range nv_erase(const_iterator p)
 191   {
 192     return range_from(s.erase(iterator_from(p)));
 193   }
 194
 195   virtual range erase(const_base_iterator first,const_base_iterator last)
 196   {return nv_erase(const_iterator(first),const_iterator(last));}
 197
 198   range nv_erase(const_iterator first,const_iterator last)
 199   {
 200     return range_from(s.erase(iterator_from(first),iterator_from(last)));
 201   }
 202
 203   virtual range erase_till_end(const_base_iterator first)
 204   {
 205     return range_from(s.erase(iterator_from(first),s.end()));
 206   }
 207
 208   virtual range erase_from_begin(const_base_iterator last)
 209   {
 210     return range_from(s.erase(s.begin(),iterator_from(last)));
 211   }
 212
 213   virtual base_sentinel clear()noexcept{return nv_clear();}
 214   base_sentinel         nv_clear()noexcept{s.clear();return sentinel();}
 215
 216 private:
 217   friend Model;
 218
 219   template<typename... Args>
 220   static segment_backend_unique_ptr new_(
 221     segment_allocator_type al,Args&&... args)
 222   {
 223     auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1);
 224     try{
 225       ::new ((void*)p) packed_segment{std::forward<Args>(args)...};
 226     }
 227     catch(...){
 228       std::allocator_traits<segment_allocator_type>::deallocate(al,p,1);
 229       throw;
 230     }
 231     return {p,&delete_};
 232   }
 233
 234   static void delete_(segment_backend* p)
 235   {
 236     auto q=static_cast<packed_segment*>(p);
 237     auto al=segment_allocator_type{q->s.get_allocator()};
 238     q->~packed_segment();
 239     std::allocator_traits<segment_allocator_type>::deallocate(al,q,1);
 240   }
 241
 242   packed_segment(const Allocator& al):s{typename store::allocator_type{al}}{}
 243   packed_segment(store&& s):s{std::move(s)}{}
 244
 245   static Concrete& concrete_ref(value_pointer p)noexcept
 246   {
 247     return *static_cast<Concrete*>(p);
 248   }
 249
 250   static const Concrete& const_concrete_ref(const_value_pointer p)noexcept
 251   {
 252     return *static_cast<const Concrete*>(p);
 253   }
 254
 255   static Concrete* concrete_ptr(store_value_type* p)noexcept
 256   {
 257     return reinterpret_cast<Concrete*>(
 258       static_cast<value_holder_base<Concrete>*>(p));
 259   }
 260
 261   static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept
 262   {
 263     return concrete_ptr(const_cast<store_value_type*>(p));
 264   }
 265
 266   static value_type* value_ptr(const store_value_type* p)noexcept
 267   {
 268     return const_cast<value_type*>(Model::value_ptr(const_concrete_ptr(p)));
 269   }
 270
 271   static const store_value_type* const_store_value_type_ptr(
 272     const Concrete* p)noexcept
 273   {
 274     return static_cast<const value_holder<Concrete>*>(
 275       reinterpret_cast<const value_holder_base<Concrete>*>(p));
 276   }
 277
 278   /* It would have sufficed if iterator_from returned const_store_iterator
 279    * except for the fact that some old versions of libstdc++ claiming to be
 280    * C++11 compliant do not however provide std::vector modifier ops taking
 281    * const_iterator's.
 282    */
 283
 284   store_iterator iterator_from(const_base_iterator p)
 285   {
 286     return iterator_from(static_cast<const_iterator>(p));
 287   }
 288
 289   store_iterator iterator_from(const_iterator p)
 290   {
 291     return s.begin()+(const_store_value_type_ptr(p)-s.data());
 292   }
 293
 294   base_sentinel sentinel()const noexcept
 295   {
 296     return base_iterator{
 297       value_ptr(s.data()+s.size()),
 298       sizeof(store_value_type)
 299     };
 300   }
 301
 302   range range_from(const_store_iterator it)const
 303   {
 304     return {
 305       {value_ptr(s.data()+(it-s.begin())),sizeof(store_value_type)},
 306       sentinel()
 307     };
 308   }
 309
 310   range range_from(std::size_t n)const
 311   {
 312     return {
 313       {value_ptr(s.data()+n),sizeof(store_value_type)},
 314       sentinel()
 315     };
 316   }
 317
 318   store s;
 319 };
 320
 321 } /* namespace poly_collection::detail */
 322
 323 } /* namespace poly_collection */
 324
 325 } /* namespace boost */
 326
 327 #endif