sys/contrib/ck/include/ck_queue.h

   1 /*
   2  * Copyright 2012-2015 Samy Al Bahra.
   3  * 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  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 /*-
  28  * Copyright (c) 1991, 1993
  29  *      The Regents of the University of California.  All rights reserved.
  30  *
  31  * Redistribution and use in source and binary forms, with or without
  32  * modification, are permitted provided that the following conditions
  33  * are met:
  34  * 1. Redistributions of source code must retain the above copyright
  35  *    notice, this list of conditions and the following disclaimer.
  36  * 2. Redistributions in binary form must reproduce the above copyright
  37  *    notice, this list of conditions and the following disclaimer in the
  38  *    documentation and/or other materials provided with the distribution.
  39  * 4. Neither the name of the University nor the names of its contributors
  40  *    may be used to endorse or promote products derived from this software
  41  *    without specific prior written permission.
  42  *
  43  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  44  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  45  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  46  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  47  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  48  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  49  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  50  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  51  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  52  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  53  * SUCH DAMAGE.
  54  *
  55  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
  56  * $FreeBSD: release/9.0.0/sys/sys/queue.h 221843 2011-05-13 15:49:23Z mdf $
  57  */
  58
  59 #ifndef CK_QUEUE_H
  60 #define CK_QUEUE_H
  61
  62 #include <ck_pr.h>
  63
  64 /*
  65  * This file defines three types of data structures: singly-linked lists,
  66  * singly-linked tail queues and lists.
  67  *
  68  * A singly-linked list is headed by a single forward pointer. The elements
  69  * are singly linked for minimum space and pointer manipulation overhead at
  70  * the expense of O(n) removal for arbitrary elements. New elements can be
  71  * added to the list after an existing element or at the head of the list.
  72  * Elements being removed from the head of the list should use the explicit
  73  * macro for this purpose for optimum efficiency. A singly-linked list may
  74  * only be traversed in the forward direction.  Singly-linked lists are ideal
  75  * for applications with large datasets and few or no removals or for
  76  * implementing a LIFO queue.
  77  *
  78  * A singly-linked tail queue is headed by a pair of pointers, one to the
  79  * head of the list and the other to the tail of the list. The elements are
  80  * singly linked for minimum space and pointer manipulation overhead at the
  81  * expense of O(n) removal for arbitrary elements. New elements can be added
  82  * to the list after an existing element, at the head of the list, or at the
  83  * end of the list. Elements being removed from the head of the tail queue
  84  * should use the explicit macro for this purpose for optimum efficiency.
  85  * A singly-linked tail queue may only be traversed in the forward direction.
  86  * Singly-linked tail queues are ideal for applications with large datasets
  87  * and few or no removals or for implementing a FIFO queue.
  88  *
  89  * A list is headed by a single forward pointer (or an array of forward
  90  * pointers for a hash table header). The elements are doubly linked
  91  * so that an arbitrary element can be removed without a need to
  92  * traverse the list. New elements can be added to the list before
  93  * or after an existing element or at the head of the list. A list
  94  * may only be traversed in the forward direction.
  95  *
  96  * It is safe to use _FOREACH/_FOREACH_SAFE in the presence of concurrent
  97  * modifications to the list. Writers to these lists must, on the other hand,
  98  * implement writer-side synchronization. The _SWAP operations are not atomic.
  99  * This facility is currently unsupported on architectures such as the Alpha
 100  * which require load-depend memory fences.
 101  *
 102  *                              CK_SLIST        CK_LIST CK_STAILQ
 103  * _HEAD                        +               +       +
 104  * _HEAD_INITIALIZER            +               +       +
 105  * _ENTRY                       +               +       +
 106  * _INIT                        +               +       +
 107  * _EMPTY                       +               +       +
 108  * _FIRST                       +               +       +
 109  * _NEXT                        +               +       +
 110  * _FOREACH                     +               +       +
 111  * _FOREACH_SAFE                +               +       +
 112  * _INSERT_HEAD                 +               +       +
 113  * _INSERT_BEFORE               -               +       -
 114  * _INSERT_AFTER                +               +       +
 115  * _INSERT_TAIL                 -               -       +
 116  * _REMOVE_AFTER                +               -       +
 117  * _REMOVE_HEAD                 +               -       +
 118  * _REMOVE                      +               +       +
 119  * _SWAP                        +               +       +
 120  * _MOVE                        +               +       +
 121  */
 122
 123 /*
 124  * Singly-linked List declarations.
 125  */
 126 #define CK_SLIST_HEAD(name, type)                                               \
 127 struct name {                                                                   \
 128         struct type *cslh_first;        /* first element */                             \
 129 }
 130
 131 #define CK_SLIST_HEAD_INITIALIZER(head)                                         \
 132         { NULL }
 133
 134 #define CK_SLIST_ENTRY(type)                                                    \
 135 struct {                                                                        \
 136         struct type *csle_next; /* next element */                              \
 137 }
 138
 139 /*
 140  * Singly-linked List functions.
 141  */
 142 #define CK_SLIST_EMPTY(head)                                                    \
 143         (ck_pr_load_ptr(&(head)->cslh_first) == NULL)
 144
 145 #define CK_SLIST_FIRST(head)                                                    \
 146         (ck_pr_load_ptr(&(head)->cslh_first))
 147
 148 #define CK_SLIST_NEXT(elm, field)                                               \
 149         ck_pr_load_ptr(&((elm)->field.csle_next))
 150
 151 #define CK_SLIST_FOREACH(var, head, field)                                      \
 152         for ((var) = CK_SLIST_FIRST((head));                                    \
 153             (var);                                                              \
 154             (var) = CK_SLIST_NEXT((var), field))
 155
 156 #define CK_SLIST_FOREACH_FROM(var, head, field)                                 \
 157         for ((var) = ((var) != NULL ? (var) : CK_SLIST_FIRST((head)));          \
 158             (var);                                                              \
 159             (var) = CK_SLIST_NEXT((var), field))
 160
 161 #define CK_SLIST_FOREACH_SAFE(var, head, field, tvar)                           \
 162         for ((var) = CK_SLIST_FIRST(head);                                      \
 163             (var) && ((tvar) = CK_SLIST_NEXT(var, field), 1);                   \
 164             (var) = (tvar))
 165
 166 #define CK_SLIST_FOREACH_PREVPTR(var, varp, head, field)                        \
 167         for ((varp) = &(head)->cslh_first;                                      \
 168             ((var) = ck_pr_load_ptr(varp)) != NULL;                             \
 169             (varp) = &(var)->field.csle_next)
 170
 171 #define CK_SLIST_INIT(head) do {                                                \
 172         ck_pr_store_ptr(&(head)->cslh_first, NULL);                             \
 173         ck_pr_fence_store();                                                    \
 174 } while (0)
 175
 176 #define CK_SLIST_INSERT_AFTER(a, b, field) do {                                 \
 177         (b)->field.csle_next = (a)->field.csle_next;                            \
 178         ck_pr_fence_store();                                                    \
 179         ck_pr_store_ptr(&(a)->field.csle_next, b);                              \
 180 } while (0)
 181
 182 #define CK_SLIST_INSERT_HEAD(head, elm, field) do {                             \
 183         (elm)->field.csle_next = (head)->cslh_first;                            \
 184         ck_pr_fence_store();                                                    \
 185         ck_pr_store_ptr(&(head)->cslh_first, elm);                              \
 186 } while (0)
 187
 188 #define CK_SLIST_INSERT_PREVPTR(prevp, slistelm, elm, field) do {               \
 189         (elm)->field.csle_next = (slistelm);                                    \
 190         ck_pr_fence_store();                                                    \
 191         ck_pr_store_ptr(prevp, elm);                                            \
 192 } while (0)
 193
 194 #define CK_SLIST_REMOVE_AFTER(elm, field) do {                                  \
 195         ck_pr_store_ptr(&(elm)->field.csle_next,                                \
 196             (elm)->field.csle_next->field.csle_next);                           \
 197 } while (0)
 198
 199 #define CK_SLIST_REMOVE(head, elm, type, field) do {                            \
 200         if ((head)->cslh_first == (elm)) {                                      \
 201                 CK_SLIST_REMOVE_HEAD((head), field);                            \
 202         } else {                                                                \
 203                 struct type *curelm = (head)->cslh_first;                       \
 204                 while (curelm->field.csle_next != (elm))                        \
 205                         curelm = curelm->field.csle_next;                       \
 206                 CK_SLIST_REMOVE_AFTER(curelm, field);                           \
 207         }                                                                       \
 208 } while (0)
 209
 210 #define CK_SLIST_REMOVE_HEAD(head, field) do {                                  \
 211         ck_pr_store_ptr(&(head)->cslh_first,                                    \
 212                 (head)->cslh_first->field.csle_next);                           \
 213 } while (0)
 214
 215 #define CK_SLIST_REMOVE_PREVPTR(prevp, elm, field) do {                         \
 216         ck_pr_store_ptr(prevptr, (elm)->field.csle_next);                       \
 217 } while (0)
 218
 219 #define CK_SLIST_MOVE(head1, head2, field) do {                                 \
 220         ck_pr_store_ptr(&(head1)->cslh_first, (head2)->cslh_first);             \
 221 } while (0)
 222
 223 /*
 224  * This operation is not applied atomically.
 225  */
 226 #define CK_SLIST_SWAP(a, b, type) do {                                          \
 227         struct type *swap_first = (a)->cslh_first;                              \
 228         (a)->cslh_first = (b)->cslh_first;                                      \
 229         (b)->cslh_first = swap_first;                                           \
 230 } while (0)
 231
 232 /*
 233  * Singly-linked Tail queue declarations.
 234  */
 235 #define CK_STAILQ_HEAD(name, type)                                      \
 236 struct name {                                                           \
 237         struct type *cstqh_first;/* first element */                    \
 238         struct type **cstqh_last;/* addr of last next element */                \
 239 }
 240
 241 #define CK_STAILQ_HEAD_INITIALIZER(head)                                \
 242         { NULL, &(head).cstqh_first }
 243
 244 #define CK_STAILQ_ENTRY(type)                                           \
 245 struct {                                                                \
 246         struct type *cstqe_next;        /* next element */                      \
 247 }
 248
 249 /*
 250  * Singly-linked Tail queue functions.
 251  */
 252 #define CK_STAILQ_CONCAT(head1, head2) do {                                     \
 253         if ((head2)->cstqh_first != NULL) {                                     \
 254                 ck_pr_store_ptr((head1)->cstqh_last, (head2)->cstqh_first);     \
 255                 ck_pr_fence_store();                                            \
 256                 (head1)->cstqh_last = (head2)->cstqh_last;                      \
 257                 CK_STAILQ_INIT((head2));                                        \
 258         }                                                                       \
 259 } while (0)
 260
 261 #define CK_STAILQ_EMPTY(head)   (ck_pr_load_ptr(&(head)->cstqh_first) == NULL)
 262
 263 #define CK_STAILQ_FIRST(head)   (ck_pr_load_ptr(&(head)->cstqh_first))
 264
 265 #define CK_STAILQ_FOREACH(var, head, field)                             \
 266         for((var) = CK_STAILQ_FIRST((head));                            \
 267            (var);                                                       \
 268            (var) = CK_STAILQ_NEXT((var), field))
 269
 270 #define CK_STAILQ_FOREACH_FROM(var, head, field)                        \
 271         for ((var) = ((var) != NULL ? (var) : CK_STAILQ_FIRST((head))); \
 272             (var);                                                      \
 273             (var) = CK_STAILQ_NEXT((var), field))
 274
 275 #define CK_STAILQ_FOREACH_SAFE(var, head, field, tvar)                  \
 276         for ((var) = CK_STAILQ_FIRST((head));                           \
 277             (var) && ((tvar) =                                          \
 278                 CK_STAILQ_NEXT((var), field), 1);                       \
 279             (var) = (tvar))
 280
 281 #define CK_STAILQ_INIT(head) do {                                       \
 282         ck_pr_store_ptr(&(head)->cstqh_first, NULL);                    \
 283         ck_pr_fence_store();                                            \
 284         (head)->cstqh_last = &(head)->cstqh_first;                      \
 285 } while (0)
 286
 287 #define CK_STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {                    \
 288         (elm)->field.cstqe_next = (tqelm)->field.cstqe_next;                    \
 289         ck_pr_fence_store();                                                    \
 290         ck_pr_store_ptr(&(tqelm)->field.cstqe_next, elm);                       \
 291         if ((elm)->field.cstqe_next == NULL)                                    \
 292                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 293 } while (0)
 294
 295 #define CK_STAILQ_INSERT_HEAD(head, elm, field) do {                            \
 296         (elm)->field.cstqe_next = (head)->cstqh_first;                          \
 297         ck_pr_fence_store();                                                    \
 298         ck_pr_store_ptr(&(head)->cstqh_first, elm);                             \
 299         if ((elm)->field.cstqe_next == NULL)                                    \
 300                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 301 } while (0)
 302
 303 #define CK_STAILQ_INSERT_TAIL(head, elm, field) do {                            \
 304         (elm)->field.cstqe_next = NULL;                                         \
 305         ck_pr_fence_store();                                                    \
 306         ck_pr_store_ptr((head)->cstqh_last, (elm));                             \
 307         (head)->cstqh_last = &(elm)->field.cstqe_next;                          \
 308 } while (0)
 309
 310 #define CK_STAILQ_NEXT(elm, field)                                              \
 311         (ck_pr_load_ptr(&(elm)->field.cstqe_next))
 312
 313 #define CK_STAILQ_REMOVE(head, elm, type, field) do {                           \
 314         if ((head)->cstqh_first == (elm)) {                                     \
 315                 CK_STAILQ_REMOVE_HEAD((head), field);                           \
 316         } else {                                                                \
 317                 struct type *curelm = (head)->cstqh_first;                      \
 318                 while (curelm->field.cstqe_next != (elm))                       \
 319                         curelm = curelm->field.cstqe_next;                      \
 320                 CK_STAILQ_REMOVE_AFTER(head, curelm, field);                    \
 321         }                                                                       \
 322 } while (0)
 323
 324 #define CK_STAILQ_REMOVE_AFTER(head, elm, field) do {                           \
 325         ck_pr_store_ptr(&(elm)->field.cstqe_next,                               \
 326             (elm)->field.cstqe_next->field.cstqe_next);                         \
 327         if ((elm)->field.cstqe_next == NULL)                                    \
 328                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 329 } while (0)
 330
 331 #define CK_STAILQ_REMOVE_HEAD(head, field) do {                                 \
 332         ck_pr_store_ptr(&(head)->cstqh_first,                                   \
 333             (head)->cstqh_first->field.cstqe_next);                             \
 334         if ((head)->cstqh_first == NULL)                                                \
 335                 (head)->cstqh_last = &(head)->cstqh_first;                      \
 336 } while (0)
 337
 338 #define CK_STAILQ_MOVE(head1, head2, field) do {                                \
 339         ck_pr_store_ptr(&(head1)->cstqh_first, (head2)->cstqh_first);           \
 340         (head1)->cstqh_last = (head2)->cstqh_last;                              \
 341         if ((head2)->cstqh_last == &(head2)->cstqh_first)                               \
 342                 (head1)->cstqh_last = &(head1)->cstqh_first;                    \
 343 } while (0)
 344
 345 /*
 346  * This operation is not applied atomically.
 347  */
 348 #define CK_STAILQ_SWAP(head1, head2, type) do {                         \
 349         struct type *swap_first = CK_STAILQ_FIRST(head1);               \
 350         struct type **swap_last = (head1)->cstqh_last;                  \
 351         CK_STAILQ_FIRST(head1) = CK_STAILQ_FIRST(head2);                \
 352         (head1)->cstqh_last = (head2)->cstqh_last;                      \
 353         CK_STAILQ_FIRST(head2) = swap_first;                            \
 354         (head2)->cstqh_last = swap_last;                                        \
 355         if (CK_STAILQ_EMPTY(head1))                                     \
 356                 (head1)->cstqh_last = &(head1)->cstqh_first;            \
 357         if (CK_STAILQ_EMPTY(head2))                                     \
 358                 (head2)->cstqh_last = &(head2)->cstqh_first;            \
 359 } while (0)
 360
 361 /*
 362  * List declarations.
 363  */
 364 #define CK_LIST_HEAD(name, type)                                                \
 365 struct name {                                                                   \
 366         struct type *clh_first; /* first element */                             \
 367 }
 368
 369 #define CK_LIST_HEAD_INITIALIZER(head)                                          \
 370         { NULL }
 371
 372 #define CK_LIST_ENTRY(type)                                                     \
 373 struct {                                                                        \
 374         struct type *cle_next;  /* next element */                              \
 375         struct type **cle_prev; /* address of previous next element */          \
 376 }
 377
 378 #define CK_LIST_FIRST(head)             ck_pr_load_ptr(&(head)->clh_first)
 379 #define CK_LIST_EMPTY(head)             (CK_LIST_FIRST(head) == NULL)
 380 #define CK_LIST_NEXT(elm, field)        ck_pr_load_ptr(&(elm)->field.cle_next)
 381
 382 #define CK_LIST_FOREACH(var, head, field)                                       \
 383         for ((var) = CK_LIST_FIRST((head));                                     \
 384             (var);                                                              \
 385             (var) = CK_LIST_NEXT((var), field))
 386
 387 #define CK_LIST_FOREACH_FROM(var, head, field)                                  \
 388         for ((var) = ((var) != NULL ? (var) : CK_LIST_FIRST((head)));           \
 389             (var);                                                              \
 390             (var) = CK_LIST_NEXT((var), field))
 391
 392 #define CK_LIST_FOREACH_SAFE(var, head, field, tvar)                              \
 393         for ((var) = CK_LIST_FIRST((head));                                       \
 394             (var) && ((tvar) = CK_LIST_NEXT((var), field), 1);                    \
 395             (var) = (tvar))
 396
 397 #define CK_LIST_INIT(head) do {                                                 \
 398         ck_pr_store_ptr(&(head)->clh_first, NULL);                              \
 399         ck_pr_fence_store();                                                    \
 400 } while (0)
 401
 402 #define CK_LIST_INSERT_AFTER(listelm, elm, field) do {                          \
 403         (elm)->field.cle_next = (listelm)->field.cle_next;                      \
 404         (elm)->field.cle_prev = &(listelm)->field.cle_next;                     \
 405         ck_pr_fence_store();                                                    \
 406         if ((listelm)->field.cle_next != NULL)                                  \
 407                 (listelm)->field.cle_next->field.cle_prev = &(elm)->field.cle_next;\
 408         ck_pr_store_ptr(&(listelm)->field.cle_next, elm);                       \
 409 } while (0)
 410
 411 #define CK_LIST_INSERT_BEFORE(listelm, elm, field) do {                         \
 412         (elm)->field.cle_prev = (listelm)->field.cle_prev;                      \
 413         (elm)->field.cle_next = (listelm);                                      \
 414         ck_pr_fence_store();                                                    \
 415         ck_pr_store_ptr((listelm)->field.cle_prev, (elm));                      \
 416         (listelm)->field.cle_prev = &(elm)->field.cle_next;                     \
 417 } while (0)
 418
 419 #define CK_LIST_INSERT_HEAD(head, elm, field) do {                              \
 420         (elm)->field.cle_next = (head)->clh_first;                              \
 421         ck_pr_fence_store();                                                    \
 422         if ((elm)->field.cle_next != NULL)                                      \
 423                 (head)->clh_first->field.cle_prev =  &(elm)->field.cle_next;    \
 424         ck_pr_store_ptr(&(head)->clh_first, elm);                               \
 425         (elm)->field.cle_prev = &(head)->clh_first;                             \
 426 } while (0)
 427
 428 #define CK_LIST_REMOVE(elm, field) do {                                         \
 429         ck_pr_store_ptr((elm)->field.cle_prev, (elm)->field.cle_next);          \
 430         if ((elm)->field.cle_next != NULL)                                      \
 431                 (elm)->field.cle_next->field.cle_prev = (elm)->field.cle_prev;  \
 432 } while (0)
 433
 434 #define CK_LIST_MOVE(head1, head2, field) do {                          \
 435         ck_pr_store_ptr(&(head1)->clh_first, (head2)->clh_first);               \
 436         if ((head1)->clh_first != NULL)                                 \
 437                 (head1)->clh_first->field.cle_prev = &(head1)->clh_first;       \
 438 } while (0)
 439
 440 /*
 441  * This operation is not applied atomically.
 442  */
 443 #define CK_LIST_SWAP(head1, head2, type, field) do {                    \
 444         struct type *swap_tmp = (head1)->clh_first;                     \
 445         (head1)->clh_first = (head2)->clh_first;                                \
 446         (head2)->clh_first = swap_tmp;                                  \
 447         if ((swap_tmp = (head1)->clh_first) != NULL)                    \
 448                 swap_tmp->field.cle_prev = &(head1)->clh_first;         \
 449         if ((swap_tmp = (head2)->clh_first) != NULL)                    \
 450                 swap_tmp->field.cle_prev = &(head2)->clh_first;         \
 451 } while (0)
 452
 453 #endif /* CK_QUEUE_H */