LLVM 20.0.0git
Classes | Public Member Functions | List of all members
llvm::codeview::LazyRandomTypeCollection Class Reference

Provides amortized O(1) random access to a CodeView type stream. More...

#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"

Inheritance diagram for llvm::codeview::LazyRandomTypeCollection:
Inheritance graph
[legend]

Public Member Functions

 LazyRandomTypeCollection (uint32_t RecordCountHint)
 
 LazyRandomTypeCollection (StringRef Data, uint32_t RecordCountHint)
 
 LazyRandomTypeCollection (ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
 
 LazyRandomTypeCollection (const CVTypeArray &Types, uint32_t RecordCountHint, PartialOffsetArray PartialOffsets)
 
 LazyRandomTypeCollection (const CVTypeArray &Types, uint32_t RecordCountHint)
 
void reset (ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
 
void reset (StringRef Data, uint32_t RecordCountHint)
 
void reset (BinaryStreamReader &Reader, uint32_t RecordCountHint)
 
uint32_t getOffsetOfType (TypeIndex Index)
 
std::optional< CVTypetryGetType (TypeIndex Index)
 
CVType getType (TypeIndex Index) override
 
StringRef getTypeName (TypeIndex Index) override
 
bool contains (TypeIndex Index) override
 
uint32_t size () override
 
uint32_t capacity () override
 
std::optional< TypeIndexgetFirst () override
 
std::optional< TypeIndexgetNext (TypeIndex Prev) override
 
bool replaceType (TypeIndex &Index, CVType Data, bool Stabilize) override
 
- Public Member Functions inherited from llvm::codeview::TypeCollection
virtual ~TypeCollection ()=default
 
bool empty ()
 
virtual std::optional< TypeIndexgetFirst ()=0
 
virtual std::optional< TypeIndexgetNext (TypeIndex Prev)=0
 
virtual CVType getType (TypeIndex Index)=0
 
virtual StringRef getTypeName (TypeIndex Index)=0
 
virtual bool contains (TypeIndex Index)=0
 
virtual uint32_t size ()=0
 
virtual uint32_t capacity ()=0
 
virtual bool replaceType (TypeIndex &Index, CVType Data, bool Stabilize)=0
 
template<typename TFunc >
void ForEachRecord (TFunc Func)
 

Detailed 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).

Definition at line 48 of file LazyRandomTypeCollection.h.

Constructor & Destructor Documentation

◆ LazyRandomTypeCollection() [1/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( uint32_t  RecordCountHint)
explicit

Definition at line 33 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [2/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( StringRef  Data,
uint32_t  RecordCountHint 
)

Definition at line 49 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [3/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( ArrayRef< uint8_t >  Data,
uint32_t  RecordCountHint 
)

Definition at line 44 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [4/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( const CVTypeArray Types,
uint32_t  RecordCountHint,
PartialOffsetArray  PartialOffsets 
)

Definition at line 37 of file LazyRandomTypeCollection.cpp.

References Allocator.

◆ LazyRandomTypeCollection() [5/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( const CVTypeArray Types,
uint32_t  RecordCountHint 
)

Definition at line 54 of file LazyRandomTypeCollection.cpp.

Member Function Documentation

◆ capacity()

uint32_t LazyRandomTypeCollection::capacity ( )
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 146 of file LazyRandomTypeCollection.cpp.

◆ contains()

bool LazyRandomTypeCollection::contains ( TypeIndex  Index)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 133 of file LazyRandomTypeCollection.cpp.

Referenced by getOffsetOfType(), getType(), and tryGetType().

◆ getFirst()

std::optional< TypeIndex > LazyRandomTypeCollection::getFirst ( )
overridevirtual

◆ getNext()

std::optional< TypeIndex > LazyRandomTypeCollection::getNext ( TypeIndex  Prev)
overridevirtual

◆ getOffsetOfType()

uint32_t LazyRandomTypeCollection::getOffsetOfType ( TypeIndex  Index)

Definition at line 81 of file LazyRandomTypeCollection.cpp.

References assert(), contains(), and error.

◆ getType()

CVType LazyRandomTypeCollection::getType ( TypeIndex  Index)
overridevirtual

◆ getTypeName()

StringRef LazyRandomTypeCollection::getTypeName ( TypeIndex  Index)
overridevirtual

◆ replaceType()

bool LazyRandomTypeCollection::replaceType ( TypeIndex Index,
CVType  Data,
bool  Stabilize 
)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 279 of file LazyRandomTypeCollection.cpp.

References llvm_unreachable.

◆ reset() [1/3]

void LazyRandomTypeCollection::reset ( ArrayRef< uint8_t >  Data,
uint32_t  RecordCountHint 
)

Definition at line 75 of file LazyRandomTypeCollection.cpp.

References llvm::Data, llvm::little, and reset().

Referenced by reset().

◆ reset() [2/3]

void LazyRandomTypeCollection::reset ( BinaryStreamReader Reader,
uint32_t  RecordCountHint 
)

◆ reset() [3/3]

void LazyRandomTypeCollection::reset ( StringRef  Data,
uint32_t  RecordCountHint 
)

Definition at line 70 of file LazyRandomTypeCollection.cpp.

References llvm::Data, llvm::little, and reset().

◆ size()

uint32_t LazyRandomTypeCollection::size ( )
overridevirtual

◆ tryGetType()

std::optional< CVType > LazyRandomTypeCollection::tryGetType ( TypeIndex  Index)

The documentation for this class was generated from the following files: