ASTVector.h revision 314564
1109998Smarkm//===- ASTVector.h - Vector that uses ASTContext for allocation --*- C++ -*-=// 2109998Smarkm// 3109998Smarkm// The LLVM Compiler Infrastructure 4109998Smarkm// 5109998Smarkm// This file is distributed under the University of Illinois Open Source 6109998Smarkm// License. See LICENSE.TXT for details. 7109998Smarkm// 8109998Smarkm//===----------------------------------------------------------------------===// 9109998Smarkm// 10109998Smarkm// This file provides ASTVector, a vector ADT whose contents are 11109998Smarkm// allocated using the allocator associated with an ASTContext.. 12109998Smarkm// 13109998Smarkm//===----------------------------------------------------------------------===// 14109998Smarkm 15109998Smarkm// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h. 16109998Smarkm// We can refactor this core logic into something common. 17109998Smarkm 18109998Smarkm#ifndef LLVM_CLANG_AST_ASTVECTOR_H 19109998Smarkm#define LLVM_CLANG_AST_ASTVECTOR_H 20109998Smarkm 21109998Smarkm#include "clang/AST/AttrIterator.h" 22109998Smarkm#include "llvm/ADT/PointerIntPair.h" 23109998Smarkm#include "llvm/Support/type_traits.h" 24109998Smarkm#include <algorithm> 25109998Smarkm#include <cstring> 26109998Smarkm#include <memory> 27109998Smarkm 28109998Smarkmnamespace clang { 29109998Smarkm class ASTContext; 30109998Smarkm 31109998Smarkmtemplate<typename T> 32109998Smarkmclass ASTVector { 33109998Smarkmprivate: 34109998Smarkm T *Begin, *End; 35109998Smarkm llvm::PointerIntPair<T*, 1, bool> Capacity; 36109998Smarkm 37109998Smarkm void setEnd(T *P) { this->End = P; } 38109998Smarkm 39109998Smarkmprotected: 40109998Smarkm // Make a tag bit available to users of this class. 41109998Smarkm // FIXME: This is a horrible hack. 42109998Smarkm bool getTag() const { return Capacity.getInt(); } 43109998Smarkm void setTag(bool B) { Capacity.setInt(B); } 44109998Smarkm 45109998Smarkmpublic: 46109998Smarkm // Default ctor - Initialize to empty. 47109998Smarkm ASTVector() : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {} 48109998Smarkm 49109998Smarkm ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) { 50109998Smarkm O.Begin = O.End = nullptr; 51109998Smarkm O.Capacity.setPointer(nullptr); 52109998Smarkm O.Capacity.setInt(false); 53109998Smarkm } 54109998Smarkm 55109998Smarkm ASTVector(const ASTContext &C, unsigned N) 56109998Smarkm : Begin(nullptr), End(nullptr), Capacity(nullptr, false) { 57109998Smarkm reserve(C, N); 58109998Smarkm } 59109998Smarkm 60109998Smarkm ASTVector &operator=(ASTVector &&RHS) { 61109998Smarkm ASTVector O(std::move(RHS)); 62109998Smarkm using std::swap; 63109998Smarkm swap(Begin, O.Begin); 64109998Smarkm swap(End, O.End); 65109998Smarkm swap(Capacity, O.Capacity); 66109998Smarkm return *this; 67109998Smarkm } 68109998Smarkm 69109998Smarkm ~ASTVector() { 70109998Smarkm if (std::is_class<T>::value) { 71109998Smarkm // Destroy the constructed elements in the vector. 72109998Smarkm destroy_range(Begin, End); 73109998Smarkm } 74 } 75 76 typedef size_t size_type; 77 typedef ptrdiff_t difference_type; 78 typedef T value_type; 79 typedef T* iterator; 80 typedef const T* const_iterator; 81 82 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 83 typedef std::reverse_iterator<iterator> reverse_iterator; 84 85 typedef T& reference; 86 typedef const T& const_reference; 87 typedef T* pointer; 88 typedef const T* const_pointer; 89 90 // forward iterator creation methods. 91 iterator begin() { return Begin; } 92 const_iterator begin() const { return Begin; } 93 iterator end() { return End; } 94 const_iterator end() const { return End; } 95 96 // reverse iterator creation methods. 97 reverse_iterator rbegin() { return reverse_iterator(end()); } 98 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 99 reverse_iterator rend() { return reverse_iterator(begin()); } 100 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 101 102 bool empty() const { return Begin == End; } 103 size_type size() const { return End-Begin; } 104 105 reference operator[](unsigned idx) { 106 assert(Begin + idx < End); 107 return Begin[idx]; 108 } 109 const_reference operator[](unsigned idx) const { 110 assert(Begin + idx < End); 111 return Begin[idx]; 112 } 113 114 reference front() { 115 return begin()[0]; 116 } 117 const_reference front() const { 118 return begin()[0]; 119 } 120 121 reference back() { 122 return end()[-1]; 123 } 124 const_reference back() const { 125 return end()[-1]; 126 } 127 128 void pop_back() { 129 --End; 130 End->~T(); 131 } 132 133 T pop_back_val() { 134 T Result = back(); 135 pop_back(); 136 return Result; 137 } 138 139 void clear() { 140 if (std::is_class<T>::value) { 141 destroy_range(Begin, End); 142 } 143 End = Begin; 144 } 145 146 /// data - Return a pointer to the vector's buffer, even if empty(). 147 pointer data() { 148 return pointer(Begin); 149 } 150 151 /// data - Return a pointer to the vector's buffer, even if empty(). 152 const_pointer data() const { 153 return const_pointer(Begin); 154 } 155 156 void push_back(const_reference Elt, const ASTContext &C) { 157 if (End < this->capacity_ptr()) { 158 Retry: 159 new (End) T(Elt); 160 ++End; 161 return; 162 } 163 grow(C); 164 goto Retry; 165 } 166 167 void reserve(const ASTContext &C, unsigned N) { 168 if (unsigned(this->capacity_ptr()-Begin) < N) 169 grow(C, N); 170 } 171 172 /// capacity - Return the total number of elements in the currently allocated 173 /// buffer. 174 size_t capacity() const { return this->capacity_ptr() - Begin; } 175 176 /// append - Add the specified range to the end of the SmallVector. 177 /// 178 template<typename in_iter> 179 void append(const ASTContext &C, in_iter in_start, in_iter in_end) { 180 size_type NumInputs = std::distance(in_start, in_end); 181 182 if (NumInputs == 0) 183 return; 184 185 // Grow allocated space if needed. 186 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 187 this->grow(C, this->size()+NumInputs); 188 189 // Copy the new elements over. 190 // TODO: NEED To compile time dispatch on whether in_iter is a random access 191 // iterator to use the fast uninitialized_copy. 192 std::uninitialized_copy(in_start, in_end, this->end()); 193 this->setEnd(this->end() + NumInputs); 194 } 195 196 /// append - Add the specified range to the end of the SmallVector. 197 /// 198 void append(const ASTContext &C, size_type NumInputs, const T &Elt) { 199 // Grow allocated space if needed. 200 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 201 this->grow(C, this->size()+NumInputs); 202 203 // Copy the new elements over. 204 std::uninitialized_fill_n(this->end(), NumInputs, Elt); 205 this->setEnd(this->end() + NumInputs); 206 } 207 208 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 209 /// starting with "Dest", constructing elements into it as needed. 210 template<typename It1, typename It2> 211 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 212 std::uninitialized_copy(I, E, Dest); 213 } 214 215 iterator insert(const ASTContext &C, iterator I, const T &Elt) { 216 if (I == this->end()) { // Important special case for empty vector. 217 push_back(Elt, C); 218 return this->end()-1; 219 } 220 221 if (this->End < this->capacity_ptr()) { 222 Retry: 223 new (this->end()) T(this->back()); 224 this->setEnd(this->end()+1); 225 // Push everything else over. 226 std::copy_backward(I, this->end()-1, this->end()); 227 *I = Elt; 228 return I; 229 } 230 size_t EltNo = I-this->begin(); 231 this->grow(C); 232 I = this->begin()+EltNo; 233 goto Retry; 234 } 235 236 iterator insert(const ASTContext &C, iterator I, size_type NumToInsert, 237 const T &Elt) { 238 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 239 size_t InsertElt = I - this->begin(); 240 241 if (I == this->end()) { // Important special case for empty vector. 242 append(C, NumToInsert, Elt); 243 return this->begin() + InsertElt; 244 } 245 246 // Ensure there is enough space. 247 reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 248 249 // Uninvalidate the iterator. 250 I = this->begin()+InsertElt; 251 252 // If there are more elements between the insertion point and the end of the 253 // range than there are being inserted, we can use a simple approach to 254 // insertion. Since we already reserved space, we know that this won't 255 // reallocate the vector. 256 if (size_t(this->end()-I) >= NumToInsert) { 257 T *OldEnd = this->end(); 258 append(C, this->end()-NumToInsert, this->end()); 259 260 // Copy the existing elements that get replaced. 261 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 262 263 std::fill_n(I, NumToInsert, Elt); 264 return I; 265 } 266 267 // Otherwise, we're inserting more elements than exist already, and we're 268 // not inserting at the end. 269 270 // Copy over the elements that we're about to overwrite. 271 T *OldEnd = this->end(); 272 this->setEnd(this->end() + NumToInsert); 273 size_t NumOverwritten = OldEnd-I; 274 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 275 276 // Replace the overwritten part. 277 std::fill_n(I, NumOverwritten, Elt); 278 279 // Insert the non-overwritten middle part. 280 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 281 return I; 282 } 283 284 template<typename ItTy> 285 iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) { 286 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 287 size_t InsertElt = I - this->begin(); 288 289 if (I == this->end()) { // Important special case for empty vector. 290 append(C, From, To); 291 return this->begin() + InsertElt; 292 } 293 294 size_t NumToInsert = std::distance(From, To); 295 296 // Ensure there is enough space. 297 reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 298 299 // Uninvalidate the iterator. 300 I = this->begin()+InsertElt; 301 302 // If there are more elements between the insertion point and the end of the 303 // range than there are being inserted, we can use a simple approach to 304 // insertion. Since we already reserved space, we know that this won't 305 // reallocate the vector. 306 if (size_t(this->end()-I) >= NumToInsert) { 307 T *OldEnd = this->end(); 308 append(C, this->end()-NumToInsert, this->end()); 309 310 // Copy the existing elements that get replaced. 311 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 312 313 std::copy(From, To, I); 314 return I; 315 } 316 317 // Otherwise, we're inserting more elements than exist already, and we're 318 // not inserting at the end. 319 320 // Copy over the elements that we're about to overwrite. 321 T *OldEnd = this->end(); 322 this->setEnd(this->end() + NumToInsert); 323 size_t NumOverwritten = OldEnd-I; 324 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 325 326 // Replace the overwritten part. 327 for (; NumOverwritten > 0; --NumOverwritten) { 328 *I = *From; 329 ++I; ++From; 330 } 331 332 // Insert the non-overwritten middle part. 333 this->uninitialized_copy(From, To, OldEnd); 334 return I; 335 } 336 337 void resize(const ASTContext &C, unsigned N, const T &NV) { 338 if (N < this->size()) { 339 this->destroy_range(this->begin()+N, this->end()); 340 this->setEnd(this->begin()+N); 341 } else if (N > this->size()) { 342 if (this->capacity() < N) 343 this->grow(C, N); 344 construct_range(this->end(), this->begin()+N, NV); 345 this->setEnd(this->begin()+N); 346 } 347 } 348 349private: 350 /// grow - double the size of the allocated memory, guaranteeing space for at 351 /// least one more element or MinSize if specified. 352 void grow(const ASTContext &C, size_type MinSize = 1); 353 354 void construct_range(T *S, T *E, const T &Elt) { 355 for (; S != E; ++S) 356 new (S) T(Elt); 357 } 358 359 void destroy_range(T *S, T *E) { 360 while (S != E) { 361 --E; 362 E->~T(); 363 } 364 } 365 366protected: 367 const_iterator capacity_ptr() const { 368 return (iterator) Capacity.getPointer(); 369 } 370 iterator capacity_ptr() { return (iterator)Capacity.getPointer(); } 371}; 372 373// Define this out-of-line to dissuade the C++ compiler from inlining it. 374template <typename T> 375void ASTVector<T>::grow(const ASTContext &C, size_t MinSize) { 376 size_t CurCapacity = this->capacity(); 377 size_t CurSize = size(); 378 size_t NewCapacity = 2*CurCapacity; 379 if (NewCapacity < MinSize) 380 NewCapacity = MinSize; 381 382 // Allocate the memory from the ASTContext. 383 T *NewElts = new (C, alignof(T)) T[NewCapacity]; 384 385 // Copy the elements over. 386 if (Begin != End) { 387 if (std::is_class<T>::value) { 388 std::uninitialized_copy(Begin, End, NewElts); 389 // Destroy the original elements. 390 destroy_range(Begin, End); 391 } else { 392 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 393 memcpy(NewElts, Begin, CurSize * sizeof(T)); 394 } 395 } 396 397 // ASTContext never frees any memory. 398 Begin = NewElts; 399 End = NewElts+CurSize; 400 Capacity.setPointer(Begin+NewCapacity); 401} 402 403} // end: clang namespace 404#endif 405