legacy-libs/grpc/deps/grpc/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   bool operator==(const InlinedVector& other) const {
 101     if (size_ != other.size_) return false;
 102     for (size_t i = 0; i < size_; ++i) {
 103       // Note that this uses == instead of != so that the data class doesn't
 104       // have to implement !=.
 105       if (!(data()[i] == other.data()[i])) return false;
 106     }
 107     return true;
 108   }
 109
 110   void reserve(size_t capacity) {
 111     if (capacity > capacity_) {
 112       T* new_dynamic =
 113           std::alignment_of<T>::value == 0
 114               ? static_cast<T*>(gpr_malloc(sizeof(T) * capacity))
 115               : static_cast<T*>(gpr_malloc_aligned(
 116                     sizeof(T) * capacity, std::alignment_of<T>::value));
 117       move_elements(data(), new_dynamic, size_);
 118       free_dynamic();
 119       dynamic_ = new_dynamic;
 120       capacity_ = capacity;
 121     }
 122   }
 123
 124   template <typename... Args>
 125   void emplace_back(Args&&... args) {
 126     if (size_ == capacity_) {
 127       reserve(capacity_ * 2);
 128     }
 129     new (&(data()[size_])) T(std::forward<Args>(args)...);
 130     ++size_;
 131   }
 132
 133   void push_back(const T& value) { emplace_back(value); }
 134
 135   void push_back(T&& value) { emplace_back(std::move(value)); }
 136
 137   void pop_back() {
 138     assert(!empty());
 139     size_t s = size();
 140     T& value = data()[s - 1];
 141     value.~T();
 142     size_--;
 143   }
 144
 145   size_t size() const { return size_; }
 146   bool empty() const { return size_ == 0; }
 147
 148   size_t capacity() const { return capacity_; }
 149
 150   void clear() {
 151     destroy_elements();
 152     init_data();
 153   }
 154
 155  private:
 156   void copy_from(const InlinedVector& v) {
 157     // if v is allocated, make sure we have enough capacity.
 158     if (v.dynamic_ != nullptr) {
 159       reserve(v.capacity_);
 160     }
 161     // copy over elements
 162     for (size_t i = 0; i < v.size_; ++i) {
 163       new (&(data()[i])) T(v[i]);
 164     }
 165     // copy over metadata
 166     size_ = v.size_;
 167     capacity_ = v.capacity_;
 168   }
 169
 170   void move_from(InlinedVector& v) {
 171     // if v is allocated, then we steal its dynamic array; otherwise, we
 172     // move the elements individually.
 173     if (v.dynamic_ != nullptr) {
 174       dynamic_ = v.dynamic_;
 175     } else {
 176       move_elements(v.data(), data(), v.size_);
 177     }
 178     // copy over metadata
 179     size_ = v.size_;
 180     capacity_ = v.capacity_;
 181     // null out the original
 182     v.init_data();
 183   }
 184
 185   static void move_elements(T* src, T* dst, size_t num_elements) {
 186     for (size_t i = 0; i < num_elements; ++i) {
 187       new (&dst[i]) T(std::move(src[i]));
 188       src[i].~T();
 189     }
 190   }
 191
 192   void init_data() {
 193     dynamic_ = nullptr;
 194     size_ = 0;
 195     capacity_ = N;
 196   }
 197
 198   void destroy_elements() {
 199     for (size_t i = 0; i < size_; ++i) {
 200       T& value = data()[i];
 201       value.~T();
 202     }
 203     free_dynamic();
 204   }
 205
 206   void free_dynamic() {
 207     if (dynamic_ != nullptr) {
 208       if (std::alignment_of<T>::value == 0) {
 209         gpr_free(dynamic_);
 210       } else {
 211         gpr_free_aligned(dynamic_);
 212       }
 213     }
 214   }
 215
 216   typename std::aligned_storage<sizeof(T)>::type inline_[N];
 217   T* dynamic_;
 218   size_t size_;
 219   size_t capacity_;
 220 };
 221
 222 }  // namespace grpc_core
 223
 224 #endif /* GRPC_CORE_LIB_GPRPP_INLINED_VECTOR_H */