GRPC Core  9.0.0
inlined_vector.h
Go to the documentation of this file.
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 
23 
24 #include <cassert>
25 #include <cstring>
26 
28 
29 #if GRPC_USE_ABSL
30 #include "absl/container/inlined_vector.h"
31 #endif
32 
33 namespace grpc_core {
34 
35 #if GRPC_USE_ABSL
36 
37 template <typename T, size_t N, typename A = std::allocator<T>>
38 using InlinedVector = absl::InlinedVector<T, N, A>;
39 
40 #else
41 
42 // NOTE: We eventually want to use absl::InlinedVector here. However,
43 // there are currently build problems that prevent us from using absl.
44 // In the interim, we define a custom implementation as a place-holder,
45 // with the intent to eventually replace this with the absl
46 // implementation.
47 //
48 // This place-holder implementation does not implement the full set of
49 // functionality from the absl version; it has just the methods that we
50 // currently happen to need in gRPC. If additional functionality is
51 // needed before this gets replaced with the absl version, it can be
52 // added, with the following proviso:
53 //
54 // ANY METHOD ADDED HERE MUST COMPLY WITH THE INTERFACE IN THE absl
55 // IMPLEMENTATION!
56 //
57 // TODO(nnoble, roth): Replace this with absl::InlinedVector once we
58 // integrate absl into the gRPC build system in a usable way.
59 template <typename T, size_t N>
61  public:
62  InlinedVector() { init_data(); }
63  ~InlinedVector() { destroy_elements(); }
64 
65  // copy constructor
67  init_data();
68  copy_from(v);
69  }
70 
72  if (this != &v) {
73  clear();
74  copy_from(v);
75  }
76  return *this;
77  }
78 
79  // move constructor
81  init_data();
82  move_from(v);
83  }
84 
86  if (this != &v) {
87  clear();
88  move_from(v);
89  }
90  return *this;
91  }
92 
93  T* data() {
94  return dynamic_ != nullptr ? dynamic_ : reinterpret_cast<T*>(inline_);
95  }
96 
97  const T* data() const {
98  return dynamic_ != nullptr ? dynamic_ : reinterpret_cast<const T*>(inline_);
99  }
100 
101  T& operator[](size_t offset) {
102  assert(offset < size_);
103  return data()[offset];
104  }
105 
106  const T& operator[](size_t offset) const {
107  assert(offset < size_);
108  return data()[offset];
109  }
110 
111  bool operator==(const InlinedVector& other) const {
112  if (size_ != other.size_) return false;
113  for (size_t i = 0; i < size_; ++i) {
114  // Note that this uses == instead of != so that the data class doesn't
115  // have to implement !=.
116  if (!(data()[i] == other.data()[i])) return false;
117  }
118  return true;
119  }
120 
121  bool operator!=(const InlinedVector& other) const {
122  return !(*this == other);
123  }
124 
125  void reserve(size_t capacity) {
126  if (capacity > capacity_) {
127  T* new_dynamic =
128  std::alignment_of<T>::value == 0
129  ? static_cast<T*>(gpr_malloc(sizeof(T) * capacity))
130  : static_cast<T*>(gpr_malloc_aligned(
131  sizeof(T) * capacity, std::alignment_of<T>::value));
132  move_elements(data(), new_dynamic, size_);
133  free_dynamic();
134  dynamic_ = new_dynamic;
135  capacity_ = capacity;
136  }
137  }
138 
139  void resize(size_t new_size) {
140  while (new_size > size_) emplace_back();
141  while (new_size < size_) pop_back();
142  }
143 
144  template <typename... Args>
145  void emplace_back(Args&&... args) {
146  if (size_ == capacity_) {
147  reserve(capacity_ * 2);
148  }
149  new (&(data()[size_])) T(std::forward<Args>(args)...);
150  ++size_;
151  }
152 
153  void push_back(const T& value) { emplace_back(value); }
154 
155  void push_back(T&& value) { emplace_back(std::move(value)); }
156 
157  void pop_back() {
158  assert(!empty());
159  size_t s = size();
160  T& value = data()[s - 1];
161  value.~T();
162  size_--;
163  }
164 
165  size_t size() const { return size_; }
166  bool empty() const { return size_ == 0; }
167 
168  size_t capacity() const { return capacity_; }
169 
170  void clear() {
171  destroy_elements();
172  init_data();
173  }
174 
175  private:
176  void copy_from(const InlinedVector& v) {
177  // if v is allocated, make sure we have enough capacity.
178  if (v.dynamic_ != nullptr) {
179  reserve(v.capacity_);
180  }
181  // copy over elements
182  for (size_t i = 0; i < v.size_; ++i) {
183  new (&(data()[i])) T(v[i]);
184  }
185  // copy over metadata
186  size_ = v.size_;
187  capacity_ = v.capacity_;
188  }
189 
190  void move_from(InlinedVector& v) {
191  // if v is allocated, then we steal its dynamic array; otherwise, we
192  // move the elements individually.
193  if (v.dynamic_ != nullptr) {
194  dynamic_ = v.dynamic_;
195  } else {
196  move_elements(v.data(), data(), v.size_);
197  }
198  // copy over metadata
199  size_ = v.size_;
200  capacity_ = v.capacity_;
201  // null out the original
202  v.init_data();
203  }
204 
205  static void move_elements(T* src, T* dst, size_t num_elements) {
206  for (size_t i = 0; i < num_elements; ++i) {
207  new (&dst[i]) T(std::move(src[i]));
208  src[i].~T();
209  }
210  }
211 
212  void init_data() {
213  dynamic_ = nullptr;
214  size_ = 0;
215  capacity_ = N;
216  }
217 
218  void destroy_elements() {
219  for (size_t i = 0; i < size_; ++i) {
220  T& value = data()[i];
221  value.~T();
222  }
223  free_dynamic();
224  }
225 
226  void free_dynamic() {
227  if (dynamic_ != nullptr) {
228  if (std::alignment_of<T>::value == 0) {
229  gpr_free(dynamic_);
230  } else {
231  gpr_free_aligned(dynamic_);
232  }
233  }
234  }
235 
236  typename std::aligned_storage<sizeof(T)>::type inline_[N];
237  T* dynamic_;
238  size_t size_;
239  size_t capacity_;
240 };
241 
242 #endif
243 
244 } // namespace grpc_core
245 
246 #endif /* GRPC_CORE_LIB_GPRPP_INLINED_VECTOR_H */
Definition: inlined_vector.h:60
void push_back(T &&value)
Definition: inlined_vector.h:155
T * data()
Definition: inlined_vector.h:93
bool operator==(const InlinedVector &other) const
Definition: inlined_vector.h:111
InlinedVector(InlinedVector &&v)
Definition: inlined_vector.h:80
void resize(size_t new_size)
Definition: inlined_vector.h:139
const T & operator[](size_t offset) const
Definition: inlined_vector.h:106
~InlinedVector()
Definition: inlined_vector.h:63
void pop_back()
Definition: inlined_vector.h:157
T & operator[](size_t offset)
Definition: inlined_vector.h:101
const T * data() const
Definition: inlined_vector.h:97
void reserve(size_t capacity)
Definition: inlined_vector.h:125
void push_back(const T &value)
Definition: inlined_vector.h:153
void emplace_back(Args &&... args)
Definition: inlined_vector.h:145
size_t size() const
Definition: inlined_vector.h:165
bool empty() const
Definition: inlined_vector.h:166
InlinedVector & operator=(const InlinedVector &v)
Definition: inlined_vector.h:71
void clear()
Definition: inlined_vector.h:170
bool operator!=(const InlinedVector &other) const
Definition: inlined_vector.h:121
InlinedVector()
Definition: inlined_vector.h:62
size_t capacity() const
Definition: inlined_vector.h:168
InlinedVector & operator=(InlinedVector &&v)
Definition: inlined_vector.h:85
InlinedVector(const InlinedVector &v)
Definition: inlined_vector.h:66
GPRAPI void * gpr_malloc_aligned(size_t size, size_t alignment)
aligned malloc, never returns NULL, will align to alignment, which must be a power of 2.
Definition: alloc.cc:65
GPRAPI void gpr_free(void *ptr)
free
Definition: alloc.cc:50
GPRAPI void * gpr_malloc(size_t size)
malloc.
Definition: alloc.cc:28
GPRAPI void gpr_free_aligned(void *ptr)
free memory allocated by gpr_malloc_aligned
Definition: alloc.cc:74
Round Robin Policy.
Definition: backend_metric.cc:24