1#pragma once
2
3#include <stdbool.h>
4#include <stdint.h>
5#include <assert.h>
6#include <stdlib.h>
7#include <string.h>
8
9#define FF_LIST_DEFAULT_ALLOC 16
10
11typedef struct FFlist {
12 uint8_t* data;
13 uint32_t length;
14 uint32_t capacity;
15} FFlist;
16
17// Removes the first element, and copy its value to `*result`
18// `result` is only written when the list is not empty, so it may be null for an empty list
19[[gnu::nonnull(1), nodiscard]] bool ffListShift(FFlist* list, uint32_t elementSize, void* __restrict result);
20// Removes the last element, and copy its value to `*result`
21[[gnu::nonnull(1), nodiscard]] bool ffListPop(FFlist* list, uint32_t elementSize, void* __restrict result);
22
23[[gnu::nonnull(1)]] static inline void ffListInit(FFlist* list) {
24 list->capacity = 0;
25 list->length = 0;
26 list->data = nullptr;
27}
28
29[[gnu::nonnull(1)]] static inline void ffListInitA(FFlist* list, uint32_t elementSize, uint32_t capacity) {
30 ffListInit(list);
31 list->capacity = capacity;
32 list->data = __builtin_expect(capacity == 0, 0) ? nullptr : (uint8_t*) malloc((size_t) capacity * elementSize);
33}
34
35[[nodiscard]] static inline FFlist ffListCreate() {
36 FFlist result;
37 ffListInit(&result);
38 return result;
39}
40
41[[nodiscard]] static inline FFlist ffListCreateA(uint32_t elementSize, uint32_t capacity) {
42 FFlist result;
43 ffListInitA(&result, elementSize, capacity);
44 return result;
45}
46
47[[gnu::nonnull(1), gnu::pure, nodiscard]] static inline void* ffListGet(const FFlist* list, uint32_t elementSize, uint32_t index) {
48 assert(list->capacity > index);
49 return list->data + (index * elementSize);
50}
51
52// Not `pure`: `compFunc` is caller-supplied and may have side effects
53[[gnu::nonnull(1, 3, 4), nodiscard]] static inline uint32_t ffListFirstIndexComp(const FFlist* list, uint32_t elementSize, void* compElement, bool (*compFunc)(const void*, const void*)) {
54 for (uint32_t i = 0; i < list->length; i++) {
55 if (compFunc(ffListGet(list, elementSize, i), compElement)) {
56 return i;
57 }
58 }
59
60 return list->length;
61}
62
63// Not `pure`, same reason as ffListFirstIndexComp
64[[gnu::nonnull(1, 3, 4), nodiscard]] static inline bool ffListContains(const FFlist* list, uint32_t elementSize, void* compElement, bool (*compFunc)(const void*, const void*)) {
65 return ffListFirstIndexComp(list, elementSize, compElement, compFunc) != list->length;
66}
67
68[[gnu::nonnull(1, 3)]] static inline void ffListSort(FFlist* list, uint32_t elementSize, int (*compar)(const void*, const void*)) {
69 qsort(list->data, list->length, elementSize, compar);
70}
71
72// Move the contents of `src` into `list`, and left `src` empty
73[[gnu::nonnull(1)]] static inline void ffListInitMove(FFlist* list, FFlist* src) {
74 if (src) {
75 list->capacity = src->capacity;
76 list->length = src->length;
77 list->data = src->data;
78 ffListInit(src);
79 } else {
80 ffListInit(list);
81 }
82}
83
84[[gnu::nonnull(1)]] static inline void ffListDestroy(FFlist* list) {
85 if (!list->data) {
86 return;
87 }
88
89 // Avoid free-after-use. These 3 assignments are cheap so don't remove them
90 list->capacity = list->length = 0;
91 free(list->data);
92 list->data = nullptr;
93}
94
95[[gnu::nonnull(1)]] static inline void ffListClear(FFlist* list) {
96 list->length = 0;
97}
98
99[[gnu::nonnull(1)]] static inline void ffListReserve(FFlist* list, uint32_t elementSize, uint32_t newCapacity) {
100 if (__builtin_expect(newCapacity <= list->capacity, false)) {
101 return;
102 }
103
104 list->data = (uint8_t*) realloc(list->data, (size_t) newCapacity * elementSize);
105 list->capacity = newCapacity;
106}
107
108[[gnu::nonnull(1)]] static inline void* ffListAdd(FFlist* list, uint32_t elementSize) {
109 if (__builtin_expect(list->length == list->capacity, false)) {
110 ffListReserve(list, elementSize, list->capacity == 0 ? FF_LIST_DEFAULT_ALLOC : list->capacity * 2);
111 }
112
113 ++list->length;
114 return ffListGet(list, elementSize, list->length - 1);
115}
116
117[[gnu::nonnull(1)]] static inline void ffListRemoveAt(FFlist* list, uint32_t elementSize, uint32_t index) {
118 assert(list->length > index);
119 memmove(list->data + (index * elementSize), list->data + ((index + 1) * elementSize), (size_t) (list->length - index - 1) * elementSize);
120 --list->length;
121}
122
123[[gnu::nonnull(1, 4)]] static inline void ffListInsertAt(FFlist* list, uint32_t elementSize, uint32_t index, const void* element) {
124 assert(list->length >= index);
125 ffListAdd(list, elementSize);
126 memmove(list->data + ((index + 1) * elementSize), list->data + (index * elementSize), (size_t) (list->length - index - 1) * elementSize);
127 memcpy(list->data + (index * elementSize), element, elementSize);
128}
129
130#define FF_LIST_FOR_EACH(itemType, itemVarName, listVar) \
131 for (itemType* itemVarName = (itemType*) (listVar).data; \
132 itemVarName - (itemType*) (listVar).data < (intptr_t) (listVar).length; \
133 ++itemVarName)
134
135#define FF_LIST_AUTO_DESTROY [[gnu::cleanup(ffListDestroy)]] FFlist
136
137#define FF_LIST_GET(itemType, listVar, index) \
138 ({ \
139 assert((listVar).capacity > (index)); \
140 (itemType*) (listVar).data + (index); \
141 })
142
143#define FF_LIST_ADD(itemType, listVar) (itemType*) ffListAdd(&(listVar), (uint32_t) sizeof(itemType))
144
145#define FF_LIST_REMOVE_AT(itemType, listVar, index) \
146 ffListRemoveAt(&(listVar), (uint32_t) sizeof(itemType), (index))
147
148#define FF_LIST_INSERT_AT(itemType, listVar, index, pElement) \
149 ffListInsertAt(&(listVar), (uint32_t) sizeof(itemType), (index), (pElement))
150
151#define FF_LIST_FIRST(itemType, listVar) FF_LIST_GET(itemType, listVar, 0)
152#define FF_LIST_LAST(itemType, listVar) \
153 ({ \
154 assert((listVar).length > 0); \
155 FF_LIST_GET(itemType, listVar, ((listVar).length - 1)); \
156 })
157
158#define FF_LIST_CONTAINS(listVar, pCompElement, compFunc) \
159 ({ \
160 typedef typeof(*(pCompElement)) compElementType; \
161 typedef bool compFuncType(const compElementType*, const compElementType*); \
162 static_assert(__builtin_types_compatible_p(typeof(compFunc), compFuncType), "Incompatible callback function"); \
163 ffListContains(&(listVar), (uint32_t) sizeof(*(pCompElement)), (pCompElement), (bool (*)(const void*, const void*)) compFunc); \
164 })
165
166#define FF_LIST_SHIFT(listVar, pResult) \
167 ffListShift(&(listVar), (uint32_t) sizeof(*(pResult)), (pResult))
168#define FF_LIST_POP(listVar, pResult) \
169 ffListPop(&(listVar), (uint32_t) sizeof(*(pResult)), (pResult))