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

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  *
   3  * Copyright (c) 1991, 1993
   4  *      The Regents of the University of California.  All rights reserved.
   5  */
   6
   7 #ifndef _SYS_QUEUE_H_
   8 #define _SYS_QUEUE_H_
   9
  10 /*
  11  * This file defines tail queues.
  12  *
  13  * A tail queue is headed by a pair of pointers, one to the head of the
  14  * list and the other to the tail of the list. The elements are doubly
  15  * linked so that an arbitrary element can be removed without a need to
  16  * traverse the list. New elements can be added to the list before or
  17  * after an existing element, at the head of the list, or at the end of
  18  * the list. A tail queue may be traversed in either direction.
  19  *
  20  * Below is a summary of implemented functions where:
  21  *  +  means the macro is available
  22  *  -  means the macro is not available
  23  *  s  means the macro is available but is slow (runs in O(n) time)
  24  *
  25  *                              TAILQ
  26  * _HEAD                        +
  27  * _CLASS_HEAD                  +
  28  * _HEAD_INITIALIZER            +
  29  * _ENTRY                       +
  30  * _CLASS_ENTRY                 +
  31  * _INIT                        +
  32  * _EMPTY                       +
  33  * _FIRST                       +
  34  * _NEXT                        +
  35  * _PREV                        +
  36  * _LAST                        +
  37  * _LAST_FAST                   +
  38  * _FOREACH                     +
  39  * _FOREACH_FROM                +
  40  * _FOREACH_SAFE                +
  41  * _FOREACH_FROM_SAFE           +
  42  * _FOREACH_REVERSE             +
  43  * _FOREACH_REVERSE_FROM        +
  44  * _FOREACH_REVERSE_SAFE        +
  45  * _FOREACH_REVERSE_FROM_SAFE   +
  46  * _INSERT_HEAD                 +
  47  * _INSERT_BEFORE               +
  48  * _INSERT_AFTER                +
  49  * _INSERT_TAIL                 +
  50  * _CONCAT                      +
  51  * _REMOVE_AFTER                -
  52  * _REMOVE_HEAD                 -
  53  * _REMOVE                      +
  54  * _SWAP                        +
  55  *
  56  */
  57
  58 #ifdef __cplusplus
  59 extern "C" {
  60 #endif
  61
  62 /*
  63  * List definitions.
  64  */
  65 #define LIST_HEAD(name, type)                                           \
  66 struct name {                                                           \
  67         struct type *lh_first;  /* first element */                     \
  68 }
  69
  70 #define QMD_TRACE_ELEM(elem)
  71 #define QMD_TRACE_HEAD(head)
  72 #define TRACEBUF
  73 #define TRACEBUF_INITIALIZER
  74
  75 #define TRASHIT(x)
  76 #define QMD_IS_TRASHED(x)       0
  77
  78 #define QMD_SAVELINK(name, link)
  79
  80 #ifdef __cplusplus
  81 /*
  82  * In C++ there can be structure lists and class lists:
  83  */
  84 #define QUEUE_TYPEOF(type) type
  85 #else
  86 #define QUEUE_TYPEOF(type) struct type
  87 #endif
  88
  89 /*
  90  * Tail queue declarations.
  91  */
  92 #define TAILQ_HEAD(name, type)                                          \
  93 struct name {                                                           \
  94         struct type *tqh_first; /* first element */                     \
  95         struct type **tqh_last; /* addr of last next element */         \
  96         TRACEBUF                                                        \
  97 }
  98
  99 #define TAILQ_CLASS_HEAD(name, type)                                    \
 100 struct name {                                                           \
 101         class type *tqh_first;  /* first element */                     \
 102         class type **tqh_last;  /* addr of last next element */         \
 103         TRACEBUF                                                        \
 104 }
 105
 106 #define TAILQ_HEAD_INITIALIZER(head)                                    \
 107         { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
 108
 109 #define TAILQ_ENTRY(type)                                               \
 110 struct {                                                                \
 111         struct type *tqe_next;  /* next element */                      \
 112         struct type **tqe_prev; /* address of previous next element */  \
 113         TRACEBUF                                                        \
 114 }
 115
 116 #define TAILQ_CLASS_ENTRY(type)                                         \
 117 struct {                                                                \
 118         class type *tqe_next;   /* next element */                      \
 119         class type **tqe_prev;  /* address of previous next element */  \
 120         TRACEBUF                                                        \
 121 }
 122
 123 /*
 124  * Tail queue functions.
 125  */
 126 #define QMD_TAILQ_CHECK_HEAD(head, field)
 127 #define QMD_TAILQ_CHECK_TAIL(head, headname)
 128 #define QMD_TAILQ_CHECK_NEXT(elm, field)
 129 #define QMD_TAILQ_CHECK_PREV(elm, field)
 130
 131 #define TAILQ_CONCAT(head1, head2, field) do {                          \
 132         if (!TAILQ_EMPTY(head2)) {                                      \
 133                 *(head1)->tqh_last = (head2)->tqh_first;                \
 134                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
 135                 (head1)->tqh_last = (head2)->tqh_last;                  \
 136                 TAILQ_INIT((head2));                                    \
 137                 QMD_TRACE_HEAD(head1);                                  \
 138                 QMD_TRACE_HEAD(head2);                                  \
 139         }                                                               \
 140 } while (0)
 141
 142 #define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
 143
 144 #define TAILQ_FIRST(head)       ((head)->tqh_first)
 145
 146 #define TAILQ_FOREACH(var, head, field)                                 \
 147         for ((var) = TAILQ_FIRST((head));                               \
 148             (var);                                                      \
 149             (var) = TAILQ_NEXT((var), field))
 150
 151 #define TAILQ_FOREACH_FROM(var, head, field)                            \
 152         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 153             (var);                                                      \
 154             (var) = TAILQ_NEXT((var), field))
 155
 156 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
 157         for ((var) = TAILQ_FIRST((head));                               \
 158             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 159             (var) = (tvar))
 160
 161 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)                 \
 162         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 163             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 164             (var) = (tvar))
 165
 166 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
 167         for ((var) = TAILQ_LAST((head), headname);                      \
 168             (var);                                                      \
 169             (var) = TAILQ_PREV((var), headname, field))
 170
 171 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)          \
 172         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 173             (var);                                                      \
 174             (var) = TAILQ_PREV((var), headname, field))
 175
 176 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
 177         for ((var) = TAILQ_LAST((head), headname);                      \
 178             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 179             (var) = (tvar))
 180
 181 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
 182         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 183             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 184             (var) = (tvar))
 185
 186 #define TAILQ_INIT(head) do {                                           \
 187         TAILQ_FIRST((head)) = NULL;                                     \
 188         (head)->tqh_last = &TAILQ_FIRST((head));                        \
 189         QMD_TRACE_HEAD(head);                                           \
 190 } while (0)
 191
 192 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
 193         QMD_TAILQ_CHECK_NEXT(listelm, field);                           \
 194         TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field);        \
 195         if (TAILQ_NEXT((listelm), field) != NULL)                       \
 196                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 197                     &TAILQ_NEXT((elm), field);                          \
 198         else {                                                          \
 199                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 200                 QMD_TRACE_HEAD(head);                                   \
 201         }                                                               \
 202         TAILQ_NEXT((listelm), field) = (elm);                           \
 203         (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
 204         QMD_TRACE_ELEM(&(elm)->field);                                  \
 205         QMD_TRACE_ELEM(&(listelm)->field);                              \
 206 } while (0)
 207
 208 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
 209         QMD_TAILQ_CHECK_PREV(listelm, field);                           \
 210         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
 211         TAILQ_NEXT((elm), field) = (listelm);                           \
 212         *(listelm)->field.tqe_prev = (elm);                             \
 213         (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
 214         QMD_TRACE_ELEM(&(elm)->field);                                  \
 215         QMD_TRACE_ELEM(&(listelm)->field);                              \
 216 } while (0)
 217
 218 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
 219         QMD_TAILQ_CHECK_HEAD(head, field);                              \
 220         TAILQ_NEXT((elm), field) = TAILQ_FIRST((head));                 \
 221         if (TAILQ_FIRST((head)) != NULL)                                \
 222                 TAILQ_FIRST((head))->field.tqe_prev =                   \
 223                     &TAILQ_NEXT((elm), field);                          \
 224         else                                                            \
 225                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 226         TAILQ_FIRST((head)) = (elm);                                    \
 227         (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
 228         QMD_TRACE_HEAD(head);                                           \
 229         QMD_TRACE_ELEM(&(elm)->field);                                  \
 230 } while (0)
 231
 232 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
 233         QMD_TAILQ_CHECK_TAIL(head, field);                              \
 234         TAILQ_NEXT((elm), field) = NULL;                                \
 235         (elm)->field.tqe_prev = (head)->tqh_last;                       \
 236         *(head)->tqh_last = (elm);                                      \
 237         (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
 238         QMD_TRACE_HEAD(head);                                           \
 239         QMD_TRACE_ELEM(&(elm)->field);                                  \
 240 } while (0)
 241
 242 #define TAILQ_LAST(head, headname)                                      \
 243         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 244
 245 /*
 246  * The FAST function is fast in that it causes no data access other
 247  * then the access to the head. The standard LAST function above
 248  * will cause a data access of both the element you want and
 249  * the previous element. FAST is very useful for instances when
 250  * you may want to prefetch the last data element.
 251  */
 252 #define TAILQ_LAST_FAST(head, type, field)                      \
 253         (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last,     \
 254         QUEUE_TYPEOF(type), field.tqe_next))
 255
 256 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 257
 258 #define TAILQ_PREV(elm, headname, field)                                \
 259         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 260
 261 #define TAILQ_REMOVE(head, elm, field) do {                             \
 262         QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                   \
 263         QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                   \
 264         QMD_TAILQ_CHECK_NEXT(elm, field);                               \
 265         QMD_TAILQ_CHECK_PREV(elm, field);                               \
 266         if ((TAILQ_NEXT((elm), field)) != NULL)                         \
 267                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 268                     (elm)->field.tqe_prev;                              \
 269         else {                                                          \
 270                 (head)->tqh_last = (elm)->field.tqe_prev;               \
 271                 QMD_TRACE_HEAD(head);                                   \
 272         }                                                               \
 273         *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
 274         TRASHIT(*oldnext);                                              \
 275         TRASHIT(*oldprev);                                              \
 276         QMD_TRACE_ELEM(&(elm)->field);                                  \
 277 } while (0)
 278
 279 #define TAILQ_SWAP(head1, head2, type, field) do {                      \
 280         QUEUE_TYPEOF(type) * swap_first = (head1)->tqh_first;           \
 281         QUEUE_TYPEOF(type) * *swap_last = (head1)->tqh_last;            \
 282         (head1)->tqh_first = (head2)->tqh_first;                        \
 283         (head1)->tqh_last = (head2)->tqh_last;                          \
 284         (head2)->tqh_first = swap_first;                                \
 285         (head2)->tqh_last = swap_last;                                  \
 286         swap_first = (head1)->tqh_first;                                \
 287         if (swap_first != NULL)                                         \
 288                 swap_first->field.tqe_prev = &(head1)->tqh_first;       \
 289         else                                                            \
 290                 (head1)->tqh_last = &(head1)->tqh_first;                \
 291         swap_first = (head2)->tqh_first;                                \
 292         if (swap_first != NULL)                 \
 293                 swap_first->field.tqe_prev = &(head2)->tqh_first;       \
 294         else                                                            \
 295                 (head2)->tqh_last = &(head2)->tqh_first;                \
 296 } while (0)
 297
 298 #ifdef __cplusplus
 299 }
 300 #endif
 301
 302 #endif /* _SYS_QUEUE_H_ */