SmallVector.h revision f28265402130eb03762d9a6333fd8f87765a8875
1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the SmallVector class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_SMALLVECTOR_H 15#define LLVM_ADT_SMALLVECTOR_H 16 17#include <cassert> 18#include <memory> 19 20namespace llvm { 21 22/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 23/// for the case when the array is small. It contains some number of elements 24/// in-place, which allows it to avoid heap allocation when the actual number of 25/// elements is below that threshold. This allows normal "small" cases to be 26/// fast without losing generality for large inputs. 27/// 28/// Note that this does not attempt to be exception safe. 29/// 30template <typename T, unsigned N> 31class SmallVector { 32 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 33 // don't want it to be automatically run, so we need to represent the space as 34 // something else. An array of char would work great, but might not be 35 // aligned sufficiently. Instead, we either use GCC extensions, or some 36 // number of union instances for the space, which guarantee maximal alignment. 37 union U { 38 double D; 39 long double LD; 40 long long L; 41 void *P; 42 }; 43 44 /// InlineElts - These are the 'N' elements that are stored inline in the body 45 /// of the vector 46 U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)]; 47 T *Begin, *End, *Capacity; 48public: 49 // Default ctor - Initialize to empty. 50 SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { 51 } 52 53 SmallVector(const SmallVector &RHS) { 54 unsigned RHSSize = RHS.size(); 55 Begin = (T*)InlineElts; 56 57 // Doesn't fit in the small case? Allocate space. 58 if (RHSSize > N) { 59 End = Capacity = Begin; 60 grow(RHSSize); 61 } 62 End = Begin+RHSSize; 63 Capacity = Begin+N; 64 std::uninitialized_copy(RHS.begin(), RHS.end(), Begin); 65 } 66 ~SmallVector() { 67 // If this wasn't grown from the inline copy, deallocate the old space. 68 if ((void*)Begin != (void*)InlineElts) 69 delete[] (char*)Begin; 70 } 71 72 typedef size_t size_type; 73 typedef T* iterator; 74 typedef const T* const_iterator; 75 typedef T& reference; 76 typedef const T& const_reference; 77 78 bool empty() const { return Begin == End; } 79 size_type size() const { return End-Begin; } 80 81 iterator begin() { return Begin; } 82 const_iterator begin() const { return Begin; } 83 84 iterator end() { return End; } 85 const_iterator end() const { return End; } 86 87 reference operator[](unsigned idx) { 88 assert(idx < size() && "out of range reference!"); 89 return Begin[idx]; 90 } 91 const_reference operator[](unsigned idx) const { 92 assert(idx < size() && "out of range reference!"); 93 return Begin[idx]; 94 } 95 96 reference back() { 97 assert(!empty() && "SmallVector is empty!"); 98 return end()[-1]; 99 } 100 const_reference back() const { 101 assert(!empty() && "SmallVector is empty!"); 102 return end()[-1]; 103 } 104 105 void push_back(const_reference Elt) { 106 if (End < Capacity) { 107 Retry: 108 new (End) T(Elt); 109 ++End; 110 return; 111 } 112 grow(); 113 goto Retry; 114 } 115 116 const SmallVector &operator=(const SmallVector &RHS) { 117 // Avoid self-assignment. 118 if (this == &RHS) return *this; 119 120 // If we already have sufficient space, assign the common elements, then 121 // destroy any excess. 122 unsigned RHSSize = RHS.size(); 123 unsigned CurSize = size(); 124 if (CurSize >= RHSSize) { 125 // Assign common elements. 126 for (unsigned i = 0; i != RHSSize; ++i) 127 Begin[i] = RHS.Begin[i]; 128 129 // Destroy excess elements. 130 for (unsigned i = RHSSize; i != CurSize; ++i) 131 Begin[i].~T(); 132 133 // Trim. 134 End = Begin + RHSSize; 135 return *this; 136 } 137 138 // If we have to grow to have enough elements, destroy the current elements. 139 // This allows us to avoid copying them during the grow. 140 if (Capacity-Begin < RHSSize) { 141 // Destroy current elements. 142 for (T *I = Begin, E = End; I != E; ++I) 143 I->~T(); 144 End = Begin; 145 CurSize = 0; 146 grow(RHSSize); 147 } else { 148 // Otherwise, use assignment for the already-constructed elements. 149 for (unsigned i = 0; i != CurSize; ++i) 150 Begin[i] = RHS.Begin[i]; 151 } 152 153 // Copy construct the new elements in place. 154 std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize); 155 156 // Set end. 157 End = Begin+RHSSize; 158 } 159 160private: 161 /// isSmall - Return true if this is a smallvector which has not had dynamic 162 /// memory allocated for it. 163 bool isSmall() const { 164 return (void*)Begin == (void*)InlineElts; 165 } 166 167 /// grow - double the size of the allocated memory, guaranteeing space for at 168 /// least one more element or MinSize if specified. 169 void grow(unsigned MinSize = 0) { 170 unsigned CurCapacity = Capacity-Begin; 171 unsigned CurSize = size(); 172 unsigned NewCapacity = 2*CurCapacity; 173 if (NewCapacity < MinSize) 174 NewCapacity = MinSize; 175 T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]); 176 177 // Copy the elements over. 178 std::uninitialized_copy(Begin, End, NewElts); 179 180 // Destroy the original elements. 181 for (T *I = Begin, *E = End; I != E; ++I) 182 I->~T(); 183 184 // If this wasn't grown from the inline copy, deallocate the old space. 185 if (!isSmall()) 186 delete[] (char*)Begin; 187 188 Begin = NewElts; 189 End = NewElts+CurSize; 190 Capacity = Begin+NewCapacity*2; 191 } 192}; 193 194} // End llvm namespace 195 196#endif 197