TinyPtrVector.h revision 40dab1059e72d3af59f2523fa8a7d05f40dafca5
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  typedef typename VecTy::value_type value_type;
31
32  llvm::PointerUnion<EltTy, VecTy*> Val;
33
34  TinyPtrVector() {}
35  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
36    if (VecTy *V = Val.template dyn_cast<VecTy*>())
37      Val = new VecTy(*V);
38  }
39#if LLVM_USE_RVALUE_REFERENCES
40  TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
41    RHS.Val = (EltTy)0;
42  }
43#endif
44  ~TinyPtrVector() {
45    if (VecTy *V = Val.template dyn_cast<VecTy*>())
46      delete V;
47  }
48
49  // implicit conversion operator to ArrayRef.
50  operator ArrayRef<EltTy>() const {
51    if (Val.isNull())
52      return ArrayRef<EltTy>();
53    if (Val.template is<EltTy>())
54      return *Val.getAddrOfPtr1();
55    return *Val.template get<VecTy*>();
56  }
57
58  bool empty() const {
59    // This vector can be empty if it contains no element, or if it
60    // contains a pointer to an empty vector.
61    if (Val.isNull()) return true;
62    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
63      return Vec->empty();
64    return false;
65  }
66
67  unsigned size() const {
68    if (empty())
69      return 0;
70    if (Val.template is<EltTy>())
71      return 1;
72    return Val.template get<VecTy*>()->size();
73  }
74
75  typedef const EltTy *const_iterator;
76  typedef EltTy *iterator;
77
78  iterator begin() {
79    if (Val.template is<EltTy>())
80      return Val.getAddrOfPtr1();
81
82    return Val.template get<VecTy *>()->begin();
83
84  }
85  iterator end() {
86    if (Val.template is<EltTy>())
87      return begin() + (Val.isNull() ? 0 : 1);
88
89    return Val.template get<VecTy *>()->end();
90  }
91
92  const_iterator begin() const {
93    return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
94  }
95
96  const_iterator end() const {
97    return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
98  }
99
100  EltTy operator[](unsigned i) const {
101    assert(!Val.isNull() && "can't index into an empty vector");
102    if (EltTy V = Val.template dyn_cast<EltTy>()) {
103      assert(i == 0 && "tinyvector index out of range");
104      return V;
105    }
106
107    assert(i < Val.template get<VecTy*>()->size() &&
108           "tinyvector index out of range");
109    return (*Val.template get<VecTy*>())[i];
110  }
111
112  EltTy front() const {
113    assert(!empty() && "vector empty");
114    if (EltTy V = Val.template dyn_cast<EltTy>())
115      return V;
116    return Val.template get<VecTy*>()->front();
117  }
118
119  EltTy back() const {
120    assert(!empty() && "vector empty");
121    if (EltTy V = Val.template dyn_cast<EltTy>())
122      return V;
123    return Val.template get<VecTy*>()->back();
124  }
125
126
127  void push_back(EltTy NewVal) {
128    assert(NewVal != 0 && "Can't add a null value");
129
130    // If we have nothing, add something.
131    if (Val.isNull()) {
132      Val = NewVal;
133      return;
134    }
135
136    // If we have a single value, convert to a vector.
137    if (EltTy V = Val.template dyn_cast<EltTy>()) {
138      Val = new VecTy();
139      Val.template get<VecTy*>()->push_back(V);
140    }
141
142    // Add the new value, we know we have a vector.
143    Val.template get<VecTy*>()->push_back(NewVal);
144  }
145
146  void pop_back() {
147    // If we have a single value, convert to empty.
148    if (Val.template is<EltTy>())
149      Val = (EltTy)0;
150    else if (VecTy *Vec = Val.template get<VecTy*>())
151      Vec->pop_back();
152  }
153
154
155  void clear() {
156    // If we have a single value, convert to empty.
157    if (Val.template is<EltTy>()) {
158      Val = (EltTy)0;
159    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
160      // If we have a vector form, just clear it.
161      Vec->clear();
162    }
163    // Otherwise, we're already empty.
164  }
165
166  iterator erase(iterator I) {
167    // If we have a single value, convert to empty.
168    if (Val.template is<EltTy>()) {
169      if (I == begin())
170        Val = (EltTy)0;
171    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
172      // multiple items in a vector; just do the erase, there is no
173      // benefit to collapsing back to a pointer
174      return Vec->erase(I);
175    }
176    return end();
177  }
178
179private:
180  void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
181#if LLVM_USE_RVALUE_REFERENCES
182  void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET.
183#endif
184};
185} // end namespace llvm
186
187#endif
188