Line data Source code
1 : //===- BinaryStreamArray.h - Array backed by an arbitrary stream *- 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 : #ifndef LLVM_SUPPORT_BINARYSTREAMARRAY_H
11 : #define LLVM_SUPPORT_BINARYSTREAMARRAY_H
12 :
13 : #include "llvm/ADT/ArrayRef.h"
14 : #include "llvm/ADT/iterator.h"
15 : #include "llvm/Support/BinaryStreamRef.h"
16 : #include "llvm/Support/Error.h"
17 : #include <cassert>
18 : #include <cstdint>
19 :
20 : /// Lightweight arrays that are backed by an arbitrary BinaryStream. This file
21 : /// provides two different array implementations.
22 : ///
23 : /// VarStreamArray - Arrays of variable length records. The user specifies
24 : /// an Extractor type that can extract a record from a given offset and
25 : /// return the number of bytes consumed by the record.
26 : ///
27 : /// FixedStreamArray - Arrays of fixed length records. This is similar in
28 : /// spirit to ArrayRef<T>, but since it is backed by a BinaryStream, the
29 : /// elements of the array need not be laid out in contiguous memory.
30 : namespace llvm {
31 :
32 : /// VarStreamArrayExtractor is intended to be specialized to provide customized
33 : /// extraction logic. On input it receives a BinaryStreamRef pointing to the
34 : /// beginning of the next record, but where the length of the record is not yet
35 : /// known. Upon completion, it should return an appropriate Error instance if
36 : /// a record could not be extracted, or if one could be extracted it should
37 : /// return success and set Len to the number of bytes this record occupied in
38 : /// the underlying stream, and it should fill out the fields of the value type
39 : /// Item appropriately to represent the current record.
40 : ///
41 : /// You can specialize this template for your own custom value types to avoid
42 : /// having to specify a second template argument to VarStreamArray (documented
43 : /// below).
44 : template <typename T> struct VarStreamArrayExtractor {
45 : // Method intentionally deleted. You must provide an explicit specialization
46 : // with the following method implemented.
47 : Error operator()(BinaryStreamRef Stream, uint32_t &Len,
48 : T &Item) const = delete;
49 : };
50 :
51 : /// VarStreamArray represents an array of variable length records backed by a
52 : /// stream. This could be a contiguous sequence of bytes in memory, it could
53 : /// be a file on disk, or it could be a PDB stream where bytes are stored as
54 : /// discontiguous blocks in a file. Usually it is desirable to treat arrays
55 : /// as contiguous blocks of memory, but doing so with large PDB files, for
56 : /// example, could mean allocating huge amounts of memory just to allow
57 : /// re-ordering of stream data to be contiguous before iterating over it. By
58 : /// abstracting this out, we need not duplicate this memory, and we can
59 : /// iterate over arrays in arbitrarily formatted streams. Elements are parsed
60 : /// lazily on iteration, so there is no upfront cost associated with building
61 : /// or copying a VarStreamArray, no matter how large it may be.
62 : ///
63 : /// You create a VarStreamArray by specifying a ValueType and an Extractor type.
64 : /// If you do not specify an Extractor type, you are expected to specialize
65 : /// VarStreamArrayExtractor<T> for your ValueType.
66 : ///
67 : /// By default an Extractor is default constructed in the class, but in some
68 : /// cases you might find it useful for an Extractor to maintain state across
69 : /// extractions. In this case you can provide your own Extractor through a
70 : /// secondary constructor. The following examples show various ways of
71 : /// creating a VarStreamArray.
72 : ///
73 : /// // Will use VarStreamArrayExtractor<MyType> as the extractor.
74 : /// VarStreamArray<MyType> MyTypeArray;
75 : ///
76 : /// // Will use a default-constructed MyExtractor as the extractor.
77 : /// VarStreamArray<MyType, MyExtractor> MyTypeArray2;
78 : ///
79 : /// // Will use the specific instance of MyExtractor provided.
80 : /// // MyExtractor need not be default-constructible in this case.
81 : /// MyExtractor E(SomeContext);
82 : /// VarStreamArray<MyType, MyExtractor> MyTypeArray3(E);
83 : ///
84 :
85 : template <typename ValueType, typename Extractor> class VarStreamArrayIterator;
86 :
87 : template <typename ValueType,
88 : typename Extractor = VarStreamArrayExtractor<ValueType>>
89 4328 : class VarStreamArray {
90 : friend class VarStreamArrayIterator<ValueType, Extractor>;
91 :
92 : public:
93 : typedef VarStreamArrayIterator<ValueType, Extractor> Iterator;
94 :
95 : VarStreamArray() = default;
96 :
97 : explicit VarStreamArray(const Extractor &E) : E(E) {}
98 :
99 13 : explicit VarStreamArray(BinaryStreamRef Stream) : Stream(Stream) {}
100 :
101 : VarStreamArray(BinaryStreamRef Stream, const Extractor &E)
102 : : Stream(Stream), E(E) {}
103 :
104 : Iterator begin(bool *HadError = nullptr) const {
105 1502 : return Iterator(*this, E, HadError);
106 : }
107 :
108 1145 : bool valid() const { return Stream.valid(); }
109 :
110 0 : Iterator end() const { return Iterator(E); }
111 :
112 : bool empty() const { return Stream.getLength() == 0; }
113 :
114 : /// given an offset into the array's underlying stream, return an
115 : /// iterator to the record at that offset. This is considered unsafe
116 : /// since the behavior is undefined if \p Offset does not refer to the
117 : /// beginning of a valid record.
118 : Iterator at(uint32_t Offset) const {
119 1277 : return Iterator(*this, E, Offset, nullptr);
120 : }
121 :
122 : const Extractor &getExtractor() const { return E; }
123 : Extractor &getExtractor() { return E; }
124 :
125 : BinaryStreamRef getUnderlyingStream() const { return Stream; }
126 : void setUnderlyingStream(BinaryStreamRef S) { Stream = S; }
127 :
128 : private:
129 : BinaryStreamRef Stream;
130 : Extractor E;
131 : };
132 :
133 : template <typename ValueType, typename Extractor>
134 : class VarStreamArrayIterator
135 : : public iterator_facade_base<VarStreamArrayIterator<ValueType, Extractor>,
136 : std::forward_iterator_tag, ValueType> {
137 : typedef VarStreamArrayIterator<ValueType, Extractor> IterType;
138 : typedef VarStreamArray<ValueType, Extractor> ArrayType;
139 :
140 : public:
141 : VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
142 : bool *HadError)
143 1907 : : VarStreamArrayIterator(Array, E, 0, HadError) {}
144 :
145 3225 : VarStreamArrayIterator(const ArrayType &Array, const Extractor &E,
146 : uint32_t Offset, bool *HadError)
147 : : IterRef(Array.Stream.drop_front(Offset)), Extract(E),
148 5396 : Array(&Array), AbsOffset(Offset), HadError(HadError) {
149 3209 : if (IterRef.getLength() == 0)
150 : moveToEnd();
151 : else {
152 9282 : auto EC = Extract(IterRef, ThisLen, ThisValue);
153 3094 : if (EC) {
154 0 : consumeError(std::move(EC));
155 : markError();
156 : }
157 : }
158 3225 : }
159 584 :
160 : VarStreamArrayIterator() = default;
161 751 : explicit VarStreamArrayIterator(const Extractor &E) : Extract(E) {}
162 2788 : ~VarStreamArrayIterator() = default;
163 584 :
164 8914 : bool operator==(const IterType &R) const {
165 8914 : if (Array && R.Array) {
166 1440 : // Both have a valid array, make sure they're same.
167 480 : assert(Array == R.Array);
168 0 : return IterRef == R.IterRef;
169 : }
170 :
171 : // Both iterators are at the end.
172 9498 : if (!Array && !R.Array)
173 1070 : return true;
174 :
175 : // One is not at the end and one is.
176 582 : return false;
177 291 : }
178 609 :
179 609 : const ValueType &operator*() const {
180 867 : assert(Array && !HasError);
181 289 : return ThisValue;
182 0 : }
183 :
184 : ValueType &operator*() {
185 : assert(Array && !HasError);
186 900 : return ThisValue;
187 349 : }
188 :
189 12497 : IterType &operator+=(unsigned N) {
190 24993 : for (unsigned I = 0; I < N; ++I) {
191 339 : // We are done with the current record, discard it so that we are
192 2183 : // positioned at the next record.
193 14193 : AbsOffset += ThisLen;
194 25037 : IterRef = IterRef.drop_front(ThisLen);
195 12349 : if (IterRef.getLength() == 0) {
196 0 : // There is nothing after the current record, we must make this an end
197 : // iterator.
198 : moveToEnd();
199 : } else {
200 2522 : // There is some data after the current record.
201 33769 : auto EC = Extract(IterRef, ThisLen, ThisValue);
202 11117 : if (EC) {
203 501 : consumeError(std::move(EC));
204 769 : markError();
205 11177 : } else if (ThisLen == 0) {
206 1416 : // An empty record? Make this an end iterator.
207 1416 : moveToEnd();
208 180 : }
209 60 : }
210 0 : }
211 12010 : return *this;
212 : }
213 :
214 1480 : uint32_t offset() const { return AbsOffset; }
215 450 : uint32_t getRecordLength() const { return ThisLen; }
216 :
217 237 : private:
218 298 : void moveToEnd() {
219 915 : Array = nullptr;
220 3145 : ThisLen = 0;
221 2246 : }
222 33 : void markError() {
223 16 : moveToEnd();
224 0 : HasError = true;
225 0 : if (HadError != nullptr)
226 0 : *HadError = true;
227 : }
228 2232 :
229 399 : ValueType ThisValue;
230 12 : BinaryStreamRef IterRef;
231 734 : Extractor Extract;
232 1527 : const ArrayType *Array{nullptr};
233 37 : uint32_t ThisLen{0};
234 640 : uint32_t AbsOffset{0};
235 1369 : bool HasError{false};
236 1533 : bool *HadError{nullptr};
237 754 : };
238 0 :
239 15 : template <typename T> class FixedStreamArrayIterator;
240 :
241 : /// FixedStreamArray is similar to VarStreamArray, except with each record
242 665 : /// having a fixed-length. As with VarStreamArray, there is no upfront
243 2316 : /// cost associated with building or copying a FixedStreamArray, as the
244 694 : /// memory for each element is not read from the backing stream until that
245 1658 : /// element is iterated.
246 8758 : template <typename T> class FixedStreamArray {
247 697 : friend class FixedStreamArrayIterator<T>;
248 1269 :
249 2857 : public:
250 3182 : typedef FixedStreamArrayIterator<T> Iterator;
251 1591 :
252 0 : FixedStreamArray() = default;
253 2889 : explicit FixedStreamArray(BinaryStreamRef Stream) : Stream(Stream) {
254 0 : assert(Stream.getLength() % sizeof(T) == 0);
255 599 : }
256 2464 :
257 4296 : bool operator==(const FixedStreamArray<T> &Other) const {
258 1354 : return Stream == Other.Stream;
259 599 : }
260 1198 :
261 1953 : bool operator!=(const FixedStreamArray<T> &Other) const {
262 166 : return !(*this == Other);
263 166 : }
264 :
265 : FixedStreamArray &operator=(const FixedStreamArray &) = default;
266 :
267 89740 : const T &operator[](uint32_t Index) const {
268 590 : assert(Index < size());
269 86671 : uint32_t Off = Index * sizeof(T);
270 87129 : ArrayRef<uint8_t> Data;
271 173414 : if (auto EC = Stream.readBytes(Off, sizeof(T), Data)) {
272 : assert(false && "Unexpected failure reading from stream");
273 618 : // This should never happen since we asserted that the stream length was
274 1236 : // an exact multiple of the element size.
275 292 : consumeError(std::move(EC));
276 311 : }
277 1236 : assert(llvm::alignmentAdjustment(Data.data(), alignof(T)) == 0);
278 87031 : return *reinterpret_cast<const T *>(Data.data());
279 432 : }
280 576 :
281 1336 : uint32_t size() const { return Stream.getLength() / sizeof(T); }
282 588 :
283 470 : bool empty() const { return size() == 0; }
284 1251 :
285 506 : FixedStreamArrayIterator<T> begin() const {
286 50 : return FixedStreamArrayIterator<T>(*this, 0);
287 0 : }
288 0 :
289 601 : FixedStreamArrayIterator<T> end() const {
290 650 : return FixedStreamArrayIterator<T>(*this, size());
291 1025 : }
292 90 :
293 75283 : const T &front() const { return *begin(); }
294 2598 : const T &back() const {
295 74400 : FixedStreamArrayIterator<T> I = end();
296 73984 : return *(--I);
297 149292 : }
298 2747 :
299 1322 : BinaryStreamRef getUnderlyingStream() const { return Stream; }
300 :
301 624 : private:
302 1036 : BinaryStreamRef Stream;
303 49 : };
304 74188 :
305 4039 : template <typename T>
306 9132 : class FixedStreamArrayIterator
307 660 : : public iterator_facade_base<FixedStreamArrayIterator<T>,
308 939 : std::random_access_iterator_tag, const T> {
309 2078 :
310 1793 : public:
311 0 : FixedStreamArrayIterator(const FixedStreamArray<T> &Array, uint32_t Index)
312 649 : : Array(Array), Index(Index) {}
313 1072 :
314 344 : FixedStreamArrayIterator<T> &
315 1480 : operator=(const FixedStreamArrayIterator<T> &Other) {
316 153 : Array = Other.Array;
317 1235 : Index = Other.Index;
318 28 : return *this;
319 67 : }
320 888 :
321 152 : const T &operator*() const { return Array[Index]; }
322 903 : const T &operator*() { return Array[Index]; }
323 824 :
324 1369 : bool operator==(const FixedStreamArrayIterator<T> &R) const {
325 148 : assert(Array == R.Array);
326 1314 : return (Index == R.Index) && (Array == R.Array);
327 124 : }
328 21 :
329 243 : FixedStreamArrayIterator<T> &operator+=(std::ptrdiff_t N) {
330 1016 : Index += N;
331 20 : return *this;
332 169 : }
333 341 :
334 479 : FixedStreamArrayIterator<T> &operator-=(std::ptrdiff_t N) {
335 217 : assert(std::ptrdiff_t(Index) >= N);
336 85 : Index -= N;
337 64 : return *this;
338 141 : }
339 0 :
340 41 : std::ptrdiff_t operator-(const FixedStreamArrayIterator<T> &R) const {
341 503 : assert(Array == R.Array);
342 160 : assert(Index >= R.Index);
343 601 : return Index - R.Index;
344 0 : }
345 351 :
346 382 : bool operator<(const FixedStreamArrayIterator<T> &RHS) const {
347 14 : assert(Array == RHS.Array);
348 470 : return Index < RHS.Index;
349 196 : }
350 3194 :
351 402 : private:
352 2802 : FixedStreamArray<T> Array;
353 5 : uint32_t Index;
354 238 : };
355 5 :
356 470 : } // namespace llvm
357 333 :
358 560 : #endif // LLVM_SUPPORT_BINARYSTREAMARRAY_H
|
