]>
Commit | Line | Data |
---|---|---|
efab4b61 KZ |
1 | /* |
2 | * Copyright (C) 2008 Karel Zak <kzak@redhat.com> | |
3 | * Copyright (C) 1999-2008 by Theodore Ts'o | |
4 | * | |
0f23ee0c KZ |
5 | * This file may be redistributed under the terms of the |
6 | * GNU Lesser General Public License. | |
7 | * | |
efab4b61 | 8 | * (based on list.h from e2fsprogs) |
5b9df028 | 9 | * Merge sort based on kernel's implementation. |
efab4b61 KZ |
10 | */ |
11 | ||
85950b68 KZ |
12 | #ifndef UTIL_LINUX_LIST_H |
13 | #define UTIL_LINUX_LIST_H | |
efab4b61 | 14 | |
eb06d5d4 KZ |
15 | #include "c.h" |
16 | ||
efab4b61 KZ |
17 | /* TODO: use AC_C_INLINE */ |
18 | #ifdef __GNUC__ | |
19 | #define _INLINE_ static __inline__ | |
20 | #else /* For Watcom C */ | |
21 | #define _INLINE_ static inline | |
22 | #endif | |
23 | ||
24 | /* | |
25 | * Simple doubly linked list implementation. | |
26 | * | |
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. | |
32 | */ | |
33 | ||
34 | struct list_head { | |
35 | struct list_head *next, *prev; | |
36 | }; | |
37 | ||
efab4b61 KZ |
38 | #define INIT_LIST_HEAD(ptr) do { \ |
39 | (ptr)->next = (ptr); (ptr)->prev = (ptr); \ | |
40 | } while (0) | |
41 | ||
42 | /* | |
43 | * Insert a new entry between two known consecutive entries. | |
44 | * | |
45 | * This is only for internal list manipulation where we know | |
46 | * the prev/next entries already! | |
47 | */ | |
48 | _INLINE_ void __list_add(struct list_head * add, | |
49 | struct list_head * prev, | |
50 | struct list_head * next) | |
51 | { | |
52 | next->prev = add; | |
53 | add->next = next; | |
54 | add->prev = prev; | |
55 | prev->next = add; | |
56 | } | |
57 | ||
58 | /** | |
59 | * list_add - add a new entry | |
60 | * @add: new entry to be added | |
61 | * @head: list head to add it after | |
62 | * | |
63 | * Insert a new entry after the specified head. | |
64 | * This is good for implementing stacks. | |
65 | */ | |
66 | _INLINE_ void list_add(struct list_head *add, struct list_head *head) | |
67 | { | |
68 | __list_add(add, head, head->next); | |
69 | } | |
70 | ||
71 | /** | |
72 | * list_add_tail - add a new entry | |
73 | * @add: new entry to be added | |
74 | * @head: list head to add it before | |
75 | * | |
76 | * Insert a new entry before the specified head. | |
77 | * This is useful for implementing queues. | |
78 | */ | |
79 | _INLINE_ void list_add_tail(struct list_head *add, struct list_head *head) | |
80 | { | |
81 | __list_add(add, head->prev, head); | |
82 | } | |
83 | ||
84 | /* | |
85 | * Delete a list entry by making the prev/next entries | |
86 | * point to each other. | |
87 | * | |
88 | * This is only for internal list manipulation where we know | |
89 | * the prev/next entries already! | |
90 | */ | |
91 | _INLINE_ void __list_del(struct list_head * prev, | |
92 | struct list_head * next) | |
93 | { | |
94 | next->prev = prev; | |
95 | prev->next = next; | |
96 | } | |
97 | ||
98 | /** | |
99 | * list_del - deletes entry from list. | |
100 | * @entry: the element to delete from the list. | |
101 | * | |
102 | * list_empty() on @entry does not return true after this, @entry is | |
103 | * in an undefined state. | |
104 | */ | |
105 | _INLINE_ void list_del(struct list_head *entry) | |
106 | { | |
107 | __list_del(entry->prev, entry->next); | |
108 | } | |
109 | ||
110 | /** | |
111 | * list_del_init - deletes entry from list and reinitialize it. | |
112 | * @entry: the element to delete from the list. | |
113 | */ | |
114 | _INLINE_ void list_del_init(struct list_head *entry) | |
115 | { | |
116 | __list_del(entry->prev, entry->next); | |
117 | INIT_LIST_HEAD(entry); | |
118 | } | |
119 | ||
120 | /** | |
121 | * list_empty - tests whether a list is empty | |
122 | * @head: the list to test. | |
123 | */ | |
124 | _INLINE_ int list_empty(struct list_head *head) | |
125 | { | |
126 | return head->next == head; | |
127 | } | |
128 | ||
c391642d | 129 | /** |
59da1544 | 130 | * list_entry_is_last - tests whether is entry last in the list |
c391642d KZ |
131 | * @entry: the entry to test. |
132 | * @head: the list to test. | |
133 | */ | |
59da1544 | 134 | _INLINE_ int list_entry_is_last(struct list_head *entry, struct list_head *head) |
c391642d KZ |
135 | { |
136 | return head->prev == entry; | |
137 | } | |
138 | ||
7ca122ba KZ |
139 | /** |
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. | |
143 | */ | |
144 | _INLINE_ int list_entry_is_first(struct list_head *entry, struct list_head *head) | |
145 | { | |
146 | return head->next == entry; | |
147 | } | |
148 | ||
efab4b61 KZ |
149 | /** |
150 | * list_splice - join two lists | |
151 | * @list: the new list to add. | |
152 | * @head: the place to add it in the first list. | |
153 | */ | |
154 | _INLINE_ void list_splice(struct list_head *list, struct list_head *head) | |
155 | { | |
156 | struct list_head *first = list->next; | |
157 | ||
158 | if (first != list) { | |
159 | struct list_head *last = list->prev; | |
160 | struct list_head *at = head->next; | |
161 | ||
162 | first->prev = head; | |
163 | head->next = first; | |
164 | ||
165 | last->next = at; | |
166 | at->prev = last; | |
167 | } | |
168 | } | |
169 | ||
170 | /** | |
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. | |
175 | */ | |
eb06d5d4 | 176 | #define list_entry(ptr, type, member) container_of(ptr, type, member) |
7293e97a KZ |
177 | |
178 | #define list_first_entry(head, type, member) \ | |
179 | ((head) && (head)->next != (head) ? list_entry((head)->next, type, member) : NULL) | |
180 | ||
59da1544 KZ |
181 | #define list_last_entry(head, type, member) \ |
182 | ((head) && (head)->prev != (head) ? list_entry((head)->prev, type, member) : NULL) | |
183 | ||
efab4b61 KZ |
184 | /** |
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. | |
188 | */ | |
189 | #define list_for_each(pos, head) \ | |
190 | for (pos = (head)->next; pos != (head); pos = pos->next) | |
191 | ||
c391642d KZ |
192 | /** |
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. | |
196 | */ | |
197 | #define list_for_each_backwardly(pos, head) \ | |
198 | for (pos = (head)->prev; pos != (head); pos = pos->prev) | |
199 | ||
efab4b61 KZ |
200 | /** |
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). | |
206 | */ | |
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) | |
210 | ||
7ca122ba KZ |
211 | _INLINE_ size_t list_count_entries(struct list_head *head) |
212 | { | |
213 | struct list_head *pos; | |
214 | size_t ct = 0; | |
215 | ||
216 | list_for_each(pos, head) | |
217 | ct++; | |
218 | ||
219 | return ct; | |
220 | } | |
221 | ||
5b9df028 DB |
222 | #define MAX_LIST_LENGTH_BITS 20 |
223 | ||
224 | /* | |
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. | |
228 | */ | |
229 | _INLINE_ struct list_head *merge(int (*cmp)(struct list_head *a, | |
6736192a KZ |
230 | struct list_head *b, |
231 | void *data), | |
232 | void *data, | |
5b9df028 DB |
233 | struct list_head *a, struct list_head *b) |
234 | { | |
235 | struct list_head head, *tail = &head; | |
236 | ||
237 | while (a && b) { | |
238 | /* if equal, take 'a' -- important for sort stability */ | |
6736192a | 239 | if ((*cmp)(a, b, data) <= 0) { |
5b9df028 DB |
240 | tail->next = a; |
241 | a = a->next; | |
242 | } else { | |
243 | tail->next = b; | |
244 | b = b->next; | |
245 | } | |
246 | tail = tail->next; | |
247 | } | |
c42206e4 | 248 | tail->next = a ? a : b; |
5b9df028 DB |
249 | return head.next; |
250 | } | |
251 | ||
252 | /* | |
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 | |
257 | * throughout. | |
258 | */ | |
259 | _INLINE_ void merge_and_restore_back_links(int (*cmp)(struct list_head *a, | |
6736192a KZ |
260 | struct list_head *b, |
261 | void *data), | |
262 | void *data, | |
5b9df028 DB |
263 | struct list_head *head, |
264 | struct list_head *a, struct list_head *b) | |
265 | { | |
266 | struct list_head *tail = head; | |
267 | ||
268 | while (a && b) { | |
269 | /* if equal, take 'a' -- important for sort stability */ | |
6736192a | 270 | if ((*cmp)(a, b, data) <= 0) { |
5b9df028 DB |
271 | tail->next = a; |
272 | a->prev = tail; | |
273 | a = a->next; | |
274 | } else { | |
275 | tail->next = b; | |
276 | b->prev = tail; | |
277 | b = b->next; | |
278 | } | |
279 | tail = tail->next; | |
280 | } | |
c42206e4 | 281 | tail->next = a ? a : b; |
5b9df028 DB |
282 | |
283 | do { | |
284 | /* | |
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. | |
289 | */ | |
6736192a | 290 | (*cmp)(tail->next, tail->next, data); |
5b9df028 DB |
291 | |
292 | tail->next->prev = tail; | |
293 | tail = tail->next; | |
294 | } while (tail->next); | |
295 | ||
296 | tail->next = head; | |
297 | head->prev = tail; | |
298 | } | |
299 | ||
300 | ||
301 | /** | |
302 | * list_sort - sort a list | |
303 | * @head: the list to sort | |
304 | * @cmp: the elements comparison function | |
305 | * | |
306 | * This function implements "merge sort", which has O(nlog(n)) | |
307 | * complexity. | |
308 | * | |
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. | |
313 | */ | |
314 | _INLINE_ void list_sort(struct list_head *head, | |
315 | int (*cmp)(struct list_head *a, | |
6736192a KZ |
316 | struct list_head *b, |
317 | void *data), | |
318 | void *data) | |
5b9df028 DB |
319 | { |
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[] */ | |
323 | size_t max_lev = 0; | |
324 | struct list_head *list; | |
325 | ||
326 | if (list_empty(head)) | |
327 | return; | |
328 | ||
329 | memset(part, 0, sizeof(part)); | |
330 | ||
331 | head->prev->next = NULL; | |
332 | list = head->next; | |
333 | ||
334 | while (list) { | |
335 | struct list_head *cur = list; | |
336 | list = list->next; | |
337 | cur->next = NULL; | |
338 | ||
339 | for (lev = 0; part[lev]; lev++) { | |
6736192a | 340 | cur = merge(cmp, data, part[lev], cur); |
5b9df028 DB |
341 | part[lev] = NULL; |
342 | } | |
343 | if (lev > max_lev) { | |
344 | /* list passed to list_sort() too long for efficiency */ | |
345 | if (lev >= ARRAY_SIZE(part) - 1) | |
346 | lev--; | |
347 | max_lev = lev; | |
348 | } | |
349 | part[lev] = cur; | |
350 | } | |
351 | ||
352 | for (lev = 0; lev < max_lev; lev++) | |
353 | if (part[lev]) | |
6736192a | 354 | list = merge(cmp, data, part[lev], list); |
5b9df028 | 355 | |
6736192a | 356 | merge_and_restore_back_links(cmp, data, head, part[max_lev], list); |
5b9df028 DB |
357 | } |
358 | ||
efab4b61 KZ |
359 | #undef _INLINE_ |
360 | ||
85950b68 | 361 | #endif /* UTIL_LINUX_LIST_H */ |