1 //===- LazyRandomTypeCollection.h ---------------------------- *- 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_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H 11 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H 12 13 #include "llvm/DebugInfo/CodeView/TypeCollection.h" 14 #include "llvm/DebugInfo/CodeView/TypeDatabase.h" 15 #include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h" 16 #include "llvm/DebugInfo/CodeView/TypeIndex.h" 17 #include "llvm/DebugInfo/CodeView/TypeRecord.h" 18 #include "llvm/Support/Error.h" 19 20 namespace llvm { 21 namespace codeview { 22 23 class TypeDatabase; 24 class TypeVisitorCallbacks; 25 26 /// \brief Provides amortized O(1) random access to a CodeView type stream. 27 /// Normally to access a type from a type stream, you must know its byte 28 /// offset into the type stream, because type records are variable-lengthed. 29 /// However, this is not the way we prefer to access them. For example, given 30 /// a symbol record one of the fields may be the TypeIndex of the symbol's 31 /// type record. Or given a type record such as an array type, there might 32 /// be a TypeIndex for the element type. Sequential access is perfect when 33 /// we're just dumping every entry, but it's very poor for real world usage. 34 /// 35 /// Type streams in PDBs contain an additional field which is a list of pairs 36 /// containing indices and their corresponding offsets, roughly every ~8KB of 37 /// record data. This general idea need not be confined to PDBs though. By 38 /// supplying such an array, the producer of a type stream can allow the 39 /// consumer much better access time, because the consumer can find the nearest 40 /// index in this array, and do a linear scan forward only from there. 41 /// 42 /// LazyRandomTypeCollection implements this algorithm, but additionally goes 43 /// one step further by caching offsets of every record that has been visited at 44 /// least once. This way, even repeated visits of the same record will never 45 /// require more than one linear scan. For a type stream of N elements divided 46 /// into M chunks of roughly equal size, this yields a worst case lookup time 47 /// of O(N/M) and an amortized time of O(1). 48 class LazyRandomTypeCollection : public TypeCollection { 49 typedef FixedStreamArray<TypeIndexOffset> PartialOffsetArray; 50 51 public: 52 explicit LazyRandomTypeCollection(uint32_t RecordCountHint); 53 LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint); 54 LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint); 55 LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint, 56 PartialOffsetArray PartialOffsets); 57 LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint); 58 59 void reset(ArrayRef<uint8_t> Data); 60 void reset(StringRef Data); 61 62 CVType getType(TypeIndex Index) override; 63 StringRef getTypeName(TypeIndex Index) override; 64 bool contains(TypeIndex Index) override; 65 uint32_t size() override; 66 uint32_t capacity() override; 67 Optional<TypeIndex> getFirst() override; 68 Optional<TypeIndex> getNext(TypeIndex Prev) override; 69 70 private: 71 const TypeDatabase &database() const { return Database; } 72 Error ensureTypeExists(TypeIndex Index); 73 74 Error visitRangeForType(TypeIndex TI); 75 Error fullScanForType(TypeIndex TI); 76 Error visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End); 77 Error visitOneRecord(TypeIndex TI, uint32_t Offset, CVType &Record); 78 79 BumpPtrAllocator Allocator; 80 StringSaver NameStorage; 81 82 SmallVector<StringRef, 10> TypeNames; 83 84 /// Visited records get automatically added to the type database. 85 TypeDatabase Database; 86 87 /// The type array to allow random access visitation of. 88 CVTypeArray Types; 89 90 /// The database visitor which adds new records to the database. 91 TypeDatabaseVisitor DatabaseVisitor; 92 93 /// A vector mapping type indices to type offset. For every record that has 94 /// been visited, contains the absolute offset of that record in the record 95 /// array. 96 std::vector<uint32_t> KnownOffsets; 97 98 /// An array of index offsets for the given type stream, allowing log(N) 99 /// lookups of a type record by index. Similar to KnownOffsets but only 100 /// contains offsets for some type indices, some of which may not have 101 /// ever been visited. 102 PartialOffsetArray PartialOffsets; 103 }; 104 105 } // end namespace codeview 106 } // end namespace llvm 107 108 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H 109
