LLVM: llvm::TrieHashIndexGenerator Struct Reference

LLVM 20.0.0git

The utility class that helps computing the index of the object inside trie from its hash. More...

#include "llvm/ADT/TrieHashIndexGenerator.h"

Public Member Functions
size_t	getNumBits () const

size_t	next ()

size_t	hint (unsigned Index, unsigned Bit)

size_t	getCollidingBits (ArrayRef< uint8_t > CollidingBits) const

size_t	end () const

Static Public Member Functions
static size_t	getIndex (ArrayRef< uint8_t > Bytes, size_t StartBit, size_t NumBits)

Public Attributes
size_t	NumRootBits

size_t	NumSubtrieBits

ArrayRef< uint8_t >	Bytes

std::optional< size_t >	StartBit = std::nullopt

Detailed Description

The utility class that helps computing the index of the object inside trie from its hash.

The generator can be configured with the number of bits used for each level of trie structure with NumRootsBits and NumSubtrieBits. For example, try computing indexes for a 16-bit hash 0x1234 with 8-bit root and 4-bit sub-trie:

IndexGenerator IndexGen{8, 4, Hash}; size_t index1 = IndexGen.next(); // index 18 in root node. size_t index2 = IndexGen.next(); // index 3 in sub-trie level 1. size_t index3 = IndexGen.next(); // index 4 in sub-tire level 2.

This is used by different trie implementation to figure out where to insert/find the object in the data structure.

Definition at line 31 of file TrieHashIndexGenerator.h.

Member Function Documentation

◆ end()

size_t llvm::TrieHashIndexGenerator::end ( ) const

inline

Definition at line 83 of file TrieHashIndexGenerator.h.

Referenced by next().

◆ getCollidingBits()

size_t llvm::TrieHashIndexGenerator::getCollidingBits ( ArrayRef< uint8_t > CollidingBits ) const

inline

Definition at line 78 of file TrieHashIndexGenerator.h.

References assert(), getIndex(), NumSubtrieBits, and StartBit.

◆ getIndex()

static size_t llvm::TrieHashIndexGenerator::getIndex	(	ArrayRef< uint8_t >	Bytes,
		size_t	StartBit,
		size_t	NumBits
	)

inlinestatic

Definition at line 87 of file TrieHashIndexGenerator.h.

References assert(), Bytes, llvm::ArrayRef< T >::drop_front(), Index, llvm::ArrayRef< T >::size(), and StartBit.

Referenced by getCollidingBits(), and next().

◆ getNumBits()

size_t llvm::TrieHashIndexGenerator::getNumBits ( ) const

inline

Definition at line 38 of file TrieHashIndexGenerator.h.

References assert(), Bytes, NumRootBits, NumSubtrieBits, llvm::ArrayRef< T >::size(), and StartBit.

◆ hint()

size_t llvm::TrieHashIndexGenerator::hint	(	unsigned	Index,
		unsigned	Bit
	)

inline

Definition at line 68 of file TrieHashIndexGenerator.h.

References assert(), Bytes, Index, NumRootBits, NumSubtrieBits, llvm::ArrayRef< T >::size(), and StartBit.

◆ next()

size_t llvm::TrieHashIndexGenerator::next ( )

inline

Definition at line 47 of file TrieHashIndexGenerator.h.

References assert(), Bytes, end(), getIndex(), NumRootBits, NumSubtrieBits, llvm::ArrayRef< T >::size(), and StartBit.

Member Data Documentation

◆ Bytes

ArrayRef<uint8_t> llvm::TrieHashIndexGenerator::Bytes

Definition at line 34 of file TrieHashIndexGenerator.h.

Referenced by getIndex(), getNumBits(), hint(), and next().

◆ NumRootBits

size_t llvm::TrieHashIndexGenerator::NumRootBits

Definition at line 32 of file TrieHashIndexGenerator.h.

Referenced by getNumBits(), hint(), and next().

◆ NumSubtrieBits

size_t llvm::TrieHashIndexGenerator::NumSubtrieBits

Definition at line 33 of file TrieHashIndexGenerator.h.

Referenced by getCollidingBits(), getNumBits(), hint(), and next().

◆ StartBit

std::optional<size_t> llvm::TrieHashIndexGenerator::StartBit = std::nullopt

Definition at line 35 of file TrieHashIndexGenerator.h.

Referenced by getCollidingBits(), getIndex(), getNumBits(), hint(), and next().

The documentation for this struct was generated from the following file:

include/llvm/ADT/TrieHashIndexGenerator.h