15fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek//===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- C++ -*-=// 25fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// 35fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// The LLVM Compiler Infrastructure 45fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// 55fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// This file is distributed under the University of Illinois Open Source 65fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// License. See LICENSE.TXT for details. 75fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// 85fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek//===----------------------------------------------------------------------===// 95fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// 105fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// This file provides BumpVector, a vector-like ADT whose contents are 115fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// allocated from a BumpPtrAllocator. 125fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// 135fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek//===----------------------------------------------------------------------===// 145fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 155fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 165fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// refactor this core logic into something common that is shared between 175fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// the two. The main thing that is different is the allocation strategy. 185fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 195fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#ifndef LLVM_CLANG_BUMP_VECTOR 205fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#define LLVM_CLANG_BUMP_VECTOR 215fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 225fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#include "llvm/Support/type_traits.h" 235fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#include "llvm/Support/Allocator.h" 2487342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek#include "llvm/ADT/PointerIntPair.h" 255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#include <algorithm> 26f7bb329deb2f8ce9ae7f187d6fbe0f98deaeed0dDaniel Dunbar#include <cstring> 27403ba3522d1b1c97ae5fad81c1a2c4b3a754e1c1Nick Lewycky#include <iterator> 2868f774dc9f4ad823dff4195821ba789e4e61a3a6Duncan Sands#include <memory> 295fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 305fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremeneknamespace clang { 315fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 325fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass BumpVectorContext { 33375e69cb19e9ba65ab5f822ad5d44cffae15edb1Ted Kremenek llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 345fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekpublic: 3587342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 3687342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek /// and destroys it when the BumpVectorContext object is destroyed. 37375e69cb19e9ba65ab5f822ad5d44cffae15edb1Ted Kremenek BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 3887342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek 3987342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek /// Construct a new BumpVectorContext that reuses an existing 4087342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 4187342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek /// BumpVectorContext object is destroyed. 42375e69cb19e9ba65ab5f822ad5d44cffae15edb1Ted Kremenek BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 4387342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek 4487342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek ~BumpVectorContext() { 4587342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek if (Alloc.getInt()) 4687342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek delete Alloc.getPointer(); 4787342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek } 4887342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek 4987342dc37237c6efb9e311bacb12547de3ccbc0fTed Kremenek llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 505fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek}; 515fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 525fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenektemplate<typename T> 535fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass BumpVector { 545fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T *Begin, *End, *Capacity; 555fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekpublic: 565fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Default ctor - Initialize to empty. 575fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek explicit BumpVector(BumpVectorContext &C, unsigned N) 585fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek : Begin(NULL), End(NULL), Capacity(NULL) { 595fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reserve(C, N); 605fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 615fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 625fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ~BumpVector() { 635fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 645fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Destroy the constructed elements in the vector. 655fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 665fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 675fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 685fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 695fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef size_t size_type; 705fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef ptrdiff_t difference_type; 715fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T value_type; 725fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T* iterator; 735fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T* const_iterator; 745fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 755fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 765fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 775fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 785fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T& reference; 795fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T& const_reference; 805fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T* pointer; 815fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T* const_pointer; 825fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 835fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // forward iterator creation methods. 845fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek iterator begin() { return Begin; } 855fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_iterator begin() const { return Begin; } 865fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek iterator end() { return End; } 875fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_iterator end() const { return End; } 885fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 895fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // reverse iterator creation methods. 905fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reverse_iterator rbegin() { return reverse_iterator(end()); } 915fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 925fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reverse_iterator rend() { return reverse_iterator(begin()); } 935fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 945fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 955fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek bool empty() const { return Begin == End; } 965fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_type size() const { return End-Begin; } 975fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 985fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference operator[](unsigned idx) { 995fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek assert(Begin + idx < End); 1005fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Begin[idx]; 1015fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1025fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference operator[](unsigned idx) const { 1035fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek assert(Begin + idx < End); 1045fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Begin[idx]; 1055fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1065fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1075fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference front() { 1085fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return begin()[0]; 1095fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1105fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference front() const { 1115fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return begin()[0]; 1125fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1135fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1145fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference back() { 1155fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return end()[-1]; 1165fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1175fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference back() const { 1185fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return end()[-1]; 1195fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1205fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1215fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void pop_back() { 1225fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek --End; 1235fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End->~T(); 1245fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1265fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T pop_back_val() { 1275fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T Result = back(); 1285fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek pop_back(); 1295fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Result; 1305fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1315fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1325fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void clear() { 1335fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 1345fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 1355fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1365fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End = Begin; 1375fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1385fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1395fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1405fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek pointer data() { 1415fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return pointer(Begin); 1425fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1435fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1445fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1455fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_pointer data() const { 1465fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return const_pointer(Begin); 1475fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1485fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1495fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void push_back(const_reference Elt, BumpVectorContext &C) { 1505fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (End < Capacity) { 1515fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Retry: 1525fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek new (End) T(Elt); 1535fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ++End; 1545fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return; 1555fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1565fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek grow(C); 1575fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek goto Retry; 1585fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 15958eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek 16058eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek /// insert - Insert some number of copies of element into a position. Return 16158eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek /// iterator to position after last inserted copy. 16258eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek iterator insert(iterator I, size_t Cnt, const_reference E, 16358eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek BumpVectorContext &C) { 16458eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek assert (I >= Begin && I <= End && "Iterator out of bounds."); 16558eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek if (End + Cnt <= Capacity) { 16658eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek Retry: 16758eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek move_range_right(I, End, Cnt); 16858eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek construct_range(I, I + Cnt, E); 16958eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek End += Cnt; 17058eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek return I + Cnt; 17158eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek } 17258eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek ptrdiff_t D = I - Begin; 17358eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek grow(C, size() + Cnt); 17458eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek I = Begin + D; 17558eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek goto Retry; 17658eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek } 17758eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek 1785fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void reserve(BumpVectorContext &C, unsigned N) { 1795fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (unsigned(Capacity-Begin) < N) 1805fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek grow(C, N); 1815fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1825fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1835fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// capacity - Return the total number of elements in the currently allocated 1845fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// buffer. 1855fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t capacity() const { return Capacity - Begin; } 1865fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1875fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekprivate: 1885fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// grow - double the size of the allocated memory, guaranteeing space for at 1895fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// least one more element or MinSize if specified. 1901488c7a0989e4543b9acb46fa02a54d12a9d0cc9Ted Kremenek void grow(BumpVectorContext &C, size_type MinSize = 1); 1915fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1925fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void construct_range(T *S, T *E, const T &Elt) { 1935fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek for (; S != E; ++S) 1945fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek new (S) T(Elt); 1955fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1965fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1975fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void destroy_range(T *S, T *E) { 1985fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek while (S != E) { 1995fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek --E; 2005fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek E->~T(); 20158eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek } 20258eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek } 20358eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek 20458eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek void move_range_right(T *S, T *E, size_t D) { 20558eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 20658eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek --E; 20758eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek new (I) T(*E); 20858eb45baff08fd27aeef65fc4e6ae35a4b3a1d90Ted Kremenek E->~T(); 2095fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 2105fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 2115fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek}; 2125fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 2135fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// Define this out-of-line to dissuade the C++ compiler from inlining it. 2145fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenektemplate <typename T> 2155fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 2165fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t CurCapacity = Capacity-Begin; 2175fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t CurSize = size(); 2185fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t NewCapacity = 2*CurCapacity; 2195fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (NewCapacity < MinSize) 2205fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek NewCapacity = MinSize; 2215fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 2225fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Allocate the memory from the BumpPtrAllocator. 223f0e75d6baf0dc6ba0a7d66726d9e3ba455db8639Ted Kremenek T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 2245fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 2255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Copy the elements over. 2265fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 2275fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek std::uninitialized_copy(Begin, End, NewElts); 2285fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Destroy the original elements. 2295fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 2305fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 2315fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek else { 2325fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 2335fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek memcpy(NewElts, Begin, CurSize * sizeof(T)); 2345fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 2355fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 2365fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // For now, leak 'Begin'. We can add it back to a freelist in 2375fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // BumpVectorContext. 2385fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Begin = NewElts; 2395fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End = NewElts+CurSize; 2405fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Capacity = Begin+NewCapacity; 2415fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek} 2425fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 2435fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek} // end: clang namespace 2445fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#endif // end: LLVM_CLANG_BUMP_VECTOR 245