1 #ifndef LINKLIST_H_INCLUDED
2 #define LINKLIST_H_INCLUDED
7 /*----------------------------------------------------------------------------
8 This is a header for an element of a doubly linked list, or an anchor
11 itemP == NULL means it's an anchor; otherwise it's a header.
13 Initialize a list header with list_init_header(). You don't have to
14 do anything to terminate a list header.
16 Initialize an anchor with list_make_emtpy(). You don't have to do anything
17 to terminate a list header.
18 -----------------------------------------------------------------------------*/
19 struct list_head
* nextP
;
20 /* For a header, this is the address of the list header for
21 the next element in the list. If there is no next element,
22 it points to the anchor. If the header is not in a list at
25 For an anchor, it is the address of the list header of the
26 first element. If the list is empty, it points to the
29 struct list_head
* prevP
;
30 /* For a header, this is the address of the list header for
31 the previous element in the list. If there is no previous element,
32 it points to the anchor. If the header is not in a list at
35 For an anchor, it is the address of the list header of the
36 last element. If the list is empty, it points to the
40 /* For a header, this is the address of the list element to which it
41 belongs. For an anchor, this is NULL.
45 static __inline__
void
46 list_init_header(struct list_head
* const headerP
,
49 headerP
->prevP
= NULL
;
50 headerP
->nextP
= NULL
;
51 headerP
->itemP
= itemP
;
57 list_is_linked(struct list_head
* headerP
) {
58 return headerP
->prevP
!= NULL
;
64 list_is_empty(struct list_head
* const anchorP
) {
65 return anchorP
->nextP
== anchorP
;
70 static __inline__
unsigned int
71 list_count(struct list_head
* const anchorP
) {
76 for (p
= anchorP
->nextP
, count
= 0;
78 p
= p
->nextP
, ++count
);
85 static __inline__
void
86 list_make_empty(struct list_head
* const anchorP
) {
87 anchorP
->prevP
= anchorP
;
88 anchorP
->nextP
= anchorP
;
89 anchorP
->itemP
= NULL
;
92 static __inline__
void
93 list_insert_after(struct list_head
* const beforeHeaderP
,
94 struct list_head
* const newHeaderP
) {
95 newHeaderP
->prevP
= beforeHeaderP
;
96 newHeaderP
->nextP
= beforeHeaderP
->nextP
;
98 beforeHeaderP
->nextP
= newHeaderP
;
99 newHeaderP
->nextP
->prevP
= newHeaderP
;
104 static __inline__
void
105 list_add_tail(struct list_head
* const anchorP
,
106 struct list_head
* const headerP
) {
107 list_insert_after(anchorP
->prevP
, headerP
);
112 static __inline__
void
113 list_add_head(struct list_head
* const anchorP
,
114 struct list_head
* const headerP
) {
115 list_insert_after(anchorP
, headerP
);
120 static __inline__
void
121 list_remove(struct list_head
* const headerP
) {
122 headerP
->prevP
->nextP
= headerP
->nextP
;
123 headerP
->nextP
->prevP
= headerP
->prevP
;
124 headerP
->prevP
= NULL
;
125 headerP
->nextP
= NULL
;
130 static __inline__
struct list_head
*
131 list_remove_head(struct list_head
* const anchorP
) {
132 struct list_head
* retval
;
134 if (list_is_empty(anchorP
))
137 retval
= anchorP
->nextP
;
145 static __inline__
struct list_head
*
146 list_remove_tail(struct list_head
* const anchorP
) {
147 struct list_head
* retval
;
149 if (list_is_empty(anchorP
))
152 retval
= anchorP
->prevP
;
160 static __inline__
void *
161 list_foreach(struct list_head
* const anchorP
,
162 void * functionP(struct list_head
* const, void * const),
163 void * const context
) {
165 struct list_head
* p
;
166 struct list_head
* nextP
;
169 for (p
= anchorP
->nextP
, nextP
= p
->nextP
, result
=NULL
;
170 p
!= anchorP
&& result
== NULL
;
171 p
= nextP
, nextP
= p
->nextP
)
172 result
= (*functionP
)(p
, context
);
179 static __inline__
void
180 list_append(struct list_head
* const newAnchorP
,
181 struct list_head
* const baseAnchorP
) {
183 if (!list_is_empty(newAnchorP
)) {
184 baseAnchorP
->prevP
->nextP
= newAnchorP
->nextP
;
185 newAnchorP
->nextP
->prevP
= baseAnchorP
->prevP
;
186 newAnchorP
->prevP
->nextP
= baseAnchorP
;
187 baseAnchorP
->prevP
= newAnchorP
->prevP
;