1 /*
2 * Copyright (C) 2008 Karel Zak <kzak@redhat.com>
3 * Copyright (C) 1999-2008 by Theodore Ts'o
4 *
5 * This file may be redistributed under the terms of the
6 * GNU Lesser General Public License.
7 *
8 * (based on list.h from e2fsprogs)
9 * Merge sort based on kernel's implementation.
10 */
11
12 #ifndef UTIL_LINUX_LIST_H
13 #define UTIL_LINUX_LIST_H
14
15 #include "c.h"
16
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
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
129 /**
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.
133 */
134 _INLINE_ int list_entry_is_last(struct list_head *entry, struct list_head *head)
135 {
136 return head->prev == entry;
137 }
138
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
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 */
176 #define list_entry(ptr, type, member) container_of(ptr, type, member)
177
178 #define list_first_entry(head, type, member) \
179 ((head) && (head)->next != (head) ? list_entry((head)->next, type, member) : NULL)
180
181 #define list_last_entry(head, type, member) \
182 ((head) && (head)->prev != (head) ? list_entry((head)->prev, type, member) : NULL)
183
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
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
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
211 /**
212 * list_free - remove all entries from list and call freefunc()
213 * for each entry
214 * @head: the head for your list
215 * @type: the type of the struct this is embedded in.
216 * @member: the name of the list_struct within the struct.
217 * @freefunc: the list entry deallocator
218 */
219 #define list_free(head, type, member, freefunc) \
220 do { \
221 struct list_head *__p, *__pnext; \
222 \
223 list_for_each_safe (__p, __pnext, (head)) { \
224 type *__elt = list_entry(__p, type, member); \
225 list_del(__p); \
226 freefunc(__elt); \
227 } \
228 } while (0)
229
230 _INLINE_ size_t list_count_entries(struct list_head *head)
231 {
232 struct list_head *pos;
233 size_t ct = 0;
234
235 list_for_each(pos, head)
236 ct++;
237
238 return ct;
239 }
240
241 #define MAX_LIST_LENGTH_BITS 20
242
243 /*
244 * Returns a list organized in an intermediate format suited
245 * to chaining of merge() calls: null-terminated, no reserved or
246 * sentinel head node, "prev" links not maintained.
247 */
248 _INLINE_ struct list_head *merge(int (*cmp)(struct list_head *a,
249 struct list_head *b,
250 void *data),
251 void *data,
252 struct list_head *a, struct list_head *b)
253 {
254 struct list_head head, *tail = &head;
255
256 while (a && b) {
257 /* if equal, take 'a' -- important for sort stability */
258 if ((*cmp)(a, b, data) <= 0) {
259 tail->next = a;
260 a = a->next;
261 } else {
262 tail->next = b;
263 b = b->next;
264 }
265 tail = tail->next;
266 }
267 tail->next = a ? a : b;
268 return head.next;
269 }
270
271 /*
272 * Combine final list merge with restoration of standard doubly-linked
273 * list structure. This approach duplicates code from merge(), but
274 * runs faster than the tidier alternatives of either a separate final
275 * prev-link restoration pass, or maintaining the prev links
276 * throughout.
277 */
278 _INLINE_ void merge_and_restore_back_links(int (*cmp)(struct list_head *a,
279 struct list_head *b,
280 void *data),
281 void *data,
282 struct list_head *head,
283 struct list_head *a, struct list_head *b)
284 {
285 struct list_head *tail = head;
286
287 while (a && b) {
288 /* if equal, take 'a' -- important for sort stability */
289 if ((*cmp)(a, b, data) <= 0) {
290 tail->next = a;
291 a->prev = tail;
292 a = a->next;
293 } else {
294 tail->next = b;
295 b->prev = tail;
296 b = b->next;
297 }
298 tail = tail->next;
299 }
300 tail->next = a ? a : b;
301
302 do {
303 /*
304 * In worst cases this loop may run many iterations.
305 * Continue callbacks to the client even though no
306 * element comparison is needed, so the client's cmp()
307 * routine can invoke cond_resched() periodically.
308 */
309 (*cmp)(tail->next, tail->next, data);
310
311 tail->next->prev = tail;
312 tail = tail->next;
313 } while (tail->next);
314
315 tail->next = head;
316 head->prev = tail;
317 }
318
319
320 /**
321 * list_sort - sort a list
322 * @head: the list to sort
323 * @cmp: the elements comparison function
324 *
325 * This function implements "merge sort", which has O(nlog(n))
326 * complexity.
327 *
328 * The comparison function @cmp must return a negative value if @a
329 * should sort before @b, and a positive value if @a should sort after
330 * @b. If @a and @b are equivalent, and their original relative
331 * ordering is to be preserved, @cmp must return 0.
332 */
333 _INLINE_ void list_sort(struct list_head *head,
334 int (*cmp)(struct list_head *a,
335 struct list_head *b,
336 void *data),
337 void *data)
338 {
339 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
340 -- last slot is a sentinel */
341 size_t lev; /* index into part[] */
342 size_t max_lev = 0;
343 struct list_head *list;
344
345 if (list_empty(head))
346 return;
347
348 memset(part, 0, sizeof(part));
349
350 head->prev->next = NULL;
351 list = head->next;
352
353 while (list) {
354 struct list_head *cur = list;
355 list = list->next;
356 cur->next = NULL;
357
358 for (lev = 0; part[lev]; lev++) {
359 cur = merge(cmp, data, part[lev], cur);
360 part[lev] = NULL;
361 }
362 if (lev > max_lev) {
363 /* list passed to list_sort() too long for efficiency */
364 if (lev >= ARRAY_SIZE(part) - 1)
365 lev--;
366 max_lev = lev;
367 }
368 part[lev] = cur;
369 }
370
371 for (lev = 0; lev < max_lev; lev++)
372 if (part[lev])
373 list = merge(cmp, data, part[lev], list);
374
375 merge_and_restore_back_links(cmp, data, head, part[max_lev], list);
376 }
377
378 #undef _INLINE_
379
380 #endif /* UTIL_LINUX_LIST_H */