src/core/lib/gprpp/inlined_vector.h

   1 /*
   2  *
   3  * Copyright 2017 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #ifndef GRPC_CORE_LIB_GPRPP_INLINED_VECTOR_H
  20 #define GRPC_CORE_LIB_GPRPP_INLINED_VECTOR_H
  21
  22 #include <grpc/support/port_platform.h>
  23
  24 #include <cassert>
  25 #include <cstring>
  26
  27 #include "src/core/lib/gprpp/memory.h"
  28
  29 namespace grpc_core {
  30
  31 // NOTE: We eventually want to use absl::InlinedVector here.  However,
  32 // there are currently build problems that prevent us from using absl.
  33 // In the interim, we define a custom implementation as a place-holder,
  34 // with the intent to eventually replace this with the absl
  35 // implementation.
  36 //
  37 // This place-holder implementation does not implement the full set of
  38 // functionality from the absl version; it has just the methods that we
  39 // currently happen to need in gRPC.  If additional functionality is
  40 // needed before this gets replaced with the absl version, it can be
  41 // added, with the following proviso:
  42 //
  43 // ANY METHOD ADDED HERE MUST COMPLY WITH THE INTERFACE IN THE absl
  44 // IMPLEMENTATION!
  45 //
  46 // TODO(nnoble, roth): Replace this with absl::InlinedVector once we
  47 // integrate absl into the gRPC build system in a usable way.
  48 template <typename T, size_t N>
  49 class InlinedVector {
  50  public:
  51   InlinedVector() { init_data(); }
  52   ~InlinedVector() { destroy_elements(); }
  53
  54   // copy constructor
  55   InlinedVector(const InlinedVector& v) {
  56     init_data();
  57     copy_from(v);
  58   }
  59
  60   InlinedVector& operator=(const InlinedVector& v) {
  61     if (this != &v) {
  62       clear();
  63       copy_from(v);
  64     }
  65     return *this;
  66   }
  67
  68   // move constructor
  69   InlinedVector(InlinedVector&& v) {
  70     init_data();
  71     move_from(v);
  72   }
  73
  74   InlinedVector& operator=(InlinedVector&& v) {
  75     if (this != &v) {
  76       clear();
  77       move_from(v);
  78     }
  79     return *this;
  80   }
  81
  82   T* data() {
  83     return dynamic_ != nullptr ? dynamic_ : reinterpret_cast<T*>(inline_);
  84   }
  85
  86   const T* data() const {
  87     return dynamic_ != nullptr ? dynamic_ : reinterpret_cast<const T*>(inline_);
  88   }
  89
  90   T& operator[](size_t offset) {
  91     assert(offset < size_);
  92     return data()[offset];
  93   }
  94
  95   const T& operator[](size_t offset) const {
  96     assert(offset < size_);
  97     return data()[offset];
  98   }
  99
 100   void reserve(size_t capacity) {
 101     if (capacity > capacity_) {
 102       T* new_dynamic = static_cast<T*>(gpr_malloc(sizeof(T) * capacity));
 103       move_elements(data(), new_dynamic, size_);
 104       gpr_free(dynamic_);
 105       dynamic_ = new_dynamic;
 106       capacity_ = capacity;
 107     }
 108   }
 109
 110   template <typename... Args>
 111   void emplace_back(Args&&... args) {
 112     if (size_ == capacity_) {
 113       reserve(capacity_ * 2);
 114     }
 115     new (&(data()[size_])) T(std::forward<Args>(args)...);
 116     ++size_;
 117   }
 118
 119   void push_back(const T& value) { emplace_back(value); }
 120
 121   void push_back(T&& value) { emplace_back(std::move(value)); }
 122
 123   void pop_back() {
 124     assert(!empty());
 125     size_t s = size();
 126     T& value = data()[s - 1];
 127     value.~T();
 128     size_--;
 129   }
 130
 131   size_t size() const { return size_; }
 132   bool empty() const { return size_ == 0; }
 133
 134   size_t capacity() const { return capacity_; }
 135
 136   void clear() {
 137     destroy_elements();
 138     init_data();
 139   }
 140
 141  private:
 142   void copy_from(const InlinedVector& v) {
 143     // if v is allocated, make sure we have enough capacity.
 144     if (v.dynamic_ != nullptr) {
 145       reserve(v.capacity_);
 146     }
 147     // copy over elements
 148     for (size_t i = 0; i < v.size_; ++i) {
 149       new (&(data()[i])) T(v[i]);
 150     }
 151     // copy over metadata
 152     size_ = v.size_;
 153     capacity_ = v.capacity_;
 154   }
 155
 156   void move_from(InlinedVector& v) {
 157     // if v is allocated, then we steal its dynamic array; otherwise, we
 158     // move the elements individually.
 159     if (v.dynamic_ != nullptr) {
 160       dynamic_ = v.dynamic_;
 161     } else {
 162       move_elements(v.data(), data(), v.size_);
 163     }
 164     // copy over metadata
 165     size_ = v.size_;
 166     capacity_ = v.capacity_;
 167     // null out the original
 168     v.init_data();
 169   }
 170
 171   static void move_elements(T* src, T* dst, size_t num_elements) {
 172     for (size_t i = 0; i < num_elements; ++i) {
 173       new (&dst[i]) T(std::move(src[i]));
 174       src[i].~T();
 175     }
 176   }
 177
 178   void init_data() {
 179     dynamic_ = nullptr;
 180     size_ = 0;
 181     capacity_ = N;
 182   }
 183
 184   void destroy_elements() {
 185     for (size_t i = 0; i < size_; ++i) {
 186       T& value = data()[i];
 187       value.~T();
 188     }
 189     gpr_free(dynamic_);
 190   }
 191
 192   typename std::aligned_storage<sizeof(T)>::type inline_[N];
 193   T* dynamic_;
 194   size_t size_;
 195   size_t capacity_;
 196 };
 197
 198 }  // namespace grpc_core
 199
 200 #endif /* GRPC_CORE_LIB_GPRPP_INLINED_VECTOR_H */