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:

Methods

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)

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)

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)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:64

Parameters

const llvm::codeview::CVTypeArray& Types
uint32_t RecordCountHint

LazyRandomTypeCollection(uint32_t RecordCountHint)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:59

Parameters

uint32_t RecordCountHint

uint32_t capacity()

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:78

bool contains(llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:76

Parameters

llvm::codeview::TypeIndex Index

void ensureCapacityFor(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:85

Parameters

llvm::codeview::TypeIndex Index

llvm::Error ensureTypeExists(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:84

Parameters

llvm::codeview::TypeIndex Index

llvm::Error fullScanForType(
    llvm::codeview::TypeIndex TI)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:88

Parameters

llvm::codeview::TypeIndex TI

Optional<llvm::codeview::TypeIndex> getFirst()

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:79

Optional<llvm::codeview::TypeIndex> getNext(
    llvm::codeview::TypeIndex Prev)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:80

Parameters

llvm::codeview::TypeIndex Prev

uint32_t getOffsetOfType(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:70

Parameters

llvm::codeview::TypeIndex Index

llvm::codeview::CVType getType(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:74

Parameters

llvm::codeview::TypeIndex Index

llvm::StringRef getTypeName(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:75

Parameters

llvm::codeview::TypeIndex Index

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)

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)

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)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:66

Parameters

ArrayRef<uint8_t> Data
uint32_t RecordCountHint

uint32_t size()

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:77

Optional<llvm::codeview::CVType> tryGetType(
    llvm::codeview::TypeIndex Index)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:72

Parameters

llvm::codeview::TypeIndex Index

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)

Declared at: llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h:87

Parameters

llvm::codeview::TypeIndex TI