~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/list.h

Version: ~ [ linux-5.2-rc1 ] ~ [ linux-5.1.2 ] ~ [ linux-5.0.16 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.43 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.119 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.176 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.179 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.139 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.67 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp