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$
  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) && (ck_pr_fence_load(), 1);                                   \
 154             (var) = CK_SLIST_NEXT((var), field))
 155
 156 #define CK_SLIST_FOREACH_SAFE(var, head, field, tvar)                            \
 157         for ((var) = CK_SLIST_FIRST(head);                                       \
 158             (var) && (ck_pr_fence_load(), (tvar) = CK_SLIST_NEXT(var, field), 1);\
 159             (var) = (tvar))
 160
 161 #define CK_SLIST_FOREACH_PREVPTR(var, varp, head, field)                        \
 162         for ((varp) = &(head)->cslh_first;                                      \
 163             ((var) = ck_pr_load_ptr(varp)) != NULL && (ck_pr_fence_load(), 1);  \
 164             (varp) = &(var)->field.csle_next)
 165
 166 #define CK_SLIST_INIT(head) do {                                                \
 167         ck_pr_store_ptr(&(head)->cslh_first, NULL);                             \
 168         ck_pr_fence_store();                                                    \
 169 } while (0)
 170
 171 #define CK_SLIST_INSERT_AFTER(a, b, field) do {                                 \
 172         (b)->field.csle_next = (a)->field.csle_next;                            \
 173         ck_pr_fence_store();                                                    \
 174         ck_pr_store_ptr(&(a)->field.csle_next, b);                              \
 175 } while (0)
 176
 177 #define CK_SLIST_INSERT_HEAD(head, elm, field) do {                             \
 178         (elm)->field.csle_next = (head)->cslh_first;                            \
 179         ck_pr_fence_store();                                                    \
 180         ck_pr_store_ptr(&(head)->cslh_first, elm);                              \
 181 } while (0)
 182
 183 #define CK_SLIST_REMOVE_AFTER(elm, field) do {                                  \
 184         ck_pr_store_ptr(&(elm)->field.csle_next,                                        \
 185             (elm)->field.csle_next->field.csle_next);                           \
 186 } while (0)
 187
 188 #define CK_SLIST_REMOVE(head, elm, type, field) do {                            \
 189         if ((head)->cslh_first == (elm)) {                                      \
 190                 CK_SLIST_REMOVE_HEAD((head), field);                            \
 191         } else {                                                                \
 192                 struct type *curelm = (head)->cslh_first;                       \
 193                 while (curelm->field.csle_next != (elm))                                \
 194                         curelm = curelm->field.csle_next;                       \
 195                 CK_SLIST_REMOVE_AFTER(curelm, field);                           \
 196         }                                                                       \
 197 } while (0)
 198
 199 #define CK_SLIST_REMOVE_HEAD(head, field) do {                                  \
 200         ck_pr_store_ptr(&(head)->cslh_first,                                    \
 201                 (head)->cslh_first->field.csle_next);                           \
 202 } while (0)
 203
 204 #define CK_SLIST_MOVE(head1, head2, field) do {                                 \
 205         ck_pr_store_ptr(&(head1)->cslh_first, (head2)->cslh_first);             \
 206 } while (0)
 207
 208 /*
 209  * This operation is not applied atomically.
 210  */
 211 #define CK_SLIST_SWAP(a, b, type) do {                                          \
 212         struct type *swap_first = (a)->cslh_first;                              \
 213         (a)->cslh_first = (b)->cslh_first;                                      \
 214         (b)->cslh_first = swap_first;                                           \
 215 } while (0)
 216
 217 /*
 218  * Singly-linked Tail queue declarations.
 219  */
 220 #define CK_STAILQ_HEAD(name, type)                                      \
 221 struct name {                                                           \
 222         struct type *cstqh_first;/* first element */                    \
 223         struct type **cstqh_last;/* addr of last next element */                \
 224 }
 225
 226 #define CK_STAILQ_HEAD_INITIALIZER(head)                                \
 227         { NULL, &(head).cstqh_first }
 228
 229 #define CK_STAILQ_ENTRY(type)                                           \
 230 struct {                                                                \
 231         struct type *cstqe_next;        /* next element */                      \
 232 }
 233
 234 /*
 235  * Singly-linked Tail queue functions.
 236  */
 237 #define CK_STAILQ_CONCAT(head1, head2) do {                                     \
 238         if ((head2)->cstqh_first != NULL) {                                     \
 239                 ck_pr_store_ptr((head1)->cstqh_last, (head2)->cstqh_first);     \
 240                 ck_pr_fence_store();                                            \
 241                 (head1)->cstqh_last = (head2)->cstqh_last;                      \
 242                 CK_STAILQ_INIT((head2));                                        \
 243         }                                                                       \
 244 } while (0)
 245
 246 #define CK_STAILQ_EMPTY(head)   (ck_pr_load_ptr(&(head)->cstqh_first) == NULL)
 247
 248 #define CK_STAILQ_FIRST(head)   (ck_pr_load_ptr(&(head)->cstqh_first))
 249
 250 #define CK_STAILQ_FOREACH(var, head, field)                             \
 251         for((var) = CK_STAILQ_FIRST((head));                            \
 252            (var) && (ck_pr_fence_load(), 1);                            \
 253            (var) = CK_STAILQ_NEXT((var), field))
 254
 255 #define CK_STAILQ_FOREACH_SAFE(var, head, field, tvar)                  \
 256         for ((var) = CK_STAILQ_FIRST((head));                           \
 257             (var) && (ck_pr_fence_load(), (tvar) =                      \
 258                 CK_STAILQ_NEXT((var), field), 1);                       \
 259             (var) = (tvar))
 260
 261 #define CK_STAILQ_INIT(head) do {                                       \
 262         ck_pr_store_ptr(&(head)->cstqh_first, NULL);                    \
 263         ck_pr_fence_store();                                            \
 264         (head)->cstqh_last = &(head)->cstqh_first;                      \
 265 } while (0)
 266
 267 #define CK_STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {                    \
 268         (elm)->field.cstqe_next = (tqelm)->field.cstqe_next;                    \
 269         ck_pr_fence_store();                                                    \
 270         ck_pr_store_ptr(&(tqelm)->field.cstqe_next, elm);                       \
 271         if ((elm)->field.cstqe_next == NULL)                                    \
 272                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 273 } while (0)
 274
 275 #define CK_STAILQ_INSERT_HEAD(head, elm, field) do {                            \
 276         (elm)->field.cstqe_next = (head)->cstqh_first;                          \
 277         ck_pr_fence_store();                                                    \
 278         ck_pr_store_ptr(&(head)->cstqh_first, elm);                             \
 279         if ((elm)->field.cstqe_next == NULL)                                    \
 280                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 281 } while (0)
 282
 283 #define CK_STAILQ_INSERT_TAIL(head, elm, field) do {                            \
 284         (elm)->field.cstqe_next = NULL;                                         \
 285         ck_pr_fence_store();                                                    \
 286         ck_pr_store_ptr((head)->cstqh_last, (elm));                             \
 287         (head)->cstqh_last = &(elm)->field.cstqe_next;                          \
 288 } while (0)
 289
 290 #define CK_STAILQ_NEXT(elm, field)                                              \
 291         (ck_pr_load_ptr(&(elm)->field.cstqe_next))
 292
 293 #define CK_STAILQ_REMOVE(head, elm, type, field) do {                           \
 294         if ((head)->cstqh_first == (elm)) {                                     \
 295                 CK_STAILQ_REMOVE_HEAD((head), field);                           \
 296         } else {                                                                \
 297                 struct type *curelm = (head)->cstqh_first;                      \
 298                 while (curelm->field.cstqe_next != (elm))                       \
 299                         curelm = curelm->field.cstqe_next;                      \
 300                 CK_STAILQ_REMOVE_AFTER(head, curelm, field);                    \
 301         }                                                                       \
 302 } while (0)
 303
 304 #define CK_STAILQ_REMOVE_AFTER(head, elm, field) do {                           \
 305         ck_pr_store_ptr(&(elm)->field.cstqe_next,                               \
 306             (elm)->field.cstqe_next->field.cstqe_next);                         \
 307         if ((elm)->field.cstqe_next == NULL)                                    \
 308                 (head)->cstqh_last = &(elm)->field.cstqe_next;                  \
 309 } while (0)
 310
 311 #define CK_STAILQ_REMOVE_HEAD(head, field) do {                                 \
 312         ck_pr_store_ptr(&(head)->cstqh_first,                                   \
 313             (head)->cstqh_first->field.cstqe_next);                             \
 314         if ((head)->cstqh_first == NULL)                                                \
 315                 (head)->cstqh_last = &(head)->cstqh_first;                      \
 316 } while (0)
 317
 318 #define CK_STAILQ_MOVE(head1, head2, field) do {                                \
 319         ck_pr_store_ptr(&(head1)->cstqh_first, (head2)->cstqh_first);           \
 320         (head1)->cstqh_last = (head2)->cstqh_last;                              \
 321         if ((head2)->cstqh_last == &(head2)->cstqh_first)                               \
 322                 (head1)->cstqh_last = &(head1)->cstqh_first;                    \
 323 } while (0)
 324
 325 /*
 326  * This operation is not applied atomically.
 327  */
 328 #define CK_STAILQ_SWAP(head1, head2, type) do {                         \
 329         struct type *swap_first = CK_STAILQ_FIRST(head1);               \
 330         struct type **swap_last = (head1)->cstqh_last;                  \
 331         CK_STAILQ_FIRST(head1) = CK_STAILQ_FIRST(head2);                \
 332         (head1)->cstqh_last = (head2)->cstqh_last;                      \
 333         CK_STAILQ_FIRST(head2) = swap_first;                            \
 334         (head2)->cstqh_last = swap_last;                                        \
 335         if (CK_STAILQ_EMPTY(head1))                                     \
 336                 (head1)->cstqh_last = &(head1)->cstqh_first;            \
 337         if (CK_STAILQ_EMPTY(head2))                                     \
 338                 (head2)->cstqh_last = &(head2)->cstqh_first;            \
 339 } while (0)
 340
 341 /*
 342  * List declarations.
 343  */
 344 #define CK_LIST_HEAD(name, type)                                                \
 345 struct name {                                                                   \
 346         struct type *clh_first; /* first element */                             \
 347 }
 348
 349 #define CK_LIST_HEAD_INITIALIZER(head)                                          \
 350         { NULL }
 351
 352 #define CK_LIST_ENTRY(type)                                                     \
 353 struct {                                                                        \
 354         struct type *cle_next;  /* next element */                              \
 355         struct type **cle_prev; /* address of previous next element */          \
 356 }
 357
 358 #define CK_LIST_FIRST(head)             ck_pr_load_ptr(&(head)->clh_first)
 359 #define CK_LIST_EMPTY(head)             (CK_LIST_FIRST(head) == NULL)
 360 #define CK_LIST_NEXT(elm, field)        ck_pr_load_ptr(&(elm)->field.cle_next)
 361
 362 #define CK_LIST_FOREACH(var, head, field)                                       \
 363         for ((var) = CK_LIST_FIRST((head));                                     \
 364             (var) && (ck_pr_fence_load(), 1);                                   \
 365             (var) = CK_LIST_NEXT((var), field))
 366
 367 #define CK_LIST_FOREACH_SAFE(var, head, field, tvar)                              \
 368         for ((var) = CK_LIST_FIRST((head));                                       \
 369             (var) && (ck_pr_fence_load(), (tvar) = CK_LIST_NEXT((var), field), 1);\
 370             (var) = (tvar))
 371
 372 #define CK_LIST_INIT(head) do {                                                 \
 373         ck_pr_store_ptr(&(head)->clh_first, NULL);                              \
 374         ck_pr_fence_store();                                                    \
 375 } while (0)
 376
 377 #define CK_LIST_INSERT_AFTER(listelm, elm, field) do {                          \
 378         (elm)->field.cle_next = (listelm)->field.cle_next;                      \
 379         (elm)->field.cle_prev = &(listelm)->field.cle_next;                     \
 380         ck_pr_fence_store();                                                    \
 381         if ((listelm)->field.cle_next != NULL)                                  \
 382                 (listelm)->field.cle_next->field.cle_prev = &(elm)->field.cle_next;\
 383         ck_pr_store_ptr(&(listelm)->field.cle_next, elm);                       \
 384 } while (0)
 385
 386 #define CK_LIST_INSERT_BEFORE(listelm, elm, field) do {                         \
 387         (elm)->field.cle_prev = (listelm)->field.cle_prev;                      \
 388         (elm)->field.cle_next = (listelm);                                      \
 389         ck_pr_fence_store();                                                    \
 390         ck_pr_store_ptr((listelm)->field.cle_prev, (elm));                      \
 391         (listelm)->field.cle_prev = &(elm)->field.cle_next;                     \
 392 } while (0)
 393
 394 #define CK_LIST_INSERT_HEAD(head, elm, field) do {                              \
 395         (elm)->field.cle_next = (head)->clh_first;                              \
 396         ck_pr_fence_store();                                                    \
 397         if ((elm)->field.cle_next != NULL)                                      \
 398                 (head)->clh_first->field.cle_prev =  &(elm)->field.cle_next;    \
 399         ck_pr_store_ptr(&(head)->clh_first, elm);                               \
 400         (elm)->field.cle_prev = &(head)->clh_first;                             \
 401 } while (0)
 402
 403 #define CK_LIST_REMOVE(elm, field) do {                                         \
 404         ck_pr_store_ptr((elm)->field.cle_prev, (elm)->field.cle_next);          \
 405         if ((elm)->field.cle_next != NULL)                                      \
 406                 (elm)->field.cle_next->field.cle_prev = (elm)->field.cle_prev;  \
 407 } while (0)
 408
 409 #define CK_LIST_MOVE(head1, head2, field) do {                          \
 410         ck_pr_store_ptr(&(head1)->clh_first, (head2)->clh_first);               \
 411         if ((head1)->clh_first != NULL)                                 \
 412                 (head1)->clh_first->field.cle_prev = &(head1)->clh_first;       \
 413 } while (0)
 414
 415 /*
 416  * This operation is not applied atomically.
 417  */
 418 #define CK_LIST_SWAP(head1, head2, type, field) do {                    \
 419         struct type *swap_tmp = (head1)->clh_first;                     \
 420         (head1)->clh_first = (head2)->clh_first;                                \
 421         (head2)->clh_first = swap_tmp;                                  \
 422         if ((swap_tmp = (head1)->clh_first) != NULL)                    \
 423                 swap_tmp->field.cle_prev = &(head1)->clh_first;         \
 424         if ((swap_tmp = (head2)->clh_first) != NULL)                    \
 425                 swap_tmp->field.cle_prev = &(head2)->clh_first;         \
 426 } while (0)
 427
 428 #endif /* CK_QUEUE_H */