Segmented list where each segment contains multiple nodes Allows growing the list without having to invalidate all previous memory addresses. More...

#include <segmented_list.hpp>

Classes
struct	ConstIter
	Const reference for mutating elements Using custom iterator for speed. More...

struct	ConstPtrIter
	Pointer iterator for mutating elements Using custom iterator for speed. More...

struct	PtrIter
	Pointer iterator for mutating elements Using custom iterator for speed. More...

Public Types
using	Elem = T

Public Member Functions
PtrIter	ptr_iter () noexcept
	Mutable iterator that gives element pointers.

ConstPtrIter	ptr_iter () const noexcept
	Const iterator that gives const element pointers.

ConstIter	iter () const noexcept
	Const iterator that gives element references.

size_t	size () const noexcept
	Gets the size of the list.

Result< void, AllocationError >	init (Allocator &alloc, size_t initCapacity)
	Initializes a segmented list.

Result< void, AllocationError >	init (Allocator &alloc, std::initializer_list< T > list)
	Initializes a segmented list.

void	deinit (Allocator &alloc)
	Cleans up memory tied to segmented list.

void	drop_unused_segments (Allocator &alloc)
	Lowers memory footprint by dropping unused segments.

Result< void, CollectionAddNoAllocationError >	push (const T &elem) noexcept
	Pushes a new element.

Result< void, AllocationError >	push (Allocator &alloc, const T &elem) noexcept
	Pushes a new element.

const T &	operator[] (size_t index) const noexcept
	Access element at index.

T &	operator[] (size_t index) noexcept
	Access element at index.

const T &	at (size_t index) const noexcept
	Access element at index.

T &	at (size_t index) noexcept
	Access element at index.

bool	operator== (const SegmentedList &other)

bool	operator!= (const SegmentedList &other)

void	pop ()
	remove last element

size_t	capacity () const

Detailed Description

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

Segmented list where each segment contains multiple nodes Allows growing the list without having to invalidate all previous memory addresses.

Only allows removing elements at the end.

The only operations which invalidate existing memory addresses are pop(), swap_remove(), and deinit() Otherwise, memory addresses are guaranteed to remain stable

Accessing elements is \(O(log_{1.5}(N))\) Adding elements is \(O(1)\) Removing elements is \(O(1)\), but only removes last element

For a more flexible removal/insertion,

See also: GenList or; ArrayList

Definition at line 45 of file segmented_list.hpp.

Member Typedef Documentation

◆ Elem

template<typename T>

using mtcore::SegmentedList< T >::Elem = T

Definition at line 46 of file segmented_list.hpp.

Member Function Documentation

◆ at() [1/2]

template<typename T>

const T & mtcore::SegmentedList< T >::at ( size_t index ) const

inlinenodiscardnoexcept

Access element at index.

Parameters

index index to access

Returns: reference at index

Definition at line 372 of file segmented_list.hpp.

                                                           {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      const Segment *cur = &start;
      while (cur) {
        if (index < cur->elements.len) {
          return cur->elements[index];
        }
        index -= cur->elements.len;
        cur = cur->next;
      }
      unreachable("OUT OF BOUNDS ACCESS");
    }

Here is the caller graph for this function:

◆ at() [2/2]

template<typename T>

T & mtcore::SegmentedList< T >::at ( size_t index )

inlinenodiscardnoexcept

Access element at index.

Parameters

index index to access

Returns: reference at index

Definition at line 391 of file segmented_list.hpp.

                                               {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(index < len, "OUT OF BOUNDS ACCESS");
      Segment *cur = &start;
      while (cur) {
        if (index < cur->elements.size()) {
          return cur->elements[index];
        }
        index -= cur->elements.size();
        cur = cur->next;
      }
      unreachable("OUT OF BOUNDS ACCESS");
    }

◆ capacity()

template<typename T>

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

inlinenodiscard

Definition at line 439 of file segmented_list.hpp.

439{ return totalCapacity; }

◆ deinit()

template<typename T>

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

inline

Cleans up memory tied to segmented list.

Parameters

alloc allocator to clean up memory with

