class LazyRandomTypeCollection
Declaration
class LazyRandomTypeCollection : public TypeCollection { /* full declaration omitted */ };
Description
Provides amortized O(1) random access to a CodeView type stream. Normally to access a type from a type stream, you must know its byte offset into the type stream, because type records are variable-lengthed. However, this is not the way we prefer to access them. For example, given a symbol record one of the fields may be the TypeIndex of the symbol's type record. Or given a type record such as an array type, there might be a TypeIndex for the element type. Sequential access is perfect when we're just dumping every entry, but it's very poor for real world usage. Type streams in PDBs contain an additional field which is a list of pairs containing indices and their corresponding offsets, roughly every ~8KB of record data. This general idea need not be confined to PDBs though. By supplying such an array, the producer of a type stream can allow the consumer much better access time, because the consumer can find the nearest index in this array, and do a linear scan forward only from there. LazyRandomTypeCollection implements this algorithm, but additionally goes one step further by caching offsets of every record that has been visited at least once. This way, even repeated visits of the same record will never require more than one linear scan. For a type stream of N elements divided into M chunks of roughly equal size, this yields a worst case lookup time of O(N/M) and an amortized time of O(1).
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:49
Inherits from: TypeCollection
Member Variables
- private uint32_t Count = 0
- Number of actual records.
- private llvm::codeview::TypeIndex LargestTypeIndex = TypeIndex::None()
- The largest type index which we've visited.
- private llvm::BumpPtrAllocator Allocator
- private llvm::StringSaver NameStorage
- private llvm::codeview::CVTypeArray Types
- The type array to allow random access visitation of.
- private std::vector<CacheEntry> Records
- private llvm::codeview::LazyRandomTypeCollection:: PartialOffsetArray PartialOffsets
- An array of index offsets for the given type stream, allowing log(N) lookups of a type record by index. Similar to KnownOffsets but only contains offsets for some type indices, some of which may not have ever been visited.
Method Overview
- public LazyRandomTypeCollection(llvm::StringRef Data, uint32_t RecordCountHint)
- public LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint)
- public LazyRandomTypeCollection(const llvm::codeview::CVTypeArray & Types, uint32_t RecordCountHint, llvm::codeview::LazyRandomTypeCollection::PartialOffsetArray PartialOffsets)
- public LazyRandomTypeCollection(const llvm::codeview::CVTypeArray & Types, uint32_t RecordCountHint)
- public LazyRandomTypeCollection(uint32_t RecordCountHint)
- public uint32_t capacity()
- public bool contains(llvm::codeview::TypeIndex Index)
- private void ensureCapacityFor(llvm::codeview::TypeIndex Index)
- private llvm::Error ensureTypeExists(llvm::codeview::TypeIndex Index)
- private llvm::Error fullScanForType(llvm::codeview::TypeIndex TI)
- public Optional<llvm::codeview::TypeIndex> getFirst()
- public Optional<llvm::codeview::TypeIndex> getNext(llvm::codeview::TypeIndex Prev)
- public uint32_t getOffsetOfType(llvm::codeview::TypeIndex Index)
- public llvm::codeview::CVType getType(llvm::codeview::TypeIndex Index)
- public llvm::StringRef getTypeName(llvm::codeview::TypeIndex Index)
- public bool replaceType(llvm::codeview::TypeIndex & Index, llvm::codeview::CVType Data, bool Stabilize)
- public void reset(llvm::BinaryStreamReader & Reader, uint32_t RecordCountHint)
- public void reset(llvm::StringRef Data, uint32_t RecordCountHint)
- public void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint)
- public uint32_t size()
- public Optional<llvm::codeview::CVType> tryGetType(llvm::codeview::TypeIndex Index)
- private void visitRange(llvm::codeview::TypeIndex Begin, uint32_t BeginOffset, llvm::codeview::TypeIndex End)
- private llvm::Error visitRangeForType(llvm::codeview::TypeIndex TI)
Inherited from TypeCollection:
- public ForEachRecord
- public capacity
- public contains
- public empty
- public getFirst
- public getNext
- public getType
- public getTypeName
- public replaceType
- public size
Methods
¶LazyRandomTypeCollection(llvm::StringRef Data,
uint32_t RecordCountHint)
LazyRandomTypeCollection(llvm::StringRef Data,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:60
Parameters
- llvm::StringRef Data
- uint32_t RecordCountHint
¶LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
uint32_t RecordCountHint)
LazyRandomTypeCollection(ArrayRef<uint8_t> Data,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:61
Parameters
- ArrayRef<uint8_t> Data
- uint32_t RecordCountHint
¶LazyRandomTypeCollection(
const llvm::codeview::CVTypeArray& Types,
uint32_t RecordCountHint,
llvm::codeview::LazyRandomTypeCollection::
PartialOffsetArray PartialOffsets)
LazyRandomTypeCollection(
const llvm::codeview::CVTypeArray& Types,
uint32_t RecordCountHint,
llvm::codeview::LazyRandomTypeCollection::
PartialOffsetArray PartialOffsets)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:62
Parameters
- const llvm::codeview::CVTypeArray& Types
- uint32_t RecordCountHint
- llvm::codeview::LazyRandomTypeCollection:: PartialOffsetArray PartialOffsets
¶LazyRandomTypeCollection(
const llvm::codeview::CVTypeArray& Types,
uint32_t RecordCountHint)
LazyRandomTypeCollection(
const llvm::codeview::CVTypeArray& Types,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:64
Parameters
- const llvm::codeview::CVTypeArray& Types
- uint32_t RecordCountHint
¶LazyRandomTypeCollection(uint32_t RecordCountHint)
LazyRandomTypeCollection(uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:59
Parameters
- uint32_t RecordCountHint
¶uint32_t capacity()
uint32_t capacity()
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:78
¶bool contains(llvm::codeview::TypeIndex Index)
bool contains(llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:76
Parameters
¶void ensureCapacityFor(
llvm::codeview::TypeIndex Index)
void ensureCapacityFor(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:85
Parameters
¶llvm::Error ensureTypeExists(
llvm::codeview::TypeIndex Index)
llvm::Error ensureTypeExists(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:84
Parameters
¶llvm::Error fullScanForType(
llvm::codeview::TypeIndex TI)
llvm::Error fullScanForType(
llvm::codeview::TypeIndex TI)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:88
Parameters
¶Optional<llvm::codeview::TypeIndex> getFirst()
Optional<llvm::codeview::TypeIndex> getFirst()
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:79
¶Optional<llvm::codeview::TypeIndex> getNext(
llvm::codeview::TypeIndex Prev)
Optional<llvm::codeview::TypeIndex> getNext(
llvm::codeview::TypeIndex Prev)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:80
Parameters
¶uint32_t getOffsetOfType(
llvm::codeview::TypeIndex Index)
uint32_t getOffsetOfType(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:70
Parameters
¶llvm::codeview::CVType getType(
llvm::codeview::TypeIndex Index)
llvm::codeview::CVType getType(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:74
Parameters
¶llvm::StringRef getTypeName(
llvm::codeview::TypeIndex Index)
llvm::StringRef getTypeName(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:75
Parameters
¶bool replaceType(llvm::codeview::TypeIndex& Index,
llvm::codeview::CVType Data,
bool Stabilize)
bool replaceType(llvm::codeview::TypeIndex& Index,
llvm::codeview::CVType Data,
bool Stabilize)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:81
Parameters
- llvm::codeview::TypeIndex& Index
- llvm::codeview::CVType Data
- bool Stabilize
¶void reset(llvm::BinaryStreamReader& Reader,
uint32_t RecordCountHint)
void reset(llvm::BinaryStreamReader& Reader,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:68
Parameters
- llvm::BinaryStreamReader& Reader
- uint32_t RecordCountHint
¶void reset(llvm::StringRef Data,
uint32_t RecordCountHint)
void reset(llvm::StringRef Data,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:67
Parameters
- llvm::StringRef Data
- uint32_t RecordCountHint
¶void reset(ArrayRef<uint8_t> Data,
uint32_t RecordCountHint)
void reset(ArrayRef<uint8_t> Data,
uint32_t RecordCountHint)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:66
Parameters
- ArrayRef<uint8_t> Data
- uint32_t RecordCountHint
¶uint32_t size()
uint32_t size()
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:77
¶Optional<llvm::codeview::CVType> tryGetType(
llvm::codeview::TypeIndex Index)
Optional<llvm::codeview::CVType> tryGetType(
llvm::codeview::TypeIndex Index)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:72
Parameters
¶void visitRange(llvm::codeview::TypeIndex Begin,
uint32_t BeginOffset,
llvm::codeview::TypeIndex End)
void visitRange(llvm::codeview::TypeIndex Begin,
uint32_t BeginOffset,
llvm::codeview::TypeIndex End)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:89
Parameters
- llvm::codeview::TypeIndex Begin
- uint32_t BeginOffset
- llvm::codeview::TypeIndex End
¶llvm::Error visitRangeForType(
llvm::codeview::TypeIndex TI)
llvm::Error visitRangeForType(
llvm::codeview::TypeIndex TI)
Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:87