ceph/src/boost/boost/multi_array.hpp

   1 // Copyright 2002 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Boost.MultiArray Library
   8 //  Authors: Ronald Garcia
   9 //           Jeremy Siek
  10 //           Andrew Lumsdaine
  11 //  See http://www.boost.org/libs/multi_array for documentation.
  12
  13 #ifndef BOOST_MULTI_ARRAY_RG071801_HPP
  14 #define BOOST_MULTI_ARRAY_RG071801_HPP
  15
  16 //
  17 // multi_array.hpp - contains the multi_array class template
  18 // declaration and definition
  19 //
  20
  21 #if defined(__GNUC__) && ((__GNUC__*100 + __GNUC_MINOR__) >= 406)
  22 #  pragma GCC diagnostic push
  23 #  pragma GCC diagnostic ignored "-Wshadow"
  24 #endif
  25
  26 #include "boost/multi_array/base.hpp"
  27 #include "boost/multi_array/collection_concept.hpp"
  28 #include "boost/multi_array/copy_array.hpp"
  29 #include "boost/multi_array/iterator.hpp"
  30 #include "boost/multi_array/subarray.hpp"
  31 #include "boost/multi_array/multi_array_ref.hpp"
  32 #include "boost/multi_array/algorithm.hpp"
  33 #include "boost/array.hpp"
  34 #include "boost/mpl/if.hpp"
  35 #include "boost/type_traits.hpp"
  36 #include <algorithm>
  37 #include <cstddef>
  38 #include <functional>
  39 #include <numeric>
  40 #include <vector>
  41
  42
  43
  44 namespace boost {
  45   namespace detail {
  46     namespace multi_array {
  47
  48       struct populate_index_ranges {
  49         multi_array_types::index_range
  50         // RG: underscore on extent_ to stifle strange MSVC warning.
  51         operator()(multi_array_types::index base,
  52                    multi_array_types::size_type extent_) {
  53           return multi_array_types::index_range(base,base+extent_);
  54         }
  55       };
  56
  57 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
  58 //
  59 // Compilers that don't support partial ordering may need help to
  60 // disambiguate multi_array's templated constructors.  Even vc6/7 are
  61 // capable of some limited SFINAE, so we take the most-general version
  62 // out of the overload set with disable_multi_array_impl.
  63 //
  64 template <typename T, std::size_t NumDims, typename TPtr>
  65 char is_multi_array_impl_help(const_multi_array_view<T,NumDims,TPtr>&);
  66 template <typename T, std::size_t NumDims, typename TPtr>
  67 char is_multi_array_impl_help(const_sub_array<T,NumDims,TPtr>&);
  68 template <typename T, std::size_t NumDims, typename TPtr>
  69 char is_multi_array_impl_help(const_multi_array_ref<T,NumDims,TPtr>&);
  70
  71 char ( &is_multi_array_impl_help(...) )[2];
  72
  73 template <class T>
  74 struct is_multi_array_impl
  75 {
  76     static T x;
  77     BOOST_STATIC_CONSTANT(bool, value = sizeof((is_multi_array_impl_help)(x)) == 1);
  78
  79   typedef mpl::bool_<value> type;
  80 };
  81
  82 template <bool multi_array = false>
  83 struct disable_multi_array_impl_impl
  84 {
  85     typedef int type;
  86 };
  87
  88 template <>
  89 struct disable_multi_array_impl_impl<true>
  90 {
  91     // forming a pointer to a reference triggers SFINAE
  92     typedef int& type;
  93 };
  94
  95
  96 template <class T>
  97 struct disable_multi_array_impl :
  98   disable_multi_array_impl_impl<is_multi_array_impl<T>::value>
  99 { };
 100
 101
 102 template <>
 103 struct disable_multi_array_impl<int>
 104 {
 105   typedef int type;
 106 };
 107
 108
 109 #endif
 110
 111     } //namespace multi_array
 112   } // namespace detail
 113
 114 template<typename T, std::size_t NumDims,
 115   typename Allocator>
 116 class multi_array :
 117   public multi_array_ref<T,NumDims>
 118 {
 119   typedef multi_array_ref<T,NumDims> super_type;
 120 public:
 121   typedef typename super_type::value_type value_type;
 122   typedef typename super_type::reference reference;
 123   typedef typename super_type::const_reference const_reference;
 124   typedef typename super_type::iterator iterator;
 125   typedef typename super_type::const_iterator const_iterator;
 126   typedef typename super_type::reverse_iterator reverse_iterator;
 127   typedef typename super_type::const_reverse_iterator const_reverse_iterator;
 128   typedef typename super_type::element element;
 129   typedef typename super_type::size_type size_type;
 130   typedef typename super_type::difference_type difference_type;
 131   typedef typename super_type::index index;
 132   typedef typename super_type::extent_range extent_range;
 133
 134
 135   template <std::size_t NDims>
 136   struct const_array_view {
 137     typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
 138   };
 139
 140   template <std::size_t NDims>
 141   struct array_view {
 142     typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
 143   };
 144
 145   explicit multi_array() :
 146     super_type((T*)initial_base_,c_storage_order(),
 147                /*index_bases=*/0, /*extents=*/0) {
 148     allocate_space();
 149   }
 150
 151   template <class ExtentList>
 152   explicit multi_array(
 153       ExtentList const& extents
 154 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 155       , typename mpl::if_<
 156       detail::multi_array::is_multi_array_impl<ExtentList>,
 157       int&,int>::type* = 0
 158 #endif
 159       ) :
 160     super_type((T*)initial_base_,extents) {
 161     boost::function_requires<
 162       detail::multi_array::CollectionConcept<ExtentList> >();
 163     allocate_space();
 164   }
 165
 166
 167   template <class ExtentList>
 168   explicit multi_array(ExtentList const& extents,
 169                        const general_storage_order<NumDims>& so) :
 170     super_type((T*)initial_base_,extents,so) {
 171     boost::function_requires<
 172       detail::multi_array::CollectionConcept<ExtentList> >();
 173     allocate_space();
 174   }
 175
 176   template <class ExtentList>
 177   explicit multi_array(ExtentList const& extents,
 178                        const general_storage_order<NumDims>& so,
 179                        Allocator const& alloc) :
 180     super_type((T*)initial_base_,extents,so), allocator_(alloc) {
 181     boost::function_requires<
 182       detail::multi_array::CollectionConcept<ExtentList> >();
 183     allocate_space();
 184   }
 185
 186
 187   explicit multi_array(const detail::multi_array
 188                        ::extent_gen<NumDims>& ranges) :
 189     super_type((T*)initial_base_,ranges) {
 190
 191     allocate_space();
 192   }
 193
 194
 195   explicit multi_array(const detail::multi_array
 196                        ::extent_gen<NumDims>& ranges,
 197                        const general_storage_order<NumDims>& so) :
 198     super_type((T*)initial_base_,ranges,so) {
 199
 200     allocate_space();
 201   }
 202
 203
 204   explicit multi_array(const detail::multi_array
 205                        ::extent_gen<NumDims>& ranges,
 206                        const general_storage_order<NumDims>& so,
 207                        Allocator const& alloc) :
 208     super_type((T*)initial_base_,ranges,so), allocator_(alloc) {
 209
 210     allocate_space();
 211   }
 212
 213   multi_array(const multi_array& rhs) :
 214   super_type(rhs), allocator_(rhs.allocator_) {
 215     allocate_space();
 216     boost::detail::multi_array::copy_n(rhs.base_,rhs.num_elements(),base_);
 217   }
 218
 219
 220   //
 221   // A multi_array is constructible from any multi_array_ref, subarray, or
 222   // array_view object.  The following constructors ensure that.
 223   //
 224
 225   // Due to limited support for partial template ordering,
 226   // MSVC 6&7 confuse the following with the most basic ExtentList
 227   // constructor.
 228 #ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 229   template <typename OPtr>
 230   multi_array(const const_multi_array_ref<T,NumDims,OPtr>& rhs,
 231               const general_storage_order<NumDims>& so = c_storage_order())
 232     : super_type(0,so,rhs.index_bases(),rhs.shape())
 233   {
 234     allocate_space();
 235     // Warning! storage order may change, hence the following copy technique.
 236     std::copy(rhs.begin(),rhs.end(),this->begin());
 237   }
 238
 239   template <typename OPtr>
 240   multi_array(const detail::multi_array::
 241               const_sub_array<T,NumDims,OPtr>& rhs,
 242               const general_storage_order<NumDims>& so = c_storage_order())
 243     : super_type(0,so,rhs.index_bases(),rhs.shape())
 244   {
 245     allocate_space();
 246     std::copy(rhs.begin(),rhs.end(),this->begin());
 247   }
 248
 249
 250   template <typename OPtr>
 251   multi_array(const detail::multi_array::
 252               const_multi_array_view<T,NumDims,OPtr>& rhs,
 253               const general_storage_order<NumDims>& so = c_storage_order())
 254     : super_type(0,so,rhs.index_bases(),rhs.shape())
 255   {
 256     allocate_space();
 257     std::copy(rhs.begin(),rhs.end(),this->begin());
 258   }
 259
 260 #else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 261   // More limited support for MSVC
 262
 263
 264   multi_array(const const_multi_array_ref<T,NumDims>& rhs)
 265     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 266   {
 267     allocate_space();
 268     // Warning! storage order may change, hence the following copy technique.
 269     std::copy(rhs.begin(),rhs.end(),this->begin());
 270   }
 271
 272   multi_array(const const_multi_array_ref<T,NumDims>& rhs,
 273               const general_storage_order<NumDims>& so)
 274     : super_type(0,so,rhs.index_bases(),rhs.shape())
 275   {
 276     allocate_space();
 277     // Warning! storage order may change, hence the following copy technique.
 278     std::copy(rhs.begin(),rhs.end(),this->begin());
 279   }
 280
 281   multi_array(const detail::multi_array::
 282               const_sub_array<T,NumDims>& rhs)
 283     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 284   {
 285     allocate_space();
 286     std::copy(rhs.begin(),rhs.end(),this->begin());
 287   }
 288
 289   multi_array(const detail::multi_array::
 290               const_sub_array<T,NumDims>& rhs,
 291               const general_storage_order<NumDims>& so)
 292     : super_type(0,so,rhs.index_bases(),rhs.shape())
 293   {
 294     allocate_space();
 295     std::copy(rhs.begin(),rhs.end(),this->begin());
 296   }
 297
 298
 299   multi_array(const detail::multi_array::
 300               const_multi_array_view<T,NumDims>& rhs)
 301     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 302   {
 303     allocate_space();
 304     std::copy(rhs.begin(),rhs.end(),this->begin());
 305   }
 306
 307   multi_array(const detail::multi_array::
 308               const_multi_array_view<T,NumDims>& rhs,
 309               const general_storage_order<NumDims>& so)
 310     : super_type(0,so,rhs.index_bases(),rhs.shape())
 311   {
 312     allocate_space();
 313     std::copy(rhs.begin(),rhs.end(),this->begin());
 314   }
 315
 316 #endif // !BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 317
 318   // Thes constructors are necessary because of more exact template matches.
 319   multi_array(const multi_array_ref<T,NumDims>& rhs)
 320     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 321   {
 322     allocate_space();
 323     // Warning! storage order may change, hence the following copy technique.
 324     std::copy(rhs.begin(),rhs.end(),this->begin());
 325   }
 326
 327   multi_array(const multi_array_ref<T,NumDims>& rhs,
 328               const general_storage_order<NumDims>& so)
 329     : super_type(0,so,rhs.index_bases(),rhs.shape())
 330   {
 331     allocate_space();
 332     // Warning! storage order may change, hence the following copy technique.
 333     std::copy(rhs.begin(),rhs.end(),this->begin());
 334   }
 335
 336
 337   multi_array(const detail::multi_array::
 338               sub_array<T,NumDims>& rhs)
 339     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 340   {
 341     allocate_space();
 342     std::copy(rhs.begin(),rhs.end(),this->begin());
 343   }
 344
 345   multi_array(const detail::multi_array::
 346               sub_array<T,NumDims>& rhs,
 347               const general_storage_order<NumDims>& so)
 348     : super_type(0,so,rhs.index_bases(),rhs.shape())
 349   {
 350     allocate_space();
 351     std::copy(rhs.begin(),rhs.end(),this->begin());
 352   }
 353
 354
 355   multi_array(const detail::multi_array::
 356               multi_array_view<T,NumDims>& rhs)
 357     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 358   {
 359     allocate_space();
 360     std::copy(rhs.begin(),rhs.end(),this->begin());
 361   }
 362
 363   multi_array(const detail::multi_array::
 364               multi_array_view<T,NumDims>& rhs,
 365               const general_storage_order<NumDims>& so)
 366     : super_type(0,so,rhs.index_bases(),rhs.shape())
 367   {
 368     allocate_space();
 369     std::copy(rhs.begin(),rhs.end(),this->begin());
 370   }
 371
 372   // Since assignment is a deep copy, multi_array_ref
 373   // contains all the necessary code.
 374   template <typename ConstMultiArray>
 375   multi_array& operator=(const ConstMultiArray& other) {
 376     super_type::operator=(other);
 377     return *this;
 378   }
 379
 380   multi_array& operator=(const multi_array& other) {
 381     if (&other != this) {
 382       super_type::operator=(other);
 383     }
 384     return *this;
 385   }
 386
 387
 388   template <typename ExtentList>
 389   multi_array& resize(const ExtentList& extents) {
 390     boost::function_requires<
 391       detail::multi_array::CollectionConcept<ExtentList> >();
 392
 393     typedef detail::multi_array::extent_gen<NumDims> gen_type;
 394     gen_type ranges;
 395
 396     for (int i=0; i != NumDims; ++i) {
 397       typedef typename gen_type::range range_type;
 398       ranges.ranges_[i] = range_type(0,extents[i]);
 399     }
 400
 401     return this->resize(ranges);
 402   }
 403
 404
 405
 406   multi_array& resize(const detail::multi_array
 407                       ::extent_gen<NumDims>& ranges) {
 408
 409
 410     // build a multi_array with the specs given
 411     multi_array new_array(ranges,this->storage_order());
 412
 413
 414     // build a view of tmp with the minimum extents
 415
 416     // Get the minimum extents of the arrays.
 417     boost::array<size_type,NumDims> min_extents;
 418
 419     const size_type& (*min)(const size_type&, const size_type&) =
 420       std::min;
 421     std::transform(new_array.extent_list_.begin(),new_array.extent_list_.end(),
 422                    this->extent_list_.begin(),
 423                    min_extents.begin(),
 424                    min);
 425
 426
 427     // typedef boost::array<index,NumDims> index_list;
 428     // Build index_gen objects to create views with the same shape
 429
 430     // these need to be separate to handle non-zero index bases
 431     typedef detail::multi_array::index_gen<NumDims,NumDims> index_gen;
 432     index_gen old_idxes;
 433     index_gen new_idxes;
 434
 435     std::transform(new_array.index_base_list_.begin(),
 436                    new_array.index_base_list_.end(),
 437                    min_extents.begin(),new_idxes.ranges_.begin(),
 438                    detail::multi_array::populate_index_ranges());
 439
 440     std::transform(this->index_base_list_.begin(),
 441                    this->index_base_list_.end(),
 442                    min_extents.begin(),old_idxes.ranges_.begin(),
 443                    detail::multi_array::populate_index_ranges());
 444
 445     // Build same-shape views of the two arrays
 446     typename
 447       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_old = (*this)[old_idxes];
 448     typename
 449       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_new = new_array[new_idxes];
 450
 451     // Set the right portion of the new array
 452     view_new = view_old;
 453
 454     using std::swap;
 455     // Swap the internals of these arrays.
 456     swap(this->super_type::base_,new_array.super_type::base_);
 457     swap(this->storage_,new_array.storage_);
 458     swap(this->extent_list_,new_array.extent_list_);
 459     swap(this->stride_list_,new_array.stride_list_);
 460     swap(this->index_base_list_,new_array.index_base_list_);
 461     swap(this->origin_offset_,new_array.origin_offset_);
 462     swap(this->directional_offset_,new_array.directional_offset_);
 463     swap(this->num_elements_,new_array.num_elements_);
 464     swap(this->allocator_,new_array.allocator_);
 465     swap(this->base_,new_array.base_);
 466     swap(this->allocated_elements_,new_array.allocated_elements_);
 467
 468     return *this;
 469   }
 470
 471
 472   ~multi_array() {
 473     deallocate_space();
 474   }
 475
 476 private:
 477   void allocate_space() {
 478     typename Allocator::const_pointer no_hint=0;
 479     base_ = allocator_.allocate(this->num_elements(),no_hint);
 480     this->set_base_ptr(base_);
 481     allocated_elements_ = this->num_elements();
 482     std::uninitialized_fill_n(base_,allocated_elements_,T());
 483   }
 484
 485   void deallocate_space() {
 486     if(base_) {
 487       for(T* i = base_; i != base_+allocated_elements_; ++i)
 488         allocator_.destroy(i);
 489       allocator_.deallocate(base_,allocated_elements_);
 490     }
 491   }
 492
 493   typedef boost::array<size_type,NumDims> size_list;
 494   typedef boost::array<index,NumDims> index_list;
 495
 496   Allocator allocator_;
 497   T* base_;
 498   size_type allocated_elements_;
 499   enum {initial_base_ = 0};
 500 };
 501
 502 } // namespace boost
 503
 504 #if defined(__GNUC__) && ((__GNUC__*100 + __GNUC_MINOR__) >= 406)
 505 #  pragma GCC diagnostic pop
 506 #endif
 507
 508 #endif // BOOST_MULTI_ARRAY_RG071801_HPP