1//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_ADT_TINYPTRVECTOR_H
10#define LLVM_ADT_TINYPTRVECTOR_H
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/ADT/None.h"
14#include "llvm/ADT/PointerUnion.h"
15#include "llvm/ADT/SmallVector.h"
16#include <cassert>
17#include <cstddef>
18#include <iterator>
19#include <type_traits>
20
21namespace llvm {
22
23/// TinyPtrVector - This class is specialized for cases where there are
24/// normally 0 or 1 element in a vector, but is general enough to go beyond that
25/// when required.
26///
27/// NOTE: This container doesn't allow you to store a null pointer into it.
28///
29template <typename EltTy>
30class TinyPtrVector {
31public:
32  using VecTy = SmallVector<EltTy, 4>;
33  using value_type = typename VecTy::value_type;
34  // EltTy must be the first pointer type so that is<EltTy> is true for the
35  // default-constructed PtrUnion. This allows an empty TinyPtrVector to
36  // naturally vend a begin/end iterator of type EltTy* without an additional
37  // check for the empty state.
38  using PtrUnion = PointerUnion<EltTy, VecTy *>;
39
40private:
41  PtrUnion Val;
42
43public:
44  TinyPtrVector() = default;
45
46  ~TinyPtrVector() {
47    if (VecTy *V = Val.template dyn_cast<VecTy*>())
48      delete V;
49  }
50
51  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
52    if (VecTy *V = Val.template dyn_cast<VecTy*>())
53      Val = new VecTy(*V);
54  }
55
56  TinyPtrVector &operator=(const TinyPtrVector &RHS) {
57    if (this == &RHS)
58      return *this;
59    if (RHS.empty()) {
60      this->clear();
61      return *this;
62    }
63
64    // Try to squeeze into the single slot. If it won't fit, allocate a copied
65    // vector.
66    if (Val.template is<EltTy>()) {
67      if (RHS.size() == 1)
68        Val = RHS.front();
69      else
70        Val = new VecTy(*RHS.Val.template get<VecTy*>());
71      return *this;
72    }
73
74    // If we have a full vector allocated, try to re-use it.
75    if (RHS.Val.template is<EltTy>()) {
76      Val.template get<VecTy*>()->clear();
77      Val.template get<VecTy*>()->push_back(RHS.front());
78    } else {
79      *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
80    }
81    return *this;
82  }
83
84  TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
85    RHS.Val = (EltTy)nullptr;
86  }
87
88  TinyPtrVector &operator=(TinyPtrVector &&RHS) {
89    if (this == &RHS)
90      return *this;
91    if (RHS.empty()) {
92      this->clear();
93      return *this;
94    }
95
96    // If this vector has been allocated on the heap, re-use it if cheap. If it
97    // would require more copying, just delete it and we'll steal the other
98    // side.
99    if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
100      if (RHS.Val.template is<EltTy>()) {
101        V->clear();
102        V->push_back(RHS.front());
103        RHS.Val = EltTy();
104        return *this;
105      }
106      delete V;
107    }
108
109    Val = RHS.Val;
110    RHS.Val = EltTy();
111    return *this;
112  }
113
114  TinyPtrVector(std::initializer_list<EltTy> IL)
115      : Val(IL.size() == 0
116                ? PtrUnion()
117                : IL.size() == 1 ? PtrUnion(*IL.begin())
118                                 : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
119
120  /// Constructor from an ArrayRef.
121  ///
122  /// This also is a constructor for individual array elements due to the single
123  /// element constructor for ArrayRef.
124  explicit TinyPtrVector(ArrayRef<EltTy> Elts)
125      : Val(Elts.empty()
126                ? PtrUnion()
127                : Elts.size() == 1
128                      ? PtrUnion(Elts[0])
129                      : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
130
131  TinyPtrVector(size_t Count, EltTy Value)
132      : Val(Count == 0 ? PtrUnion()
133                       : Count == 1 ? PtrUnion(Value)
134                                    : PtrUnion(new VecTy(Count, Value))) {}
135
136  // implicit conversion operator to ArrayRef.
137  operator ArrayRef<EltTy>() const {
138    if (Val.isNull())
139      return None;
140    if (Val.template is<EltTy>())
141      return *Val.getAddrOfPtr1();
142    return *Val.template get<VecTy*>();
143  }
144
145  // implicit conversion operator to MutableArrayRef.
146  operator MutableArrayRef<EltTy>() {
147    if (Val.isNull())
148      return None;
149    if (Val.template is<EltTy>())
150      return *Val.getAddrOfPtr1();
151    return *Val.template get<VecTy*>();
152  }
153
154  // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
155  template<typename U,
156           typename std::enable_if<
157               std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
158               bool>::type = false>
159  operator ArrayRef<U>() const {
160    return operator ArrayRef<EltTy>();
161  }
162
163  bool empty() const {
164    // This vector can be empty if it contains no element, or if it
165    // contains a pointer to an empty vector.
166    if (Val.isNull()) return true;
167    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
168      return Vec->empty();
169    return false;
170  }
171
172  unsigned size() const {
173    if (empty())
174      return 0;
175    if (Val.template is<EltTy>())
176      return 1;
177    return Val.template get<VecTy*>()->size();
178  }
179
180  using iterator = EltTy *;
181  using const_iterator = const EltTy *;
182  using reverse_iterator = std::reverse_iterator<iterator>;
183  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
184
185  iterator begin() {
186    if (Val.template is<EltTy>())
187      return Val.getAddrOfPtr1();
188
189    return Val.template get<VecTy *>()->begin();
190  }
191
192  iterator end() {
193    if (Val.template is<EltTy>())
194      return begin() + (Val.isNull() ? 0 : 1);
195
196    return Val.template get<VecTy *>()->end();
197  }
198
199  const_iterator begin() const {
200    return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
201  }
202
203  const_iterator end() const {
204    return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
205  }
206
207  reverse_iterator rbegin() { return reverse_iterator(end()); }
208  reverse_iterator rend() { return reverse_iterator(begin()); }
209
210  const_reverse_iterator rbegin() const {
211    return const_reverse_iterator(end());
212  }
213
214  const_reverse_iterator rend() const {
215    return const_reverse_iterator(begin());
216  }
217
218  EltTy operator[](unsigned i) const {
219    assert(!Val.isNull() && "can't index into an empty vector");
220    if (Val.template is<EltTy>()) {
221      assert(i == 0 && "tinyvector index out of range");
222      return Val.template get<EltTy>();
223    }
224
225    assert(i < Val.template get<VecTy*>()->size() &&
226           "tinyvector index out of range");
227    return (*Val.template get<VecTy*>())[i];
228  }
229
230  EltTy front() const {
231    assert(!empty() && "vector empty");
232    if (Val.template is<EltTy>())
233      return Val.template get<EltTy>();
234    return Val.template get<VecTy*>()->front();
235  }
236
237  EltTy back() const {
238    assert(!empty() && "vector empty");
239    if (Val.template is<EltTy>())
240      return Val.template get<EltTy>();
241    return Val.template get<VecTy*>()->back();
242  }
243
244  void push_back(EltTy NewVal) {
245    // If we have nothing, add something.
246    if (Val.isNull()) {
247      Val = NewVal;
248      assert(!Val.isNull() && "Can't add a null value");
249      return;
250    }
251
252    // If we have a single value, convert to a vector.
253    if (Val.template is<EltTy>()) {
254      EltTy V = Val.template get<EltTy>();
255      Val = new VecTy();
256      Val.template get<VecTy*>()->push_back(V);
257    }
258
259    // Add the new value, we know we have a vector.
260    Val.template get<VecTy*>()->push_back(NewVal);
261  }
262
263  void pop_back() {
264    // If we have a single value, convert to empty.
265    if (Val.template is<EltTy>())
266      Val = (EltTy)nullptr;
267    else if (VecTy *Vec = Val.template get<VecTy*>())
268      Vec->pop_back();
269  }
270
271  void clear() {
272    // If we have a single value, convert to empty.
273    if (Val.template is<EltTy>()) {
274      Val = EltTy();
275    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
276      // If we have a vector form, just clear it.
277      Vec->clear();
278    }
279    // Otherwise, we're already empty.
280  }
281
282  iterator erase(iterator I) {
283    assert(I >= begin() && "Iterator to erase is out of bounds.");
284    assert(I < end() && "Erasing at past-the-end iterator.");
285
286    // If we have a single value, convert to empty.
287    if (Val.template is<EltTy>()) {
288      if (I == begin())
289        Val = EltTy();
290    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
291      // multiple items in a vector; just do the erase, there is no
292      // benefit to collapsing back to a pointer
293      return Vec->erase(I);
294    }
295    return end();
296  }
297
298  iterator erase(iterator S, iterator E) {
299    assert(S >= begin() && "Range to erase is out of bounds.");
300    assert(S <= E && "Trying to erase invalid range.");
301    assert(E <= end() && "Trying to erase past the end.");
302
303    if (Val.template is<EltTy>()) {
304      if (S == begin() && S != E)
305        Val = EltTy();
306    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
307      return Vec->erase(S, E);
308    }
309    return end();
310  }
311
312  iterator insert(iterator I, const EltTy &Elt) {
313    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
314    assert(I <= this->end() && "Inserting past the end of the vector.");
315    if (I == end()) {
316      push_back(Elt);
317      return std::prev(end());
318    }
319    assert(!Val.isNull() && "Null value with non-end insert iterator.");
320    if (Val.template is<EltTy>()) {
321      EltTy V = Val.template get<EltTy>();
322      assert(I == begin());
323      Val = Elt;
324      push_back(V);
325      return begin();
326    }
327
328    return Val.template get<VecTy*>()->insert(I, Elt);
329  }
330
331  template<typename ItTy>
332  iterator insert(iterator I, ItTy From, ItTy To) {
333    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
334    assert(I <= this->end() && "Inserting past the end of the vector.");
335    if (From == To)
336      return I;
337
338    // If we have a single value, convert to a vector.
339    ptrdiff_t Offset = I - begin();
340    if (Val.isNull()) {
341      if (std::next(From) == To) {
342        Val = *From;
343        return begin();
344      }
345
346      Val = new VecTy();
347    } else if (Val.template is<EltTy>()) {
348      EltTy V = Val.template get<EltTy>();
349      Val = new VecTy();
350      Val.template get<VecTy*>()->push_back(V);
351    }
352    return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
353  }
354};
355
356} // end namespace llvm
357
358#endif // LLVM_ADT_TINYPTRVECTOR_H
359