forked from sysprog21/lab0-c
-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.h
435 lines (391 loc) · 13.8 KB
/
list.h
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
/* Linux-like doubly-linked list implementation */
#pragma once
#ifdef __cplusplus
extern "C" {
#endif
#include <stddef.h>
/* "typeof" is a GNU extension.
* Reference: https://gcc.gnu.org/onlinedocs/gcc/Typeof.html
*/
#if defined(__GNUC__)
#define __LIST_HAVE_TYPEOF 1
#endif
/**
* struct list_head - Head and node of a doubly-linked list
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
*
* The simple doubly-linked list consists of a head and nodes attached to
* this head. Both node and head share the same struct type. The list_*
* functions and macros can be used to access and modify this data structure.
*
* The @prev pointer of the list head points to the last list node of the
* list and @next points to the first list node of the list. For an empty list,
* both member variables point to the head.
*
* The list nodes are usually embedded in a container structure which holds the
* actual data. Such an container object is called entry. The helper list_entry
* can be used to calculate the object address from the address of the node.
*/
struct list_head {
struct list_head *prev;
struct list_head *next;
};
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
/**
* LIST_HEAD - Declare list head and initialize it
* @head: name of the new object
*/
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
/**
* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*
* This can also be used to initialize a unlinked list node.
*
* A node is usually linked inside a list, will be added to a list in
* the near future or the entry containing the node will be free'd soon.
*
* But an unlinked node may be given to a function which uses list_del(_init)
* before it ends up in a previously mentioned state. The list_del(_init) on an
* initialized node is well defined and safe. But the result of a
* list_del(_init) on an uninitialized node is undefined (unrelated memory is
* modified, crashes, ...).
*/
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
/**
* list_add() - Add a list node to the beginning of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
/**
* list_add_tail() - Add a list node to the end of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*
* The node is only removed from the list. Neither the memory of the removed
* node nor the memory of the entry containing the node is free'd. The node
* has to be handled like an uninitialized node. Accessing the next or prev
* pointer of the node is not safe.
*
* Unlinked, initialized nodes are also uninitialized after list_del.
*
* LIST_POISONING can be enabled during build-time to provoke an invalid memory
* access when the memory behind the next/prev pointer is used after a list_del.
* This only works on systems which prohibit access to the predefined memory
* addresses.
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
/**
* list_del_init() - Remove a list node from the list and reinitialize it
* @node: pointer to the node
*
* The removed node will not end up in an uninitialized state like when using
* list_del. Instead the node is initialized again to the unlinked state.
*/
static inline void list_del_init(struct list_head *node)
{
list_del(node);
INIT_LIST_HEAD(node);
}
/**
* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*
* Return: 0 - list is not empty !0 - list is empty
*/
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
/**
* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*
* Return: 0 - list is not singular !0 -list has exactly one entry
*/
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
/**
* list_splice() - Add list nodes from a list to beginning of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*
* All nodes from @list are added to to the beginning of the list of @head.
* It is similar to list_add but for multiple nodes. The @list head is not
* modified and has to be initialized to be used as a valid list head/node
* again.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *head_first = head->next;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->next = list_first;
list_first->prev = head;
list_last->next = head_first;
head_first->prev = list_last;
}
/**
* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*
* All nodes from @list are added to to the end of the list of @head.
* It is similar to list_add_tail but for multiple nodes. The @list head is not
* modified and has to be initialized to be used as a valid list head/node
* again.
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
/**
* list_splice_init() - Move list nodes from a list to beginning of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*
* All nodes from @list are added to to the beginning of the list of @head.
* It is similar to list_add but for multiple nodes.
*
* The @list head will not end up in an uninitialized state like when using
* list_splice. Instead the @list is initialized again to the an empty
* list/unlinked state.
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
list_splice(list, head);
INIT_LIST_HEAD(list);
}
/**
* list_splice_tail_init() - Move list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*
* All nodes from @list are added to to the end of the list of @head.
* It is similar to list_add_tail but for multiple nodes.
*
* The @list head will not end up in an uninitialized state like when using
* list_splice. Instead the @list is initialized again to the an empty
* list/unlinked state.
*/
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
{
list_splice_tail(list, head);
INIT_LIST_HEAD(list);
}
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*
* All entries from the beginning of the list @head_from to (including) the
* @node is moved to @head_to.
*
* @head_to is replaced when @head_from is not empty. @node must be a real
* list node from @head_from or the behavior is undefined.
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
/**
* list_move() - Move a list node to the beginning of the list
* @node: pointer to the node
* @head: pointer to the head of the list
*
* The @node is removed from its old position/node and add to the beginning of
* @head
*/
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
/**
* list_move_tail() - Move a list node to the end of the list
* @node: pointer to the node
* @head: pointer to the head of the list
*
* The @node is removed from its old position/node and add to the end of @head
*/
static inline void list_move_tail(struct list_head *node,
struct list_head *head)
{
list_del(node);
list_add_tail(node, head);
}
/**
* list_entry() - Calculate address of entry that contains list node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of entry containing node
*/
#define list_entry(node, type, member) container_of(node, type, member)
/**
* list_first_entry() - get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of first entry in list
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
/**
* list_last_entry() - get last entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of last entry in list
*/
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
/**
* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*
* The nodes and the head of the list must be kept unmodified while
* iterating through it. Any modifications to the the list will cause undefined
* behavior.
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
/**
* list_for_each_entry - iterate over list entries
* @entry: pointer used as iterator
* @head: pointer to the head of the list
* @member: name of the list_head member variable in struct type of @entry
*
* The nodes and the head of the list must be kept unmodified while
* iterating through it. Any modifications to the the list will cause undefined
* behavior.
*
* FIXME: remove dependency of __typeof__ extension
*/
#ifdef __LIST_HAVE_TYPEOF
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
#endif
/**
* list_for_each_safe - iterate over list nodes and allow deletes
* @node: list_head pointer used as iterator
* @safe: list_head pointer used to store info for next entry in list
* @head: pointer to the head of the list
*
* The current node (iterator) is allowed to be removed from the list. Any
* other modifications to the the list will cause undefined behavior.
*/
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
/**
* list_for_each_entry_safe - iterate over list entries and allow deletes
* @entry: pointer used as iterator
* @safe: @type pointer used to store info for next entry in list
* @head: pointer to the head of the list
* @member: name of the list_head member variable in struct type of @entry
*
* The current node (iterator) is allowed to be removed from the list. Any
* other modifications to the the list will cause undefined behavior.
*
* FIXME: remove dependency of __typeof__ extension
*/
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
#undef __LIST_HAVE_TYPEOF
#ifdef __cplusplus
}
#endif