list.h

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #ifndef _LINUX_LIST_H
  20 #define _LINUX_LIST_H
  21
  22 #define LIST_POISON1  ((struct list_head *) 0x00100100)
  23 #define LIST_POISON2  ((struct list_head *) 0x00200200)
  24
  25 /*
  26  * Simple doubly linked list implementation.
  27  *
  28  * Some of the internal functions ("__xxx") are useful when
  29  * manipulating whole lists rather than single entries, as
  30  * sometimes we already know the next/prev entries and we can
  31  * generate better code by using them directly rather than
  32  * using the generic single-entry routines.
  33  */
  34
  35 struct list_head {
  36         struct list_head *next, *prev;
  37 };
  38
  39 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  40
  41 #define LIST_HEAD(name) \
  42         struct list_head name = LIST_HEAD_INIT(name)
  43
  44 static inline void INIT_LIST_HEAD(struct list_head *list)
  45 {
  46         list->next = list;
  47         list->prev = list;
  48 }
  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 #ifndef CONFIG_DEBUG_LIST
  57 static inline void __list_add(struct list_head *xnew,
  58                               struct list_head *prev,
  59                               struct list_head *next)
  60 {
  61         next->prev = xnew;
  62         xnew->next = next;
  63         xnew->prev = prev;
  64         prev->next = xnew;
  65 }
  66 #else
  67 extern void __list_add(struct list_head *xnew,
  68                               struct list_head *prev,
  69                               struct list_head *next);
  70 #endif
  71
  72 /**
  73  * list_add - add a new entry
  74  * @new: new entry to be added
  75  * @head: list head to add it after
  76  *
  77  * Insert a new entry after the specified head.
  78  * This is good for implementing stacks.
  79  */
  80 #ifndef CONFIG_DEBUG_LIST
  81 static inline void list_add(struct list_head *xnew, struct list_head *head)
  82 {
  83         __list_add(xnew, head, head->next);
  84 }
  85 #else
  86 extern void list_add(struct list_head *xnew, struct list_head *head);
  87 #endif
  88
  89
  90 /**
  91  * list_add_tail - add a new entry
  92  * @new: new entry to be added
  93  * @head: list head to add it before
  94  *
  95  * Insert a new entry before the specified head.
  96  * This is useful for implementing queues.
  97  */
  98 static inline void list_add_tail(struct list_head *xnew, struct list_head *head)
  99 {
 100         __list_add(xnew, head->prev, head);
 101 }
 102
 103 /*
 104  * Delete a list entry by making the prev/next entries
 105  * point to each other.
 106  *
 107  * This is only for internal list manipulation where we know
 108  * the prev/next entries already!
 109  */
 110 static inline void __list_del(struct list_head * prev, struct list_head * next)
 111 {
 112         next->prev = prev;
 113         prev->next = next;
 114 }
 115
 116 /**
 117  * list_del - deletes entry from list.
 118  * @entry: the element to delete from the list.
 119  * Note: list_empty on entry does not return true after this, the entry is
 120  * in an undefined state.
 121  */
 122 #ifndef CONFIG_DEBUG_LIST
 123 static inline void list_del(struct list_head *entry)
 124 {
 125         __list_del(entry->prev, entry->next);
 126         entry->next = LIST_POISON1;
 127         entry->prev = LIST_POISON2;
 128 }
 129 #else
 130 extern void list_del(struct list_head *entry);
 131 #endif
 132
 133 /**
 134  * list_replace - replace old entry by new one
 135  * @old : the element to be replaced
 136  * @new : the new element to insert
 137  * Note: if 'old' was empty, it will be overwritten.
 138  */
 139 static inline void list_replace(struct list_head *old,
 140                                 struct list_head *xnew)
 141 {
 142         xnew->next = old->next;
 143         xnew->next->prev = xnew;
 144         xnew->prev = old->prev;
 145         xnew->prev->next = xnew;
 146 }
 147
 148 static inline void list_replace_init(struct list_head *old,
 149                                         struct list_head *xnew)
 150 {
 151         list_replace(old, xnew);
 152         INIT_LIST_HEAD(old);
 153 }
 154 /**
 155  * list_del_init - deletes entry from list and reinitialize it.
 156  * @entry: the element to delete from the list.
 157  */
 158 static inline void list_del_init(struct list_head *entry)
 159 {
 160         __list_del(entry->prev, entry->next);
 161         INIT_LIST_HEAD(entry);
 162 }
 163
 164 /**
 165  * list_move - delete from one list and add as another's head
 166  * @list: the entry to move
 167  * @head: the head that will precede our entry
 168  */
 169 static inline void list_move(struct list_head *list, struct list_head *head)
 170 {
 171         __list_del(list->prev, list->next);
 172         list_add(list, head);
 173 }
 174
 175 /**
 176  * list_move_tail - delete from one list and add as another's tail
 177  * @list: the entry to move
 178  * @head: the head that will follow our entry
 179  */
 180 static inline void list_move_tail(struct list_head *list,
 181                                   struct list_head *head)
 182 {
 183         __list_del(list->prev, list->next);
 184         list_add_tail(list, head);
 185 }
 186
 187 /**
 188  * list_is_last - tests whether @list is the last entry in list @head
 189  * @list: the entry to test
 190  * @head: the head of the list
 191  */
 192 static inline int list_is_last(const struct list_head *list,
 193                                 const struct list_head *head)
 194 {
 195         return list->next == head;
 196 }
 197
 198 /**
 199  * list_empty - tests whether a list is empty
 200  * @head: the list to test.
 201  */
 202 static inline int list_empty(const struct list_head *head)
 203 {
 204         return head->next == head;
 205 }
 206
 207 /**
 208  * list_empty_careful - tests whether a list is empty and not being modified
 209  * @head: the list to test
 210  *
 211  * Description:
 212  * tests whether a list is empty _and_ checks that no other CPU might be
 213  * in the process of modifying either member (next or prev)
 214  *
 215  * NOTE: using list_empty_careful() without synchronization
 216  * can only be safe if the only activity that can happen
 217  * to the list entry is list_del_init(). Eg. it cannot be used
 218  * if another CPU could re-list_add() it.
 219  */
 220 static inline int list_empty_careful(const struct list_head *head)
 221 {
 222         struct list_head *next = head->next;
 223         return (next == head) && (next == head->prev);
 224 }
 225
 226 static inline void __list_splice(struct list_head *list,
 227                                  struct list_head *head)
 228 {
 229         struct list_head *first = list->next;
 230         struct list_head *last = list->prev;
 231         struct list_head *at = head->next;
 232
 233         first->prev = head;
 234         head->next = first;
 235
 236         last->next = at;
 237         at->prev = last;
 238 }
 239
 240 /**
 241  * list_splice - join two lists
 242  * @list: the new list to add.
 243  * @head: the place to add it in the first list.
 244  */
 245 static inline void list_splice(struct list_head *list, struct list_head *head)
 246 {
 247         if (!list_empty(list))
 248                 __list_splice(list, head);
 249 }
 250
 251 /**
 252  * list_splice_init - join two lists and reinitialise the emptied list.
 253  * @list: the new list to add.
 254  * @head: the place to add it in the first list.
 255  *
 256  * The list at @list is reinitialised
 257  */
 258 static inline void list_splice_init(struct list_head *list,
 259                                     struct list_head *head)
 260 {
 261         if (!list_empty(list)) {
 262                 __list_splice(list, head);
 263                 INIT_LIST_HEAD(list);
 264         }
 265 }
 266
 267 /**
 268  * list_entry - get the struct for this entry
 269  * @ptr:        the &struct list_head pointer.
 270  * @type:       the type of the struct this is embedded in.
 271  * @member:     the name of the list_struct within the struct.
 272  */
 273 #define list_entry(ptr, type, member) \
 274         container_of(ptr, type, member)
 275
 276 /**
 277  * list_for_each        -       iterate over a list
 278  * @pos:        the &struct list_head to use as a loop cursor.
 279  * @head:       the head for your list.
 280  */
 281 #define list_for_each(pos, head) \
 282         for (pos = (head)->next; pos != (head); \
 283                 pos = pos->next)
 284
 285 /**
 286  * __list_for_each      -       iterate over a list
 287  * @pos:        the &struct list_head to use as a loop cursor.
 288  * @head:       the head for your list.
 289  *
 290  * This variant differs from list_for_each() in that it's the
 291  * simplest possible list iteration code, no prefetching is done.
 292  * Use this for code that knows the list to be very short (empty
 293  * or 1 entry) most of the time.
 294  */
 295 #define __list_for_each(pos, head) \
 296         for (pos = (head)->next; pos != (head); pos = pos->next)
 297
 298 /**
 299  * list_for_each_prev   -       iterate over a list backwards
 300  * @pos:        the &struct list_head to use as a loop cursor.
 301  * @head:       the head for your list.
 302  */
 303 #define list_for_each_prev(pos, head) \
 304         for (pos = (head)->prev; pos != (head); \
 305                 pos = pos->prev)
 306
 307 /**
 308  * list_for_each_safe - iterate over a list safe against removal of list entry
 309  * @pos:        the &struct list_head to use as a loop cursor.
 310  * @n:          another &struct list_head to use as temporary storage
 311  * @head:       the head for your list.
 312  */
 313 #define list_for_each_safe(pos, n, head) \
 314         for (pos = (head)->next, n = pos->next; pos != (head); \
 315                 pos = n, n = pos->next)
 316
 317 /**
 318  * list_for_each_entry  -       iterate over list of given type
 319  * @pos:        the type * to use as a loop cursor.
 320  * @head:       the head for your list.
 321  * @member:     the name of the list_struct within the struct.
 322  */
 323 #define list_for_each_entry(pos, head, member)                          \
 324         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 325              &pos->member != (head);    \
 326              pos = list_entry(pos->member.next, typeof(*pos), member))
 327
 328 /**
 329  * list_for_each_entry_reverse - iterate backwards over list of given type.
 330  * @pos:        the type * to use as a loop cursor.
 331  * @head:       the head for your list.
 332  * @member:     the name of the list_struct within the struct.
 333  */
 334 #define list_for_each_entry_reverse(pos, head, member)                  \
 335         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 336              &pos->member != (head);    \
 337              pos = list_entry(pos->member.prev, typeof(*pos), member))
 338
 339 /**
 340  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
 341  * @pos:        the type * to use as a start point
 342  * @head:       the head of the list
 343  * @member:     the name of the list_struct within the struct.
 344  *
 345  * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
 346  */
 347 #define list_prepare_entry(pos, head, member) \
 348         ((pos) ? : list_entry(head, typeof(*pos), member))
 349
 350 /**
 351  * list_for_each_entry_continue - continue iteration over list of given type
 352  * @pos:        the type * to use as a loop cursor.
 353  * @head:       the head for your list.
 354  * @member:     the name of the list_struct within the struct.
 355  *
 356  * Continue to iterate over list of given type, continuing after
 357  * the current position.
 358  */
 359 #define list_for_each_entry_continue(pos, head, member)                 \
 360         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 361              &pos->member != (head);    \
 362              pos = list_entry(pos->member.next, typeof(*pos), member))
 363
 364 /**
 365  * list_for_each_entry_from - iterate over list of given type from the current point
 366  * @pos:        the type * to use as a loop cursor.
 367  * @head:       the head for your list.
 368  * @member:     the name of the list_struct within the struct.
 369  *
 370  * Iterate over list of given type, continuing from current position.
 371  */
 372 #define list_for_each_entry_from(pos, head, member)                     \
 373         for (; &pos->member != (head);  \
 374              pos = list_entry(pos->member.next, typeof(*pos), member))
 375
 376 /**
 377  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 378  * @pos:        the type * to use as a loop cursor.
 379  * @n:          another type * to use as temporary storage
 380  * @head:       the head for your list.
 381  * @member:     the name of the list_struct within the struct.
 382  */
 383 #define list_for_each_entry_safe(pos, n, head, member)                  \
 384         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 385                 n = list_entry(pos->member.next, typeof(*pos), member); \
 386              &pos->member != (head);                                    \
 387              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 388
 389 /**
 390  * list_for_each_entry_safe_continue
 391  * @pos:        the type * to use as a loop cursor.
 392  * @n:          another type * to use as temporary storage
 393  * @head:       the head for your list.
 394  * @member:     the name of the list_struct within the struct.
 395  *
 396  * Iterate over list of given type, continuing after current point,
 397  * safe against removal of list entry.
 398  */
 399 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 400         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 401                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 402              &pos->member != (head);                                            \
 403              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 404
 405 /**
 406  * list_for_each_entry_safe_from
 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  * Iterate over list of given type from current point, safe against
 413  * removal of list entry.
 414  */
 415 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 416         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 417              &pos->member != (head);                                            \
 418              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 419
 420 /**
 421  * list_for_each_entry_safe_reverse
 422  * @pos:        the type * to use as a loop cursor.
 423  * @n:          another type * to use as temporary storage
 424  * @head:       the head for your list.
 425  * @member:     the name of the list_struct within the struct.
 426  *
 427  * Iterate backwards over list of given type, safe against removal
 428  * of list entry.
 429  */
 430 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 431         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 432                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 433              &pos->member != (head);                                    \
 434              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 435
 436 #endif