BumpVector.h revision f0e75d6baf0dc6ba0a7d66726d9e3ba455db8639 
1//===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- 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//  This file provides BumpVector, a vector-like ADT whose contents are
11//  allocated from a BumpPtrAllocator.
12//
13//===----------------------------------------------------------------------===//
14
15// FIXME: Most of this is copy-and-paste from SmallVector.h.  We can
16// refactor this core logic into something common that is shared between
17// the two.  The main thing that is different is the allocation strategy.
18
19#ifndef LLVM_CLANG_BUMP_VECTOR
20#define LLVM_CLANG_BUMP_VECTOR
21
22#include "llvm/Support/type_traits.h"
23#include "llvm/Support/Allocator.h"
24#include <algorithm>
25
26namespace clang {
27
28class BumpVectorContext {
29  llvm::BumpPtrAllocator Alloc;
30public:
31  llvm::BumpPtrAllocator &getAllocator() { return Alloc; }
32};
33
34template<typename T>
35class BumpVector {
36  T *Begin, *End, *Capacity;
37public:
38  // Default ctor - Initialize to empty.
39  explicit BumpVector(BumpVectorContext &C, unsigned N)
40  : Begin(NULL), End(NULL), Capacity(NULL) {
41    reserve(C, N);
42  }
43
44  ~BumpVector() {
45    if (llvm::is_class<T>::value) {
46      // Destroy the constructed elements in the vector.
47      destroy_range(Begin, End);
48    }
49  }
50
51  typedef size_t size_type;
52  typedef ptrdiff_t difference_type;
53  typedef T value_type;
54  typedef T* iterator;
55  typedef const T* const_iterator;
56
57  typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
58  typedef std::reverse_iterator<iterator>  reverse_iterator;
59
60  typedef T& reference;
61  typedef const T& const_reference;
62  typedef T* pointer;
63  typedef const T* const_pointer;
64
65  // forward iterator creation methods.
66  iterator begin() { return Begin; }
67  const_iterator begin() const { return Begin; }
68  iterator end() { return End; }
69  const_iterator end() const { return End; }
70
71  // reverse iterator creation methods.
72  reverse_iterator rbegin()            { return reverse_iterator(end()); }
73  const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
74  reverse_iterator rend()              { return reverse_iterator(begin()); }
75  const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
76
77  bool empty() const { return Begin == End; }
78  size_type size() const { return End-Begin; }
79
80  reference operator[](unsigned idx) {
81    assert(Begin + idx < End);
82    return Begin[idx];
83  }
84  const_reference operator[](unsigned idx) const {
85    assert(Begin + idx < End);
86    return Begin[idx];
87  }
88
89  reference front() {
90    return begin()[0];
91  }
92  const_reference front() const {
93    return begin()[0];
94  }
95
96  reference back() {
97    return end()[-1];
98  }
99  const_reference back() const {
100    return end()[-1];
101  }
102
103  void pop_back() {
104    --End;
105    End->~T();
106  }
107
108  T pop_back_val() {
109    T Result = back();
110    pop_back();
111    return Result;
112  }
113
114  void clear() {
115    if (llvm::is_class<T>::value) {
116      destroy_range(Begin, End);
117    }
118    End = Begin;
119  }
120
121  /// data - Return a pointer to the vector's buffer, even if empty().
122  pointer data() {
123    return pointer(Begin);
124  }
125
126  /// data - Return a pointer to the vector's buffer, even if empty().
127  const_pointer data() const {
128    return const_pointer(Begin);
129  }
130
131  void push_back(const_reference Elt, BumpVectorContext &C) {
132    if (End < Capacity) {
133    Retry:
134      new (End) T(Elt);
135      ++End;
136      return;
137    }
138    grow(C);
139    goto Retry;
140  }
141
142  void reserve(BumpVectorContext &C, unsigned N) {
143    if (unsigned(Capacity-Begin) < N)
144      grow(C, N);
145  }
146
147  /// capacity - Return the total number of elements in the currently allocated
148  /// buffer.
149  size_t capacity() const { return Capacity - Begin; }
150
151private:
152  /// grow - double the size of the allocated memory, guaranteeing space for at
153  /// least one more element or MinSize if specified.
154  void grow(BumpVectorContext &C, size_type MinSize = 0);
155
156  void construct_range(T *S, T *E, const T &Elt) {
157    for (; S != E; ++S)
158      new (S) T(Elt);
159  }
160
161  void destroy_range(T *S, T *E) {
162    while (S != E) {
163      --E;
164      E->~T();
165    }
166  }
167};
168
169// Define this out-of-line to dissuade the C++ compiler from inlining it.
170template <typename T>
171void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
172  size_t CurCapacity = Capacity-Begin;
173  size_t CurSize = size();
174  size_t NewCapacity = 2*CurCapacity;
175  if (NewCapacity < MinSize)
176    NewCapacity = MinSize;
177
178  // Allocate the memory from the BumpPtrAllocator.
179  T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
180
181  // Copy the elements over.
182  if (llvm::is_class<T>::value) {
183    std::uninitialized_copy(Begin, End, NewElts);
184    // Destroy the original elements.
185    destroy_range(Begin, End);
186  }
187  else {
188    // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
189    memcpy(NewElts, Begin, CurSize * sizeof(T));
190  }
191
192  // For now, leak 'Begin'.  We can add it back to a freelist in
193  // BumpVectorContext.
194  Begin = NewElts;
195  End = NewElts+CurSize;
196  Capacity = Begin+NewCapacity;
197}
198
199} // end: clang namespace
200#endif // end: LLVM_CLANG_BUMP_VECTOR
201