inc/queue.h

   1 /*
   2  * Copyright (c) 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 4. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  *      @(#)queue.h     8.3 (Berkeley) 12/13/93
  30  *
  31  * For Jos, extra comments have been added to this file, and the original
  32  * TAILQ and CIRCLEQ definitions have been removed.   - August 9, 2005
  33  */
  34
  35 #ifndef JOS_INC_QUEUE_H
  36 #define JOS_INC_QUEUE_H
  37
  38 /*
  39  * A list is headed by a single forward pointer (or an array of forward
  40  * pointers for a hash table header). The elements are doubly linked
  41  * so that an arbitrary element can be removed without a need to
  42  * traverse the list. New elements can be added to the list before
  43  * or after an existing element or at the head of the list. A list
  44  * may only be traversed in the forward direction.
  45  */
  46
  47 /*
  48  * An example using the below functions.
  49  */
  50 #if 0
  51
  52 struct Frob
  53 {
  54         int frobozz;
  55         LIST_ENTRY(Frob) frob_link;     /* this contains the list element pointers */
  56 };
  57
  58 LIST_HEAD(Frob_list, Frob)              /* defines struct Frob_list as a list of Frob */
  59
  60 struct Frob_list flist;                 /* declare a Frob list */
  61
  62 LIST_INIT(&flist);                      /* clear flist (globals are cleared anyway) */
  63 flist = LIST_HEAD_INITIALIZER(&flist);  /* alternate way to clear flist */
  64
  65 if(LIST_EMPTY(&flist))                  /* check whether list is empty */
  66         printf("list is empty\n");
  67
  68 struct Frob *f = LIST_FIRST(&flist);    /* f is first element in list */
  69 f = LIST_NEXT(f, frob_link);            /* now f is next (second) element in list */
  70 f = LIST_NEXT(f, frob_link);            /* now f is next (third) element in list */
  71
  72 for(f=LIST_FIRST(&flist); f != 0;       /* iterate over elements in flist */
  73     f = LIST_NEXT(f, frob_link))
  74         printf("f %d\n", f->frobozz);
  75
  76 LIST_FOREACH(f, &flist, frob_link)      /* alternate way to say that */
  77         printf("f %d\n", f->frobozz);
  78
  79 f = LIST_NEXT(LIST_FIRST(&flist));      /* f is second element in list */
  80 LIST_INSERT_AFTER(f, g, frob_link);     /* add g right after f in list */
  81 LIST_REMOVE(g, frob_link);              /* remove g from list (can't insert twice!) */
  82 LIST_INSERT_BEFORE(f, g, frob_link);    /* add g right before f */
  83 LIST_REMOVE(g, frob_link);              /* remove g again */
  84 LIST_INSERT_HEAD(&flist, g, frob_link); /* add g as first element in list */
  85
  86 #endif
  87
  88 /*
  89  * List declarations.
  90  */
  91
  92 /*
  93  * A list is headed by a structure defined by the LIST_HEAD macro.  This structure con‐
  94  * tains a single pointer to the first element on the list.  The elements are doubly
  95  * linked so that an arbitrary element can be removed without traversing the list.  New
  96  * elements can be added to the list after an existing element or at the head of the list.
  97  * A LIST_HEAD structure is declared as follows:
  98  *
  99  *       LIST_HEAD(HEADNAME, TYPE) head;
 100  *
 101  * where HEADNAME is the name of the structure to be defined, and TYPE is the type of the
 102  * elements to be linked into the list.  A pointer to the head of the list can later be
 103  * declared as:
 104  *
 105  *       struct HEADNAME *headp;
 106  *
 107  * (The names head and headp are user selectable.)
 108  */
 109 #define LIST_HEAD(name, type)                                           \
 110 struct name {                                                           \
 111         struct type *lh_first;  /* first element */                     \
 112 }
 113
 114 /*
 115  * Set a list head variable to LIST_HEAD_INITIALIZER(head)
 116  * to reset it to the empty list.
 117  */
 118 #define LIST_HEAD_INITIALIZER(head)                                     \
 119         { NULL }
 120
 121 /*
 122  * Use this inside a structure "LIST_ENTRY(type) field" to use
 123  * x as the list piece.
 124  *
 125  * The le_prev points at the pointer to the structure containing
 126  * this very LIST_ENTRY, so that if we want to remove this list entry,
 127  * we can do *le_prev = le_next to update the structure pointing at us.
 128  */
 129 #define LIST_ENTRY(type)                                                \
 130 struct {                                                                \
 131         struct type *le_next;   /* next element */                      \
 132         struct type **le_prev;  /* ptr to ptr to this element */        \
 133 }
 134
 135 /*
 136  * List functions.
 137  */
 138
 139 /*
 140  * Is the list named "head" empty?
 141  */
 142 #define LIST_EMPTY(head)        ((head)->lh_first == NULL)
 143
 144 /*
 145  * Return the first element in the list named "head".
 146  */
 147 #define LIST_FIRST(head)        ((head)->lh_first)
 148
 149 /*
 150  * Return the element after "elm" in the list.
 151  * The "field" name is the link element as above.
 152  */
 153 #define LIST_NEXT(elm, field)   ((elm)->field.le_next)
 154
 155 /*
 156  * Iterate over the elements in the list named "head".
 157  * During the loop, assign the list elements to the variable "var"
 158  * and use the LIST_ENTRY structure member "field" as the link field.
 159  */
 160 #define LIST_FOREACH(var, head, field)                                  \
 161         for ((var) = LIST_FIRST((head));                                \
 162             (var);                                                      \
 163             (var) = LIST_NEXT((var), field))
 164
 165 /*
 166  * Reset the list named "head" to the empty list.
 167  */
 168 #define LIST_INIT(head) do {                                            \
 169         LIST_FIRST((head)) = NULL;                                      \
 170 } while (0)
 171
 172 /*
 173  * Insert the element "elm" *after* the element "listelm" which is
 174  * already in the list.  The "field" name is the link element
 175  * as above.
 176  */
 177 #define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
 178         if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
 179                 LIST_NEXT((listelm), field)->field.le_prev =            \
 180                     &LIST_NEXT((elm), field);                           \
 181         LIST_NEXT((listelm), field) = (elm);                            \
 182         (elm)->field.le_prev = &LIST_NEXT((listelm), field);            \
 183 } while (0)
 184
 185 /*
 186  * Insert the element "elm" *before* the element "listelm" which is
 187  * already in the list.  The "field" name is the link element
 188  * as above.
 189  */
 190 #define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
 191         (elm)->field.le_prev = (listelm)->field.le_prev;                \
 192         LIST_NEXT((elm), field) = (listelm);                            \
 193         *(listelm)->field.le_prev = (elm);                              \
 194         (listelm)->field.le_prev = &LIST_NEXT((elm), field);            \
 195 } while (0)
 196
 197 /*
 198  * Insert the element "elm" at the head of the list named "head".
 199  * The "field" name is the link element as above.
 200  */
 201 #define LIST_INSERT_HEAD(head, elm, field) do {                         \
 202         if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
 203                 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
 204         LIST_FIRST((head)) = (elm);                                     \
 205         (elm)->field.le_prev = &LIST_FIRST((head));                     \
 206 } while (0)
 207
 208 /*
 209  * Remove the element "elm" from the list.
 210  * The "field" name is the link element as above.
 211  */
 212 #define LIST_REMOVE(elm, field) do {                                    \
 213         if (LIST_NEXT((elm), field) != NULL)                            \
 214                 LIST_NEXT((elm), field)->field.le_prev =                \
 215                     (elm)->field.le_prev;                               \
 216         *(elm)->field.le_prev = LIST_NEXT((elm), field);                \
 217 } while (0)
 218
 219 #endif  /* !_SYS_QUEUE_H_ */