Fix delta path handling.
[project/uci.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_last - tests whether @list is the last entry in list @head
171 * @list: the entry to test
172 * @head: the head of the list
173 */
174 static inline int list_is_last(const struct list_head *list,
175 const struct list_head *head)
176 {
177 return list->next == head;
178 }
179
180 /**
181 * list_empty - tests whether a list is empty
182 * @head: the list to test.
183 */
184 static inline int list_empty(const struct list_head *head)
185 {
186 return head->next == head;
187 }
188
189 /**
190 * list_empty_careful - tests whether a list is empty and not being modified
191 * @head: the list to test
192 *
193 * Description:
194 * tests whether a list is empty _and_ checks that no other CPU might be
195 * in the process of modifying either member (next or prev)
196 *
197 * NOTE: using list_empty_careful() without synchronization
198 * can only be safe if the only activity that can happen
199 * to the list entry is list_del_init(). Eg. it cannot be used
200 * if another CPU could re-list_add() it.
201 */
202 static inline int list_empty_careful(const struct list_head *head)
203 {
204 struct list_head *next = head->next;
205 return (next == head) && (next == head->prev);
206 }
207
208 static inline void __list_splice(struct list_head *list,
209 struct list_head *head)
210 {
211 struct list_head *first = list->next;
212 struct list_head *last = list->prev;
213 struct list_head *at = head->next;
214
215 first->prev = head;
216 head->next = first;
217
218 last->next = at;
219 at->prev = last;
220 }
221
222 /**
223 * list_splice - join two lists
224 * @list: the new list to add.
225 * @head: the place to add it in the first list.
226 */
227 static inline void list_splice(struct list_head *list, struct list_head *head)
228 {
229 if (!list_empty(list))
230 __list_splice(list, head);
231 }
232
233 /**
234 * list_splice_init - join two lists and reinitialise the emptied list.
235 * @list: the new list to add.
236 * @head: the place to add it in the first list.
237 *
238 * The list at @list is reinitialised
239 */
240 static inline void list_splice_init(struct list_head *list,
241 struct list_head *head)
242 {
243 if (!list_empty(list)) {
244 __list_splice(list, head);
245 INIT_LIST_HEAD(list);
246 }
247 }
248
249 /**
250 * list_entry - get the struct for this entry
251 * @ptr: the &struct list_head pointer.
252 * @type: the type of the struct this is embedded in.
253 * @member: the name of the list_struct within the struct.
254 */
255 #define list_entry(ptr, type, member) \
256 container_of(ptr, type, member)
257
258 /**
259 * list_first_entry - get the first element from a list
260 * @ptr: the list head to take the element from.
261 * @type: the type of the struct this is embedded in.
262 * @member: the name of the list_struct within the struct.
263 *
264 * Note, that list is expected to be not empty.
265 */
266 #define list_first_entry(ptr, type, member) \
267 list_entry((ptr)->next, type, member)
268
269 /**
270 * list_for_each - iterate over a list
271 * @pos: the &struct list_head to use as a loop cursor.
272 * @head: the head for your list.
273 */
274 #define list_for_each(pos, head) \
275 for (pos = (head)->next; pos != (head); \
276 pos = pos->next)
277
278 /**
279 * __list_for_each - iterate over a list
280 * @pos: the &struct list_head to use as a loop cursor.
281 * @head: the head for your list.
282 *
283 * This variant differs from list_for_each() in that it's the
284 * simplest possible list iteration code, no prefetching is done.
285 * Use this for code that knows the list to be very short (empty
286 * or 1 entry) most of the time.
287 */
288 #define __list_for_each(pos, head) \
289 for (pos = (head)->next; pos != (head); pos = pos->next)
290
291 /**
292 * list_for_each_prev - iterate over a list backwards
293 * @pos: the &struct list_head to use as a loop cursor.
294 * @head: the head for your list.
295 */
296 #define list_for_each_prev(pos, head) \
297 for (pos = (head)->prev; pos != (head); \
298 pos = pos->prev)
299
300 /**
301 * list_for_each_safe - iterate over a list safe against removal of list entry
302 * @pos: the &struct list_head to use as a loop cursor.
303 * @n: another &struct list_head to use as temporary storage
304 * @head: the head for your list.
305 */
306 #define list_for_each_safe(pos, n, head) \
307 for (pos = (head)->next, n = pos->next; pos != (head); \
308 pos = n, n = pos->next)
309
310 /**
311 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
312 * @pos: the &struct list_head to use as a loop cursor.
313 * @n: another &struct list_head to use as temporary storage
314 * @head: the head for your list.
315 */
316 #define list_for_each_prev_safe(pos, n, head) \
317 for (pos = (head)->prev, n = pos->prev; \
318 pos != (head); \
319 pos = n, n = pos->prev)
320
321 /**
322 * list_for_each_entry - iterate over list of given type
323 * @pos: the type * to use as a loop cursor.
324 * @head: the head for your list.
325 * @member: the name of the list_struct within the struct.
326 */
327 #define list_for_each_entry(pos, head, member) \
328 for (pos = list_entry((head)->next, typeof(*pos), member); \
329 &pos->member != (head); \
330 pos = list_entry(pos->member.next, typeof(*pos), member))
331
332 /**
333 * list_for_each_entry_reverse - iterate backwards 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_reverse(pos, head, member) \
339 for (pos = list_entry((head)->prev, typeof(*pos), member); \
340 &pos->member != (head); \
341 pos = list_entry(pos->member.prev, typeof(*pos), member))
342
343 /**
344 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
345 * @pos: the type * to use as a start point
346 * @head: the head of the list
347 * @member: the name of the list_struct within the struct.
348 *
349 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
350 */
351 #define list_prepare_entry(pos, head, member) \
352 ((pos) ? : list_entry(head, typeof(*pos), member))
353
354 /**
355 * list_for_each_entry_continue - continue iteration over list of given type
356 * @pos: the type * to use as a loop cursor.
357 * @head: the head for your list.
358 * @member: the name of the list_struct within the struct.
359 *
360 * Continue to iterate over list of given type, continuing after
361 * the current position.
362 */
363 #define list_for_each_entry_continue(pos, head, member) \
364 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
365 &pos->member != (head); \
366 pos = list_entry(pos->member.next, typeof(*pos), member))
367
368 /**
369 * list_for_each_entry_continue_reverse - iterate backwards from the given point
370 * @pos: the type * to use as a loop cursor.
371 * @head: the head for your list.
372 * @member: the name of the list_struct within the struct.
373 *
374 * Start to iterate over list of given type backwards, continuing after
375 * the current position.
376 */
377 #define list_for_each_entry_continue_reverse(pos, head, member) \
378 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
379 &pos->member != (head); \
380 pos = list_entry(pos->member.prev, typeof(*pos), member))
381
382 /**
383 * list_for_each_entry_from - iterate over list of given type from the current point
384 * @pos: the type * to use as a loop cursor.
385 * @head: the head for your list.
386 * @member: the name of the list_struct within the struct.
387 *
388 * Iterate over list of given type, continuing from current position.
389 */
390 #define list_for_each_entry_from(pos, head, member) \
391 for (; &pos->member != (head); \
392 pos = list_entry(pos->member.next, typeof(*pos), member))
393
394 /**
395 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
396 * @pos: the type * to use as a loop cursor.
397 * @n: another type * to use as temporary storage
398 * @head: the head for your list.
399 * @member: the name of the list_struct within the struct.
400 */
401 #define list_for_each_entry_safe(pos, n, head, member) \
402 for (pos = list_entry((head)->next, typeof(*pos), member), \
403 n = list_entry(pos->member.next, typeof(*pos), member); \
404 &pos->member != (head); \
405 pos = n, n = list_entry(n->member.next, typeof(*n), member))
406
407 /**
408 * list_for_each_entry_safe_continue
409 * @pos: the type * to use as a loop cursor.
410 * @n: another type * to use as temporary storage
411 * @head: the head for your list.
412 * @member: the name of the list_struct within the struct.
413 *
414 * Iterate over list of given type, continuing after current point,
415 * safe against removal of list entry.
416 */
417 #define list_for_each_entry_safe_continue(pos, n, head, member) \
418 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
419 n = list_entry(pos->member.next, typeof(*pos), member); \
420 &pos->member != (head); \
421 pos = n, n = list_entry(n->member.next, typeof(*n), member))
422
423 /**
424 * list_for_each_entry_safe_from
425 * @pos: the type * to use as a loop cursor.
426 * @n: another type * to use as temporary storage
427 * @head: the head for your list.
428 * @member: the name of the list_struct within the struct.
429 *
430 * Iterate over list of given type from current point, safe against
431 * removal of list entry.
432 */
433 #define list_for_each_entry_safe_from(pos, n, head, member) \
434 for (n = list_entry(pos->member.next, typeof(*pos), member); \
435 &pos->member != (head); \
436 pos = n, n = list_entry(n->member.next, typeof(*n), member))
437
438 /**
439 * list_for_each_entry_safe_reverse
440 * @pos: the type * to use as a loop cursor.
441 * @n: another type * to use as temporary storage
442 * @head: the head for your list.
443 * @member: the name of the list_struct within the struct.
444 *
445 * Iterate backwards over list of given type, safe against removal
446 * of list entry.
447 */
448 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
449 for (pos = list_entry((head)->prev, typeof(*pos), member), \
450 n = list_entry(pos->member.prev, typeof(*pos), member); \
451 &pos->member != (head); \
452 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
453
454 /*
455 * Double linked lists with a single pointer list head.
456 * Mostly useful for hash tables where the two pointer list head is
457 * too wasteful.
458 * You lose the ability to access the tail in O(1).
459 */
460
461 struct hlist_head {
462 struct hlist_node *first;
463 };
464
465 struct hlist_node {
466 struct hlist_node *next, **pprev;
467 };
468
469 #define HLIST_HEAD_INIT { .first = NULL }
470 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
471 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
472 static inline void INIT_HLIST_NODE(struct hlist_node *h)
473 {
474 h->next = NULL;
475 h->pprev = NULL;
476 }
477
478 static inline int hlist_unhashed(const struct hlist_node *h)
479 {
480 return !h->pprev;
481 }
482
483 static inline int hlist_empty(const struct hlist_head *h)
484 {
485 return !h->first;
486 }
487
488 static inline void __hlist_del(struct hlist_node *n)
489 {
490 struct hlist_node *next = n->next;
491 struct hlist_node **pprev = n->pprev;
492 *pprev = next;
493 if (next)
494 next->pprev = pprev;
495 }
496
497 static inline void hlist_del(struct hlist_node *n)
498 {
499 __hlist_del(n);
500 n->next = NULL;
501 n->pprev = NULL;
502 }
503
504 static inline void hlist_del_init(struct hlist_node *n)
505 {
506 if (!hlist_unhashed(n)) {
507 __hlist_del(n);
508 INIT_HLIST_NODE(n);
509 }
510 }
511
512
513 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
514 {
515 struct hlist_node *first = h->first;
516 n->next = first;
517 if (first)
518 first->pprev = &n->next;
519 h->first = n;
520 n->pprev = &h->first;
521 }
522
523
524 /* next must be != NULL */
525 static inline void hlist_add_before(struct hlist_node *n,
526 struct hlist_node *next)
527 {
528 n->pprev = next->pprev;
529 n->next = next;
530 next->pprev = &n->next;
531 *(n->pprev) = n;
532 }
533
534 static inline void hlist_add_after(struct hlist_node *n,
535 struct hlist_node *next)
536 {
537 next->next = n->next;
538 n->next = next;
539 next->pprev = &n->next;
540
541 if(next->next)
542 next->next->pprev = &next->next;
543 }
544
545 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
546
547 #define hlist_for_each(pos, head) \
548 for (pos = (head)->first; pos; pos = pos->next)
549
550 #define hlist_for_each_safe(pos, n, head) \
551 for (pos = (head)->first; pos; pos = n)
552
553 /**
554 * hlist_for_each_entry - iterate over list of given type
555 * @tpos: the type * to use as a loop cursor.
556 * @pos: the &struct hlist_node to use as a loop cursor.
557 * @head: the head for your list.
558 * @member: the name of the hlist_node within the struct.
559 */
560 #define hlist_for_each_entry(tpos, pos, head, member) \
561 for (pos = (head)->first; pos && \
562 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
563 pos = pos->next)
564
565 /**
566 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
567 * @tpos: the type * to use as a loop cursor.
568 * @pos: the &struct hlist_node to use as a loop cursor.
569 * @member: the name of the hlist_node within the struct.
570 */
571 #define hlist_for_each_entry_continue(tpos, pos, member) \
572 for (pos = (pos)->next; pos && \
573 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
574 pos = pos->next)
575
576 /**
577 * hlist_for_each_entry_from - iterate over a hlist continuing from 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_from(tpos, pos, member) \
583 for (; pos && \
584 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
585 pos = pos->next)
586
587 /**
588 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
589 * @tpos: the type * to use as a loop cursor.
590 * @pos: the &struct hlist_node to use as a loop cursor.
591 * @n: another &struct hlist_node to use as temporary storage
592 * @head: the head for your list.
593 * @member: the name of the hlist_node within the struct.
594 */
595 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
596 for (pos = (head)->first; \
597 pos && ({ n = pos->next; 1; }) && \
598 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
599 pos = n)
600
601 #endif