GblRingList Struct Reference

#include <gimbal_ring_list.h>

Collaboration diagram for GblRingList:

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, except for the list can also be indexed from back-to-front with negative indices.

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

Each node should be 12 bytes large on 32-bit and 24-bytes large on 64-bit architectures.

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, GblRingList

Definition at line 122 of file gimbal_ring_list.h.

Field Documentation

listNode

GblDoublyLinkedListNode GblRingList::listNode

< Unionization of linked list node pointers, so they can be referred to generically or strongly-typed.

Linked list node as a generic GblDoublyLinkedListNode type.

Definition at line 124 of file gimbal_ring_list.h.

pNext

struct GblRingList* GblRingList::pNext

Points to next node within the list (or wraps back to first node, if list tail).

Definition at line 126 of file gimbal_ring_list.h.

pPrev

struct GblRingList* GblRingList::pPrev

Points to previous node within the list (or wraps back to last, if list head)

Definition at line 127 of file gimbal_ring_list.h.

[struct]

struct { ... } GblRingList::ringNode

Linked list node as strongly-typed GblRingList pointers.

size

uintptr_t GblRingList::size

< Unionization between payload data types for the list head and list nodes.

List head contains the total number of nodes within the list.

Definition at line 131 of file gimbal_ring_list.h.

pData

void* GblRingList::pData

List entries contain void* pointers to arbitrary data payloads.

Definition at line 132 of file gimbal_ring_list.h.

---

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

• gimbal_ring_list.h