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