#include <gimbal_ring_list.h>

Data Fields
union {

GblDoublyLinkedListNode listNode

struct {

struct GblRingList * pNext

struct GblRingList * pPrev

} ringNode

};

union {

uintptr_t size

void * pData

};

Detailed Description

Non-intrusive circularly doubly linked list with C++-style STL API.

GblRingList is a non-intrusive circular doubly-linked list with an API mirroring C++'s std::vector, or that of an abstract List from other languges. All values are stored in the form of void* pointers.

Each entry within the list is maintained as a simple GblDoublyLinkedListNode connecting it to the prevous and next entries along with a void* as a data payload (with the list head storing its size in that union field instead). While these nodes are directly accessible, a higher-level API is presented, which manages allocations and node relationships internally.

The GblRingList API has been tweaked for convenience within the C programming language. This is why many of the methods are provided as overridden macros implementing default values and function overloading for doing things such as inserting or removing multiple entries at once.

Operation	Time Complexity
iteration	O(N)
insertion/removal (middle)	O(N)
insertion/removal (front or back)	O(1)
access (front or back)	O(1)
random access (middle)	O(N)

Note: As it's non-intrusive, every list entry must dynamically allocate a new node when a value is added to the list, which would normally result in lots of small, disjoint heap allocations, causing fragmentation. However, this is not the case with GblRingList. LibGimbal uses an arena allocator internally to efficiently allocate each node from contiguous blocks of data, also maintaining a free list to reuse nodes as they become available.

See also: GblDoublyLinkedListNode

Definition at line 70 of file gimbal_ring_list.h.

Field Documentation

◆ listNode

GblDoublyLinkedListNode GblRingList::listNode

Definition at line 72 of file gimbal_ring_list.h.

◆ pNext

struct GblRingList* GblRingList::pNext

Definition at line 74 of file gimbal_ring_list.h.

◆ pPrev

struct GblRingList* GblRingList::pPrev

Definition at line 75 of file gimbal_ring_list.h.

◆ size

uintptr_t GblRingList::size

Definition at line 79 of file gimbal_ring_list.h.

◆ pData

void* GblRingList::pData

Definition at line 80 of file gimbal_ring_list.h.

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

gimbal_ring_list.h