include/heimqueue.h

   1 /*      $NetBSD: queue.h,v 1.38 2004/04/18 14:12:05 lukem Exp $ */
   2 /*      $Id$ */
   3
   4 /*
   5  * Copyright (c) 1991, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
  33  */
  34
  35 #ifndef _HEIM_QUEUE_H_
  36 #define _HEIM_QUEUE_H_
  37
  38 /*
  39  * Singly-linked List definitions.
  40  */
  41 #define HEIM_SLIST_HEAD(name, type)                                             \
  42 struct name {                                                           \
  43         struct type *slh_first; /* first element */                     \
  44 }
  45
  46 #define HEIM_SLIST_HEAD_INITIALIZER(head)                                       \
  47         { NULL }
  48
  49 #define HEIM_SLIST_ENTRY(type)                                          \
  50 struct {                                                                \
  51         struct type *sle_next;  /* next element */                      \
  52 }
  53
  54 /*
  55  * Singly-linked List functions.
  56  */
  57 #define HEIM_SLIST_INIT(head) do {                                              \
  58         (head)->slh_first = NULL;                                       \
  59 } while (/*CONSTCOND*/0)
  60
  61 #define HEIM_SLIST_INSERT_AFTER(slistelm, elm, field) do {                      \
  62         (elm)->field.sle_next = (slistelm)->field.sle_next;             \
  63         (slistelm)->field.sle_next = (elm);                             \
  64 } while (/*CONSTCOND*/0)
  65
  66 #define HEIM_SLIST_INSERT_HEAD(head, elm, field) do {                   \
  67         (elm)->field.sle_next = (head)->slh_first;                      \
  68         (head)->slh_first = (elm);                                      \
  69 } while (/*CONSTCOND*/0)
  70
  71 #define HEIM_SLIST_REMOVE_HEAD(head, field) do {                                \
  72         (head)->slh_first = (head)->slh_first->field.sle_next;          \
  73 } while (/*CONSTCOND*/0)
  74
  75 #define HEIM_SLIST_REMOVE(head, elm, type, field) do {                  \
  76         if ((head)->slh_first == (elm)) {                               \
  77                 HEIM_SLIST_REMOVE_HEAD((head), field);                  \
  78         }                                                               \
  79         else {                                                          \
  80                 struct type *curelm = (head)->slh_first;                \
  81                 while(curelm->field.sle_next != (elm))                  \
  82                         curelm = curelm->field.sle_next;                \
  83                 curelm->field.sle_next =                                \
  84                     curelm->field.sle_next->field.sle_next;             \
  85         }                                                               \
  86 } while (/*CONSTCOND*/0)
  87
  88 #define HEIM_SLIST_FOREACH(var, head, field)                                    \
  89         for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
  90
  91 /*
  92  * Singly-linked List access methods.
  93  */
  94 #define HEIM_SLIST_EMPTY(head)  ((head)->slh_first == NULL)
  95 #define HEIM_SLIST_FIRST(head)  ((head)->slh_first)
  96 #define HEIM_SLIST_NEXT(elm, field)     ((elm)->field.sle_next)
  97
  98 /*
  99  * Singly-linked List atomic functions.
 100  */
 101 #include "heimbase.h"
 102
 103 #define HEIM_SLIST_ATOMIC_INSERT_HEAD(head, elm, field) do {            \
 104         (elm)->field.sle_next =                                         \
 105             heim_base_exchange_pointer(&(head)->slh_first, (elm));      \
 106 } while (/*CONSTCOND*/0)
 107
 108 #define HEIM_SLIST_ATOMIC_FOREACH(var, head, field)                             \
 109         for ((void)heim_base_exchange_pointer(&(var), (head)->slh_first);       \
 110              (var) != NULL;                                                     \
 111              (void)heim_base_exchange_pointer(&(var), (var)->field.sle_next))
 112
 113 /*
 114  * Tail queue definitions.
 115  */
 116 #define HEIM_TAILQ_HEAD(name, type)                                     \
 117 struct name {                                                           \
 118         struct type *tqh_first; /* first element */                     \
 119         struct type **tqh_last; /* addr of last next element */         \
 120 }
 121
 122 #define HEIM_TAILQ_HEAD_INITIALIZER(head)                               \
 123         { NULL, &(head).tqh_first }
 124 #define HEIM_TAILQ_ENTRY(type)                                          \
 125 struct {                                                                \
 126         struct type *tqe_next;  /* next element */                      \
 127         struct type **tqe_prev; /* address of previous next element */  \
 128 }
 129
 130 /*
 131  * Tail queue functions.
 132  */
 133 #if defined(_KERNEL) && defined(QUEUEDEBUG)
 134 #define QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field)             \
 135         if ((head)->tqh_first &&                                        \
 136             (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)    \
 137                 panic("HEIM_TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
 138 #define QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field)             \
 139         if (*(head)->tqh_last != NULL)                                  \
 140                 panic("HEIM_TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
 141 #define QUEUEDEBUG_HEIM_TAILQ_OP(elm, field)                            \
 142         if ((elm)->field.tqe_next &&                                    \
 143             (elm)->field.tqe_next->field.tqe_prev !=                    \
 144             &(elm)->field.tqe_next)                                     \
 145                 panic("HEIM_TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
 146         if (*(elm)->field.tqe_prev != (elm))                            \
 147                 panic("HEIM_TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
 148 #define QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field)               \
 149         if ((elm)->field.tqe_next == NULL &&                            \
 150             (head)->tqh_last != &(elm)->field.tqe_next)                 \
 151                 panic("HEIM_TAILQ_PREREMOVE head %p elm %p %s:%d",      \
 152                       (head), (elm), __FILE__, __LINE__);
 153 #define QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field)                    \
 154         (elm)->field.tqe_next = (void *)1L;                             \
 155         (elm)->field.tqe_prev = (void *)1L;
 156 #else
 157 #define QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field)
 158 #define QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field)
 159 #define QUEUEDEBUG_HEIM_TAILQ_OP(elm, field)
 160 #define QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field)
 161 #define QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field)
 162 #endif
 163
 164 #define HEIM_TAILQ_INIT(head) do {                                      \
 165         (head)->tqh_first = NULL;                                       \
 166         (head)->tqh_last = &(head)->tqh_first;                          \
 167 } while (/*CONSTCOND*/0)
 168
 169 #define HEIM_TAILQ_INSERT_HEAD(head, elm, field) do {                   \
 170         QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD((head), (elm), field)         \
 171         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
 172                 (head)->tqh_first->field.tqe_prev =                     \
 173                     &(elm)->field.tqe_next;                             \
 174         else                                                            \
 175                 (head)->tqh_last = &(elm)->field.tqe_next;              \
 176         (head)->tqh_first = (elm);                                      \
 177         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
 178 } while (/*CONSTCOND*/0)
 179
 180 #define HEIM_TAILQ_INSERT_TAIL(head, elm, field) do {                   \
 181         QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL((head), (elm), field)         \
 182         (elm)->field.tqe_next = NULL;                                   \
 183         (elm)->field.tqe_prev = (head)->tqh_last;                       \
 184         *(head)->tqh_last = (elm);                                      \
 185         (head)->tqh_last = &(elm)->field.tqe_next;                      \
 186 } while (/*CONSTCOND*/0)
 187
 188 #define HEIM_TAILQ_INSERT_AFTER(head, listelm, elm, field) do {         \
 189         QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field)                      \
 190         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
 191                 (elm)->field.tqe_next->field.tqe_prev =                 \
 192                     &(elm)->field.tqe_next;                             \
 193         else                                                            \
 194                 (head)->tqh_last = &(elm)->field.tqe_next;              \
 195         (listelm)->field.tqe_next = (elm);                              \
 196         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
 197 } while (/*CONSTCOND*/0)
 198
 199 #define HEIM_TAILQ_INSERT_BEFORE(listelm, elm, field) do {              \
 200         QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field)                      \
 201         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
 202         (elm)->field.tqe_next = (listelm);                              \
 203         *(listelm)->field.tqe_prev = (elm);                             \
 204         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
 205 } while (/*CONSTCOND*/0)
 206
 207 #define HEIM_TAILQ_REMOVE(head, elm, field) do {                        \
 208         QUEUEDEBUG_HEIM_TAILQ_PREREMOVE((head), (elm), field)           \
 209         QUEUEDEBUG_HEIM_TAILQ_OP((elm), field)                          \
 210         if (((elm)->field.tqe_next) != NULL)                            \
 211                 (elm)->field.tqe_next->field.tqe_prev =                 \
 212                     (elm)->field.tqe_prev;                              \
 213         else                                                            \
 214                 (head)->tqh_last = (elm)->field.tqe_prev;               \
 215         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
 216         QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE((elm), field);                 \
 217 } while (/*CONSTCOND*/0)
 218
 219 #define HEIM_TAILQ_FOREACH(var, head, field)                            \
 220         for ((var) = ((head)->tqh_first);                               \
 221                 (var);                                                  \
 222                 (var) = ((var)->field.tqe_next))
 223
 224 #define HEIM_TAILQ_FOREACH_SAFE(var, head, field, next)                 \
 225         for ((var) = ((head)->tqh_first);                               \
 226                 (var) != NULL && ((next) = HEIM_TAILQ_NEXT(var, field), 1); \
 227                 (var) = (next))
 228
 229 #define HEIM_TAILQ_FOREACH_REVERSE(var, head, headname, field)          \
 230         for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
 231                 (var);                                                  \
 232                 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
 233
 234 #define HEIM_TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev)       \
 235         for ((var) = HEIM_TAILQ_LAST((head), headname);                 \
 236                 (var) && ((prev) = HEIM_TAILQ_PREV((var), headname, field), 1);\
 237                 (var) = (prev))
 238
 239 #define HEIM_TAILQ_CONCAT(head1, head2, field) do {                     \
 240         if (!HEIM_TAILQ_EMPTY(head2)) {                                 \
 241                 *(head1)->tqh_last = (head2)->tqh_first;                \
 242                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
 243                 (head1)->tqh_last = (head2)->tqh_last;                  \
 244                 HEIM_TAILQ_INIT((head2));                               \
 245         }                                                               \
 246 } while (/*CONSTCOND*/0)
 247
 248 /*
 249  * Tail queue access methods.
 250  */
 251 #define HEIM_TAILQ_EMPTY(head)          ((head)->tqh_first == NULL)
 252 #define HEIM_TAILQ_FIRST(head)          ((head)->tqh_first)
 253 #define HEIM_TAILQ_NEXT(elm, field)             ((elm)->field.tqe_next)
 254
 255 #define HEIM_TAILQ_LAST(head, headname) \
 256         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 257 #define HEIM_TAILQ_PREV(elm, headname, field) \
 258         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 259
 260
 261 #endif  /* !_HEIM_QUEUE_H_ */