mtcore::GenList< T > Struct Template Reference

Represents a generational list where removed items are marked and recycled. More...

#include <gen_list.hpp>

Inheritance diagram for mtcore::GenList< T >:

Classes
struct	ConstIter
	An iterator that iterates over values (copies) of each stored element. More...
struct	HandleIter
	An iterator that iterates over all handles of each stored element. More...
struct	PtrIter
	An iterator that iterates over pointers to each stored element. More...

Public Member Functions
Result< void, AllocationError >	init (Allocator &alloc, size_t initCapacity=64)
	Initializes a generational list.
void	deinit (Allocator &alloc)
	Deinitializes a list.
Result< Handle, CollectionAddNoAllocationError >	add (const T &item) noexcept
	Adds a new item to the generational list Will first try to recycle removed items Will then try to add a new item if there is remaining capacity Will fail if there is no remaining capacity.
Result< Handle, AllocationError >	add (Allocator &alloc, const T &item) noexcept
	Adds a new item to the generational list Will first try to recycle removed items Will then try to add a new item if there is remaining capacity Will reallocate if there is no remaining capacity.
const T &	operator[] (const Handle &handle) const noexcept
	References an element by handle.
T &	operator[] (const Handle &handle) noexcept
	References an element by handle.
Optional< T >	at (const Handle &handle) const noexcept
	Gets an item at a handle If item does not exist, or handle is no longer valid, will return nullopt.
bool	is_handle_valid (const Handle &handle) const noexcept
	Checks if a handle is currently valid.
size_t	size () const noexcept
	Size of GenList (number of live elements)
size_t	capacity () const noexcept
	Capacity of GenList.
void	remove (const Handle &handle) noexcept
	Will remove the element at a handle Aborts if handle is no longer valid.
PtrIter	ptr_iter () noexcept
	Iterates over pointers of stored elements Allows changing stored elements directly.
ConstIter	iter () const noexcept
	Iterates over copied values of stored elements.
HandleIter	handles () const noexcept
	Iterates over handles for stored elements Allows accessing and manipulating elements by handles Since removed elements are only marked deleted, it is safe to remove handles while iterating so long as you do not try to access a deleted element by handle once it's been removed Note that adding elements while iterating may Result in undefined behavior.

Detailed Description

template<typename T>
struct mtcore::GenList< T >

Represents a generational list where removed items are marked and recycled.

Each element is referred to with a handle (index + generation) instead of pointers. This allows elements to be reliably referenced, even after a memory copy (such as reallocation). Additionally, it also allows detection of dead handles (i.e. the referenced element was removed), which may be important when lifetimes are complex.

Note that this data structure is not memory stable as it uses an ArrayList which does memory copies when it runs out of memory.

Accessing elements is \(O(1)\) Adding elements is \(O(N)\) (though it should be fast as we check 64 slots at once) Removing elements is \(O(1)\)

Template Parameters

T	Stored element type

Definition at line 59 of file gen_list.hpp.

Member Function Documentation

add() [1/2]

template<typename T>

Result< Handle, AllocationError > mtcore::GenList< T >::add ( Allocator & alloc, const T & item )

inlinenoexcept

Adds a new item to the generational list Will first try to recycle removed items Will then try to add a new item if there is remaining capacity Will reallocate if there is no remaining capacity.

Parameters

alloc	Allocator to use for growing memory
item	Item to add

Returns

Handle (on success) or failure

Definition at line 124 of file gen_list.hpp.

                                                                                  {
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      if (auto res = add(item); res.is_success()) {
        return res.value();
      }
 
      entries.reserve(alloc, entries.capacity() * 2);
      dead.resize(alloc, entries.capacity(), true);
 
      return add(item).value();
    }

Here is the call graph for this function:

add() [2/2]

template<typename T>

Result< Handle, CollectionAddNoAllocationError > mtcore::GenList< T >::add ( const T & item )

inlinenoexcept

Adds a new item to the generational list Will first try to recycle removed items Will then try to add a new item if there is remaining capacity Will fail if there is no remaining capacity.

Parameters

item	Item to add

Returns

Handle (on success) or failure

Definition at line 96 of file gen_list.hpp.

                                                                               {
      mtdefer { ensure(size() <= capacity(), "SIZE MISMATCH"); };
      auto index = dead.first_set();
      if (index.has_value() && index.value() < entries.size()) {
        auto i = *index;
        ensure(dead[i], "BAD INDEX");
        entries[i].generation += 1;
        entries[i].item = item;
        dead.set(i, false);
        return success(Handle{i, entries[i].generation});
      }
 
      size_t i = entries.size();
      if (auto res = entries.push(Gen{item, 0}); res.is_error()) {
        return res.error();
      }
      return success(Handle{i, 0});
    }

Here is the call graph for this function:

Here is the caller graph for this function:

at()

template<typename T>

Optional< T > mtcore::GenList< T >::at ( const Handle & handle ) const

inlinenoexcept

Gets an item at a handle If item does not exist, or handle is no longer valid, will return nullopt.

