]>
git.ipfire.org Git - thirdparty/util-linux.git/blob - include/list.h
2 * Copyright (C) 2008 Karel Zak <kzak@redhat.com>
3 * Copyright (C) 1999-2008 by Theodore Ts'o
5 * This file may be redistributed under the terms of the
6 * GNU Lesser General Public License.
8 * (based on list.h from e2fsprogs)
9 * Merge sort based on kernel's implementation.
12 #ifndef UTIL_LINUX_LIST_H
13 #define UTIL_LINUX_LIST_H
17 /* TODO: use AC_C_INLINE */
19 #define _INLINE_ static __inline__
20 #else /* For Watcom C */
21 #define _INLINE_ static inline
25 * Simple doubly linked list implementation.
27 * Some of the internal functions ("__xxx") are useful when
28 * manipulating whole lists rather than single entries, as
29 * sometimes we already know the next/prev entries and we can
30 * generate better code by using them directly rather than
31 * using the generic single-entry routines.
35 struct list_head
*next
, *prev
;
38 #define INIT_LIST_HEAD(ptr) do { \
39 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
43 * Insert a new entry between two known consecutive entries.
45 * This is only for internal list manipulation where we know
46 * the prev/next entries already!
48 _INLINE_
void __list_add(struct list_head
* add
,
49 struct list_head
* prev
,
50 struct list_head
* next
)
59 * list_add - add a new entry
60 * @add: new entry to be added
61 * @head: list head to add it after
63 * Insert a new entry after the specified head.
64 * This is good for implementing stacks.
66 _INLINE_
void list_add(struct list_head
*add
, struct list_head
*head
)
68 __list_add(add
, head
, head
->next
);
72 * list_add_tail - add a new entry
73 * @add: new entry to be added
74 * @head: list head to add it before
76 * Insert a new entry before the specified head.
77 * This is useful for implementing queues.
79 _INLINE_
void list_add_tail(struct list_head
*add
, struct list_head
*head
)
81 __list_add(add
, head
->prev
, head
);
85 * Delete a list entry by making the prev/next entries
86 * point to each other.
88 * This is only for internal list manipulation where we know
89 * the prev/next entries already!
91 _INLINE_
void __list_del(struct list_head
* prev
,
92 struct list_head
* next
)
99 * list_del - deletes entry from list.
100 * @entry: the element to delete from the list.
102 * list_empty() on @entry does not return true after this, @entry is
103 * in an undefined state.
105 _INLINE_
void list_del(struct list_head
*entry
)
107 __list_del(entry
->prev
, entry
->next
);
111 * list_del_init - deletes entry from list and reinitialize it.
112 * @entry: the element to delete from the list.
114 _INLINE_
void list_del_init(struct list_head
*entry
)
116 __list_del(entry
->prev
, entry
->next
);
117 INIT_LIST_HEAD(entry
);
121 * list_empty - tests whether a list is empty
122 * @head: the list to test.
124 _INLINE_
int list_empty(struct list_head
*head
)
126 return head
->next
== head
;
130 * list_entry_is_last - tests whether is entry last in the list
131 * @entry: the entry to test.
132 * @head: the list to test.
134 _INLINE_
int list_entry_is_last(struct list_head
*entry
, struct list_head
*head
)
136 return head
->prev
== entry
;
140 * list_entry_is_first - tests whether is entry first in the list
141 * @entry: the entry to test.
142 * @head: the list to test.
144 _INLINE_
int list_entry_is_first(struct list_head
*entry
, struct list_head
*head
)
146 return head
->next
== entry
;
150 * list_splice - join two lists
151 * @list: the new list to add.
152 * @head: the place to add it in the first list.
154 _INLINE_
void list_splice(struct list_head
*list
, struct list_head
*head
)
156 struct list_head
*first
= list
->next
;
159 struct list_head
*last
= list
->prev
;
160 struct list_head
*at
= head
->next
;
171 * list_entry - get the struct for this entry
172 * @ptr: the &struct list_head pointer.
173 * @type: the type of the struct this is embedded in.
174 * @member: the name of the list_struct within the struct.
176 #define list_entry(ptr, type, member) container_of(ptr, type, member)
178 #define list_first_entry(head, type, member) \
179 ((head) && (head)->next != (head) ? list_entry((head)->next, type, member) : NULL)
181 #define list_last_entry(head, type, member) \
182 ((head) && (head)->prev != (head) ? list_entry((head)->prev, type, member) : NULL)
185 * list_for_each - iterate over elements in a list
186 * @pos: the &struct list_head to use as a loop counter.
187 * @head: the head for your list.
189 #define list_for_each(pos, head) \
190 for (pos = (head)->next; pos != (head); pos = pos->next)
193 * list_for_each_backwardly - iterate over elements in a list in reverse
194 * @pos: the &struct list_head to use as a loop counter.
195 * @head: the head for your list.
197 #define list_for_each_backwardly(pos, head) \
198 for (pos = (head)->prev; pos != (head); pos = pos->prev)
201 * list_for_each_safe - iterate over elements in a list, but don't dereference
202 * pos after the body is done (in case it is freed)
203 * @pos: the &struct list_head to use as a loop counter.
204 * @pnext: the &struct list_head to use as a pointer to the next item.
205 * @head: the head for your list (not included in iteration).
207 #define list_for_each_safe(pos, pnext, head) \
208 for (pos = (head)->next, pnext = pos->next; pos != (head); \
209 pos = pnext, pnext = pos->next)
211 _INLINE_
size_t list_count_entries(struct list_head
*head
)
213 struct list_head
*pos
;
216 list_for_each(pos
, head
)
222 #define MAX_LIST_LENGTH_BITS 20
225 * Returns a list organized in an intermediate format suited
226 * to chaining of merge() calls: null-terminated, no reserved or
227 * sentinel head node, "prev" links not maintained.
229 _INLINE_
struct list_head
*merge(int (*cmp
)(struct list_head
*a
,
233 struct list_head
*a
, struct list_head
*b
)
235 struct list_head head
, *tail
= &head
;
238 /* if equal, take 'a' -- important for sort stability */
239 if ((*cmp
)(a
, b
, data
) <= 0) {
248 tail
->next
= a
? a
: b
;
253 * Combine final list merge with restoration of standard doubly-linked
254 * list structure. This approach duplicates code from merge(), but
255 * runs faster than the tidier alternatives of either a separate final
256 * prev-link restoration pass, or maintaining the prev links
259 _INLINE_
void merge_and_restore_back_links(int (*cmp
)(struct list_head
*a
,
263 struct list_head
*head
,
264 struct list_head
*a
, struct list_head
*b
)
266 struct list_head
*tail
= head
;
269 /* if equal, take 'a' -- important for sort stability */
270 if ((*cmp
)(a
, b
, data
) <= 0) {
281 tail
->next
= a
? a
: b
;
285 * In worst cases this loop may run many iterations.
286 * Continue callbacks to the client even though no
287 * element comparison is needed, so the client's cmp()
288 * routine can invoke cond_resched() periodically.
290 (*cmp
)(tail
->next
, tail
->next
, data
);
292 tail
->next
->prev
= tail
;
294 } while (tail
->next
);
302 * list_sort - sort a list
303 * @head: the list to sort
304 * @cmp: the elements comparison function
306 * This function implements "merge sort", which has O(nlog(n))
309 * The comparison function @cmp must return a negative value if @a
310 * should sort before @b, and a positive value if @a should sort after
311 * @b. If @a and @b are equivalent, and their original relative
312 * ordering is to be preserved, @cmp must return 0.
314 _INLINE_
void list_sort(struct list_head
*head
,
315 int (*cmp
)(struct list_head
*a
,
320 struct list_head
*part
[MAX_LIST_LENGTH_BITS
+1]; /* sorted partial lists
321 -- last slot is a sentinel */
322 size_t lev
; /* index into part[] */
324 struct list_head
*list
;
326 if (list_empty(head
))
329 memset(part
, 0, sizeof(part
));
331 head
->prev
->next
= NULL
;
335 struct list_head
*cur
= list
;
339 for (lev
= 0; part
[lev
]; lev
++) {
340 cur
= merge(cmp
, data
, part
[lev
], cur
);
344 /* list passed to list_sort() too long for efficiency */
345 if (lev
>= ARRAY_SIZE(part
) - 1)
352 for (lev
= 0; lev
< max_lev
; lev
++)
354 list
= merge(cmp
, data
, part
[lev
], list
);
356 merge_and_restore_back_links(cmp
, data
, head
, part
[max_lev
], list
);
361 #endif /* UTIL_LINUX_LIST_H */