#include <SmallListSet.h>

Classes
class	BaseValueIterator

class	MappedValueEnumerable

class	MappedValueIterator

class	ValueEnumerable

class	ValueIterator

Public Member Functions
size_t	Size () const

GEOMETRYCORE_API void	Resize (int32 NewSize)

GEOMETRYCORE_API void	ResizeAndAllocateBlocks (int32 NewSize)

void	Reset ()

void	Compact (int32 MaxListIndex)

bool	IsAllocated (int32 ListIndex) const

GEOMETRYCORE_API void	AllocateAt (int32 ListIndex)

GEOMETRYCORE_API void	Insert (int32 ListIndex, int32 Value)

GEOMETRYCORE_API bool	Remove (int32 ListIndex, int32 Value)

GEOMETRYCORE_API void	Move (int32 FromIndex, int32 ToIndex)

GEOMETRYCORE_API void	Clear (int32 ListIndex)

int32	GetCount (int32 ListIndex) const

int32	First (int32 ListIndex) const

GEOMETRYCORE_API bool	Contains (int32 ListIndex, int32 Value) const

template<typename IntToBoolFunc >
int32	Find (int32 ListIndex, const IntToBoolFunc &PredicateFunc, int32 InvalidValue=-1) const

template<typename IntToBoolFunc >
bool	Replace (int32 ListIndex, const IntToBoolFunc &PredicateFunc, int32 NewValue)

template<typename IntToVoidFunc >
void	Enumerate (int32 ListIndex, const IntToVoidFunc &ApplyFunc) const

void	AppendWithElementOffset (const FSmallListSet &Other, int32 ElementOffset)

bool	EnumerateEarlyOut (int32 ListIndex, TFunctionRef< bool(int32)> ApplyFunc) const

GEOMETRYCORE_API void	Serialize (FArchive &Ar, bool bCompactData, bool bUseCompression)

ValueIterator	BeginValues (int32 ListIndex) const

ValueIterator	EndValues (int32 ListIndex) const

ValueEnumerable	Values (int32 ListIndex) const

MappedValueIterator	BeginMappedValues (int32 ListIndex, const TFunction< int32(int32)> &MapFunc) const

MappedValueIterator	EndMappedValues (int32 ListIndex, const TFunction< int32(int32)> &MapFunc) const

MappedValueEnumerable	MappedValues (int32 ListIndex, TFunction< int32(int32)> MapFunc) const

FString	MemoryUsage () const

SIZE_T	GetByteCount () const

Protected Member Functions
GEOMETRYCORE_API int32	AllocateBlock ()

void	AddFreeLink (int32 ptr)

GEOMETRYCORE_API bool	RemoveFromLinkedList (int32 block_ptr, int32 val)

Protected Attributes
TDynamicVector< int32 >	ListHeads {}

TDynamicVector< int32 >	ListBlocks {}

TDynamicVector< int32 >	FreeBlocks {}

int32	AllocatedCount {0}

TDynamicVector< int32 >	LinkedListElements {}

int32	FreeHeadIndex {NullValue}

Static Protected Attributes
static constexpr int32	NullValue = -1

static constexpr int32	BLOCKSIZE = 8

static constexpr int32	BLOCK_LIST_OFFSET = BLOCKSIZE + 1

Friends
class	ValueIterator

class	BaseValueIterator

class	MappedValueIterator

FArchive &	operator<< (FArchive &Ar, FSmallListSet &Set)

bool	operator== (const FSmallListSet &Lhs, const FSmallListSet &Rhs)

bool	operator!= (const FSmallListSet &Lhs, const FSmallListSet &Rhs)

Detailed Description

FSmallListSet stores a set of short integer-valued variable-size lists. The lists are encoded into a few large TDynamicVector buffers, with internal pooling, so adding/removing lists usually does not involve any new or delete ops.

The lists are stored in two parts. The first N elements are stored in a linear subset of a TDynamicVector. If the list spills past these N elements, the extra elements are stored in a linked list (which is also stored in a flat array).

Each list stores its count, so list-size operations are constant time. All the internal "pointers" are 32-bit.

Member Function Documentation

◆ AddFreeLink()

void UE::Geometry::FSmallListSet::AddFreeLink ( int32 ptr )

inlineprotected

◆ AllocateAt()

void FSmallListSet::AllocateAt ( int32 ListIndex )

Create a list at the given ListIndex

◆ AllocateBlock()

int32 FSmallListSet::AllocateBlock ( )

protected

◆ AppendWithElementOffset()

void FSmallListSet::AppendWithElementOffset	(	const FSmallListSet &	Other,
		int32	ElementOffset
	)

Append all elements from another small list set, with ElementOffset added to all such appended elements Note: Also directly appends free blocks / free lists; does no compacting

Parameters

Other	the list to append
ElementOffset	amount to shift all appended elements