Definition at line 241 of file segmented_list.hpp.

                                  {
      if (start.elements.head != nullptr) {
        alloc.destroy_many(start.elements);
      }
      if (start.next != nullptr) {
        Segment *cur = start.next;
        while (cur) {
          Segment *next = cur->next;
          alloc.destroy_many(cur->elements);
          alloc.destroy(cur);
          cur = next;
        }
      }
      totalCapacity = 0;
      end           = nullptr;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ drop_unused_segments()

template<typename T>

void mtcore::SegmentedList< T >::drop_unused_segments ( Allocator & alloc )

inline

Lowers memory footprint by dropping unused segments.

Parameters

alloc Allocator to drop segments with

Definition at line 262 of file segmented_list.hpp.

                                                {
      ensure(start.elements.head, "NOT INITIALIZED");
      Segment *prev    = &start;
      Segment *cur     = start.next;
      end              = &start;
      size_t remaining = size();
      while (cur) {
        if (remaining > prev->elements.len) {
          remaining -= prev->elements.len;
          auto next = cur->next;
          end       = cur;
          prev      = cur;
          cur       = next;
        }
        else {
          prev->next = nullptr;
          while (cur) {
            Segment *next = cur->next;
            totalCapacity -= cur->elements.size();
            alloc.destroy_many(cur->elements);
            alloc.destroy(cur);
            cur = next;
          }
          break;
        }
      }
    }

Here is the call graph for this function:

◆ init() [1/2]

template<typename T>

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

inlinenodiscard

Initializes a segmented list.

Parameters

alloc	Allocator to use for initializing memory
initCapacity	Initial list capacity

Returns: Successful Result or error

Definition at line 190 of file segmented_list.hpp.

                                                                                            {
      ensure(initCapacity > 0, "NO INITIAL CAPACITY");
      ensure(start.elements.head == nullptr, "ALREADY INITIALIZED");
      ensure(start.elements.size() == 0, "ALREADY INITIALIZED");
      ensure(start.next == nullptr, "ALREADY INITIALIZED");
 
      auto allocRes = alloc.create_many<T>(initCapacity);
      if (allocRes.is_error()) {
        return allocRes.error();
      }
 
      start.elements = *allocRes;
      totalCapacity  = initCapacity;
      return success();
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init() [2/2]

template<typename T>

Result< void, AllocationError > mtcore::SegmentedList< T >::init	(	Allocator &	alloc,
		std::initializer_list< T >	list )

inlinenodiscard

Initializes a segmented list.

Parameters

alloc	Allocator to use for initializing memory
list	List of elements to initialize with

Returns: Successful Result or error

Definition at line 212 of file segmented_list.hpp.

                                                                                                    {
      ensure(start.elements.head == nullptr, "ALREADY INITIALIZED");
      ensure(list.size() > 0, "NO INITIAL CAPACITY");
      ensure(!start.elements.head, "ALREADY INITIALIZED");
      ensure(!start.elements.size(), "ALREADY INITIALIZED");
      ensure(!start.next, "ALREADY INITIALIZED");
 
      auto allocRes = alloc.create_many<T>(list.size());
      if (allocRes.is_error()) {
        return allocRes.error();
      }
      totalCapacity = list.size();
 
      start.elements = *allocRes;
 
      size_t i = 0;
      for (const auto &elem: list) {
        start.elements[i++] = elem;
      }
      len = list.size();
      end = &start;
 
      return success();
    }

Here is the call graph for this function:

◆ iter()

template<typename T>

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

inlinenodiscardnoexcept

Const iterator that gives element references.

Returns: Const reference iterator

Definition at line 173 of file segmented_list.hpp.

                                                  {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

Here is the caller graph for this function:

◆ operator!=()

template<typename T>

bool mtcore::SegmentedList< T >::operator!= ( const SegmentedList< T > & other )

inlinenodiscard

Parameters

other List to compare to

Returns: true if doesn't have same elements

Definition at line 427 of file segmented_list.hpp.

427{ return !(*this == other); }

◆ operator==()

template<typename T>

bool mtcore::SegmentedList< T >::operator== ( const SegmentedList< T > & other )

inlinenodiscard

Parameters

other List to compare to

Returns: true if does have same elements

Definition at line 409 of file segmented_list.hpp.

                                                              {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      ensure(other.start.elements.head != nullptr, "NOT INITIALIZED");
      if (len != other.len) {
        return false;
      }
      for (size_t i = 0; i < len; ++i) {
        if (at(i) != other.at(i)) {
          return false;
        }
      }
      return true;
    }

Here is the call graph for this function:

◆ operator[]() [1/2]

template<typename T>

const T & mtcore::SegmentedList< T >::operator[] ( size_t index ) const

inlinenodiscardnoexcept

Access element at index.

Parameters

index index to access

Returns: reference at index

Definition at line 352 of file segmented_list.hpp.

                                                                   {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      return at(index);
    }

Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename T>

T & mtcore::SegmentedList< T >::operator[] ( size_t index )

inlinenodiscardnoexcept

Access element at index.

Parameters

index index to access

Returns: reference at index

Definition at line 362 of file segmented_list.hpp.

                                                       {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      return at(index);
    }

Here is the call graph for this function:

◆ pop()

template<typename T>

void mtcore::SegmentedList< T >::pop ( )

inline

remove last element

Definition at line 432 of file segmented_list.hpp.

               {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
      if (len > 0) {
        --len;
      }
    }

◆ ptr_iter() [1/2]

template<typename T>

ConstPtrIter mtcore::SegmentedList< T >::ptr_iter ( ) const

inlinenodiscardnoexcept

Const iterator that gives const element pointers.

Returns: Pointer iterator

Definition at line 164 of file segmented_list.hpp.

                                                         {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

◆ ptr_iter() [2/2]

template<typename T>

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

inlinenodiscardnoexcept

Mutable iterator that gives element pointers.

Returns: Pointer iterator

Definition at line 155 of file segmented_list.hpp.

                                              {
      ensure(start.elements.head, "NOT INITIALIZED");
      return {0, *this, 0, &start};
    }

◆ push() [1/2]

template<typename T>

Result< void, AllocationError > mtcore::SegmentedList< T >::push	(	Allocator &	alloc,
		const T &	elem )

inlinenodiscardnoexcept

Pushes a new element.

Will allocate if there is no space

Parameters

alloc	Allocator to use for additional allocation
elem	Element to add

Returns: Success or error

Definition at line 314 of file segmented_list.hpp.

                                                                                               {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
 
      Segment *cur = end;
      if (endIndex < cur->elements.size()) {
        mtdefer { ++len; };
        cur->elements[endIndex++] = elem;
        return success();
      }
 
      auto allocSegRes = alloc.create<Segment>();
 
      if (allocSegRes.is_error()) {
        return allocSegRes.error();
      }
 
      auto allocElemRes = alloc.create_many<T>(cur->elements.size() + cur->elements.size() / 2);
      if (allocElemRes.is_error()) {
        alloc.destroy(*allocSegRes);
        return allocElemRes.error();
      }
      mtdefer { ++len; };
      cur->next                 = *allocSegRes;
      end                       = cur->next;
      endIndex                  = 0;
      cur                       = cur->next;
      cur->elements             = *allocElemRes;
      cur->elements[endIndex++] = elem;
      end                       = cur;
      totalCapacity += cur->elements.size();
      return success();
    }

Here is the call graph for this function:

◆ push() [2/2]

template<typename T>

Result< void, CollectionAddNoAllocationError > mtcore::SegmentedList< T >::push ( const T & elem )

inlinenodiscardnoexcept

Pushes a new element.

Will error if there is no space

Parameters

elem	Element to add

Returns: Success or error

Definition at line 295 of file segmented_list.hpp.

                                                                                            {
      ensure(start.elements.head != nullptr, "NOT INITIALIZED");
 
      Segment *cur = end;
      ensure(cur);
      if (endIndex < cur->elements.size()) {
        mtdefer { ++len; };
        cur->elements[endIndex++] = elem;
        return success();
      }
      return error(CollectionAddNoAllocationError::NO_ROOM);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

template<typename T>

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

inlinenodiscardnoexcept

Gets the size of the list.

Returns: Size of segmented list

Definition at line 182 of file segmented_list.hpp.

182{ return len; }

Here is the caller graph for this function:

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

segmented_list.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Elem

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ capacity()

◆ deinit()

◆ drop_unused_segments()

◆ init() [1/2]

◆ init() [2/2]

◆ iter()

◆ operator!=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop()

◆ ptr_iter() [1/2]

◆ ptr_iter() [2/2]

◆ push() [1/2]

◆ push() [2/2]

◆ size()