lib/librte_eal/windows/eal/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 #define QMD_TRACE_ELEM(elem)
  63 #define QMD_TRACE_HEAD(head)
  64 #define TRACEBUF
  65 #define TRACEBUF_INITIALIZER
  66
  67 #define TRASHIT(x)
  68 #define QMD_IS_TRASHED(x)       0
  69
  70 #define QMD_SAVELINK(name, link)
  71
  72 #ifdef __cplusplus
  73 /*
  74  * In C++ there can be structure lists and class lists:
  75  */
  76 #define QUEUE_TYPEOF(type) type
  77 #else
  78 #define QUEUE_TYPEOF(type) struct type
  79 #endif
  80
  81 /*
  82  * Tail queue declarations.
  83  */
  84 #define TAILQ_HEAD(name, type)                                          \
  85 struct name {                                                           \
  86         struct type *tqh_first; /* first element */                     \
  87         struct type **tqh_last; /* addr of last next element */         \
  88         TRACEBUF                                                        \
  89 }
  90
  91 #define TAILQ_CLASS_HEAD(name, type)                                    \
  92 struct name {                                                           \
  93         class type *tqh_first;  /* first element */                     \
  94         class type **tqh_last;  /* addr of last next element */         \
  95         TRACEBUF                                                        \
  96 }
  97
  98 #define TAILQ_HEAD_INITIALIZER(head)                                    \
  99         { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
 100
 101 #define TAILQ_ENTRY(type)                                               \
 102 struct {                                                                \
 103         struct type *tqe_next;  /* next element */                      \
 104         struct type **tqe_prev; /* address of previous next element */  \
 105         TRACEBUF                                                        \
 106 }
 107
 108 #define TAILQ_CLASS_ENTRY(type)                                         \
 109 struct {                                                                \
 110         class type *tqe_next;   /* next element */                      \
 111         class type **tqe_prev;  /* address of previous next element */  \
 112         TRACEBUF                                                        \
 113 }
 114
 115 /*
 116  * Tail queue functions.
 117  */
 118 #define QMD_TAILQ_CHECK_HEAD(head, field)
 119 #define QMD_TAILQ_CHECK_TAIL(head, headname)
 120 #define QMD_TAILQ_CHECK_NEXT(elm, field)
 121 #define QMD_TAILQ_CHECK_PREV(elm, field)
 122
 123 #define TAILQ_CONCAT(head1, head2, field) do {                          \
 124         if (!TAILQ_EMPTY(head2)) {                                      \
 125                 *(head1)->tqh_last = (head2)->tqh_first;                \
 126                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
 127                 (head1)->tqh_last = (head2)->tqh_last;                  \
 128                 TAILQ_INIT((head2));                                    \
 129                 QMD_TRACE_HEAD(head1);                                  \
 130                 QMD_TRACE_HEAD(head2);                                  \
 131         }                                                               \
 132 } while (0)
 133
 134 #define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
 135
 136 #define TAILQ_FIRST(head)       ((head)->tqh_first)
 137
 138 #define TAILQ_FOREACH(var, head, field)                                 \
 139         for ((var) = TAILQ_FIRST((head));                               \
 140             (var);                                                      \
 141             (var) = TAILQ_NEXT((var), field))
 142
 143 #define TAILQ_FOREACH_FROM(var, head, field)                            \
 144         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 145             (var);                                                      \
 146             (var) = TAILQ_NEXT((var), field))
 147
 148 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
 149         for ((var) = TAILQ_FIRST((head));                               \
 150             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 151             (var) = (tvar))
 152
 153 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)                 \
 154         for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));             \
 155             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
 156             (var) = (tvar))
 157
 158 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
 159         for ((var) = TAILQ_LAST((head), headname);                      \
 160             (var);                                                      \
 161             (var) = TAILQ_PREV((var), headname, field))
 162
 163 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)          \
 164         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 165             (var);                                                      \
 166             (var) = TAILQ_PREV((var), headname, field))
 167
 168 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
 169         for ((var) = TAILQ_LAST((head), headname);                      \
 170             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 171             (var) = (tvar))
 172
 173 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
 174         for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));    \
 175             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
 176             (var) = (tvar))
 177
 178 #define TAILQ_INIT(head) do {                                           \
 179         TAILQ_FIRST((head)) = NULL;                                     \
 180         (head)->tqh_last = &TAILQ_FIRST((head));                        \
 181         QMD_TRACE_HEAD(head);                                           \
 182 } while (0)
 183
 184 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
 185         QMD_TAILQ_CHECK_NEXT(listelm, field);                           \
 186         TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field);        \
 187         if (TAILQ_NEXT((listelm), field) != NULL)                       \
 188                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 189                     &TAILQ_NEXT((elm), field);                          \
 190         else {                                                          \
 191                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 192                 QMD_TRACE_HEAD(head);                                   \
 193         }                                                               \
 194         TAILQ_NEXT((listelm), field) = (elm);                           \
 195         (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
 196         QMD_TRACE_ELEM(&(elm)->field);                                  \
 197         QMD_TRACE_ELEM(&(listelm)->field);                              \
 198 } while (0)
 199
 200 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
 201         QMD_TAILQ_CHECK_PREV(listelm, field);                           \
 202         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
 203         TAILQ_NEXT((elm), field) = (listelm);                           \
 204         *(listelm)->field.tqe_prev = (elm);                             \
 205         (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
 206         QMD_TRACE_ELEM(&(elm)->field);                                  \
 207         QMD_TRACE_ELEM(&(listelm)->field);                              \
 208 } while (0)
 209
 210 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
 211         QMD_TAILQ_CHECK_HEAD(head, field);                              \
 212         TAILQ_NEXT((elm), field) = TAILQ_FIRST((head));                 \
 213         if (TAILQ_FIRST((head)) != NULL)                                \
 214                 TAILQ_FIRST((head))->field.tqe_prev =                   \
 215                     &TAILQ_NEXT((elm), field);                          \
 216         else                                                            \
 217                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
 218         TAILQ_FIRST((head)) = (elm);                                    \
 219         (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
 220         QMD_TRACE_HEAD(head);                                           \
 221         QMD_TRACE_ELEM(&(elm)->field);                                  \
 222 } while (0)
 223
 224 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
 225         QMD_TAILQ_CHECK_TAIL(head, field);                              \
 226         TAILQ_NEXT((elm), field) = NULL;                                \
 227         (elm)->field.tqe_prev = (head)->tqh_last;                       \
 228         *(head)->tqh_last = (elm);                                      \
 229         (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
 230         QMD_TRACE_HEAD(head);                                           \
 231         QMD_TRACE_ELEM(&(elm)->field);                                  \
 232 } while (0)
 233
 234 #define TAILQ_LAST(head, headname)                                      \
 235         (*(((struct headname *)((head)->tqh_last))->tqh_last))
 236
 237 /*
 238  * The FAST function is fast in that it causes no data access other
 239  * then the access to the head. The standard LAST function above
 240  * will cause a data access of both the element you want and
 241  * the previous element. FAST is very useful for instances when
 242  * you may want to prefetch the last data element.
 243  */
 244 #define TAILQ_LAST_FAST(head, type, field)                      \
 245         (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last,     \
 246         QUEUE_TYPEOF(type), field.tqe_next))
 247
 248 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 249
 250 #define TAILQ_PREV(elm, headname, field)                                \
 251         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 252
 253 #define TAILQ_REMOVE(head, elm, field) do {                             \
 254         QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                   \
 255         QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                   \
 256         QMD_TAILQ_CHECK_NEXT(elm, field);                               \
 257         QMD_TAILQ_CHECK_PREV(elm, field);                               \
 258         if ((TAILQ_NEXT((elm), field)) != NULL)                         \
 259                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
 260                     (elm)->field.tqe_prev;                              \
 261         else {                                                          \
 262                 (head)->tqh_last = (elm)->field.tqe_prev;               \
 263                 QMD_TRACE_HEAD(head);                                   \
 264         }                                                               \
 265         *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
 266         TRASHIT(*oldnext);                                              \
 267         TRASHIT(*oldprev);                                              \
 268         QMD_TRACE_ELEM(&(elm)->field);                                  \
 269 } while (0)
 270
 271 #define TAILQ_SWAP(head1, head2, type, field) do {                      \
 272         QUEUE_TYPEOF(type) * swap_first = (head1)->tqh_first;           \
 273         QUEUE_TYPEOF(type) * *swap_last = (head1)->tqh_last;            \
 274         (head1)->tqh_first = (head2)->tqh_first;                        \
 275         (head1)->tqh_last = (head2)->tqh_last;                          \
 276         (head2)->tqh_first = swap_first;                                \
 277         (head2)->tqh_last = swap_last;                                  \
 278         swap_first = (head1)->tqh_first;                                \
 279         if (swap_first != NULL)                                         \
 280                 swap_first->field.tqe_prev = &(head1)->tqh_first;       \
 281         else                                                            \
 282                 (head1)->tqh_last = &(head1)->tqh_first;                \
 283         swap_first = (head2)->tqh_first;                                \
 284         if (swap_first != NULL)                 \
 285                 swap_first->field.tqe_prev = &(head2)->tqh_first;       \
 286         else                                                            \
 287                 (head2)->tqh_last = &(head2)->tqh_first;                \
 288 } while (0)
 289
 290 #ifdef __cplusplus
 291 }
 292 #endif
 293
 294 #endif /* _SYS_QUEUE_H_ */