◆ BeginMappedValues()

MappedValueIterator UE::Geometry::FSmallListSet::BeginMappedValues	(	int32	ListIndex,
		const TFunction< int32(int32)> &	MapFunc
	)		const

inline

Returns: iterator for start of list at ListIndex, with given value mapping function

◆ BeginValues()

ValueIterator UE::Geometry::FSmallListSet::BeginValues ( int32 ListIndex ) const

inline

Returns: iterator for start of list at ListIndex

◆ Clear()

void FSmallListSet::Clear ( int32 ListIndex )

Remove all elements from the list at ListIndex

◆ Compact()

void FSmallListSet::Compact ( int32 MaxListIndex )

Clearing any lists at or after MaxListIndex and compact the ListBlocks and LinkedListElements so there are no free blocks or free linked list elements

◆ Contains()

bool FSmallListSet::Contains	(	int32	ListIndex,
		int32	Value
	)		const

Search for the given Value in list at ListIndex

Returns: true if found

◆ EndMappedValues()

MappedValueIterator UE::Geometry::FSmallListSet::EndMappedValues	(	int32	ListIndex,
		const TFunction< int32(int32)> &	MapFunc
	)		const

inline

Returns: iterator for end of list at ListIndex, with given value mapping function

◆ EndValues()

ValueIterator UE::Geometry::FSmallListSet::EndValues ( int32 ListIndex ) const

inline

Returns: iterator for end of list at ListIndex

◆ Enumerate()

template<typename IntToVoidFunc >

void UE::Geometry::FSmallListSet::Enumerate	(	int32	ListIndex,
		const IntToVoidFunc &	ApplyFunc
	)		const

inline

Call ApplyFunc on each element of the list at ListIndex

◆ EnumerateEarlyOut()

bool FSmallListSet::EnumerateEarlyOut	(	int32	ListIndex,
		TFunctionRef< bool(int32)>	ApplyFunc
	)		const

Call ApplyFunc on each element of the list at ListIndex, until ApplyFunc returns false

Returns: true if all elements were processed and ApplyFunc never returned false

◆ Find()

template<typename IntToBoolFunc >

int32 UE::Geometry::FSmallListSet::Find	(	int32	ListIndex,
		const IntToBoolFunc &	PredicateFunc,
		int32	InvalidValue = `-1`
	)		const

inline

Search the list at ListIndex for a value where PredicateFunc(value) returns true

Returns: the found value, or the InvalidValue argument if not found

◆ First()

int32 UE::Geometry::FSmallListSet::First ( int32 ListIndex ) const

inline

Returns: the first item in the list at ListIndex

Warning: does not check for zero-size-list!

◆ GetByteCount()

SIZE_T UE::Geometry::FSmallListSet::GetByteCount ( ) const

inline

◆ GetCount()

int32 UE::Geometry::FSmallListSet::GetCount ( int32 ListIndex ) const

inline

Returns: the size of the list at ListIndex

◆ Insert()

void FSmallListSet::Insert	(	int32	ListIndex,
		int32	Value
	)

Insert Value into list at ListIndex

◆ IsAllocated()

bool UE::Geometry::FSmallListSet::IsAllocated ( int32 ListIndex ) const

inline

Returns: true if a list has been allocated at the given ListIndex

◆ MappedValues()

MappedValueEnumerable UE::Geometry::FSmallListSet::MappedValues	(	int32	ListIndex,
		TFunction< int32(int32)>	MapFunc
	)		const

inline

Returns: a value enumerable for the given ListIndex, with the given value mapping function

◆ MemoryUsage()

FString UE::Geometry::FSmallListSet::MemoryUsage ( ) const

inline

◆ Move()

void FSmallListSet::Move	(	int32	FromIndex,
		int32	ToIndex
	)

Move list at FromIndex to ToIndex

◆ Remove()

bool FSmallListSet::Remove	(	int32	ListIndex,
		int32	Value
	)

remove Value from the list at ListIndex

Returns: false if Value was not in this list

◆ RemoveFromLinkedList()

bool FSmallListSet::RemoveFromLinkedList	(	int32	block_ptr,
		int32	val
	)

protected

◆ Replace()

template<typename IntToBoolFunc >

bool UE::Geometry::FSmallListSet::Replace	(	int32	ListIndex,
		const IntToBoolFunc &	PredicateFunc,
		int32	NewValue
	)

inline

Search the list at ListIndex for a value where PredicateFunc(value) returns true, and replace it with NewValue

Returns: true if the value was found and replaced

◆ Reset()

void UE::Geometry::FSmallListSet::Reset ( )

inline

Reset to initial state

◆ Resize()

void FSmallListSet::Resize ( int32 NewSize )

set new number of lists

◆ ResizeAndAllocateBlocks()

void FSmallListSet::ResizeAndAllocateBlocks ( int32 NewSize )

