lib/librte_eal/windows/eal/include/sys/queue.h

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1991, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  *
  31  */
  32
  33 #ifndef _SYS_QUEUE_H_
  34 #define _SYS_QUEUE_H_
  35
  36 /*
  37  * This file defines tail queues.
  38  *
  39  * A tail queue is headed by a pair of pointers, one to the head of the
  40  * list and the other to the tail of the list. The elements are doubly
  41  * linked 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 or
  43  * after an existing element, at the head of the list, or at the end of
  44  * the list. A tail queue may be traversed in either direction.
  45  *
  46  * Below is a summary of implemented functions where:
  47  *  +  means the macro is available
  48  *  -  means the macro is not available
  49  *  s  means the macro is available but is slow (runs in O(n) time)
  50  *
  51  *                              TAILQ
  52  * _HEAD                        +
  53  * _CLASS_HEAD                  +
  54  * _HEAD_INITIALIZER            +
  55  * _ENTRY                       +
  56  * _CLASS_ENTRY                 +
  57  * _INIT                        +
  58  * _EMPTY                       +
  59  * _FIRST                       +
  60  * _NEXT                        +
  61  * _PREV                        +
  62  * _LAST                        +
  63  * _LAST_FAST                   +
  64  * _FOREACH                     +
  65  * _FOREACH_FROM                +
  66  * _FOREACH_SAFE                +
  67  * _FOREACH_FROM_SAFE           +
  68  * _FOREACH_REVERSE             +
  69  * _FOREACH_REVERSE_FROM        +
  70  * _FOREACH_REVERSE_SAFE        +
  71  * _FOREACH_REVERSE_FROM_SAFE   +
  72  * _INSERT_HEAD                 +
  73  * _INSERT_BEFORE               +
  74  * _INSERT_AFTER                +
  75  * _INSERT_TAIL                 +
  76  * _CONCAT                      +
  77  * _REMOVE_AFTER                -
  78  * _REMOVE_HEAD                 -
  79  * _REMOVE                      +
  80  * _SWAP                        +
  81  *
  82  */
  83
  84 #ifdef __cplusplus
  85 extern "C" {
  86 #endif
  87
  88 #define QMD_TRACE_ELEM(elem)
  89 #define QMD_TRACE_HEAD(head)
  90 #define TRACEBUF
  91 #define TRACEBUF_INITIALIZER
  92
  93 #define TRASHIT(x)
  94 #define QMD_IS_TRASHED(x)       0
  95
  96 #define QMD_SAVELINK(name, link)
  97
  98 #ifdef __cplusplus
  99 /*
 100  * In C++ there can be structure lists and class lists:
 101  */
 102 #define QUEUE_TYPEOF(type) type
 103 #else
 104 #define QUEUE_TYPEOF(type) struct type
 105 #endif
 106
 107 /*
 108  * Tail queue declarations.
 109  */
 110 #define TAILQ_HEAD(name, type)                                          \
 111 struct name {                                                           \
 112         struct type *tqh_first; /* first element */                     \
 113         struct type **tqh_last; /* addr of last next element */         \
 114         TRACEBUF                                                        \
 115 }
 116
 117 #define TAILQ_CLASS_HEAD(name, type)                                    \
 118 struct name {                                                           \
 119         class type *tqh_first;  /* first element */                     \
 120         class type **tqh_last;  /* addr of last next element */         \
 121         TRACEBUF                                                        \
 122 }
 123
 124 #define TAILQ_HEAD_INITIALIZER(head)                                    \
 125         { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
 126
 127 #define TAILQ_ENTRY(type)                                               \
 128 struct {                                                                \
 129         struct type *tqe_next;  /* next element */                      \
 130         struct type **tqe_prev; /* address of previous next element */  \
 131         TRACEBUF                                                        \
 132 }
 133
 134 #define TAILQ_CLASS_ENTRY(type)                                         \
 135 struct {                                                                \
 136         class type *tqe_next;   /* next element */                      \
 137         class type **tqe_prev;  /* address of previous next element */  \
 138         TRACEBUF                                                        \
 139 }
 140
 141 /*
 142  * Tail queue functions.
 143  */
 144 #define QMD_TAILQ_CHECK_HEAD(head, field)
 145 #define QMD_TAILQ_CHECK_TAIL(head, headname)
 146 #define QMD_TAILQ_CHECK_NEXT(elm, field)
 147 #define QMD_TAILQ_CHECK_PREV(elm, field)
 148
 149 #define TAILQ_CONCAT(head1, head2, field) do {                          \
 150         if (!TAILQ_EMPTY(head2)) {                                      \
 151                 *(head1)->tqh_last = (head2)->tqh_first;                \
 152                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
 153                 (head1)->tqh_last = (head2)->tqh_last;                  \
 154                 TAILQ_INIT((head2));                                    \
 155                 QMD_TRACE_HEAD(head1);                                  \
 156                 QMD_TRACE_HEAD(head2);                                  \
 157         }                                                               \
 158 } while (0)
 159
 160 #define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
 161
 162 #define TAILQ_FIRST(head)       ((head)->tqh_first)
 163
 164 #define TAILQ_FOREACH(var, head, field)                                 \
 165         for ((var) = TAILQ_FIRST((head));                               \
 166             (var);                                                      \
 167             (var) = TAILQ_NEXT((var), field))
 168
 169 #define TAILQ_FOREACH_FROM(var, head, field)                            \
 170         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 171             (var);                                                      \
 172             (var) = TAILQ_NEXT((var), field))
 173
 174 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
 175         for ((var) = TAILQ_FIRST((head));                               \
 176             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 177             (var) = (tvar))
 178
 179 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)                 \
 180         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 181             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 182             (var) = (tvar))
 183
 184 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
 185         for ((var) = TAILQ_LAST((head), headname);                      \
 186             (var);                                                      \
 187             (var) = TAILQ_PREV((var), headname, field))
 188
 189 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)          \
 190         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 191             (var);                                                      \
 192             (var) = TAILQ_PREV((var), headname, field))
 193
 194 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
 195         for ((var) = TAILQ_LAST((head), headname);                      \
 196             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 197             (var) = (tvar))
 198
 199 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
 200         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 201             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 202             (var) = (tvar))
 203
 204 #define TAILQ_INIT(head) do {                                           \
 205         TAILQ_FIRST((head)) = NULL;                                     \
 206         (head)->tqh_last = &TAILQ_FIRST((head));                        \
 207         QMD_TRACE_HEAD(head);                                           \
 208 } while (0)
 209
 210 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
 211         QMD_TAILQ_CHECK_NEXT(listelm, field);                           \
 212         TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field);        \
 213         if (TAILQ_NEXT((listelm), field) != NULL)                       \
 214                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 215                     &TAILQ_NEXT((elm), field);                          \
 216         else {                                                          \
 217                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 218                 QMD_TRACE_HEAD(head);                                   \
 219         }                                                               \
 220         TAILQ_NEXT((listelm), field) = (elm);                           \
 221         (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
 222         QMD_TRACE_ELEM(&(elm)->field);                                  \
 223         QMD_TRACE_ELEM(&(listelm)->field);                              \
 224 } while (0)
 225
 226 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
 227         QMD_TAILQ_CHECK_PREV(listelm, field);                           \
 228         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
 229         TAILQ_NEXT((elm), field) = (listelm);                           \
 230         *(listelm)->field.tqe_prev = (elm);                             \
 231         (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
 232         QMD_TRACE_ELEM(&(elm)->field);                                  \
 233         QMD_TRACE_ELEM(&(listelm)->field);                              \
 234 } while (0)
 235
 236 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
 237         QMD_TAILQ_CHECK_HEAD(head, field);                              \
 238         TAILQ_NEXT((elm), field) = TAILQ_FIRST((head));                 \
 239         if (TAILQ_FIRST((head)) != NULL)                                \
 240                 TAILQ_FIRST((head))->field.tqe_prev =                   \
 241                     &TAILQ_NEXT((elm), field);                          \
 242         else                                                            \
 243                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 244         TAILQ_FIRST((head)) = (elm);                                    \
 245         (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
 246         QMD_TRACE_HEAD(head);                                           \
 247         QMD_TRACE_ELEM(&(elm)->field);                                  \
 248 } while (0)
 249
 250 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
 251         QMD_TAILQ_CHECK_TAIL(head, field);                              \
 252         TAILQ_NEXT((elm), field) = NULL;                                \
 253         (elm)->field.tqe_prev = (head)->tqh_last;                       \
 254         *(head)->tqh_last = (elm);                                      \
 255         (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
 256         QMD_TRACE_HEAD(head);                                           \
 257         QMD_TRACE_ELEM(&(elm)->field);                                  \
 258 } while (0)
 259
 260 #define TAILQ_LAST(head, headname)                                      \
 261         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 262
 263 /*
 264  * The FAST function is fast in that it causes no data access other
 265  * then the access to the head. The standard LAST function above
 266  * will cause a data access of both the element you want and
 267  * the previous element. FAST is very useful for instances when
 268  * you may want to prefetch the last data element.
 269  */
 270 #define TAILQ_LAST_FAST(head, type, field)                      \
 271         (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last,     \
 272         QUEUE_TYPEOF(type), field.tqe_next))
 273
 274 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 275
 276 #define TAILQ_PREV(elm, headname, field)                                \
 277         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 278
 279 #define TAILQ_REMOVE(head, elm, field) do {                             \
 280         QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                   \
 281         QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                   \
 282         QMD_TAILQ_CHECK_NEXT(elm, field);                               \
 283         QMD_TAILQ_CHECK_PREV(elm, field);                               \
 284         if ((TAILQ_NEXT((elm), field)) != NULL)                         \
 285                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 286                     (elm)->field.tqe_prev;                              \
 287         else {                                                          \
 288                 (head)->tqh_last = (elm)->field.tqe_prev;               \
 289                 QMD_TRACE_HEAD(head);                                   \
 290         }                                                               \
 291         *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
 292         TRASHIT(*oldnext);                                              \
 293         TRASHIT(*oldprev);                                              \
 294         QMD_TRACE_ELEM(&(elm)->field);                                  \
 295 } while (0)
 296
 297 #define TAILQ_SWAP(head1, head2, type, field) do {                      \
 298         QUEUE_TYPEOF(type) * swap_first = (head1)->tqh_first;           \
 299         QUEUE_TYPEOF(type) * *swap_last = (head1)->tqh_last;            \
 300         (head1)->tqh_first = (head2)->tqh_first;                        \
 301         (head1)->tqh_last = (head2)->tqh_last;                          \
 302         (head2)->tqh_first = swap_first;                                \
 303         (head2)->tqh_last = swap_last;                                  \
 304         swap_first = (head1)->tqh_first;                                \
 305         if (swap_first != NULL)                                         \
 306                 swap_first->field.tqe_prev = &(head1)->tqh_first;       \
 307         else                                                            \
 308                 (head1)->tqh_last = &(head1)->tqh_first;                \
 309         swap_first = (head2)->tqh_first;                                \
 310         if (swap_first != NULL)                 \
 311                 swap_first->field.tqe_prev = &(head2)->tqh_first;       \
 312         else                                                            \
 313                 (head2)->tqh_last = &(head2)->tqh_first;                \
 314 } while (0)
 315
 316 #ifdef __cplusplus
 317 }
 318 #endif
 319
 320 #endif /* _SYS_QUEUE_H_ */