1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/// Doubly-linked list.
#pragma once
#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#define DEF_LIST(name, type) \
typedef struct name##_node { \
type val; \
struct name##_node* prev; \
struct name##_node* next; \
} name##_node; \
typedef struct name##_list { \
name##_node* head; \
} name##_list;
static inline void* alloc(size_t size) {
void* ptr = calloc(1, size);
assert(ptr);
return ptr;
}
/// Create a new empty list.
#define make_list(type) \
(type##_list) { nullptr }
/// Delete the list.
#define del_list(list) \
for (__typeof__(list.head) node = list.head; node;) { \
__typeof__(node) cur = node; \
node = node->next; \
free(cur); \
} \
list.head = nullptr;
/// Whether the list is empty.
#define list_empty(list) (!list.head)
/// Prepend a value to the list.
#define list_add(list, value) \
{ \
__typeof__(list.head) node = alloc(sizeof(*list.head)); \
node->val = value; \
node->next = list.head; \
if (list.head) { \
list.head->prev = node; \
} \
list.head = node; \
}
/// Append a value to the list.
#define list_push(list, value) \
{ \
__typeof__(list.head) node = alloc(sizeof(*list.head)); \
node->val = value; \
node->next = 0; \
if (!list.head) { \
list.head = node; \
} else { \
__typeof__(list.head) next = list.head; \
while (next && next->next) { \
next = next->next; \
} \
next->next = node; \
} \
}
/// Delete the first occurrence of the value from the list.
#define list_remove(list, search_value) \
for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
if (iter->val == (search_value)) { \
del_node(list, iter); \
break; \
} \
}
/// Delete the node that contains the value at the given address from the
/// list.
#define list_remove_ptr(list, value_ptr) \
for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
if (&iter->val == value_ptr) { \
del_node(list, iter); \
break; \
} \
}
/// Delete the list node.
#define del_node(list, node) \
{ \
assert(node); \
if (node->prev) { \
node->prev->next = node->next; \
} \
if (node->next) { \
node->next->prev = node->prev; \
} \
if (list.head == node) { \
list.head = nullptr; \
} \
free(node); \
node = nullptr; \
}
/// Iterate over all the items in the list.
///
/// Use 'value' to refer to the address of the current node's value during
/// iteration.
#define list_foreach(list, value, body) \
{ \
__typeof__(list.head)* pNode = &list.head; \
while (*pNode) { \
__typeof__((*pNode)->val) value = (*pNode)->val; \
body; \
pNode = &(*pNode)->next; \
} \
}
/// Iterate over all the items in the list.
///
/// Use 'value' to refer to the address of the current node's value during
/// iteration.
#define list_foreach_mut(list, value, body) \
{ \
__typeof__(list.head) node = list.head; \
while (node) { \
__typeof__(node->val) value = node->val; \
body; \
node = node->next; \
} \
}
|
