BumpVector.h revision 5fe4d9deb543a19f557e3d85c5f33867af97cd96
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" 245fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#include <algorithm> 255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 265fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremeneknamespace clang { 275fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 285fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass BumpVectorContext { 295fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek llvm::BumpPtrAllocator Alloc; 305fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekpublic: 315fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek llvm::BumpPtrAllocator &getAllocator() { return Alloc; } 325fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek}; 335fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 345fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenektemplate<typename T> 355fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekclass BumpVector { 365fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T *Begin, *End, *Capacity; 375fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekpublic: 385fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Default ctor - Initialize to empty. 395fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek explicit BumpVector(BumpVectorContext &C, unsigned N) 405fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek : Begin(NULL), End(NULL), Capacity(NULL) { 415fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reserve(C, N); 425fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 435fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 445fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ~BumpVector() { 455fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 465fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Destroy the constructed elements in the vector. 475fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 485fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 495fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 505fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 515fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef size_t size_type; 525fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef ptrdiff_t difference_type; 535fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T value_type; 545fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T* iterator; 555fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T* const_iterator; 565fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 575fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 585fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 595fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 605fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T& reference; 615fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T& const_reference; 625fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef T* pointer; 635fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek typedef const T* const_pointer; 645fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 655fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // forward iterator creation methods. 665fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek iterator begin() { return Begin; } 675fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_iterator begin() const { return Begin; } 685fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek iterator end() { return End; } 695fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_iterator end() const { return End; } 705fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 715fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // reverse iterator creation methods. 725fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reverse_iterator rbegin() { return reverse_iterator(end()); } 735fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 745fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reverse_iterator rend() { return reverse_iterator(begin()); } 755fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 765fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 775fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek bool empty() const { return Begin == End; } 785fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_type size() const { return End-Begin; } 795fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 805fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference operator[](unsigned idx) { 815fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek assert(Begin + idx < End); 825fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Begin[idx]; 835fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 845fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference operator[](unsigned idx) const { 855fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek assert(Begin + idx < End); 865fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Begin[idx]; 875fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 885fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 895fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference front() { 905fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return begin()[0]; 915fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 925fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference front() const { 935fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return begin()[0]; 945fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 955fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 965fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek reference back() { 975fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return end()[-1]; 985fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 995fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_reference back() const { 1005fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return end()[-1]; 1015fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1025fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1035fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void pop_back() { 1045fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek --End; 1055fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End->~T(); 1065fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1075fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1085fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T pop_back_val() { 1095fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T Result = back(); 1105fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek pop_back(); 1115fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return Result; 1125fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1135fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1145fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void clear() { 1155fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 1165fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 1175fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1185fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End = Begin; 1195fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1205fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1215fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1225fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek pointer data() { 1235fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return pointer(Begin); 1245fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1265fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1275fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek const_pointer data() const { 1285fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return const_pointer(Begin); 1295fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1305fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1315fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void push_back(const_reference Elt, BumpVectorContext &C) { 1325fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (End < Capacity) { 1335fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Retry: 1345fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek new (End) T(Elt); 1355fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek ++End; 1365fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek return; 1375fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1385fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek grow(C); 1395fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek goto Retry; 1405fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1415fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1425fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void reserve(BumpVectorContext &C, unsigned N) { 1435fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (unsigned(Capacity-Begin) < N) 1445fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek grow(C, N); 1455fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1465fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1475fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// capacity - Return the total number of elements in the currently allocated 1485fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// buffer. 1495fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t capacity() const { return Capacity - Begin; } 1505fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1515fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekprivate: 1525fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// grow - double the size of the allocated memory, guaranteeing space for at 1535fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek /// least one more element or MinSize if specified. 1545fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void grow(BumpVectorContext &C, size_type MinSize = 0); 1555fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1565fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void construct_range(T *S, T *E, const T &Elt) { 1575fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek for (; S != E; ++S) 1585fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek new (S) T(Elt); 1595fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1605fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1615fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek void destroy_range(T *S, T *E) { 1625fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek while (S != E) { 1635fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek --E; 1645fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek E->~T(); 1655fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1665fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1675fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek}; 1685fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1695fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek// Define this out-of-line to dissuade the C++ compiler from inlining it. 1705fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenektemplate <typename T> 1715fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenekvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 1725fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t CurCapacity = Capacity-Begin; 1735fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t CurSize = size(); 1745fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek size_t NewCapacity = 2*CurCapacity; 1755fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (NewCapacity < MinSize) 1765fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek NewCapacity = MinSize; 1775fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1785fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Allocate the memory from the BumpPtrAllocator. 1795fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek T *NewElts = C.getAllocator().Allocate<T>(NewCapacity); 1805fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1815fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Copy the elements over. 1825fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek if (llvm::is_class<T>::value) { 1835fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek std::uninitialized_copy(Begin, End, NewElts); 1845fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Destroy the original elements. 1855fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek destroy_range(Begin, End); 1865fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1875fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek else { 1885fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 1895fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek memcpy(NewElts, Begin, CurSize * sizeof(T)); 1905fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek } 1915fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1925fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // For now, leak 'Begin'. We can add it back to a freelist in 1935fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek // BumpVectorContext. 1945fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Begin = NewElts; 1955fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek End = NewElts+CurSize; 1965fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Capacity = Begin+NewCapacity; 1975fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek} 1985fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek 1995fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek} // end: clang namespace 2005fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek#endif // end: LLVM_CLANG_BUMP_VECTOR 201