merge an avl list implementation (imported from PacketBB)
[project/libubox.git] / list.h
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3
4 #include <stddef.h>
5 /**
6 * container_of - cast a member of a structure out to the containing structure
7 * @ptr: the pointer to the member.
8 * @type: the type of the container struct this is embedded in.
9 * @member: the name of the member within the struct.
10 *
11 */
12 #ifndef container_of
13 #define container_of(ptr, type, member) ( \
14 (type *)( (char *)ptr - offsetof(type,member) ))
15 #endif
16
17
18 /*
19 * Simple doubly linked list implementation.
20 *
21 * Some of the internal functions ("__xxx") are useful when
22 * manipulating whole lists rather than single entries, as
23 * sometimes we already know the next/prev entries and we can
24 * generate better code by using them directly rather than
25 * using the generic single-entry routines.
26 */
27
28 struct list_head {
29 struct list_head *next, *prev;
30 };
31
32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
33
34 #define LIST_HEAD(name) \
35 struct list_head name = LIST_HEAD_INIT(name)
36
37 static inline void INIT_LIST_HEAD(struct list_head *list)
38 {
39 list->next = list;
40 list->prev = list;
41 }
42
43 /*
44 * Insert a new entry between two known consecutive entries.
45 *
46 * This is only for internal list manipulation where we know
47 * the prev/next entries already!
48 */
49 static inline void __list_add(struct list_head *new,
50 struct list_head *prev,
51 struct list_head *next)
52 {
53 next->prev = new;
54 new->next = next;
55 new->prev = prev;
56 prev->next = new;
57 }
58
59 /**
60 * list_add - add a new entry
61 * @new: new entry to be added
62 * @head: list head to add it after
63 *
64 * Insert a new entry after the specified head.
65 * This is good for implementing stacks.
66 */
67 static inline void list_add(struct list_head *new, struct list_head *head)
68 {
69 __list_add(new, head, head->next);
70 }
71
72
73 /**
74 * list_add_tail - add a new entry
75 * @new: new entry to be added
76 * @head: list head to add it before
77 *
78 * Insert a new entry before the specified head.
79 * This is useful for implementing queues.
80 */
81 static inline void list_add_tail(struct list_head *new, struct list_head *head)
82 {
83 __list_add(new, head->prev, head);
84 }
85
86
87 /*
88 * Delete a list entry by making the prev/next entries
89 * point to each other.
90 *
91 * This is only for internal list manipulation where we know
92 * the prev/next entries already!
93 */
94 static inline void __list_del(struct list_head * prev, struct list_head * next)
95 {
96 next->prev = prev;
97 prev->next = next;
98 }
99
100 /**
101 * list_del - deletes entry from list.
102 * @entry: the element to delete from the list.
103 * Note: list_empty() on entry does not return true after this, the entry is
104 * in an undefined state.
105 */
106 static inline void list_del(struct list_head *entry)
107 {
108 __list_del(entry->prev, entry->next);
109 entry->next = NULL;
110 entry->prev = NULL;
111 }
112
113 /**
114 * list_replace - replace old entry by new one
115 * @old : the element to be replaced
116 * @new : the new element to insert
117 *
118 * If @old was empty, it will be overwritten.
119 */
120 static inline void list_replace(struct list_head *old,
121 struct list_head *new)
122 {
123 new->next = old->next;
124 new->next->prev = new;
125 new->prev = old->prev;
126 new->prev->next = new;
127 }
128
129 static inline void list_replace_init(struct list_head *old,
130 struct list_head *new)
131 {
132 list_replace(old, new);
133 INIT_LIST_HEAD(old);
134 }
135
136 /**
137 * list_del_init - deletes entry from list and reinitialize it.
138 * @entry: the element to delete from the list.
139 */
140 static inline void list_del_init(struct list_head *entry)
141 {
142 __list_del(entry->prev, entry->next);
143 INIT_LIST_HEAD(entry);
144 }
145
146 /**
147 * list_move - delete from one list and add as another's head
148 * @list: the entry to move
149 * @head: the head that will precede our entry
150 */
151 static inline void list_move(struct list_head *list, struct list_head *head)
152 {
153 __list_del(list->prev, list->next);
154 list_add(list, head);
155 }
156
157 /**
158 * list_move_tail - delete from one list and add as another's tail
159 * @list: the entry to move
160 * @head: the head that will follow our entry
161 */
162 static inline void list_move_tail(struct list_head *list,
163 struct list_head *head)
164 {
165 __list_del(list->prev, list->next);
166 list_add_tail(list, head);
167 }
168
169 /**
170 * list_is_first - tests whether @list is the first entry in list @head
171 * @list: the entry to test
172 * @head: the head of the list
173 */
174 static inline int list_is_first(const struct list_head *list,
175 const struct list_head *head)
176 {
177 return list->prev == head;
178 }
179
180 /**
181 * list_is_last - tests whether @list is the last entry in list @head
182 * @list: the entry to test
183 * @head: the head of the list
184 */
185 static inline int list_is_last(const struct list_head *list,
186 const struct list_head *head)
187 {
188 return list->next == head;
189 }
190
191 /**
192 * list_empty - tests whether a list is empty
193 * @head: the list to test.
194 */
195 static inline int list_empty(const struct list_head *head)
196 {
197 return head->next == head;
198 }
199
200 /**
201 * list_empty_careful - tests whether a list is empty and not being modified
202 * @head: the list to test
203 *
204 * Description:
205 * tests whether a list is empty _and_ checks that no other CPU might be
206 * in the process of modifying either member (next or prev)
207 *
208 * NOTE: using list_empty_careful() without synchronization
209 * can only be safe if the only activity that can happen
210 * to the list entry is list_del_init(). Eg. it cannot be used
211 * if another CPU could re-list_add() it.
212 */
213 static inline int list_empty_careful(const struct list_head *head)
214 {
215 struct list_head *next = head->next;
216 return (next == head) && (next == head->prev);
217 }
218
219 static inline void __list_splice(struct list_head *list,
220 struct list_head *head)
221 {
222 struct list_head *first = list->next;
223 struct list_head *last = list->prev;
224 struct list_head *at = head->next;
225
226 first->prev = head;
227 head->next = first;
228
229 last->next = at;
230 at->prev = last;
231 }
232
233 /**
234 * list_splice - join two lists
235 * @list: the new list to add.
236 * @head: the place to add it in the first list.
237 */
238 static inline void list_splice(struct list_head *list, struct list_head *head)
239 {
240 if (!list_empty(list))
241 __list_splice(list, head);
242 }
243
244 /**
245 * list_splice_init - join two lists and reinitialise the emptied list.
246 * @list: the new list to add.
247 * @head: the place to add it in the first list.
248 *
249 * The list at @list is reinitialised
250 */
251 static inline void list_splice_init(struct list_head *list,
252 struct list_head *head)
253 {
254 if (!list_empty(list)) {
255 __list_splice(list, head);
256 INIT_LIST_HEAD(list);
257 }
258 }
259
260 /**
261 * list_entry - get the struct for this entry
262 * @ptr: the &struct list_head pointer.
263 * @type: the type of the struct this is embedded in.
264 * @member: the name of the list_struct within the struct.
265 */
266 #define list_entry(ptr, type, member) \
267 container_of(ptr, type, member)
268
269 /**
270 * list_first_entry - get the first element from a list
271 * @ptr: the list head to take the element from.
272 * @type: the type of the struct this is embedded in.
273 * @member: the name of the list_struct within the struct.
274 *
275 * Note, that list is expected to be not empty.
276 */
277 #define list_first_entry(ptr, type, member) \
278 list_entry((ptr)->next, type, member)
279
280 /**
281 * list_for_each - iterate over a list
282 * @pos: the &struct list_head to use as a loop cursor.
283 * @head: the head for your list.
284 */
285 #define list_for_each(pos, head) \
286 for (pos = (head)->next; pos != (head); \
287 pos = pos->next)
288
289 /**
290 * __list_for_each - iterate over a list
291 * @pos: the &struct list_head to use as a loop cursor.
292 * @head: the head for your list.
293 *
294 * This variant differs from list_for_each() in that it's the
295 * simplest possible list iteration code, no prefetching is done.
296 * Use this for code that knows the list to be very short (empty
297 * or 1 entry) most of the time.
298 */
299 #define __list_for_each(pos, head) \
300 for (pos = (head)->next; pos != (head); pos = pos->next)
301
302 /**
303 * list_for_each_prev - iterate over a list backwards
304 * @pos: the &struct list_head to use as a loop cursor.
305 * @head: the head for your list.
306 */
307 #define list_for_each_prev(pos, head) \
308 for (pos = (head)->prev; pos != (head); \
309 pos = pos->prev)
310
311 /**
312 * list_for_each_safe - iterate over a list safe against removal of list entry
313 * @pos: the &struct list_head to use as a loop cursor.
314 * @n: another &struct list_head to use as temporary storage
315 * @head: the head for your list.
316 */
317 #define list_for_each_safe(pos, n, head) \
318 for (pos = (head)->next, n = pos->next; pos != (head); \
319 pos = n, n = pos->next)
320
321 /**
322 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
323 * @pos: the &struct list_head to use as a loop cursor.
324 * @n: another &struct list_head to use as temporary storage
325 * @head: the head for your list.
326 */
327 #define list_for_each_prev_safe(pos, n, head) \
328 for (pos = (head)->prev, n = pos->prev; \
329 pos != (head); \
330 pos = n, n = pos->prev)
331
332 /**
333 * list_for_each_entry - iterate over list of given type
334 * @pos: the type * to use as a loop cursor.
335 * @head: the head for your list.
336 * @member: the name of the list_struct within the struct.
337 */
338 #define list_for_each_entry(pos, head, member) \
339 for (pos = list_entry((head)->next, typeof(*pos), member); \
340 &pos->member != (head); \
341 pos = list_entry(pos->member.next, typeof(*pos), member))
342
343 /**
344 * list_for_each_entry_reverse - iterate backwards over list of given type.
345 * @pos: the type * to use as a loop cursor.
346 * @head: the head for your list.
347 * @member: the name of the list_struct within the struct.
348 */
349 #define list_for_each_entry_reverse(pos, head, member) \
350 for (pos = list_entry((head)->prev, typeof(*pos), member); \
351 &pos->member != (head); \
352 pos = list_entry(pos->member.prev, typeof(*pos), member))
353
354 /**
355 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
356 * @pos: the type * to use as a start point
357 * @head: the head of the list
358 * @member: the name of the list_struct within the struct.
359 *
360 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
361 */
362 #define list_prepare_entry(pos, head, member) \
363 ((pos) ? : list_entry(head, typeof(*pos), member))
364
365 /**
366 * list_for_each_entry_continue - continue iteration over list of given type
367 * @pos: the type * to use as a loop cursor.
368 * @head: the head for your list.
369 * @member: the name of the list_struct within the struct.
370 *
371 * Continue to iterate over list of given type, continuing after
372 * the current position.
373 */
374 #define list_for_each_entry_continue(pos, head, member) \
375 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
376 &pos->member != (head); \
377 pos = list_entry(pos->member.next, typeof(*pos), member))
378
379 /**
380 * list_for_each_entry_continue_reverse - iterate backwards from the given point
381 * @pos: the type * to use as a loop cursor.
382 * @head: the head for your list.
383 * @member: the name of the list_struct within the struct.
384 *
385 * Start to iterate over list of given type backwards, continuing after
386 * the current position.
387 */
388 #define list_for_each_entry_continue_reverse(pos, head, member) \
389 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
390 &pos->member != (head); \
391 pos = list_entry(pos->member.prev, typeof(*pos), member))
392
393 /**
394 * list_for_each_entry_from - iterate over list of given type from the current point
395 * @pos: the type * to use as a loop cursor.
396 * @head: the head for your list.
397 * @member: the name of the list_struct within the struct.
398 *
399 * Iterate over list of given type, continuing from current position.
400 */
401 #define list_for_each_entry_from(pos, head, member) \
402 for (; &pos->member != (head); \
403 pos = list_entry(pos->member.next, typeof(*pos), member))
404
405 /**
406 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
407 * @pos: the type * to use as a loop cursor.
408 * @n: another type * to use as temporary storage
409 * @head: the head for your list.
410 * @member: the name of the list_struct within the struct.
411 */
412 #define list_for_each_entry_safe(pos, n, head, member) \
413 for (pos = list_entry((head)->next, typeof(*pos), member), \
414 n = list_entry(pos->member.next, typeof(*pos), member); \
415 &pos->member != (head); \
416 pos = n, n = list_entry(n->member.next, typeof(*n), member))
417
418 /**
419 * list_for_each_entry_safe_continue
420 * @pos: the type * to use as a loop cursor.
421 * @n: another type * to use as temporary storage
422 * @head: the head for your list.
423 * @member: the name of the list_struct within the struct.
424 *
425 * Iterate over list of given type, continuing after current point,
426 * safe against removal of list entry.
427 */
428 #define list_for_each_entry_safe_continue(pos, n, head, member) \
429 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
430 n = list_entry(pos->member.next, typeof(*pos), member); \
431 &pos->member != (head); \
432 pos = n, n = list_entry(n->member.next, typeof(*n), member))
433
434 /**
435 * list_for_each_entry_safe_from
436 * @pos: the type * to use as a loop cursor.
437 * @n: another type * to use as temporary storage
438 * @head: the head for your list.
439 * @member: the name of the list_struct within the struct.
440 *
441 * Iterate over list of given type from current point, safe against
442 * removal of list entry.
443 */
444 #define list_for_each_entry_safe_from(pos, n, head, member) \
445 for (n = list_entry(pos->member.next, typeof(*pos), member); \
446 &pos->member != (head); \
447 pos = n, n = list_entry(n->member.next, typeof(*n), member))
448
449 /**
450 * list_for_each_entry_safe_reverse
451 * @pos: the type * to use as a loop cursor.
452 * @n: another type * to use as temporary storage
453 * @head: the head for your list.
454 * @member: the name of the list_struct within the struct.
455 *
456 * Iterate backwards over list of given type, safe against removal
457 * of list entry.
458 */
459 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
460 for (pos = list_entry((head)->prev, typeof(*pos), member), \
461 n = list_entry(pos->member.prev, typeof(*pos), member); \
462 &pos->member != (head); \
463 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
464
465 /*
466 * Double linked lists with a single pointer list head.
467 * Mostly useful for hash tables where the two pointer list head is
468 * too wasteful.
469 * You lose the ability to access the tail in O(1).
470 */
471
472 struct hlist_head {
473 struct hlist_node *first;
474 };
475
476 struct hlist_node {
477 struct hlist_node *next, **pprev;
478 };
479
480 #define HLIST_HEAD_INIT { .first = NULL }
481 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
482 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
483 static inline void INIT_HLIST_NODE(struct hlist_node *h)
484 {
485 h->next = NULL;
486 h->pprev = NULL;
487 }
488
489 static inline int hlist_unhashed(const struct hlist_node *h)
490 {
491 return !h->pprev;
492 }
493
494 static inline int hlist_empty(const struct hlist_head *h)
495 {
496 return !h->first;
497 }
498
499 static inline void __hlist_del(struct hlist_node *n)
500 {
501 struct hlist_node *next = n->next;
502 struct hlist_node **pprev = n->pprev;
503 *pprev = next;
504 if (next)
505 next->pprev = pprev;
506 }
507
508 static inline void hlist_del(struct hlist_node *n)
509 {
510 __hlist_del(n);
511 n->next = NULL;
512 n->pprev = NULL;
513 }
514
515 static inline void hlist_del_init(struct hlist_node *n)
516 {
517 if (!hlist_unhashed(n)) {
518 __hlist_del(n);
519 INIT_HLIST_NODE(n);
520 }
521 }
522
523
524 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
525 {
526 struct hlist_node *first = h->first;
527 n->next = first;
528 if (first)
529 first->pprev = &n->next;
530 h->first = n;
531 n->pprev = &h->first;
532 }
533
534
535 /* next must be != NULL */
536 static inline void hlist_add_before(struct hlist_node *n,
537 struct hlist_node *next)
538 {
539 n->pprev = next->pprev;
540 n->next = next;
541 next->pprev = &n->next;
542 *(n->pprev) = n;
543 }
544
545 static inline void hlist_add_after(struct hlist_node *n,
546 struct hlist_node *next)
547 {
548 next->next = n->next;
549 n->next = next;
550 next->pprev = &n->next;
551
552 if(next->next)
553 next->next->pprev = &next->next;
554 }
555
556 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
557
558 #define hlist_for_each(pos, head) \
559 for (pos = (head)->first; pos; pos = pos->next)
560
561 #define hlist_for_each_safe(pos, n, head) \
562 for (pos = (head)->first; pos; pos = n)
563
564 /**
565 * hlist_for_each_entry - iterate over list of given type
566 * @tpos: the type * to use as a loop cursor.
567 * @pos: the &struct hlist_node to use as a loop cursor.
568 * @head: the head for your list.
569 * @member: the name of the hlist_node within the struct.
570 */
571 #define hlist_for_each_entry(tpos, pos, head, member) \
572 for (pos = (head)->first; pos && \
573 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
574 pos = pos->next)
575
576 /**
577 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
578 * @tpos: the type * to use as a loop cursor.
579 * @pos: the &struct hlist_node to use as a loop cursor.
580 * @member: the name of the hlist_node within the struct.
581 */
582 #define hlist_for_each_entry_continue(tpos, pos, member) \
583 for (pos = (pos)->next; pos && \
584 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
585 pos = pos->next)
586
587 /**
588 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
589 * @tpos: the type * to use as a loop cursor.
590 * @pos: the &struct hlist_node to use as a loop cursor.
591 * @member: the name of the hlist_node within the struct.
592 */
593 #define hlist_for_each_entry_from(tpos, pos, member) \
594 for (; pos && \
595 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
596 pos = pos->next)
597
598 /**
599 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
600 * @tpos: the type * to use as a loop cursor.
601 * @pos: the &struct hlist_node to use as a loop cursor.
602 * @n: another &struct hlist_node to use as temporary storage
603 * @head: the head for your list.
604 * @member: the name of the hlist_node within the struct.
605 */
606 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
607 for (pos = (head)->first; \
608 pos && ({ n = pos->next; 1; }) && \
609 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
610 pos = n)
611
612 #endif