aboutsummaryrefslogtreecommitdiff
path: root/list/include/list.h
diff options
context:
space:
mode:
Diffstat (limited to 'list/include/list.h')
-rw-r--r--list/include/list.h118
1 files changed, 104 insertions, 14 deletions
diff --git a/list/include/list.h b/list/include/list.h
index 945de28..facf820 100644
--- a/list/include/list.h
+++ b/list/include/list.h
@@ -1,21 +1,111 @@
1/// A doubly linked list. 1/// Doubly-linked list.
2///
3/// This list does not hold user data. Instead, the list can be used as an
4/// intrusive list or as part as a more complex data structure.
5#pragma once 2#pragma once
6 3
4#include <assert.h>
7#include <stddef.h> 5#include <stddef.h>
6#include <stdlib.h>
7
8#define DEF_LIST(type) \
9 typedef struct type##_node { \
10 type val; \
11 struct type##_node* prev; \
12 struct type##_node* next; \
13 } type##_node; \
14 typedef struct type##_list { \
15 type##_node* head; \
16 } type##_list;
17
18static inline void* alloc(size_t size) {
19 void* ptr = calloc(1, size);
20 assert(ptr);
21 return ptr;
22}
23
24/// Create a new empty list.
25#define make_list(type) \
26 (type##_list) { 0 }
27
28/// Delete the list.
29#define del_list(list) \
30 for (__typeof__(list.head) node = list.head; node;) { \
31 __typeof__(node) cur = node; \
32 node = node->next; \
33 free(cur); \
34 } \
35 list.head = 0;
8 36
9typedef struct list list; 37/// Prepend a value to the list.
38#define list_push(list, value) \
39 { \
40 __typeof__(list.head) node = alloc(sizeof(*list.head)); \
41 node->val = value; \
42 node->next = list.head; \
43 if (list.head) { \
44 list.head->prev = node; \
45 } \
46 list.head = node; \
47 }
10 48
11typedef struct list { 49/// Delete the first occurrence of the value from the list.
12 list* prev; 50#define list_remove(list, search_value) \
13 list* next; 51 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
14} list; 52 if (iter->val == (search_value)) { \
53 del_node(list, iter); \
54 break; \
55 } \
56 }
15 57
16/// Create a new list from an array of `size` items. 58/// Delete the node that contains the value at the given address from the
17void list_make(list* list, size_t size); 59/// list.
60#define list_remove_ptr(list, value_ptr) \
61 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
62 if (&iter->val == value_ptr) { \
63 del_node(list, iter); \
64 break; \
65 } \
66 }
18 67
19/// Iterates over all the items in the list. 68/// Delete the list node.
20#define list_foreach(LIST, iter) \ 69#define del_node(list, node) \
21 for (struct list* iter = LIST; iter; iter = iter->next) 70 { \
71 assert(node); \
72 if (node->prev) { \
73 node->prev->next = node->next; \
74 } \
75 if (node->next) { \
76 node->next->prev = node->prev; \
77 } \
78 if (list.head == node) { \
79 list.head = 0; \
80 } \
81 free(node); \
82 node = 0; \
83 }
84
85/// Iterate over all the items in the list.
86///
87/// Use 'value' to refer to the address of the current node's value during
88/// iteration.
89#define list_foreach(list, body) \
90 { \
91 __typeof__(list.head) node = list.head; \
92 while (node) { \
93 const __typeof__(node->val)* value = &node->val; \
94 body; \
95 node = node->next; \
96 } \
97 }
98
99/// Iterate over all the items in the list.
100///
101/// Use 'value' to refer to the address of the current node's value during
102/// iteration.
103#define list_foreach_mut(list, body) \
104 { \
105 __typeof__(list.head) node = list.head; \
106 while (node) { \
107 __typeof__(node->val)* value = &node->val; \
108 body; \
109 node = node->next; \
110 } \
111 }