Branch data Line data Source code
1 : : #ifndef _LINUX_LIST_H
2 : : #define _LINUX_LIST_H
3 : :
4 : : #include <linux/types.h>
5 : : #include <linux/stddef.h>
6 : : #include <linux/poison.h>
7 : : #include <linux/const.h>
8 : :
9 : : /*
10 : : * Simple doubly linked list implementation.
11 : : *
12 : : * Some of the internal functions ("__xxx") are useful when
13 : : * manipulating whole lists rather than single entries, as
14 : : * sometimes we already know the next/prev entries and we can
15 : : * generate better code by using them directly rather than
16 : : * using the generic single-entry routines.
17 : : */
18 : :
19 : : #define LIST_HEAD_INIT(name) { &(name), &(name) }
20 : :
21 : : #define LIST_HEAD(name) \
22 : : struct list_head name = LIST_HEAD_INIT(name)
23 : :
24 : : static inline void INIT_LIST_HEAD(struct list_head *list)
25 : : {
26 : 158003258 : list->next = list;
27 : 125540551 : list->prev = list;
28 : : }
29 : :
30 : : /*
31 : : * Insert a new entry between two known consecutive entries.
32 : : *
33 : : * This is only for internal list manipulation where we know
34 : : * the prev/next entries already!
35 : : */
36 : : #ifndef CONFIG_DEBUG_LIST
37 : : static inline void __list_add(struct list_head *new,
38 : : struct list_head *prev,
39 : : struct list_head *next)
40 : : {
41 : 263246350 : next->prev = new;
42 : 263246350 : new->next = next;
43 : 263246350 : new->prev = prev;
44 : 231251720 : prev->next = new;
45 : : }
46 : : #else
47 : : extern void __list_add(struct list_head *new,
48 : : struct list_head *prev,
49 : : struct list_head *next);
50 : : #endif
51 : :
52 : : /**
53 : : * list_add - add a new entry
54 : : * @new: new entry to be added
55 : : * @head: list head to add it after
56 : : *
57 : : * Insert a new entry after the specified head.
58 : : * This is good for implementing stacks.
59 : : */
60 : : static inline void list_add(struct list_head *new, struct list_head *head)
61 : : {
62 : 144967076 : __list_add(new, head, head->next);
63 : : }
64 : :
65 : :
66 : : /**
67 : : * list_add_tail - add a new entry
68 : : * @new: new entry to be added
69 : : * @head: list head to add it before
70 : : *
71 : : * Insert a new entry before the specified head.
72 : : * This is useful for implementing queues.
73 : : */
74 : : static inline void list_add_tail(struct list_head *new, struct list_head *head)
75 : : {
76 : 118278711 : __list_add(new, head->prev, head);
77 : : }
78 : :
79 : : /*
80 : : * Delete a list entry by making the prev/next entries
81 : : * point to each other.
82 : : *
83 : : * This is only for internal list manipulation where we know
84 : : * the prev/next entries already!
85 : : */
86 : : static inline void __list_del(struct list_head * prev, struct list_head * next)
87 : : {
88 : 252441433 : next->prev = prev;
89 : 252422791 : prev->next = next;
90 : : }
91 : :
92 : : /**
93 : : * list_del - deletes entry from list.
94 : : * @entry: the element to delete from the list.
95 : : * Note: list_empty() on entry does not return true after this, the entry is
96 : : * in an undefined state.
97 : : */
98 : : #ifndef CONFIG_DEBUG_LIST
99 : : static inline void __list_del_entry(struct list_head *entry)
100 : : {
101 : 37669334 : __list_del(entry->prev, entry->next);
102 : : }
103 : :
104 : : static inline void list_del(struct list_head *entry)
105 : : {
106 : 213145770 : __list_del(entry->prev, entry->next);
107 : 213145770 : entry->next = LIST_POISON1;
108 : 188021185 : entry->prev = LIST_POISON2;
109 : : }
110 : : #else
111 : : extern void __list_del_entry(struct list_head *entry);
112 : : extern void list_del(struct list_head *entry);
113 : : #endif
114 : :
115 : : /**
116 : : * list_replace - replace old entry by new one
117 : : * @old : the element to be replaced
118 : : * @new : the new element to insert
119 : : *
120 : : * If @old was empty, it will be overwritten.
121 : : */
122 : : static inline void list_replace(struct list_head *old,
123 : : struct list_head *new)
124 : : {
125 : 16693643 : new->next = old->next;
126 : 16693643 : new->next->prev = new;
127 : 16693643 : new->prev = old->prev;
128 : 16693643 : new->prev->next = new;
129 : : }
130 : :
131 : : static inline void list_replace_init(struct list_head *old,
132 : : struct list_head *new)
133 : : {
134 : : list_replace(old, new);
135 : : INIT_LIST_HEAD(old);
136 : : }
137 : :
138 : : /**
139 : : * list_del_init - deletes entry from list and reinitialize it.
140 : : * @entry: the element to delete from the list.
141 : : */
142 : : static inline void list_del_init(struct list_head *entry)
143 : : {
144 : : __list_del_entry(entry);
145 : : INIT_LIST_HEAD(entry);
146 : : }
147 : :
148 : : /**
149 : : * list_move - delete from one list and add as another's head
150 : : * @list: the entry to move
151 : : * @head: the head that will precede our entry
152 : : */
153 : : static inline void list_move(struct list_head *list, struct list_head *head)
154 : : {
155 : : __list_del_entry(list);
156 : : list_add(list, head);
157 : : }
158 : :
159 : : /**
160 : : * list_move_tail - delete from one list and add as another's tail
161 : : * @list: the entry to move
162 : : * @head: the head that will follow our entry
163 : : */
164 : : static inline void list_move_tail(struct list_head *list,
165 : : struct list_head *head)
166 : : {
167 : : __list_del_entry(list);
168 : : list_add_tail(list, head);
169 : : }
170 : :
171 : : /**
172 : : * list_is_last - tests whether @list is the last entry in list @head
173 : : * @list: the entry to test
174 : : * @head: the head of the list
175 : : */
176 : : static inline int list_is_last(const struct list_head *list,
177 : : const struct list_head *head)
178 : : {
179 : : return list->next == head;
180 : : }
181 : :
182 : : /**
183 : : * list_empty - tests whether a list is empty
184 : : * @head: the list to test.
185 : : */
186 : : static inline int list_empty(const struct list_head *head)
187 : : {
188 : 651112008 : return head->next == head;
189 : : }
190 : :
191 : : /**
192 : : * list_empty_careful - tests whether a list is empty and not being modified
193 : : * @head: the list to test
194 : : *
195 : : * Description:
196 : : * tests whether a list is empty _and_ checks that no other CPU might be
197 : : * in the process of modifying either member (next or prev)
198 : : *
199 : : * NOTE: using list_empty_careful() without synchronization
200 : : * can only be safe if the only activity that can happen
201 : : * to the list entry is list_del_init(). Eg. it cannot be used
202 : : * if another CPU could re-list_add() it.
203 : : */
204 : : static inline int list_empty_careful(const struct list_head *head)
205 : : {
206 : 985500 : struct list_head *next = head->next;
207 [ + + ][ + + ]: 985500 : return (next == head) && (next == head->prev);
[ # # ][ # # ]
208 : : }
209 : :
210 : : /**
211 : : * list_rotate_left - rotate the list to the left
212 : : * @head: the head of the list
213 : : */
214 : : static inline void list_rotate_left(struct list_head *head)
215 : : {
216 : : struct list_head *first;
217 : :
218 [ # # ][ # # ]: 0 : if (!list_empty(head)) {
219 : : first = head->next;
220 : : list_move_tail(first, head);
221 : : }
222 : : }
223 : :
224 : : /**
225 : : * list_is_singular - tests whether a list has just one entry.
226 : : * @head: the list to test.
227 : : */
228 : : static inline int list_is_singular(const struct list_head *head)
229 : : {
230 [ + - ][ + + ]: 183783 : return !list_empty(head) && (head->next == head->prev);
[ + + ][ + + ]
[ + + ][ + + ]
231 : : }
232 : :
233 : : static inline void __list_cut_position(struct list_head *list,
234 : : struct list_head *head, struct list_head *entry)
235 : : {
236 : : struct list_head *new_first = entry->next;
237 : : list->next = head->next;
238 : : list->next->prev = list;
239 : : list->prev = entry;
240 : : entry->next = list;
241 : : head->next = new_first;
242 : : new_first->prev = head;
243 : : }
244 : :
245 : : /**
246 : : * list_cut_position - cut a list into two
247 : : * @list: a new list to add all removed entries
248 : : * @head: a list with entries
249 : : * @entry: an entry within head, could be the head itself
250 : : * and if so we won't cut the list
251 : : *
252 : : * This helper moves the initial part of @head, up to and
253 : : * including @entry, from @head to @list. You should
254 : : * pass on @entry an element you know is on @head. @list
255 : : * should be an empty list or a list you do not care about
256 : : * losing its data.
257 : : *
258 : : */
259 : : static inline void list_cut_position(struct list_head *list,
260 : : struct list_head *head, struct list_head *entry)
261 : : {
262 : : if (list_empty(head))
263 : : return;
264 : : if (list_is_singular(head) &&
265 : : (head->next != entry && head != entry))
266 : : return;
267 : : if (entry == head)
268 : : INIT_LIST_HEAD(list);
269 : : else
270 : : __list_cut_position(list, head, entry);
271 : : }
272 : :
273 : : static inline void __list_splice(const struct list_head *list,
274 : : struct list_head *prev,
275 : : struct list_head *next)
276 : : {
277 : : struct list_head *first = list->next;
278 : 2586357 : struct list_head *last = list->prev;
279 : :
280 : 2586357 : first->prev = prev;
281 : 2586357 : prev->next = first;
282 : :
283 : 2586357 : last->next = next;
284 : 2584114 : next->prev = last;
285 : : }
286 : :
287 : : /**
288 : : * list_splice - join two lists, this is designed for stacks
289 : : * @list: the new list to add.
290 : : * @head: the place to add it in the first list.
291 : : */
292 : : static inline void list_splice(const struct list_head *list,
293 : : struct list_head *head)
294 : : {
295 [ + + ][ # # ]: 430420 : if (!list_empty(list))
[ # # ][ # # ]
[ + + ][ # # ]
[ # # ]
296 : 7225 : __list_splice(list, head, head->next);
297 : : }
298 : :
299 : : /**
300 : : * list_splice_tail - join two lists, each list being a queue
301 : : * @list: the new list to add.
302 : : * @head: the place to add it in the first list.
303 : : */
304 : : static inline void list_splice_tail(struct list_head *list,
305 : : struct list_head *head)
306 : : {
307 [ + + ][ # # ]: 2342706 : if (!list_empty(list))
[ # # ]
[ # # # # ]
308 : 2342695 : __list_splice(list, head->prev, head);
309 : : }
310 : :
311 : : /**
312 : : * list_splice_init - join two lists and reinitialise the emptied list.
313 : : * @list: the new list to add.
314 : : * @head: the place to add it in the first list.
315 : : *
316 : : * The list at @list is reinitialised
317 : : */
318 : : static inline void list_splice_init(struct list_head *list,
319 : : struct list_head *head)
320 : : {
321 [ + + ][ + + ]: 655543 : if (!list_empty(list)) {
[ # # # # ]
[ - + # #
# # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
322 : 236437 : __list_splice(list, head, head->next);
323 : : INIT_LIST_HEAD(list);
324 : : }
325 : : }
326 : :
327 : : /**
328 : : * list_splice_tail_init - join two lists and reinitialise the emptied list
329 : : * @list: the new list to add.
330 : : * @head: the place to add it in the first list.
331 : : *
332 : : * Each of the lists is a queue.
333 : : * The list at @list is reinitialised
334 : : */
335 : : static inline void list_splice_tail_init(struct list_head *list,
336 : : struct list_head *head)
337 : : {
338 [ - + ]: 6 : if (!list_empty(list)) {
[ # # # # ]
339 : 0 : __list_splice(list, head->prev, head);
340 : : INIT_LIST_HEAD(list);
341 : : }
342 : : }
343 : :
344 : : /**
345 : : * list_entry - get the struct for this entry
346 : : * @ptr: the &struct list_head pointer.
347 : : * @type: the type of the struct this is embedded in.
348 : : * @member: the name of the list_struct within the struct.
349 : : */
350 : : #define list_entry(ptr, type, member) \
351 : : container_of(ptr, type, member)
352 : :
353 : : /**
354 : : * list_first_entry - get the first element from a list
355 : : * @ptr: the list head to take the element from.
356 : : * @type: the type of the struct this is embedded in.
357 : : * @member: the name of the list_struct within the struct.
358 : : *
359 : : * Note, that list is expected to be not empty.
360 : : */
361 : : #define list_first_entry(ptr, type, member) \
362 : : list_entry((ptr)->next, type, member)
363 : :
364 : : /**
365 : : * list_last_entry - get the last element from a list
366 : : * @ptr: the list head to take the element from.
367 : : * @type: the type of the struct this is embedded in.
368 : : * @member: the name of the list_struct within the struct.
369 : : *
370 : : * Note, that list is expected to be not empty.
371 : : */
372 : : #define list_last_entry(ptr, type, member) \
373 : : list_entry((ptr)->prev, type, member)
374 : :
375 : : /**
376 : : * list_first_entry_or_null - get the first element from a list
377 : : * @ptr: the list head to take the element from.
378 : : * @type: the type of the struct this is embedded in.
379 : : * @member: the name of the list_struct within the struct.
380 : : *
381 : : * Note that if the list is empty, it returns NULL.
382 : : */
383 : : #define list_first_entry_or_null(ptr, type, member) \
384 : : (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
385 : :
386 : : /**
387 : : * list_next_entry - get the next element in list
388 : : * @pos: the type * to cursor
389 : : * @member: the name of the list_struct within the struct.
390 : : */
391 : : #define list_next_entry(pos, member) \
392 : : list_entry((pos)->member.next, typeof(*(pos)), member)
393 : :
394 : : /**
395 : : * list_prev_entry - get the prev element in list
396 : : * @pos: the type * to cursor
397 : : * @member: the name of the list_struct within the struct.
398 : : */
399 : : #define list_prev_entry(pos, member) \
400 : : list_entry((pos)->member.prev, typeof(*(pos)), member)
401 : :
402 : : /**
403 : : * list_for_each - iterate over a list
404 : : * @pos: the &struct list_head to use as a loop cursor.
405 : : * @head: the head for your list.
406 : : */
407 : : #define list_for_each(pos, head) \
408 : : for (pos = (head)->next; pos != (head); pos = pos->next)
409 : :
410 : : /**
411 : : * list_for_each_prev - iterate over a list backwards
412 : : * @pos: the &struct list_head to use as a loop cursor.
413 : : * @head: the head for your list.
414 : : */
415 : : #define list_for_each_prev(pos, head) \
416 : : for (pos = (head)->prev; pos != (head); pos = pos->prev)
417 : :
418 : : /**
419 : : * list_for_each_safe - iterate over a list safe against removal of list entry
420 : : * @pos: the &struct list_head to use as a loop cursor.
421 : : * @n: another &struct list_head to use as temporary storage
422 : : * @head: the head for your list.
423 : : */
424 : : #define list_for_each_safe(pos, n, head) \
425 : : for (pos = (head)->next, n = pos->next; pos != (head); \
426 : : pos = n, n = pos->next)
427 : :
428 : : /**
429 : : * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
430 : : * @pos: the &struct list_head to use as a loop cursor.
431 : : * @n: another &struct list_head to use as temporary storage
432 : : * @head: the head for your list.
433 : : */
434 : : #define list_for_each_prev_safe(pos, n, head) \
435 : : for (pos = (head)->prev, n = pos->prev; \
436 : : pos != (head); \
437 : : pos = n, n = pos->prev)
438 : :
439 : : /**
440 : : * list_for_each_entry - iterate over list of given type
441 : : * @pos: the type * to use as a loop cursor.
442 : : * @head: the head for your list.
443 : : * @member: the name of the list_struct within the struct.
444 : : */
445 : : #define list_for_each_entry(pos, head, member) \
446 : : for (pos = list_first_entry(head, typeof(*pos), member); \
447 : : &pos->member != (head); \
448 : : pos = list_next_entry(pos, member))
449 : :
450 : : /**
451 : : * list_for_each_entry_reverse - iterate backwards over list of given type.
452 : : * @pos: the type * to use as a loop cursor.
453 : : * @head: the head for your list.
454 : : * @member: the name of the list_struct within the struct.
455 : : */
456 : : #define list_for_each_entry_reverse(pos, head, member) \
457 : : for (pos = list_last_entry(head, typeof(*pos), member); \
458 : : &pos->member != (head); \
459 : : pos = list_prev_entry(pos, member))
460 : :
461 : : /**
462 : : * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
463 : : * @pos: the type * to use as a start point
464 : : * @head: the head of the list
465 : : * @member: the name of the list_struct within the struct.
466 : : *
467 : : * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
468 : : */
469 : : #define list_prepare_entry(pos, head, member) \
470 : : ((pos) ? : list_entry(head, typeof(*pos), member))
471 : :
472 : : /**
473 : : * list_for_each_entry_continue - continue iteration over list of given type
474 : : * @pos: the type * to use as a loop cursor.
475 : : * @head: the head for your list.
476 : : * @member: the name of the list_struct within the struct.
477 : : *
478 : : * Continue to iterate over list of given type, continuing after
479 : : * the current position.
480 : : */
481 : : #define list_for_each_entry_continue(pos, head, member) \
482 : : for (pos = list_next_entry(pos, member); \
483 : : &pos->member != (head); \
484 : : pos = list_next_entry(pos, member))
485 : :
486 : : /**
487 : : * list_for_each_entry_continue_reverse - iterate backwards from the given point
488 : : * @pos: the type * to use as a loop cursor.
489 : : * @head: the head for your list.
490 : : * @member: the name of the list_struct within the struct.
491 : : *
492 : : * Start to iterate over list of given type backwards, continuing after
493 : : * the current position.
494 : : */
495 : : #define list_for_each_entry_continue_reverse(pos, head, member) \
496 : : for (pos = list_prev_entry(pos, member); \
497 : : &pos->member != (head); \
498 : : pos = list_prev_entry(pos, member))
499 : :
500 : : /**
501 : : * list_for_each_entry_from - iterate over list of given type from the current point
502 : : * @pos: the type * to use as a loop cursor.
503 : : * @head: the head for your list.
504 : : * @member: the name of the list_struct within the struct.
505 : : *
506 : : * Iterate over list of given type, continuing from current position.
507 : : */
508 : : #define list_for_each_entry_from(pos, head, member) \
509 : : for (; &pos->member != (head); \
510 : : pos = list_next_entry(pos, member))
511 : :
512 : : /**
513 : : * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
514 : : * @pos: the type * to use as a loop cursor.
515 : : * @n: another type * to use as temporary storage
516 : : * @head: the head for your list.
517 : : * @member: the name of the list_struct within the struct.
518 : : */
519 : : #define list_for_each_entry_safe(pos, n, head, member) \
520 : : for (pos = list_first_entry(head, typeof(*pos), member), \
521 : : n = list_next_entry(pos, member); \
522 : : &pos->member != (head); \
523 : : pos = n, n = list_next_entry(n, member))
524 : :
525 : : /**
526 : : * list_for_each_entry_safe_continue - continue list iteration safe against removal
527 : : * @pos: the type * to use as a loop cursor.
528 : : * @n: another type * to use as temporary storage
529 : : * @head: the head for your list.
530 : : * @member: the name of the list_struct within the struct.
531 : : *
532 : : * Iterate over list of given type, continuing after current point,
533 : : * safe against removal of list entry.
534 : : */
535 : : #define list_for_each_entry_safe_continue(pos, n, head, member) \
536 : : for (pos = list_next_entry(pos, member), \
537 : : n = list_next_entry(pos, member); \
538 : : &pos->member != (head); \
539 : : pos = n, n = list_next_entry(n, member))
540 : :
541 : : /**
542 : : * list_for_each_entry_safe_from - iterate over list from current point safe against removal
543 : : * @pos: the type * to use as a loop cursor.
544 : : * @n: another type * to use as temporary storage
545 : : * @head: the head for your list.
546 : : * @member: the name of the list_struct within the struct.
547 : : *
548 : : * Iterate over list of given type from current point, safe against
549 : : * removal of list entry.
550 : : */
551 : : #define list_for_each_entry_safe_from(pos, n, head, member) \
552 : : for (n = list_next_entry(pos, member); \
553 : : &pos->member != (head); \
554 : : pos = n, n = list_next_entry(n, member))
555 : :
556 : : /**
557 : : * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
558 : : * @pos: the type * to use as a loop cursor.
559 : : * @n: another type * to use as temporary storage
560 : : * @head: the head for your list.
561 : : * @member: the name of the list_struct within the struct.
562 : : *
563 : : * Iterate backwards over list of given type, safe against removal
564 : : * of list entry.
565 : : */
566 : : #define list_for_each_entry_safe_reverse(pos, n, head, member) \
567 : : for (pos = list_last_entry(head, typeof(*pos), member), \
568 : : n = list_prev_entry(pos, member); \
569 : : &pos->member != (head); \
570 : : pos = n, n = list_prev_entry(n, member))
571 : :
572 : : /**
573 : : * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
574 : : * @pos: the loop cursor used in the list_for_each_entry_safe loop
575 : : * @n: temporary storage used in list_for_each_entry_safe
576 : : * @member: the name of the list_struct within the struct.
577 : : *
578 : : * list_safe_reset_next is not safe to use in general if the list may be
579 : : * modified concurrently (eg. the lock is dropped in the loop body). An
580 : : * exception to this is if the cursor element (pos) is pinned in the list,
581 : : * and list_safe_reset_next is called after re-taking the lock and before
582 : : * completing the current iteration of the loop body.
583 : : */
584 : : #define list_safe_reset_next(pos, n, member) \
585 : : n = list_next_entry(pos, member)
586 : :
587 : : /*
588 : : * Double linked lists with a single pointer list head.
589 : : * Mostly useful for hash tables where the two pointer list head is
590 : : * too wasteful.
591 : : * You lose the ability to access the tail in O(1).
592 : : */
593 : :
594 : : #define HLIST_HEAD_INIT { .first = NULL }
595 : : #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
596 : : #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
597 : : static inline void INIT_HLIST_NODE(struct hlist_node *h)
598 : : {
599 : 11890245 : h->next = NULL;
600 : 4411586 : h->pprev = NULL;
601 : : }
602 : :
603 : : static inline int hlist_unhashed(const struct hlist_node *h)
604 : : {
605 : 9308058 : return !h->pprev;
606 : : }
607 : :
608 : : static inline int hlist_empty(const struct hlist_head *h)
609 : : {
610 : 8699315 : return !h->first;
611 : : }
612 : :
613 : : static inline void __hlist_del(struct hlist_node *n)
614 : : {
615 : 9005896 : struct hlist_node *next = n->next;
616 : 4414306 : struct hlist_node **pprev = n->pprev;
617 : 9006980 : *pprev = next;
618 [ + + ][ + + ]: 10111203 : if (next)
[ + + ]
[ + + + + ]
[ + + ][ - + ]
[ + + ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
619 : 2357525 : next->pprev = pprev;
620 : : }
621 : :
622 : : static inline void hlist_del(struct hlist_node *n)
623 : : {
624 : : __hlist_del(n);
625 : 78 : n->next = LIST_POISON1;
626 : 78 : n->pprev = LIST_POISON2;
627 : : }
628 : :
629 : 3611031 : static inline void hlist_del_init(struct hlist_node *n)
630 : : {
631 [ + - # # ]: 3978076 : if (!hlist_unhashed(n)) {
[ + + + ][ +
- # # +
- ][ # # ]
[ + - ][ + - ]
632 : : __hlist_del(n);
633 : : INIT_HLIST_NODE(n);
634 : : }
635 : : }
636 : :
637 : : static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
638 : : {
639 : 4571695 : struct hlist_node *first = h->first;
640 : 4571695 : n->next = first;
641 [ + + + + ]: 4571957 : if (first)
[ + + + + ]
[ + + ][ # # ]
[ + + # #
# # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
[ # # # # ]
[ # # ][ # # ]
[ # # ]
[ # # # # ]
[ # # ]
642 : 171364 : first->pprev = &n->next;
643 : 4182702 : h->first = n;
644 : 2562204 : n->pprev = &h->first;
645 : : }
646 : :
647 : : /* next must be != NULL */
648 : : static inline void hlist_add_before(struct hlist_node *n,
649 : : struct hlist_node *next)
650 : : {
651 : : n->pprev = next->pprev;
652 : : n->next = next;
653 : : next->pprev = &n->next;
654 : : *(n->pprev) = n;
655 : : }
656 : :
657 : : static inline void hlist_add_after(struct hlist_node *n,
658 : : struct hlist_node *next)
659 : : {
660 : 0 : next->next = n->next;
661 : 0 : n->next = next;
662 : 0 : next->pprev = &n->next;
663 : :
664 [ # # ][ # # ]: 0 : if(next->next)
665 : 0 : next->next->pprev = &next->next;
666 : : }
667 : :
668 : : /* after that we'll appear to be on some hlist and hlist_del will work */
669 : : static inline void hlist_add_fake(struct hlist_node *n)
670 : : {
671 : : n->pprev = &n->next;
672 : : }
673 : :
674 : : /*
675 : : * Move a list from one list head to another. Fixup the pprev
676 : : * reference of the first entry if it exists.
677 : : */
678 : : static inline void hlist_move_list(struct hlist_head *old,
679 : : struct hlist_head *new)
680 : : {
681 : 0 : new->first = old->first;
682 [ # # ]: 0 : if (new->first)
683 : 0 : new->first->pprev = &new->first;
684 : 0 : old->first = NULL;
685 : : }
686 : :
687 : : #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
688 : :
689 : : #define hlist_for_each(pos, head) \
690 : : for (pos = (head)->first; pos ; pos = pos->next)
691 : :
692 : : #define hlist_for_each_safe(pos, n, head) \
693 : : for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
694 : : pos = n)
695 : :
696 : : #define hlist_entry_safe(ptr, type, member) \
697 : : ({ typeof(ptr) ____ptr = (ptr); \
698 : : ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
699 : : })
700 : :
701 : : /**
702 : : * hlist_for_each_entry - iterate over list of given type
703 : : * @pos: the type * to use as a loop cursor.
704 : : * @head: the head for your list.
705 : : * @member: the name of the hlist_node within the struct.
706 : : */
707 : : #define hlist_for_each_entry(pos, head, member) \
708 : : for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
709 : : pos; \
710 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
711 : :
712 : : /**
713 : : * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
714 : : * @pos: the type * to use as a loop cursor.
715 : : * @member: the name of the hlist_node within the struct.
716 : : */
717 : : #define hlist_for_each_entry_continue(pos, member) \
718 : : for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
719 : : pos; \
720 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
721 : :
722 : : /**
723 : : * hlist_for_each_entry_from - iterate over a hlist continuing from current point
724 : : * @pos: the type * to use as a loop cursor.
725 : : * @member: the name of the hlist_node within the struct.
726 : : */
727 : : #define hlist_for_each_entry_from(pos, member) \
728 : : for (; pos; \
729 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
730 : :
731 : : /**
732 : : * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
733 : : * @pos: the type * to use as a loop cursor.
734 : : * @n: another &struct hlist_node to use as temporary storage
735 : : * @head: the head for your list.
736 : : * @member: the name of the hlist_node within the struct.
737 : : */
738 : : #define hlist_for_each_entry_safe(pos, n, head, member) \
739 : : for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
740 : : pos && ({ n = pos->member.next; 1; }); \
741 : : pos = hlist_entry_safe(n, typeof(*pos), member))
742 : :
743 : : #endif
|
