1 #ifndef CADO_UTILS_DLLLIST_H
2 #define CADO_UTILS_DLLLIST_H
3
4 /* Need size_t */
5 #include <stddef.h>
6 #include <stdlib.h>
7 #include "macros.h"
8
9 #ifdef __cplusplus
10 extern "C" {
11 #endif
12
13 struct dllist_s {
14 void *data;
15 struct dllist_s *prev, *next;
16 };
17 typedef struct dllist_s dllist[1];
18 typedef struct dllist_s *dllist_ptr;
19
20 static inline void
dll_init(dllist node)21 dll_init(dllist node) {
22 node->data = node->prev = node->next = NULL;
23 }
24
25 /* Invariants:
26 A node has prev==NULL iff it is the head node.
27 A node has next==NULL iff it is the last node.
28 The head node has data==NULL. */
29
30 static inline int
dll_is_empty(dllist head)31 dll_is_empty(dllist head) {
32 return (head->next == NULL);
33 }
34
35 static inline void
dll_insert(dllist node,void * data)36 dll_insert(dllist node, void *data) {
37 dllist_ptr new_node = (dllist_ptr) malloc(sizeof(dllist));
38 ASSERT_ALWAYS(new_node != NULL);
39 new_node->prev = node;
40 new_node->next = node->next;
41 new_node->data = data;
42 node->next = new_node;
43 if (new_node->next != NULL)
44 new_node->next->prev = new_node;
45 }
46
47 static inline void
dll_append(dllist head,void * data)48 dll_append (dllist head, void *data) {
49 while (head->next != NULL)
50 head = head->next;
51 dll_insert(head, data);
52 }
53
54 static inline void
dll_delete(dllist node)55 dll_delete (dllist node) {
56 /* Can't delete head node */
57 ASSERT_ALWAYS(node->prev != NULL);
58 node->prev->next = node->next;
59 if (node->next != NULL)
60 node->next->prev = node->prev;
61 free(node);
62 }
63
64 static inline size_t
dll_length(dllist head)65 dll_length (dllist head) {
66 size_t len = 0;
67 while (head->next != NULL) {
68 head = head->next;
69 len ++;
70 }
71 return len;
72 }
73
74 /* Get the n-th node. Requires n < dll_length().
75 For n=0, returns the first node after head. */
76 static inline dllist_ptr
dll_get_nth(dllist head,size_t n)77 dll_get_nth (dllist head, size_t n) {
78 dllist_ptr node = head->next;
79 for (node = head->next; node != NULL && n != 0; n--, node = node->next);
80 ASSERT_ALWAYS(node != NULL);
81 return node;
82 }
83
84 static inline dllist_ptr
dll_find(dllist head,void * data)85 dll_find (dllist head, void *data) {
86 dllist_ptr next = head->next;
87
88 while (next != NULL) {
89 dllist_ptr node = next;
90 if (node->data == data)
91 break;
92 next = node->next;
93 }
94
95 return next;
96 }
97
98 #ifdef __cplusplus
99 }
100 #endif
101
102 #endif
103