TinyPtrVector.h revision b4c28fc93f5149a0bd7967af44c429412e751c56 
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  void push_back(EltTy NewVal) {
127    assert(NewVal != 0 && "Can't add a null value");
128
129    // If we have nothing, add something.
130    if (Val.isNull()) {
131      Val = NewVal;
132      return;
133    }
134
135    // If we have a single value, convert to a vector.
136    if (EltTy V = Val.template dyn_cast<EltTy>()) {
137      Val = new VecTy();
138      Val.template get<VecTy*>()->push_back(V);
139    }
140
141    // Add the new value, we know we have a vector.
142    Val.template get<VecTy*>()->push_back(NewVal);
143  }
144
145  void pop_back() {
146    // If we have a single value, convert to empty.
147    if (Val.template is<EltTy>())
148      Val = (EltTy)0;
149    else if (VecTy *Vec = Val.template get<VecTy*>())
150      Vec->pop_back();
151  }
152
153  void clear() {
154    // If we have a single value, convert to empty.
155    if (Val.template is<EltTy>()) {
156      Val = (EltTy)0;
157    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
158      // If we have a vector form, just clear it.
159      Vec->clear();
160    }
161    // Otherwise, we're already empty.
162  }
163
164  iterator erase(iterator I) {
165    // If we have a single value, convert to empty.
166    if (Val.template is<EltTy>()) {
167      if (I == begin())
168        Val = (EltTy)0;
169    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
170      // multiple items in a vector; just do the erase, there is no
171      // benefit to collapsing back to a pointer
172      return Vec->erase(I);
173    }
174    return end();
175  }
176
177private:
178  void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
179#if LLVM_USE_RVALUE_REFERENCES
180  void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET.
181#endif
182};
183} // end namespace llvm
184
185#endif
186