TinyPtrVector.h revision 2edc74aa1fb541253f4286a70194960dab69506b
1//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef LLVM_ADT_TINYPTRVECTOR_H
11#define LLVM_ADT_TINYPTRVECTOR_H
12
13#include "llvm/ADT/ArrayRef.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/PointerUnion.h"
16#include "llvm/Support/Compiler.h"
17
18namespace llvm {
19
20/// TinyPtrVector - This class is specialized for cases where there are
21/// normally 0 or 1 element in a vector, but is general enough to go beyond that
22/// when required.
23///
24/// NOTE: This container doesn't allow you to store a null pointer into it.
25///
26template <typename EltTy>
27class TinyPtrVector {
28public:
29  typedef llvm::SmallVector<EltTy, 4> VecTy;
30  llvm::PointerUnion<EltTy, VecTy*> Val;
31
32  TinyPtrVector() {}
33  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
34    if (VecTy *V = Val.template dyn_cast<VecTy*>())
35      Val = new VecTy(*V);
36  }
37#if LLVM_USE_RVALUE_REFERENCES
38  TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
39    RHS.Val = (EltTy)0;
40  }
41#endif
42  ~TinyPtrVector() {
43    if (VecTy *V = Val.template dyn_cast<VecTy*>())
44      delete V;
45  }
46
47  // implicit conversion operator to ArrayRef.
48  operator ArrayRef<EltTy>() const {
49    if (Val.isNull())
50      return ArrayRef<EltTy>();
51    if (Val.template is<EltTy>())
52      return *Val.getAddrOfPtr1();
53    return *Val.template get<VecTy*>();
54  }
55
56  bool empty() const {
57    // This vector can be empty if it contains no element, or if it
58    // contains a pointer to an empty vector.
59    if (Val.isNull()) return true;
60    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
61      return Vec->empty();
62    return false;
63  }
64
65  unsigned size() const {
66    if (empty())
67      return 0;
68    if (Val.template is<EltTy>())
69      return 1;
70    return Val.template get<VecTy*>()->size();
71  }
72
73  typedef const EltTy *const_iterator;
74  typedef EltTy *iterator;
75
76  iterator begin() {
77    if (empty())
78      return 0;
79
80    if (Val.template is<EltTy>())
81      return Val.getAddrOfPtr1();
82
83    return Val.template get<VecTy *>()->begin();
84
85  }
86  iterator end() {
87    if (empty())
88      return 0;
89
90    if (Val.template is<EltTy>())
91      return begin() + 1;
92
93    return Val.template get<VecTy *>()->end();
94  }
95
96  const_iterator begin() const {
97    return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
98  }
99
100  const_iterator end() const {
101    return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
102  }
103
104  EltTy operator[](unsigned i) const {
105    assert(!Val.isNull() && "can't index into an empty vector");
106    if (EltTy V = Val.template dyn_cast<EltTy>()) {
107      assert(i == 0 && "tinyvector index out of range");
108      return V;
109    }
110
111    assert(i < Val.template get<VecTy*>()->size() &&
112           "tinyvector index out of range");
113    return (*Val.template get<VecTy*>())[i];
114  }
115
116  EltTy front() const {
117    assert(!empty() && "vector empty");
118    if (EltTy V = Val.template dyn_cast<EltTy>())
119      return V;
120    return Val.template get<VecTy*>()->front();
121  }
122
123  EltTy back() const {
124    assert(!empty() && "vector empty");
125    if (EltTy V = Val.template dyn_cast<EltTy>())
126      return V;
127    return Val.template get<VecTy*>()->back();
128  }
129
130
131  void push_back(EltTy NewVal) {
132    assert(NewVal != 0 && "Can't add a null value");
133
134    // If we have nothing, add something.
135    if (Val.isNull()) {
136      Val = NewVal;
137      return;
138    }
139
140    // If we have a single value, convert to a vector.
141    if (EltTy V = Val.template dyn_cast<EltTy>()) {
142      Val = new VecTy();
143      Val.template get<VecTy*>()->push_back(V);
144    }
145
146    // Add the new value, we know we have a vector.
147    Val.template get<VecTy*>()->push_back(NewVal);
148  }
149
150  void pop_back() {
151    // If we have a single value, convert to empty.
152    if (Val.template is<EltTy>())
153      Val = (EltTy)0;
154    else if (VecTy *Vec = Val.template get<VecTy*>())
155      Vec->pop_back();
156  }
157
158
159  void clear() {
160    // If we have a single value, convert to empty.
161    if (Val.template is<EltTy>()) {
162      Val = (EltTy)0;
163    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
164      // If we have a vector form, just clear it.
165      Vec->clear();
166    }
167    // Otherwise, we're already empty.
168  }
169
170  iterator erase(iterator I) {
171    // If we have a single value, convert to empty.
172    if (Val.template is<EltTy>()) {
173      if (I == begin())
174        Val = (EltTy)0;
175    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
176      // multiple items in a vector; just do the erase, there is no
177      // benefit to collapsing back to a pointer
178      return Vec->erase(I);
179    }
180
181    return 0;
182  }
183
184private:
185  void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
186#if LLVM_USE_RVALUE_REFERENCES
187  void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET.
188#endif
189};
190} // end namespace llvm
191
192#endif
193