LLVM  8.0.1
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]
Collaboration diagram for llvm::codeview::LazyRandomTypeCollection:
Collaboration 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)
 
Optional< CVType > tryGetType (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
 
Optional< TypeIndex > getFirst () override
 
Optional< TypeIndex > getNext (TypeIndex Prev) override
 
- Public Member Functions inherited from llvm::codeview::TypeCollection
virtual ~TypeCollection ()=default
 
bool empty ()
 
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 51 of file LazyRandomTypeCollection.h.

Constructor & Destructor Documentation

◆ LazyRandomTypeCollection() [1/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( uint32_t  RecordCountHint)
explicit

Definition at line 35 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [2/5]

LazyRandomTypeCollection::LazyRandomTypeCollection ( StringRef  Data,
uint32_t  RecordCountHint 
)

Definition at line 51 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [3/5]

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

Definition at line 46 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [4/5]

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

Definition at line 39 of file LazyRandomTypeCollection.cpp.

◆ LazyRandomTypeCollection() [5/5]

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

Definition at line 57 of file LazyRandomTypeCollection.cpp.

Member Function Documentation

◆ capacity()

uint32_t LazyRandomTypeCollection::capacity ( )
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 149 of file LazyRandomTypeCollection.cpp.

References assert(), llvm::FixedStreamArray< T >::begin(), contains(), llvm::FixedStreamArray< T >::empty(), llvm::FixedStreamArray< T >::end(), llvm::codeview::TypeIndex::fromArrayIndex(), llvm::codeview::TypeIndex::isSimple(), llvm::Error::success(), llvm::codeview::TypeIndex::toArrayIndex(), and llvm::upper_bound().

◆ contains()

bool LazyRandomTypeCollection::contains ( TypeIndex  Index)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 136 of file LazyRandomTypeCollection.cpp.

References llvm::codeview::TypeIndex::isNoneType(), llvm::codeview::TypeIndex::isSimple(), and llvm::codeview::TypeIndex::toArrayIndex().

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

◆ getFirst()

Optional< TypeIndex > LazyRandomTypeCollection::getFirst ( )
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 205 of file LazyRandomTypeCollection.cpp.

References llvm::consumeError(), llvm::codeview::EC, llvm::codeview::TypeIndex::fromArrayIndex(), and llvm::codeview::None.

Referenced by llvm::pdb::NativeEnumTypes::NativeEnumTypes().

◆ getNext()

Optional< TypeIndex > LazyRandomTypeCollection::getNext ( TypeIndex  Prev)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 214 of file LazyRandomTypeCollection.cpp.

References assert(), llvm::VarStreamArray< ValueType, Extractor >::at(), llvm::VarStreamArray< ValueType, Extractor >::begin(), llvm::consumeError(), llvm::codeview::EC, llvm::FixedStreamArray< T >::empty(), llvm::codeview::TypeIndex::fromArrayIndex(), llvm::codeview::TypeIndex::isSimple(), llvm::codeview::None, and llvm::codeview::TypeIndex::toArrayIndex().

Referenced by llvm::pdb::NativeEnumTypes::NativeEnumTypes().

◆ getOffsetOfType()

uint32_t LazyRandomTypeCollection::getOffsetOfType ( TypeIndex  Index)

Definition at line 84 of file LazyRandomTypeCollection.cpp.

References assert(), contains(), error(), and llvm::codeview::TypeIndex::toArrayIndex().

◆ getType()

CVType LazyRandomTypeCollection::getType ( TypeIndex  Index)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 91 of file LazyRandomTypeCollection.cpp.

References assert(), contains(), llvm::codeview::EC, error(), llvm::codeview::TypeIndex::isSimple(), and llvm::codeview::TypeIndex::toArrayIndex().

Referenced by llvm::pdb::SymbolCache::findSymbolByTypeIndex(), llvm::pdb::NativeEnumTypes::NativeEnumTypes(), and llvm::pdb::NativeTypeFunctionSig::~NativeTypeFunctionSig().

◆ getTypeName()

StringRef LazyRandomTypeCollection::getTypeName ( TypeIndex  Index)
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 114 of file LazyRandomTypeCollection.cpp.

References llvm::codeview::computeTypeName(), llvm::consumeError(), llvm::codeview::EC, I, llvm::codeview::TypeIndex::isNoneType(), llvm::codeview::TypeIndex::isSimple(), Name, llvm::StringSaver::save(), llvm::codeview::TypeIndex::simpleTypeName(), and llvm::codeview::TypeIndex::toArrayIndex().

◆ reset() [1/3]

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

Definition at line 78 of file LazyRandomTypeCollection.cpp.

References llvm::support::little.

Referenced by reset().

◆ reset() [2/3]

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

Definition at line 73 of file LazyRandomTypeCollection.cpp.

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

◆ reset() [3/3]

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

Definition at line 61 of file LazyRandomTypeCollection.cpp.

References llvm::BinaryStreamReader::bytesRemaining(), error(), and llvm::BinaryStreamReader::readArray().

◆ size()

uint32_t LazyRandomTypeCollection::size ( )
overridevirtual

Implements llvm::codeview::TypeCollection.

Definition at line 147 of file LazyRandomTypeCollection.cpp.

◆ tryGetType()

Optional< CVType > LazyRandomTypeCollection::tryGetType ( TypeIndex  Index)

Definition at line 101 of file LazyRandomTypeCollection.cpp.

References assert(), llvm::consumeError(), contains(), llvm::codeview::EC, llvm::codeview::TypeIndex::isSimple(), llvm::codeview::None, and llvm::codeview::TypeIndex::toArrayIndex().

The documentation for this class was generated from the following files:
Generated on Sun Dec 20 2020 14:14:45 for LLVM by   doxygen 1.8.13