kernel-lib/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(const struct list_head *list,
 227                                  struct list_head *prev,
 228                                  struct list_head *next)
 229 {
 230         struct list_head *first = list->next;
 231         struct list_head *last = list->prev;
 232
 233         first->prev = prev;
 234         prev->next = first;
 235
 236         last->next = next;
 237         next->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, head->next);
 249 }
 250
 251 /**
 252  * list_splice_tail - join two lists, each list being a queue
 253  * @list: the new list to add.
 254  * @head: the place to add it in the first list.
 255  */
 256 static inline void list_splice_tail(struct list_head *list,
 257                                 struct list_head *head)
 258 {
 259         if (!list_empty(list))
 260                 __list_splice(list, head->prev, head);
 261 }
 262
 263 /**
 264  * list_splice_init - join two lists and reinitialise the emptied list.
 265  * @list: the new list to add.
 266  * @head: the place to add it in the first list.
 267  *
 268  * The list at @list is reinitialised
 269  */
 270 static inline void list_splice_init(struct list_head *list,
 271                                     struct list_head *head)
 272 {
 273         if (!list_empty(list)) {
 274                 __list_splice(list, head, head->next);
 275                 INIT_LIST_HEAD(list);
 276         }
 277 }
 278
 279 /**
 280  * list_splice_tail_init - join two lists and reinitialise the emptied list
 281  * @list: the new list to add.
 282  * @head: the place to add it in the first list.
 283  *
 284  * Each of the lists is a queue.
 285  * The list at @list is reinitialised
 286  */
 287 static inline void list_splice_tail_init(struct list_head *list,
 288                                          struct list_head *head)
 289 {
 290         if (!list_empty(list)) {
 291                 __list_splice(list, head->prev, head);
 292                 INIT_LIST_HEAD(list);
 293         }
 294 }
 295
 296 /**
 297  * list_entry - get the struct for this entry
 298  * @ptr:        the &struct list_head pointer.
 299  * @type:       the type of the struct this is embedded in.
 300  * @member:     the name of the list_struct within the struct.
 301  */
 302 #define list_entry(ptr, type, member) \
 303         container_of(ptr, type, member)
 304
 305 /**
 306  * list_first_entry - get the first element from a list
 307  * @ptr:        the list head to take the element from.
 308  * @type:       the type of the struct this is embedded in.
 309  * @member:     the name of the list_struct within the struct.
 310  *
 311  * Note, that list is expected to be not empty.
 312  */
 313 #define list_first_entry(ptr, type, member) \
 314         list_entry((ptr)->next, type, member)
 315
 316 /**
 317  * list_next_entry - get the next element from a list
 318  * @ptr:        the list head to take the element from.
 319  * @member:     the name of the list_struct within the struct.
 320  *
 321  * Note, that next is expected to be not null.
 322  */
 323 #define list_next_entry(ptr, member) \
 324         list_entry((ptr)->member.next, typeof(*ptr), member)
 325
 326 /**
 327  * list_for_each        -       iterate over a list
 328  * @pos:        the &struct list_head to use as a loop cursor.
 329  * @head:       the head for your list.
 330  */
 331 #define list_for_each(pos, head) \
 332         for (pos = (head)->next; pos != (head); \
 333                 pos = pos->next)
 334
 335 /**
 336  * __list_for_each      -       iterate over a list
 337  * @pos:        the &struct list_head to use as a loop cursor.
 338  * @head:       the head for your list.
 339  *
 340  * This variant differs from list_for_each() in that it's the
 341  * simplest possible list iteration code, no prefetching is done.
 342  * Use this for code that knows the list to be very short (empty
 343  * or 1 entry) most of the time.
 344  */
 345 #define __list_for_each(pos, head) \
 346         for (pos = (head)->next; pos != (head); pos = pos->next)
 347
 348 /**
 349  * list_for_each_prev   -       iterate over a list backwards
 350  * @pos:        the &struct list_head to use as a loop cursor.
 351  * @head:       the head for your list.
 352  */
 353 #define list_for_each_prev(pos, head) \
 354         for (pos = (head)->prev; pos != (head); \
 355                 pos = pos->prev)
 356
 357 /**
 358  * list_for_each_safe - iterate over a list safe against removal of list entry
 359  * @pos:        the &struct list_head to use as a loop cursor.
 360  * @n:          another &struct list_head to use as temporary storage
 361  * @head:       the head for your list.
 362  */
 363 #define list_for_each_safe(pos, n, head) \
 364         for (pos = (head)->next, n = pos->next; pos != (head); \
 365                 pos = n, n = pos->next)
 366
 367 /**
 368  * list_for_each_entry  -       iterate over list of given type
 369  * @pos:        the type * to use as a loop cursor.
 370  * @head:       the head for your list.
 371  * @member:     the name of the list_struct within the struct.
 372  */
 373 #define list_for_each_entry(pos, head, member)                          \
 374         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 375              &pos->member != (head);    \
 376              pos = list_entry(pos->member.next, typeof(*pos), member))
 377
 378 /**
 379  * list_for_each_entry_reverse - iterate backwards over list of given type.
 380  * @pos:        the type * to use as a loop cursor.
 381  * @head:       the head for your list.
 382  * @member:     the name of the list_struct within the struct.
 383  */
 384 #define list_for_each_entry_reverse(pos, head, member)                  \
 385         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 386              &pos->member != (head);    \
 387              pos = list_entry(pos->member.prev, typeof(*pos), member))
 388
 389 /**
 390  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
 391  * @pos:        the type * to use as a start point
 392  * @head:       the head of the list
 393  * @member:     the name of the list_struct within the struct.
 394  *
 395  * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
 396  */
 397 #define list_prepare_entry(pos, head, member) \
 398         ((pos) ? : list_entry(head, typeof(*pos), member))
 399
 400 /**
 401  * list_for_each_entry_continue - continue iteration over list of given type
 402  * @pos:        the type * to use as a loop cursor.
 403  * @head:       the head for your list.
 404  * @member:     the name of the list_struct within the struct.
 405  *
 406  * Continue to iterate over list of given type, continuing after
 407  * the current position.
 408  */
 409 #define list_for_each_entry_continue(pos, head, member)                 \
 410         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 411              &pos->member != (head);    \
 412              pos = list_entry(pos->member.next, typeof(*pos), member))
 413
 414 /**
 415  * list_for_each_entry_from - iterate over list of given type from the current point
 416  * @pos:        the type * to use as a loop cursor.
 417  * @head:       the head for your list.
 418  * @member:     the name of the list_struct within the struct.
 419  *
 420  * Iterate over list of given type, continuing from current position.
 421  */
 422 #define list_for_each_entry_from(pos, head, member)                     \
 423         for (; &pos->member != (head);  \
 424              pos = list_entry(pos->member.next, typeof(*pos), member))
 425
 426 /**
 427  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 428  * @pos:        the type * to use as a loop cursor.
 429  * @n:          another type * to use as temporary storage
 430  * @head:       the head for your list.
 431  * @member:     the name of the list_struct within the struct.
 432  */
 433 #define list_for_each_entry_safe(pos, n, head, member)                  \
 434         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 435                 n = list_entry(pos->member.next, typeof(*pos), member); \
 436              &pos->member != (head);                                    \
 437              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 438
 439 /**
 440  * list_for_each_entry_safe_continue
 441  * @pos:        the type * to use as a loop cursor.
 442  * @n:          another type * to use as temporary storage
 443  * @head:       the head for your list.
 444  * @member:     the name of the list_struct within the struct.
 445  *
 446  * Iterate over list of given type, continuing after current point,
 447  * safe against removal of list entry.
 448  */
 449 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 450         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 451                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 452              &pos->member != (head);                                            \
 453              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 454
 455 /**
 456  * list_for_each_entry_safe_from
 457  * @pos:        the type * to use as a loop cursor.
 458  * @n:          another type * to use as temporary storage
 459  * @head:       the head for your list.
 460  * @member:     the name of the list_struct within the struct.
 461  *
 462  * Iterate over list of given type from current point, safe against
 463  * removal of list entry.
 464  */
 465 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 466         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 467              &pos->member != (head);                                            \
 468              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 469
 470 /**
 471  * list_for_each_entry_safe_reverse
 472  * @pos:        the type * to use as a loop cursor.
 473  * @n:          another type * to use as temporary storage
 474  * @head:       the head for your list.
 475  * @member:     the name of the list_struct within the struct.
 476  *
 477  * Iterate backwards over list of given type, safe against removal
 478  * of list entry.
 479  */
 480 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 481         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 482                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 483              &pos->member != (head);                                    \
 484              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 485
 486 #endif