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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
// Copyright © Tavian Barnes <tavianator@tavianator.com>
// SPDX-License-Identifier: 0BSD
/**
* Intrusive linked lists.
*/
#ifndef BFS_LIST_H
#define BFS_LIST_H
#include "config.h"
#include <stdbool.h>
/**
* A singly-linked list entry.
*/
struct slink {
struct slink *next;
};
/** Initialize a list entry. */
void slink_init(struct slink *link);
/**
* A singly-linked list.
*/
struct slist {
struct slink *head;
struct slink **tail;
};
/** Initialize an empty list. */
void slist_init(struct slist *list);
/** Check if a list is empty. */
bool slist_is_empty(const struct slist *list);
/** Add an entry at the tail of the list. */
void slist_append(struct slist *list, struct slink *link);
/** Add an entry at the head of the list. */
void slist_prepend(struct slist *list, struct slink *link);
/** Add an entire list at the tail of the list. */
void slist_extend(struct slist *dest, struct slist *src);
/** Remove the head of the list. */
struct slink *slist_pop(struct slist *list);
/**
* Comparison function type for slist_sort().
*
* @param left
* The left-hand side of the comparison.
* @param right
* The right-hand side of the comparison.
* @param ptr
* An arbitrary pointer passed to slist_sort().
* @return
* Whether left <= right.
*/
typedef bool slist_cmp_fn(struct slink *left, struct slink *right, const void *ptr);
/** Sort a list. */
void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr);
/**
* A doubly-linked list entry.
*/
struct link {
struct link *prev;
struct link *next;
};
/** Initialize a list entry. */
void link_init(struct link *link);
/**
* A doubly-linked list.
*/
struct list {
struct link *head;
struct link *tail;
};
/** Initialize an empty list. */
void list_init(struct list *list);
/** Check if a list is empty. */
bool list_is_empty(const struct list *list);
/** Add an entry at the tail of the list. */
void list_append(struct list *list, struct link *link);
/** Add an entry at the head of the list. */
void list_prepend(struct list *list, struct link *link);
/** Insert an entry after the target entry. */
void list_insert_after(struct list *list, struct link *target, struct link *link);
/** Remove an entry from a list. */
void list_remove(struct list *list, struct link *link);
/** Remove the head of the list. */
struct link *list_pop(struct list *list);
/** Check if a link is attached to a list. */
bool list_attached(const struct list *list, const struct link *link);
// Helper for LIST_FOR_EACH_*()
#define LIST_FOR_EACH_IMPL(entry, type, i, member, ...) \
for (type *_next, *i = BFS_CONTAINER_OF(entry, type, member); \
i && (_next = BFS_CONTAINER_OF(i->member.next, type, member), true); \
i = _next)
/**
* Iterate over a list from the given entry.
*
* @param entry
* The entry to start from.
* @param type
* The type of the list entries.
* @param i
* The name of the loop variable, declared as type *i.
* @param member
* The name of the list link field (default: link).
*/
#define LIST_FOR_EACH_FROM(...) \
LIST_FOR_EACH_IMPL(__VA_ARGS__, link,)
/**
* Iterate over a list.
*
* @param list
* The list to iterate over.
* @param type
* The type of the list entries.
* @param i
* The name of the loop variable, declared as type *i.
* @param member
* The name of the list link field (default: link).
*/
#define LIST_FOR_EACH(list, ...) \
LIST_FOR_EACH_FROM((list)->head, __VA_ARGS__)
// Pop from a list or slist
#define LIST_POP(l) _Generic((l), \
struct list *: list_pop((struct list *)l), \
struct slist *: slist_pop((struct slist *)l))
// Helper for LIST_DRAIN()
#define LIST_DRAIN_IMPL(list, type, i, member, ...) \
for (type *i; (i = BFS_CONTAINER_OF(LIST_POP(list), type, member));)
/**
* Drain the entries from a list.
*
* @param list
* The list to drain.
* @param type
* The type of the list entries.
* @param i
* The name of the loop variable, declared as type *i.
* @param member
* The name of the list link field (default: link).
*/
#define LIST_DRAIN(...) \
LIST_DRAIN_IMPL(__VA_ARGS__, link,)
#endif // BFS_LIST_H
|
