ceph/src/boost/libs/stl_interfaces/example/static_vector.hpp

   1 // Copyright (C) 2019 T. Zachary Laine
   2 //
   3 // Distributed under the Boost Software License, Version 1.0. (See
   4 // accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6 #include <boost/stl_interfaces/sequence_container_interface.hpp>
   7
   8 #include <algorithm>
   9 #include <iterator>
  10 #include <memory>
  11 #include <tuple>
  12
  13 #include <cassert>
  14
  15
  16 // There's a test that uses this example header; this controls whether the
  17 // C++14 version (v1::) of sequence_container_interface gets used, or the
  18 // C++20 version (v2::).
  19 #if defined(USE_V2)
  20 template<typename Derived, boost::stl_interfaces::element_layout Contiguity>
  21 using sequence_container_interface =
  22     boost::stl_interfaces::v2::sequence_container_interface<Derived>;
  23 #else
  24 template<typename Derived, boost::stl_interfaces::element_layout Contiguity>
  25 using sequence_container_interface =
  26     boost::stl_interfaces::v1::sequence_container_interface<Derived, Contiguity>;
  27 #endif
  28
  29
  30 //[ static_vector_defn
  31 // The sections of member functions below are commented as they are in the
  32 // standard for std::vector.  Each section has two numbers: the number of
  33 // member functions in that section, and the number that are missing, because
  34 // they are provided by sequence_container_interface.  The purely
  35 // allocator-specific members are neither present nor part of the counts.
  36 //
  37 // We're passing boost::stl_interfaces::contiguous here, so that
  38 // sequence_container_interface knows that it should provide data().
  39 template<typename T, std::size_t N>
  40 struct static_vector : sequence_container_interface<
  41                            static_vector<T, N>,
  42                            boost::stl_interfaces::element_layout::contiguous>
  43 {
  44     // These are the types required for reversible containers.  These must be
  45     // user-defined.
  46     using value_type = T;
  47     using pointer = T *;
  48     using const_pointer = T const *;
  49     using reference = value_type &;
  50     using const_reference = value_type const &;
  51     using size_type = std::size_t;
  52     using difference_type = std::ptrdiff_t;
  53     using iterator = T *;
  54     using const_iterator = T const *;
  55     using reverse_iterator = boost::stl_interfaces::reverse_iterator<iterator>;
  56     using const_reverse_iterator =
  57         boost::stl_interfaces::reverse_iterator<const_iterator>;
  58
  59     // construct/copy/destroy (9 members, skipped 2)
  60     //
  61     // Constructors and special member functions all must be user-provided.
  62     // Were they provided by sequence_container_interface, everything would break, due
  63     // to the language rules related to them.  However, assignment from
  64     // std::initializer_list and the destructor can come from
  65     // sequence_container_interface.
  66     static_vector() noexcept : size_(0) {}
  67     explicit static_vector(size_type n) : size_(0) { resize(n); }
  68     explicit static_vector(size_type n, T const & x) : size_(0)
  69     {
  70         // Note that you must write "this->" before all the member functions
  71         // provided by sequence_container_interface, which is slightly annoying.
  72         this->assign(n, x);
  73     }
  74     template<
  75         typename InputIterator,
  76         typename Enable = std::enable_if_t<std::is_convertible<
  77             typename std::iterator_traits<InputIterator>::iterator_category,
  78             std::input_iterator_tag>::value>>
  79     static_vector(InputIterator first, InputIterator last) : size_(0)
  80     {
  81         this->assign(first, last);
  82     }
  83     static_vector(std::initializer_list<T> il) :
  84         static_vector(il.begin(), il.end())
  85     {}
  86     static_vector(static_vector const & other) : size_(0)
  87     {
  88         this->assign(other.begin(), other.end());
  89     }
  90     static_vector(static_vector && other) noexcept(
  91         noexcept(std::declval<static_vector>().emplace_back(
  92             std::move(*other.begin())))) :
  93         size_(0)
  94     {
  95         for (auto & element : other) {
  96             emplace_back(std::move(element));
  97         }
  98         other.clear();
  99     }
 100     static_vector & operator=(static_vector const & other)
 101     {
 102         this->clear();
 103         this->assign(other.begin(), other.end());
 104         return *this;
 105     }
 106     static_vector & operator=(static_vector && other) noexcept(noexcept(
 107         std::declval<static_vector>().emplace_back(std::move(*other.begin()))))
 108     {
 109         this->clear();
 110         for (auto & element : other) {
 111             emplace_back(std::move(element));
 112         }
 113         other.clear();
 114         return *this;
 115     }
 116     ~static_vector() { this->clear(); }
 117
 118     // iterators (2 members, skipped 10)
 119     //
 120     // This section is the first big win.  Instead of having to write 12
 121     // overloads line begin, cbegin, rbegin, crbegin, etc., we can just write
 122     // 2.
 123     iterator begin() noexcept { return reinterpret_cast<T *>(buf_); }
 124     iterator end() noexcept
 125     {
 126         return reinterpret_cast<T *>(buf_ + size_ * sizeof(T));
 127     }
 128
 129     // capacity (6 members, skipped 2)
 130     //
 131     // Most of these are not even part of the general requirements, because
 132     // some are specific to std::vector and related types.  However, we do get
 133     // empty and size from sequence_container_interface.
 134     size_type max_size() const noexcept { return N; }
 135     size_type capacity() const noexcept { return N; }
 136     void resize(size_type sz) noexcept
 137     {
 138         resize_impl(sz, [] { return T(); });
 139     }
 140     void resize(size_type sz, T const & x) noexcept
 141     {
 142         resize_impl(sz, [&]() -> T const & { return x; });
 143     }
 144     void reserve(size_type n) noexcept { assert(n < capacity()); }
 145     void shrink_to_fit() noexcept {}
 146
 147     // element access (skipped 8)
 148     // data access (skipped 2)
 149     //
 150     // Another big win.  sequence_container_interface provides all of the
 151     // overloads of operator[], at, front, back, and data.
 152
 153     // modifiers (5 members, skipped 9)
 154     //
 155     // In this section we again get most of the API from
 156     // sequence_container_interface.
 157
 158     // emplace_back does not look very necessary -- just look at its trivial
 159     // implementation -- but we can't provide it from
 160     // sequence_container_interface, because it is an optional sequence
 161     // container interface.  We would not want emplace_front to suddenly
 162     // appear on our std::vector-like type, and there may be some other type
 163     // for which emplace_back is a bad idea.
 164     //
 165     // However, by providing emplace_back here, we signal to the
 166     // sequence_container_interface template that our container is
 167     // back-mutation-friendly, and this allows it to provide all the overloads
 168     // of push_back and pop_back.
 169     template<typename... Args>
 170     reference emplace_back(Args &&... args)
 171     {
 172         return *emplace(end(), std::forward<Args>(args)...);
 173     }
 174     template<typename... Args>
 175     iterator emplace(const_iterator pos, Args &&... args)
 176     {
 177         auto position = const_cast<T *>(pos);
 178         bool const insert_before_end = position < end();
 179         if (insert_before_end) {
 180             auto last = end();
 181             emplace_back(std::move(this->back()));
 182             std::move_backward(position, last - 1, last);
 183         }
 184         new (position) T(std::forward<Args>(args)...);
 185         if (!insert_before_end)
 186             ++size_;
 187         return position;
 188     }
 189     // Note: The iterator category here was upgraded to ForwardIterator
 190     // (instead of vector's InputIterator), to ensure linear time complexity.
 191     template<
 192         typename ForwardIterator,
 193         typename Enable = std::enable_if_t<std::is_convertible<
 194             typename std::iterator_traits<ForwardIterator>::iterator_category,
 195             std::forward_iterator_tag>::value>>
 196     iterator
 197     insert(const_iterator pos, ForwardIterator first, ForwardIterator last)
 198     {
 199         auto position = const_cast<T *>(pos);
 200         auto const insertions = std::distance(first, last);
 201         assert(this->size() + insertions < capacity());
 202         uninitialized_generate(end(), end() + insertions, [] { return T(); });
 203         std::move_backward(position, end(), end() + insertions);
 204         std::copy(first, last, position);
 205         size_ += insertions;
 206         return position;
 207     }
 208     iterator erase(const_iterator f, const_iterator l)
 209     {
 210         auto first = const_cast<T *>(f);
 211         auto last = const_cast<T *>(l);
 212         auto end_ = this->end();
 213         auto it = std::move(last, end_, first);
 214         for (; it != end_; ++it) {
 215             it->~T();
 216         }
 217         size_ -= last - first;
 218         return first;
 219     }
 220     void swap(static_vector & other)
 221     {
 222         size_type short_size, long_size;
 223         std::tie(short_size, long_size) =
 224             std::minmax(this->size(), other.size());
 225         for (auto i = size_type(0); i < short_size; ++i) {
 226             using std::swap;
 227             swap((*this)[i], other[i]);
 228         }
 229
 230         static_vector * longer = this;
 231         static_vector * shorter = this;
 232         if (this->size() < other.size())
 233             longer = &other;
 234         else
 235             shorter = &other;
 236
 237         for (auto it = longer->begin() + short_size, last = longer->end();
 238              it != last;
 239              ++it) {
 240             shorter->emplace_back(std::move(*it));
 241         }
 242
 243         longer->resize(short_size);
 244         shorter->size_ = long_size;
 245     }
 246
 247     // Since we're getting so many overloads from
 248     // sequence_container_interface, and since many of those overloads are
 249     // implemented in terms of a user-defined function of the same name, we
 250     // need to add quite a few using declarations here.
 251     using base_type = sequence_container_interface<
 252         static_vector<T, N>,
 253         boost::stl_interfaces::element_layout::contiguous>;
 254     using base_type::begin;
 255     using base_type::end;
 256     using base_type::insert;
 257     using base_type::erase;
 258
 259     // comparisons (skipped 6)
 260
 261 private:
 262     template<typename F>
 263     static void uninitialized_generate(iterator f, iterator l, F func)
 264     {
 265         for (; f != l; ++f) {
 266             new (static_cast<void *>(std::addressof(*f))) T(func());
 267         }
 268     }
 269     template<typename F>
 270     void resize_impl(size_type sz, F func) noexcept
 271     {
 272         assert(sz < capacity());
 273         if (sz < this->size())
 274             erase(begin() + sz, end());
 275         if (this->size() < sz)
 276             uninitialized_generate(end(), begin() + sz, func);
 277         size_ = sz;
 278     }
 279
 280     alignas(T) unsigned char buf_[N * sizeof(T)];
 281     size_type size_;
 282 };
 283 //]