include/list.h

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2006 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #ifndef __LIST_H__
   7 #define __LIST_H__
   8
   9 /*
  10  * This undef is here because BSD 4.4 added some LIST_ macros into system
  11  * header file sys/queue.h. This header is included in many other system
  12  * headers and thus causes "macro redefined" warnings.
  13  *
  14  * As OS X is kind of a derivate of BSD, this affects OS X too.
  15  *
  16  * To use our own LIST_ macros (copied from kernel code), we have to
  17  * at first undefine the conflicting system macros.
  18  *
  19  */
  20 #undef LIST_HEAD
  21 #undef LIST_HEAD_INIT
  22
  23 /*
  24  * Simple, generic doubly-linked list implementation.
  25  */
  26
  27 struct list_head {
  28         struct list_head *next;
  29         struct list_head *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 #define INIT_LIST_HEAD(list) list_head_init(list)
  38 static inline void list_head_init(struct list_head *list)
  39 {
  40         list->next = list->prev = list;
  41 }
  42
  43 static inline void list_head_destroy(struct list_head *list)
  44 {
  45         list->next = list->prev = NULL;
  46 }
  47
  48 static inline void __list_add(struct list_head *add,
  49                               struct list_head *prev, struct list_head *next)
  50 {
  51         next->prev = add;
  52         add->next = next;
  53         add->prev = prev;
  54         prev->next = add;
  55 }
  56
  57 static inline void list_add(struct list_head *add, struct list_head *head)
  58 {
  59         __list_add(add, head, head->next);
  60 }
  61
  62 static inline void list_add_tail(struct list_head *add, struct list_head *head)
  63 {
  64         __list_add(add, head->prev, head);
  65 }
  66
  67 static inline void __list_del(struct list_head *prev, struct list_head *next)
  68 {
  69         next->prev = prev;
  70         prev->next = next;
  71 }
  72
  73 static inline void list_del_init(struct list_head *entry)
  74 {
  75         __list_del(entry->prev, entry->next);
  76         list_head_init(entry);
  77 }
  78
  79 static inline void list_del(struct list_head *entry)
  80 {
  81         __list_del(entry->prev, entry->next);
  82 }
  83
  84 static inline void list_move(struct list_head *list, struct list_head *head)
  85 {
  86         __list_del(list->prev, list->next);
  87         list_add(list, head);
  88 }
  89
  90 static inline void list_move_tail(struct list_head *list, struct list_head *head)
  91 {
  92         __list_del(list->prev, list->next);
  93         list_add_tail(list, head);
  94 }
  95
  96 static inline int list_empty(const struct list_head *head)
  97 {
  98         return head->next == head;
  99 }
 100
 101 static inline void __list_splice(struct list_head *list,
 102                                  struct list_head *prev,
 103                                  struct list_head *next)
 104 {
 105         struct list_head *first = list->next;
 106         struct list_head *last = list->prev;
 107
 108         first->prev = prev;
 109         prev->next = first;
 110
 111         last->next = next;
 112         next->prev = last;
 113 }
 114
 115 static inline void list_splice(struct list_head *list, struct list_head *head)
 116 {
 117         if (!list_empty(list))
 118                 __list_splice(list, head, head->next);
 119 }
 120
 121 static inline void list_splice_init(struct list_head *list,
 122                                     struct list_head *head)
 123 {
 124         if (!list_empty(list)) {
 125                 __list_splice(list, head, head->next);
 126                 list_head_init(list);
 127         }
 128 }
 129
 130 #define list_entry(ptr, type, member) ({                        \
 131         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 132         (type *)( (char *)__mptr - offsetof(type,member) );})
 133
 134 #define list_for_each(pos, head) \
 135         for (pos = (head)->next; pos != (head); pos = pos->next)
 136
 137 #define list_for_each_safe(pos, n, head) \
 138         for (pos = (head)->next, n = pos->next; pos != (head); \
 139                 pos = n, n = pos->next)
 140
 141 #define list_for_each_entry(pos, head, member)                          \
 142         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 143              &pos->member != (head);    \
 144              pos = list_entry(pos->member.next, typeof(*pos), member))
 145
 146 #define list_for_each_entry_safe(pos, n, head, member)                  \
 147         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 148                 n = list_entry(pos->member.next, typeof(*pos), member); \
 149              &pos->member != (head);                                    \
 150              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 151
 152 #define list_first_entry(ptr, type, member) \
 153         list_entry((ptr)->next, type, member)
 154
 155 #define container_of(ptr, type, member) ({                      \
 156         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 157         (type *)( (char *)__mptr - offsetof(type,member) );})
 158
 159 void list_sort(void *priv, struct list_head *head,
 160                int (*cmp)(void *priv, struct list_head *a,
 161                           struct list_head *b));
 162
 163 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
 164
 165 /**
 166  * list_splice_tail_init - join two lists and reinitialise the emptied list
 167  * @list: the new list to add.
 168  * @head: the place to add it in the first list.
 169  *
 170  * Each of the lists is a queue.
 171  * The list at @list is reinitialised
 172  */
 173 static inline void list_splice_tail_init(struct list_head *list,
 174                                          struct list_head *head)
 175 {
 176         if (!list_empty(list)) {
 177                 __list_splice(list, head->prev, head);
 178                 INIT_LIST_HEAD(list);
 179         }
 180 }
 181
 182 /**
 183  * list_last_entry - get the last element from a list
 184  * @ptr:        the list head to take the element from.
 185  * @type:       the type of the struct this is embedded in.
 186  * @member:     the name of the list_head within the struct.
 187  *
 188  * Note, that list is expected to be not empty.
 189  */
 190 #define list_last_entry(ptr, type, member) \
 191         list_entry((ptr)->prev, type, member)
 192
 193 /**
 194  * list_prev_entry - get the prev element in list
 195  * @pos:        the type * to cursor
 196  * @member:     the name of the list_head within the struct.
 197  */
 198 #define list_prev_entry(pos, member) \
 199         list_entry((pos)->member.prev, typeof(*(pos)), member)
 200
 201 /**
 202  * list_for_each_entry_reverse - iterate backwards over list of given type.
 203  * @pos:        the type * to use as a loop cursor.
 204  * @head:       the head for your list.
 205  * @member:     the name of the list_head within the struct.
 206  */
 207 #define list_for_each_entry_reverse(pos, head, member)                  \
 208         for (pos = list_last_entry(head, typeof(*pos), member);         \
 209              &pos->member != (head);                                    \
 210              pos = list_prev_entry(pos, member))
 211
 212 #endif  /* __LIST_H__ */