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
|
/*
* Copyright (C) 2019 - Vito Caputo - <vcaputo@pengaru.com>
*
* This program is free software: you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 3 as published
* by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/* (circular) Doubly-Linked List header */
/* I've been using the Linux kernel's list.h for ages, so it definitely
* takes some inspiration from that API.
*/
#ifndef _DLL_H
#define _DLL_H
#include <stddef.h> /* offsetof() */
typedef struct dll_t dll_t;
struct dll_t {
dll_t *next, *previous;
};
/* This is analagous to container_of */
#define DLL_ENTRY(_ptr, _type, _member) \
(_type *)((char *)(_ptr) - offsetof(_type, _member))
/* Declare and initialize an empty list named _name */
#define DLL_INIT(_name) \
dll_t _name = { .next = &_name, .previous = &_name }
/* Iterate list */
#define DLL_FOR_EACH(_head, _node) \
for ( (_node) = (_head)->next; \
(_node) != (_head); \
(_node) = (_node)->next \
)
/* Iterate list in a removal-safe fashion */
#define DLL_FOR_EACH_SAFE(_head, _node, _next) \
for ( (_node) = (_head)->next, (_next) = (_node)->next; \
(_node) != (_head); \
(_node) = (_next), (_next) = (_next->next) \
)
/* Iterate list as containers */
#define DLL_FOR_EACH_ENTRY(_head, _entry, _type, _member) \
for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member); \
&(_entry)->_member != (_head); \
(_entry) = DLL_ENTRY((_entry)->_member.next, _type, _member) \
)
/* Iterate list as containers in a removal-safe fashion */
#define DLL_FOR_EACH_ENTRY_SAFE(_head, _entry, _next, _type, _member) \
for ( (_entry) = DLL_ENTRY((_head)->next, _type, _member), \
(_next) = DLL_ENTRY((_entry)->_member.next, _type, _member); \
&(_entry)->_member != (_head); \
(_entry) = (_next), \
(_next) = DLL_ENTRY((_next)->_member.next, _type, _member) \
)
/* Initialize node to an empty list state,
* node is returned for convenience.
*/
static inline dll_t * dll_init(dll_t *node)
{
return node->next = node->previous = node;
}
/* Delete node from the list it belongs to,
* node is returned for convenience.
*/
static inline dll_t * dll_del(dll_t *node)
{
node->next->previous = node->previous;
node->previous->next = node->next;
return dll_init(node);
}
/* Insert node immediately before where,
* node is returned for convenience.
*/
static inline dll_t * dll_add_pre(dll_t *where, dll_t *node)
{
node->next = where;
node->previous = where->previous;
where->previous->next = node;
where->previous = node;
return node;
}
/* Insert node immediately after where,
* node is returned for convenience.
*/
static inline dll_t * dll_add_post(dll_t *where, dll_t *node)
{
node->next = where->next;
node->previous = where;
where->next->previous = node;
where->next = node;
return node;
}
static inline int dll_empty(dll_t *dll)
{
return (dll->next == dll && dll->next == dll->previous);
}
#endif
|
