Provides lookup and iteration over an on disk hash table. More...

#include "llvm/Support/OnDiskHashTable.h"

Inheritance diagram for llvm::OnDiskIterableChainedHashTable< Info >:

Classes
class	data_iterator
	Iterates over all the entries in the table, returning the data. More...

class	key_iterator
	Iterates over all of the keys in the table. More...

Public Types
typedef OnDiskChainedHashTable< Info >	base_type

typedef base_type::internal_key_type	internal_key_type

typedef base_type::external_key_type	external_key_type

typedef base_type::data_type	data_type

typedef base_type::hash_value_type	hash_value_type

typedef base_type::offset_type	offset_type

Public Types inherited from llvm::OnDiskChainedHashTable< Info >
typedef Info	InfoType

typedef Info::internal_key_type	internal_key_type

typedef Info::external_key_type	external_key_type

typedef Info::data_type	data_type

typedef Info::hash_value_type	hash_value_type

typedef Info::offset_type	offset_type

Public Member Functions
	OnDiskIterableChainedHashTable (offset_type NumBuckets, offset_type NumEntries, const unsigned char Buckets, const unsigned char Payload, const unsigned char *Base, const Info &InfoObj=Info())

key_iterator	key_begin ()

key_iterator	key_end ()

iterator_range< key_iterator >	keys ()

data_iterator	data_begin ()

data_iterator	data_end ()

iterator_range< data_iterator >	data ()

Public Member Functions inherited from llvm::OnDiskChainedHashTable< Info >
	OnDiskChainedHashTable (offset_type NumBuckets, offset_type NumEntries, const unsigned char Buckets, const unsigned char Base, const Info &InfoObj=Info())

offset_type	getNumBuckets () const

offset_type	getNumEntries () const

const unsigned char *	getBase () const

const unsigned char *	getBuckets () const

bool	isEmpty () const

iterator	find (const external_key_type &EKey, Info *InfoPtr=nullptr)
	Look up the stored data for a particular key.

iterator	find_hashed (const internal_key_type &IKey, hash_value_type KeyHash, Info *InfoPtr=nullptr)
	Look up the stored data for a particular key with a known hash.

iterator	end () const

Info &	getInfoObj ()

Static Public Member Functions
static OnDiskIterableChainedHashTable *	Create (const unsigned char Buckets, const unsigned char const Payload, const unsigned char *const Base, const Info &InfoObj=Info())
	Create the hash table.

Static Public Member Functions inherited from llvm::OnDiskChainedHashTable< Info >
static std::pair< offset_type, offset_type >	readNumBucketsAndEntries (const unsigned char *&Buckets)
	Read the number of buckets and the number of entries from a hash table produced by OnDiskHashTableGenerator::Emit, and advance the Buckets pointer past them.

static OnDiskChainedHashTable *	Create (const unsigned char Buckets, const unsigned char const Base, const Info &InfoObj=Info())
	Create the hash table.

Detailed Description

template<typename Info>
class llvm::OnDiskIterableChainedHashTable< Info >

Provides lookup and iteration over an on disk hash table.

This needs an Info that handles reading values from the hash table's payload and computes the hash for a given key. This should provide the following interface:

class ExampleLookupInfo {
public:
  typedef ExampleData data_type;
  typedef ExampleInternalKey internal_key_type; // The stored key type.
  typedef ExampleKey external_key_type; // The type to pass to find().
  typedef uint32_t hash_value_type; // The type the hash function returns.
  typedef uint32_t offset_type; // The type for offsets into the table.
 
  /// Compare two keys for equality.
  static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
  /// Calculate the hash for the given key.
  static hash_value_type ComputeHash(internal_key_type &IKey);
  /// Translate from the semantic type of a key in the hash table to the
  /// type that is actually stored and used for hashing and comparisons.
  /// The internal and external types are often the same, in which case this
  /// can simply return the passed in value.
  static const internal_key_type &GetInternalKey(external_key_type &EKey);
  /// Read the key and data length from Buffer, leaving it pointing at the
  /// following byte.
  static std::pair<offset_type, offset_type>
  ReadKeyDataLength(const unsigned char *&Buffer);
  /// Read the key from Buffer, given the KeyLen as reported from
  /// ReadKeyDataLength.
  const internal_key_type &ReadKey(const unsigned char *Buffer,
                                   offset_type KeyLen);
  /// Read the data for Key from Buffer, given the DataLen as reported from
  /// ReadKeyDataLength.
  data_type ReadData(StringRef Key, const unsigned char *Buffer,
                     offset_type DataLen);
};

Definition at line 434 of file OnDiskHashTable.h.

Member Typedef Documentation

◆ base_type

template<typename Info >

typedef OnDiskChainedHashTable<Info> llvm::OnDiskIterableChainedHashTable< Info >::base_type

Definition at line 438 of file OnDiskHashTable.h.

◆ data_type

template<typename Info >

typedef base_type::data_type llvm::OnDiskIterableChainedHashTable< Info >::data_type

Definition at line 441 of file OnDiskHashTable.h.

◆ external_key_type

template<typename Info >

typedef base_type::external_key_type llvm::OnDiskIterableChainedHashTable< Info >::external_key_type

Definition at line 440 of file OnDiskHashTable.h.

◆ hash_value_type

template<typename Info >

typedef base_type::hash_value_type llvm::OnDiskIterableChainedHashTable< Info >::hash_value_type

Definition at line 442 of file OnDiskHashTable.h.

◆ internal_key_type

template<typename Info >

typedef base_type::internal_key_type llvm::OnDiskIterableChainedHashTable< Info >::internal_key_type

Definition at line 439 of file OnDiskHashTable.h.

◆ offset_type

template<typename Info >

typedef base_type::offset_type llvm::OnDiskIterableChainedHashTable< Info >::offset_type

Definition at line 443 of file OnDiskHashTable.h.

Constructor & Destructor Documentation

◆ OnDiskIterableChainedHashTable()

template<typename Info >

llvm::OnDiskIterableChainedHashTable< Info >::OnDiskIterableChainedHashTable	(	offset_type	NumBuckets,
		offset_type	NumEntries,
		const unsigned char *	Buckets,
		const unsigned char *	Payload,
		const unsigned char *	Base,
		const Info &	InfoObj = `Info()`
	)

inline

Definition at line 495 of file OnDiskHashTable.h.

References llvm::sampleprof::Base.

Member Function Documentation

◆ Create()

template<typename Info >

static OnDiskIterableChainedHashTable * llvm::OnDiskIterableChainedHashTable< Info >::Create	(	const unsigned char *	Buckets,
		const unsigned char *const	Payload,
		const unsigned char *const	Base,
		const Info &	InfoObj = `Info()`
	)

inlinestatic

Create the hash table.

Parameters

Buckets	is the beginning of the hash table itself, which follows the payload of entire structure. This is the value returned by OnDiskHashTableGenerator::Emit.
Payload	is the beginning of the data contained in the table. This is Base plus any padding or header data that was stored, ie, the offset that the stream was at when calling Emit.
Base	is the point from which all offsets into the structure are based. This is offset 0 in the stream that was used when Emitting the table.

Definition at line 606 of file OnDiskHashTable.h.

References assert(), llvm::sampleprof::Base, and llvm::OnDiskChainedHashTable< Info >::readNumBucketsAndEntries().

Referenced by llvm::IndexedInstrProfReader::readHeader().