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
|
#ifndef LINKLIST_H_INCLUDED
#define LINKLIST_H_INCLUDED
#include "inline.h"
struct list_head {
/*----------------------------------------------------------------------------
This is a header for an element of a doubly linked list, or an anchor
for such a list.
itemP == NULL means it's an anchor; otherwise it's a header.
Initialize a list header with list_init_header(). You don't have to
do anything to terminate a list header.
Initialize an anchor with list_make_emtpy(). You don't have to do anything
to terminate a list header.
-----------------------------------------------------------------------------*/
struct list_head * nextP;
/* For a header, this is the address of the list header for
the next element in the list. If there is no next element,
it points to the anchor. If the header is not in a list at
all, it is NULL.
For an anchor, it is the address of the list header of the
first element. If the list is empty, it points to the
anchor itself.
*/
struct list_head * prevP;
/* For a header, this is the address of the list header for
the previous element in the list. If there is no previous element,
it points to the anchor. If the header is not in a list at
all, it is NULL.
For an anchor, it is the address of the list header of the
last element. If the list is empty, it points to the
anchor itself.
*/
void * itemP;
/* For a header, this is the address of the list element to which it
belongs. For an anchor, this is NULL.
*/
};
static __inline__ void
list_init_header(struct list_head * const headerP,
void * const itemP) {
headerP->prevP = NULL;
headerP->nextP = NULL;
headerP->itemP = itemP;
}
static __inline__ int
list_is_linked(struct list_head * headerP) {
return headerP->prevP != NULL;
}
static __inline__ int
list_is_empty(struct list_head * const anchorP) {
return anchorP->nextP == anchorP;
}
static __inline__ unsigned int
list_count(struct list_head * const anchorP) {
unsigned int count;
struct list_head * p;
for (p = anchorP->nextP, count = 0;
p != anchorP;
p = p->nextP, ++count);
return count;
}
static __inline__ void
list_make_empty(struct list_head * const anchorP) {
anchorP->prevP = anchorP;
anchorP->nextP = anchorP;
anchorP->itemP = NULL;
}
static __inline__ void
list_insert_after(struct list_head * const beforeHeaderP,
struct list_head * const newHeaderP) {
newHeaderP->prevP = beforeHeaderP;
newHeaderP->nextP = beforeHeaderP->nextP;
beforeHeaderP->nextP = newHeaderP;
newHeaderP->nextP->prevP = newHeaderP;
}
static __inline__ void
list_add_tail(struct list_head * const anchorP,
struct list_head * const headerP) {
list_insert_after(anchorP->prevP, headerP);
}
static __inline__ void
list_add_head(struct list_head * const anchorP,
struct list_head * const headerP) {
list_insert_after(anchorP, headerP);
}
static __inline__ void
list_remove(struct list_head * const headerP) {
headerP->prevP->nextP = headerP->nextP;
headerP->nextP->prevP = headerP->prevP;
headerP->prevP = NULL;
headerP->nextP = NULL;
}
static __inline__ struct list_head *
list_remove_head(struct list_head * const anchorP) {
struct list_head * retval;
if (list_is_empty(anchorP))
retval = NULL;
else {
retval = anchorP->nextP;
list_remove(retval);
}
return retval;
}
static __inline__ struct list_head *
list_remove_tail(struct list_head * const anchorP) {
struct list_head * retval;
if (list_is_empty(anchorP))
retval = NULL;
else {
retval = anchorP->prevP;
list_remove(retval);
}
return retval;
}
static __inline__ void *
list_foreach(struct list_head * const anchorP,
void * functionP(struct list_head *, void *),
void * const context) {
struct list_head * p;
struct list_head * nextP;
void * result;
for (p = anchorP->nextP, nextP = p->nextP, result=NULL;
p != anchorP && result == NULL;
p = nextP, nextP = p->nextP)
result = (*functionP)(p, context);
return result;
}
static __inline__ void
list_append(struct list_head * const newAnchorP,
struct list_head * const baseAnchorP) {
if (!list_is_empty(newAnchorP)) {
baseAnchorP->prevP->nextP = newAnchorP->nextP;
newAnchorP->nextP->prevP = baseAnchorP->prevP;
newAnchorP->prevP->nextP = baseAnchorP;
baseAnchorP->prevP = newAnchorP->prevP;
}
}
#endif
|
