libGimbal 0.1.0
C17-Based Extended Standard Library and Cross-Language Runtime Framework
Loading...
Searching...
No Matches
gimbal_doubly_linked_list.h
Go to the documentation of this file.
1/*! \file
2 * \brief GblDoublyLinkedListNode structure and related functions
3 * \ingroup containers
4 * \copydoc GblDoublyLinkedListNode
5 * \todo
6 * - epic BSD-style for loop macros
7 *
8 * \author Falco Girgis
9 */
10
11#ifndef GIMBAL_DOUBLY_LINKED_LIST_HPP
12#define GIMBAL_DOUBLY_LINKED_LIST_HPP
13
14#include "gimbal_linked_list.h"
15
16#define GBL_SELF_TYPE GblDoublyLinkedListNode
17
18#define GBL_DOUBLY_LINKED_LIST_NPOS GBL_NPOS
19#define GBL_DOUBLY_LINKED_LIST_NODE_INITIALIZER() { .pNext = NULL, .pPrev = NULL }
20#define GBL_DOUBLY_LINKED_LIST_NODE(name) GblDoublyLinkedListNode name = { .pNext = &name, .pPrev = &name }
21#define GBL_DOUBLY_LINKED_LIST_ENTRY(node, structure, field) GBL_CONTAINER_OF(node, structure, field)
22
23GBL_DECLS_BEGIN
24
25typedef GblLinkedListCmpFn GblDoublyLinkedListCmpFn;
26
27/*! Intrustive doubly linked list structure with vector-style API.
28 * \ingroup containers
29 *
30 * GblDoublyLinkedListNode is the low-level API around managing manually
31 * allocated, intrusive linked list structures with the list nodes
32 * embedded within their containing structures.
33 *
34 * Operation |Time Complexity
35 * ----------------------------------|------------------
36 * iteration | O(N)
37 * insertion/removal (middle) | O(N)
38 * insertion/removal (front or back) | O(1)
39 * access (front or back) | O(1)
40 * random access (middle) | O(N)
41 *
42 * \note
43 * For more a more user-friendly, high-level, abstract,
44 * non-intrusive circularly linked list structure which can be
45 * filled with arbitrary data and whose allocations are managed
46 * automatically, see the GblRingList API, built upon this one.
47 *
48 * \sa GblRingList
49 */
50typedef struct GblDoublyLinkedListNode { // Size (32-bit / 64-bit)
51 union {
52 struct GblDoublyLinkedListNode* pNext; // 4/8 bytes
53 GblLinkedListNode singleNode;
54 };
55 struct GblDoublyLinkedListNode* pPrev; // 4/8 bytes
56} GblDoublyLinkedListNode; // 8/16 total
57
58GBL_EXPORT void GblDoublyLinkedList_init (GBL_SELF) GBL_NOEXCEPT;
59GBL_EXPORT void GblDoublyLinkedList_move (GBL_SELF, GBL_SELF_TYPE* pHead) GBL_NOEXCEPT;
60
61GBL_EXPORT GblBool GblDoublyLinkedList_empty (GBL_CSELF) GBL_NOEXCEPT;
62GBL_EXPORT size_t GblDoublyLinkedList_count (GBL_CSELF) GBL_NOEXCEPT;
63
64GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_at (GBL_CSELF, intptr_t index) GBL_NOEXCEPT;
65GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_front (GBL_CSELF) GBL_NOEXCEPT;
66GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_back (GBL_CSELF) GBL_NOEXCEPT;
67GBL_EXPORT GblBool GblDoublyLinkedList_contains (GBL_CSELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
68GBL_EXPORT size_t GblDoublyLinkedList_find (GBL_CSELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
69GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_middle (GBL_CSELF) GBL_NOEXCEPT;
70GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_beforeMiddle (GBL_CSELF) GBL_NOEXCEPT;
71
72GBL_EXPORT void GblDoublyLinkedList_pushBack (GBL_SELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
73GBL_EXPORT void GblDoublyLinkedList_pushFront (GBL_SELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
74GBL_EXPORT void GblDoublyLinkedList_moveBack (GBL_SELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
75GBL_EXPORT void GblDoublyLinkedList_moveFront (GBL_SELF, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
76GBL_EXPORT GblBool GblDoublyLinkedList_join (GBL_SELF, intptr_t idx, GBL_SELF_TYPE* pList) GBL_NOEXCEPT;
77GBL_EXPORT void GblDoublyLinkedList_joinBack (GBL_SELF, GBL_SELF_TYPE* pList) GBL_NOEXCEPT;
78GBL_EXPORT void GblDoublyLinkedList_joinFront (GBL_SELF, GBL_SELF_TYPE* pList) GBL_NOEXCEPT;
79GBL_EXPORT void GblDoublyLinkedList_joinSorted (GBL_SELF,
80 GBL_SELF_TYPE* pList,
81 GblDoublyLinkedListCmpFn pCmpFn,
82 void* pClosure) GBL_NOEXCEPT;
83
84GBL_EXPORT GblBool GblDoublyLinkedList_insert (GBL_SELF, intptr_t idx, GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
85GBL_EXPORT void GblDoublyLinkedList_insertBefore (GBL_SELF_TYPE* pNode1, GBL_SELF_TYPE* pNode2) GBL_NOEXCEPT;
86GBL_EXPORT void GblDoublyLinkedList_insertAfter (GBL_SELF_TYPE* pNode1, GBL_SELF_TYPE* pNode2) GBL_NOEXCEPT;
87
88GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_popBack (GBL_SELF) GBL_NOEXCEPT;
89GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_popFront (GBL_SELF) GBL_NOEXCEPT;
90
91GBL_EXPORT GblBool GblDoublyLinkedList_swap (GBL_SELF_TYPE* pNode1, GBL_SELF_TYPE* pNode2) GBL_NOEXCEPT;
92GBL_EXPORT void GblDoublyLinkedList_remove (GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
93GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_removeBefore (GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
94GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_removeAfter (GBL_SELF_TYPE* pNode) GBL_NOEXCEPT;
95GBL_EXPORT GblBool GblDoublyLinkedList_replace (GBL_SELF_TYPE* pNode1, GBL_SELF_TYPE* pNode2) GBL_NOEXCEPT;
96GBL_EXPORT void GblDoublyLinkedList_splitAfter (GBL_SELF,
97 GBL_SELF_TYPE* pHead2,
98 GBL_SELF_TYPE* pAfter) GBL_NOEXCEPT;
99
100GBL_EXPORT GBL_SELF_TYPE* GblDoublyLinkedList_erase (GBL_SELF, intptr_t index) GBL_NOEXCEPT;
101GBL_EXPORT void GblDoublyLinkedList_clear (GBL_SELF) GBL_NOEXCEPT;
102
103GBL_EXPORT void GblDoublyLinkedList_mergeSort (GBL_SELF,
104 GblDoublyLinkedListCmpFn pCmpFn,
105 void* pClosure) GBL_NOEXCEPT;
106
107GBL_EXPORT void GblDoublyLinkedList_rotate (GBL_SELF, intptr_t n) GBL_NOEXCEPT;
108GBL_EXPORT void GblDoublyLinkedList_reverse (GBL_SELF) GBL_NOEXCEPT;
109
110GBL_DECLS_END
111
112#undef GBL_SELF_TYPE
113
114#endif // GIMBAL_DOUBLY_LINKED_LIST_HPP
GBL_NOEXCEPT
#define GBL_NOEXCEPT
Definition gimbal_compiler.h:264
GBL_DECLS_BEGIN
#define GBL_DECLS_BEGIN
Definition gimbal_decls.h:23
GBL_EXPORT
#define GBL_EXPORT
Definition gimbal_decls.h:232
GBL_CONTAINER_OF
#define GBL_CONTAINER_OF(ptr, type, member)
Definition gimbal_macro_utils.h:34
GBL_SELF_TYPE
#define GBL_SELF_TYPE
Definition gimbal_md5.h:22
GblBool
uint8_t GblBool
Basic boolean type, standardized to sizeof(char)
Definition gimbal_typedefs.h:20
GBL_NPOS
#define GBL_NPOS
Definition gimbal_typedefs.h:16
GblDoublyLinkedListNode
Intrustive doubly linked list structure with vector-style API.
Definition gimbal_doubly_linked_list.h:50