llvm::EytzingerTableSpan< T > Class Template Reference

Non-owning view of a buffer formatted as a complete binary search tree in Eytzinger (breadth-first) order. More...

#include "llvm/ADT/Eytzinger.h"

Inheritance diagram for llvm::EytzingerTableSpan< T >:

Public Types
using	iterator = const T *
using	const_iterator = const T *

Public Member Functions
	EytzingerTableSpan ()=default
	EytzingerTableSpan (const T *Data, size_t NumEntries)
iterator	begin () const
iterator	end () const
const T *	data () const
bool	empty () const
size_t	size () const
const T &	operator[] (size_t Idx) const
template<typename KeyT = T>
std::optional< size_t >	findIndex (const KeyT &Target) const
	Search this Eytzinger table for Target.
template<typename KeyT = T>
bool	contains (const KeyT &Target) const
	Check if this Eytzinger table contains Target.
bool	isSorted () const
	Verify whether the buffer satisfies strictly ascending binary search tree order in Eytzinger layout.

Detailed Description

template<typename T>
class llvm::EytzingerTableSpan< T >

Non-owning view of a buffer formatted as a complete binary search tree in Eytzinger (breadth-first) order.

Definition at line 30 of file Eytzinger.h.

Member Typedef Documentation

const_iterator

template<typename T>

using llvm::EytzingerTableSpan< T >::const_iterator = const T *

Definition at line 33 of file Eytzinger.h.

iterator

template<typename T>

using llvm::EytzingerTableSpan< T >::iterator = const T *

Definition at line 32 of file Eytzinger.h.

Constructor & Destructor Documentation

EytzingerTableSpan() [1/2]

template<typename T>

llvm::EytzingerTableSpan< T >::EytzingerTableSpan ( )

default

EytzingerTableSpan() [2/2]

template<typename T>

llvm::EytzingerTableSpan< T >::EytzingerTableSpan ( const T * Data, size_t NumEntries )

inline

Definition at line 36 of file Eytzinger.h.

References T.

Member Function Documentation

begin()

template<typename T>

iterator llvm::EytzingerTableSpan< T >::begin ( ) const

inlinenodiscard

Definition at line 39 of file Eytzinger.h.

contains()

template<typename T>

template<typename KeyT = T>

bool llvm::EytzingerTableSpan< T >::contains ( const KeyT & Target ) const

inlinenodiscard

Check if this Eytzinger table contains Target.

Definition at line 68 of file Eytzinger.h.

References findIndex().

data()

template<typename T>

const T * llvm::EytzingerTableSpan< T >::data ( ) const

inlinenodiscard

Definition at line 41 of file Eytzinger.h.

References T.

empty()

template<typename T>

bool llvm::EytzingerTableSpan< T >::empty ( ) const

inlinenodiscard

Definition at line 42 of file Eytzinger.h.

Referenced by isSorted().

end()

template<typename T>

iterator llvm::EytzingerTableSpan< T >::end ( ) const

inlinenodiscard

Definition at line 40 of file Eytzinger.h.

findIndex()

template<typename T>

template<typename KeyT = T>

std::optional< size_t > llvm::EytzingerTableSpan< T >::findIndex ( const KeyT & Target ) const

inlinenodiscard

Search this Eytzinger table for Target.

Returns the 0-based array index if found.

KeyT enables heterogeneous lookups, allowing callers to search tables of endian-specific wrappers (e.g., support::ulittle64_t) using native integer keys without explicit conversions at the call site.

Definition at line 56 of file Eytzinger.h.

References I.

Referenced by contains().

isSorted()

template<typename T>

bool llvm::EytzingerTableSpan< T >::isSorted ( ) const

inlinenodiscard

Verify whether the buffer satisfies strictly ascending binary search tree order in Eytzinger layout.

Runs iteratively in O(N) time and O(1) space.

Definition at line 74 of file Eytzinger.h.

References empty(), I, llvm::Left, llvm::Right, and T.

operator[]()

template<typename T>

const T & llvm::EytzingerTableSpan< T >::operator[] ( size_t Idx ) const

inlinenodiscard

Definition at line 44 of file Eytzinger.h.

References assert(), and T.

size()

template<typename T>

size_t llvm::EytzingerTableSpan< T >::size ( ) const

inlinenodiscard

Definition at line 43 of file Eytzinger.h.

---

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

• include/llvm/ADT/Eytzinger.h