resize to a new number of lists and pre-allocate an initial empty block for each list.

◆ Serialize()

void FSmallListSet::Serialize	(	FArchive &	Ar,
		bool	bCompactData,
		bool	bUseCompression
	)

Serialize FSmallListSet to an archive.

Parameters

Ar	Archive to serialize with
bCompactData	Only serialize unique data and/or recompute redundant data when loading.
bUseCompression	Use compression to serialize data; the resulting size will likely be smaller but serialization will take significantly longer.

◆ Size()

size_t UE::Geometry::FSmallListSet::Size ( ) const

inline

Returns: largest current list index

◆ Values()

ValueEnumerable UE::Geometry::FSmallListSet::Values ( int32 ListIndex ) const

inline

Returns: a value enumerable for the given ListIndex

Friends And Related Symbol Documentation

◆ BaseValueIterator

friend class BaseValueIterator

friend

◆ MappedValueIterator

friend class MappedValueIterator

friend

◆ operator!=

bool operator!=	(	const FSmallListSet &	Lhs,
		const FSmallListSet &	Rhs
	)

friend

◆ operator<<

FArchive & operator<<	(	FArchive &	Ar,
		FSmallListSet &	Set
	)

friend

Serialization operator for FSmallListSet.

Parameters

Ar	Archive to serialize with.
Set	Set to serialize.

Returns: Passing down serializing archive.

◆ operator==

bool operator==	(	const FSmallListSet &	Lhs,
		const FSmallListSet &	Rhs
	)

friend

◆ ValueIterator

friend class ValueIterator

friend

Member Data Documentation

◆ AllocatedCount

int32 UE::Geometry::FSmallListSet::AllocatedCount {0}

protected

number of allocated lists

◆ BLOCK_LIST_OFFSET

constexpr int32 UE::Geometry::FSmallListSet::BLOCK_LIST_OFFSET = BLOCKSIZE + 1

staticconstexprprotected

offset from start of linear-memory portion of list that contains pointer to head of variable-length linked list

◆ BLOCKSIZE

constexpr int32 UE::Geometry::FSmallListSet::BLOCKSIZE = 8

staticconstexprprotected

size of initial linear-memory portion of lists

◆ FreeBlocks

TDynamicVector<int32> UE::Geometry::FSmallListSet::FreeBlocks {}

protected

list of free blocks as indices/offsets into ListBlocks

◆ FreeHeadIndex

int32 UE::Geometry::FSmallListSet::FreeHeadIndex {NullValue}

protected

index of first free element in LinkedListElements

◆ LinkedListElements

TDynamicVector<int32> UE::Geometry::FSmallListSet::LinkedListElements {}

protected

flat buffer used to store linked-list "spill" elements each element is [value, next_ptr]

◆ ListBlocks

TDynamicVector<int32> UE::Geometry::FSmallListSet::ListBlocks {}

protected

flat buffer used to store per-list linear-memory blocks. blocks are BLOCKSIZE+2 long, elements are [CurrentCount, item0...itemN, LinkedListPtr]

◆ ListHeads

TDynamicVector<int32> UE::Geometry::FSmallListSet::ListHeads {}

protected

mapping from list index to offset into ListBlocks that contains list data

◆ NullValue

constexpr int32 UE::Geometry::FSmallListSet::NullValue = -1

staticconstexprprotected

This value is used to indicate Null in internal pointers

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

Engine/Source/Runtime/GeometryCore/Public/Util/SmallListSet.h
Engine/Source/Runtime/GeometryCore/Private/Util/SmallListSet.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Detailed Description

Member Function Documentation

◆ AddFreeLink()

◆ AllocateAt()

◆ AllocateBlock()

◆ AppendWithElementOffset()

◆ BeginMappedValues()

◆ BeginValues()

◆ Clear()

◆ Compact()

◆ Contains()

◆ EndMappedValues()

◆ EndValues()

◆ Enumerate()

◆ EnumerateEarlyOut()

◆ Find()

◆ First()

◆ GetByteCount()

◆ GetCount()

◆ Insert()

◆ IsAllocated()

◆ MappedValues()

◆ MemoryUsage()

◆ Move()

◆ Remove()

◆ RemoveFromLinkedList()

◆ Replace()

◆ Reset()

◆ Resize()

◆ ResizeAndAllocateBlocks()

◆ Serialize()

◆ Size()

◆ Values()

Friends And Related Symbol Documentation

◆ BaseValueIterator

◆ MappedValueIterator

◆ operator!=

◆ operator<<

◆ operator==

◆ ValueIterator

Member Data Documentation

◆ AllocatedCount

◆ BLOCK_LIST_OFFSET

◆ BLOCKSIZE

◆ FreeBlocks

◆ FreeHeadIndex

◆ LinkedListElements

◆ ListBlocks

◆ ListHeads

◆ NullValue