Parameters

handle

Handle (from add) to use to access element

Returns

Copy of element (if handle is valid), nullopt otherwise

Definition at line 164 of file gen_list.hpp.

                                                        {
      auto index = handle.index;
      if (index >= entries.size()) {
        return nullopt;
      }
      if (entries[index].generation != handle.generation) {
        return nullopt;
      }
      return entries[index].item;
    }

capacity()

template<typename T>

size_t mtcore::GenList< T >::capacity ( ) const

inlinenodiscardnoexcept

Capacity of GenList.

Definition at line 197 of file gen_list.hpp.

{ return entries.capacity(); }

Here is the caller graph for this function:

deinit()

template<typename T>

void mtcore::GenList< T >::deinit ( Allocator & alloc )

inline

Deinitializes a list.

Parameters

alloc

Allocator for memory cleanup

Definition at line 83 of file gen_list.hpp.

                                  {
      entries.deinit(alloc);
      dead.deinit(alloc);
    }

handles()

template<typename T>

HandleIter mtcore::GenList< T >::handles ( ) const

inlinenoexcept

Iterates over handles for stored elements Allows accessing and manipulating elements by handles Since removed elements are only marked deleted, it is safe to remove handles while iterating so long as you do not try to access a deleted element by handle once it's been removed Note that adding elements while iterating may Result in undefined behavior.

Returns

Iterator over handles for elements

Definition at line 300 of file gen_list.hpp.

{ return HandleIter{*this}; }

init()

template<typename T>

Result< void, AllocationError > mtcore::GenList< T >::init ( Allocator & alloc, size_t initCapacity = 64 )

inline

Initializes a generational list.

Parameters

alloc	Allocator for memory allocation
initCapacity	Initial list capacity

Returns

success or failure

Definition at line 67 of file gen_list.hpp.

                                                                                   {
      if (auto res = entries.init(alloc, initCapacity); res.is_error()) {
        return res;
      }
      if (auto res = dead.init(alloc, initCapacity); res.is_error()) {
        entries.deinit(alloc);
        return res;
      }
      dead.set_all(false);
      return success();
    }

Here is the call graph for this function:

is_handle_valid()

template<typename T>

bool mtcore::GenList< T >::is_handle_valid ( const Handle & handle ) const

inlinenodiscardnoexcept

Checks if a handle is currently valid.

Parameters

handle

Handle to check

Returns

true if valid, false otherwise

Definition at line 180 of file gen_list.hpp.

                                                                            {
      if (handle.index >= entries.size()) {
        return false;
      }
      if (dead[handle.index]) {
        return false;
      }
      if (entries[handle.index].generation != handle.generation) {
        return false;
      }
      return true;
    }

Here is the caller graph for this function:

iter()

template<typename T>

ConstIter mtcore::GenList< T >::iter ( ) const

inlinenoexcept

Iterates over copied values of stored elements.

Returns

Iterator over copies of elements

Definition at line 289 of file gen_list.hpp.

{ return ConstIter{*this}; }

operator[]() [1/2]

template<typename T>

const T & mtcore::GenList< T >::operator[] ( const Handle & handle ) const

inlinenoexcept

References an element by handle.

Parameters

handle

Handle (from add) to use to access element

Returns

Reference to element

Definition at line 141 of file gen_list.hpp.

                                                             {
      auto index = handle.index;
      ensure(entries[index].generation == handle.generation, "INVALID HANDLE, BAD GENERATION");
      return entries[index].item;
    }

operator[]() [2/2]

template<typename T>

T & mtcore::GenList< T >::operator[] ( const Handle & handle )

inlinenoexcept

References an element by handle.

Parameters

handle

Handle (from add) to use to access element

Returns

Reference to element

Definition at line 152 of file gen_list.hpp.

                                                 {
      auto index = handle.index;
      ensure(entries[index].generation == handle.generation, "INVALID HANDLE, BAD GENERATION");
      return entries[index].item;
    }

ptr_iter()

template<typename T>

PtrIter mtcore::GenList< T >::ptr_iter ( )

inlinenoexcept

Iterates over pointers of stored elements Allows changing stored elements directly.

Returns

Iterator over pointers to elements

Definition at line 283 of file gen_list.hpp.

{ return PtrIter{*this}; }

remove()

template<typename T>

void mtcore::GenList< T >::remove ( const Handle & handle )

inlinenoexcept

Will remove the element at a handle Aborts if handle is no longer valid.

Parameters

handle

Handle to remove element at

Definition at line 204 of file gen_list.hpp.

                                               {
      ensure(is_handle_valid(handle), "BAD HANDLE");
      dead[handle.index] = true;
    }

Here is the call graph for this function:

size()

template<typename T>

size_t mtcore::GenList< T >::size ( ) const

inlinenodiscardnoexcept

Size of GenList (number of live elements)

Definition at line 194 of file gen_list.hpp.

{ return entries.size() - dead.pop_count(); }

Here is the caller graph for this function:

---

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

• gen_list.hpp