24
24
#ifndef _DLINKLIST_H
25
25
#define _DLINKLIST_H
28
/* hook into the front of the list */
28
February 2010 - changed list format to have a prev pointer from the
29
list head. This makes DLIST_ADD_END() O(1) even though we only have
32
The scheme is as follows:
34
1) with no entries in the list:
37
2) with 1 entry in the list:
38
list_head->next == NULL
39
list_head->prev == list_head
41
3) with 2 entries in the list:
42
list_head->next == element2
43
list_head->prev == element2
44
element2->prev == list_head
45
element2->next == NULL
47
4) with N entries in the list:
48
list_head->next == element2
49
list_head->prev == elementN
50
elementN->prev == element{N-1}
51
elementN->next == NULL
53
This allows us to find the tail of the list by using
54
list_head->prev, which means we can add to the end of the list in
58
Note that the 'type' arguments below are no longer needed, but
59
are kept for now to prevent an incompatible argument change
64
add an element at the front of a list
29
66
#define DLIST_ADD(list, p) \
33
(p)->next = (p)->prev = NULL; \
69
(p)->prev = (list) = (p); \
72
(p)->prev = (list)->prev; \
35
73
(list)->prev = (p); \
36
74
(p)->next = (list); \
42
/* remove an element from a list - element doesn't have to be in list. */
80
remove an element from a list
81
Note that the element doesn't have to be in the list. If it
82
isn't then this is a no-op
43
84
#define DLIST_REMOVE(list, p) \
45
86
if ((p) == (list)) { \
87
if ((p)->next) (p)->next->prev = (p)->prev; \
46
88
(list) = (p)->next; \
47
if (list) (list)->prev = NULL; \
89
} else if ((list) && (p) == (list)->prev) { \
90
(p)->prev->next = NULL; \
91
(list)->prev = (p)->prev; \
49
93
if ((p)->prev) (p)->prev->next = (p)->next; \
50
94
if ((p)->next) (p)->next->prev = (p)->prev; \
52
if ((p) != (list)) (p)->next = (p)->prev = NULL; \
55
/* promote an element to the top of the list */
56
#define DLIST_PROMOTE(list, p) \
58
DLIST_REMOVE(list, p); \
62
/* hook into the end of the list - needs a tmp pointer */
63
#define DLIST_ADD_END(list, p, type) \
67
(p)->next = (p)->prev = NULL; \
70
for (tmp = (list); tmp->next; tmp = tmp->next) ; \
96
if ((p) != (list)) (p)->next = (p)->prev = NULL; \
100
find the head of the list given any element in it.
101
Note that this costs O(N), so you should avoid this macro
104
#define DLIST_HEAD(p, result_head) \
106
(result_head) = (p); \
107
while (DLIST_PREV(result_head)) (result_head) = (result_head)->prev; \
110
/* return the last element in the list */
111
#define DLIST_TAIL(list) ((list)?(list)->prev:NULL)
113
/* return the previous element in the list. */
114
#define DLIST_PREV(p) (((p)->prev && (p)->prev->next != NULL)?(p)->prev:NULL)
77
116
/* insert 'p' after the given element 'el' in a list. If el is NULL then
78
117
this is the same as a DLIST_ADD() */
81
120
if (!(list) || !(el)) { \
82
121
DLIST_ADD(list, p); \
87
if (p->next) p->next->prev = p; \
124
(p)->next = (el)->next; \
126
if ((p)->next) (p)->next->prev = (p); \
127
if ((list)->prev == (el)) (list)->prev = (p); \
91
/* demote an element to the end of the list, needs a tmp pointer */
92
#define DLIST_DEMOTE(list, p, tmp) \
94
DLIST_REMOVE(list, p); \
95
DLIST_ADD_END(list, p, tmp); \
98
/* concatenate two lists - putting all elements of the 2nd list at the
99
end of the first list */
100
#define DLIST_CONCATENATE(list1, list2, type) \
106
for (tmp = (list1); tmp->next; tmp = tmp->next) ; \
107
tmp->next = (list2); \
109
(list2)->prev = tmp; \
133
add to the end of a list.
134
Note that 'type' is ignored
136
#define DLIST_ADD_END(list, p, type) \
139
DLIST_ADD(list, p); \
141
DLIST_ADD_AFTER(list, p, (list)->prev); \
145
/* promote an element to the from of a list */
146
#define DLIST_PROMOTE(list, p) \
148
DLIST_REMOVE(list, p); \
149
DLIST_ADD(list, p); \
153
demote an element to the end of a list.
154
Note that 'type' is ignored
156
#define DLIST_DEMOTE(list, p, type) \
158
DLIST_REMOVE(list, p); \
159
DLIST_ADD_END(list, p, NULL); \
163
concatenate two lists - putting all elements of the 2nd list at the
164
end of the first list.
165
Note that 'type' is ignored
167
#define DLIST_CONCATENATE(list1, list2, type) \
172
(list1)->prev->next = (list2); \
174
void *_tmplist = (void *)(list1)->prev; \
175
(list1)->prev = (list2)->prev; \
176
(list2)->prev = _tmplist; \
114
181
#endif /* _DLINKLIST_H */