]>
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_splice - join two lists
141 * @list: the new list to add.
142 * @head: the place to add it in the first list.
144 _INLINE_
void list_splice(struct list_head
*list
, struct list_head
*head
)
146 struct list_head
*first
= list
->next
;
149 struct list_head
*last
= list
->prev
;
150 struct list_head
*at
= head
->next
;
161 * list_entry - get the struct for this entry
162 * @ptr: the &struct list_head pointer.
163 * @type: the type of the struct this is embedded in.
164 * @member: the name of the list_struct within the struct.
166 #define list_entry(ptr, type, member) container_of(ptr, type, member)
168 #define list_first_entry(head, type, member) \
169 ((head) && (head)->next != (head) ? list_entry((head)->next, type, member) : NULL)
171 #define list_last_entry(head, type, member) \
172 ((head) && (head)->prev != (head) ? list_entry((head)->prev, type, member) : NULL)
175 * list_for_each - iterate over elements in a list
176 * @pos: the &struct list_head to use as a loop counter.
177 * @head: the head for your list.
179 #define list_for_each(pos, head) \
180 for (pos = (head)->next; pos != (head); pos = pos->next)
183 * list_for_each_backwardly - iterate over elements in a list in reverse
184 * @pos: the &struct list_head to use as a loop counter.
185 * @head: the head for your list.
187 #define list_for_each_backwardly(pos, head) \
188 for (pos = (head)->prev; pos != (head); pos = pos->prev)
191 * list_for_each_safe - iterate over elements in a list, but don't dereference
192 * pos after the body is done (in case it is freed)
193 * @pos: the &struct list_head to use as a loop counter.
194 * @pnext: the &struct list_head to use as a pointer to the next item.
195 * @head: the head for your list (not included in iteration).
197 #define list_for_each_safe(pos, pnext, head) \
198 for (pos = (head)->next, pnext = pos->next; pos != (head); \
199 pos = pnext, pnext = pos->next)
201 #define MAX_LIST_LENGTH_BITS 20
204 * Returns a list organized in an intermediate format suited
205 * to chaining of merge() calls: null-terminated, no reserved or
206 * sentinel head node, "prev" links not maintained.
208 _INLINE_
struct list_head
*merge(int (*cmp
)(struct list_head
*a
,
212 struct list_head
*a
, struct list_head
*b
)
214 struct list_head head
, *tail
= &head
;
217 /* if equal, take 'a' -- important for sort stability */
218 if ((*cmp
)(a
, b
, data
) <= 0) {
227 tail
->next
= a
? a
: b
;
232 * Combine final list merge with restoration of standard doubly-linked
233 * list structure. This approach duplicates code from merge(), but
234 * runs faster than the tidier alternatives of either a separate final
235 * prev-link restoration pass, or maintaining the prev links
238 _INLINE_
void merge_and_restore_back_links(int (*cmp
)(struct list_head
*a
,
242 struct list_head
*head
,
243 struct list_head
*a
, struct list_head
*b
)
245 struct list_head
*tail
= head
;
248 /* if equal, take 'a' -- important for sort stability */
249 if ((*cmp
)(a
, b
, data
) <= 0) {
260 tail
->next
= a
? a
: b
;
264 * In worst cases this loop may run many iterations.
265 * Continue callbacks to the client even though no
266 * element comparison is needed, so the client's cmp()
267 * routine can invoke cond_resched() periodically.
269 (*cmp
)(tail
->next
, tail
->next
, data
);
271 tail
->next
->prev
= tail
;
273 } while (tail
->next
);
281 * list_sort - sort a list
282 * @head: the list to sort
283 * @cmp: the elements comparison function
285 * This function implements "merge sort", which has O(nlog(n))
288 * The comparison function @cmp must return a negative value if @a
289 * should sort before @b, and a positive value if @a should sort after
290 * @b. If @a and @b are equivalent, and their original relative
291 * ordering is to be preserved, @cmp must return 0.
293 _INLINE_
void list_sort(struct list_head
*head
,
294 int (*cmp
)(struct list_head
*a
,
299 struct list_head
*part
[MAX_LIST_LENGTH_BITS
+1]; /* sorted partial lists
300 -- last slot is a sentinel */
301 size_t lev
; /* index into part[] */
303 struct list_head
*list
;
305 if (list_empty(head
))
308 memset(part
, 0, sizeof(part
));
310 head
->prev
->next
= NULL
;
314 struct list_head
*cur
= list
;
318 for (lev
= 0; part
[lev
]; lev
++) {
319 cur
= merge(cmp
, data
, part
[lev
], cur
);
323 /* list passed to list_sort() too long for efficiency */
324 if (lev
>= ARRAY_SIZE(part
) - 1)
331 for (lev
= 0; lev
< max_lev
; lev
++)
333 list
= merge(cmp
, data
, part
[lev
], list
);
335 merge_and_restore_back_links(cmp
, data
, head
, part
[max_lev
], list
);
340 #endif /* UTIL_LINUX_LIST_H */