1309260Scognet/* 2309260Scognet * Copyright 2012-2015 Samy Al Bahra. 3309260Scognet * All rights reserved. 4309260Scognet * 5309260Scognet * Redistribution and use in source and binary forms, with or without 6309260Scognet * modification, are permitted provided that the following conditions 7309260Scognet * are met: 8309260Scognet * 1. Redistributions of source code must retain the above copyright 9309260Scognet * notice, this list of conditions and the following disclaimer. 10309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 11309260Scognet * notice, this list of conditions and the following disclaimer in the 12309260Scognet * documentation and/or other materials provided with the distribution. 13309260Scognet * 14309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24309260Scognet * SUCH DAMAGE. 25309260Scognet */ 26309260Scognet 27309260Scognet/*- 28309260Scognet * Copyright (c) 1991, 1993 29309260Scognet * The Regents of the University of California. All rights reserved. 30309260Scognet * 31309260Scognet * Redistribution and use in source and binary forms, with or without 32309260Scognet * modification, are permitted provided that the following conditions 33309260Scognet * are met: 34309260Scognet * 1. Redistributions of source code must retain the above copyright 35309260Scognet * notice, this list of conditions and the following disclaimer. 36309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 37309260Scognet * notice, this list of conditions and the following disclaimer in the 38309260Scognet * documentation and/or other materials provided with the distribution. 39309260Scognet * 4. Neither the name of the University nor the names of its contributors 40309260Scognet * may be used to endorse or promote products derived from this software 41309260Scognet * without specific prior written permission. 42309260Scognet * 43309260Scognet * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 44309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 45309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 46309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 47309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 48309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 49309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 50309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 51309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 52309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 53309260Scognet * SUCH DAMAGE. 54309260Scognet * 55309260Scognet * @(#)queue.h 8.5 (Berkeley) 8/20/94 56309260Scognet * $FreeBSD: stable/11/sys/contrib/ck/include/ck_queue.h 339650 2018-10-23 13:12:42Z avg $ 57309260Scognet */ 58309260Scognet 59309260Scognet#ifndef CK_QUEUE_H 60309260Scognet#define CK_QUEUE_H 61309260Scognet 62309260Scognet#include <ck_pr.h> 63309260Scognet 64309260Scognet/* 65309260Scognet * This file defines three types of data structures: singly-linked lists, 66309260Scognet * singly-linked tail queues and lists. 67309260Scognet * 68309260Scognet * A singly-linked list is headed by a single forward pointer. The elements 69309260Scognet * are singly linked for minimum space and pointer manipulation overhead at 70309260Scognet * the expense of O(n) removal for arbitrary elements. New elements can be 71309260Scognet * added to the list after an existing element or at the head of the list. 72309260Scognet * Elements being removed from the head of the list should use the explicit 73309260Scognet * macro for this purpose for optimum efficiency. A singly-linked list may 74309260Scognet * only be traversed in the forward direction. Singly-linked lists are ideal 75309260Scognet * for applications with large datasets and few or no removals or for 76309260Scognet * implementing a LIFO queue. 77309260Scognet * 78309260Scognet * A singly-linked tail queue is headed by a pair of pointers, one to the 79309260Scognet * head of the list and the other to the tail of the list. The elements are 80309260Scognet * singly linked for minimum space and pointer manipulation overhead at the 81309260Scognet * expense of O(n) removal for arbitrary elements. New elements can be added 82309260Scognet * to the list after an existing element, at the head of the list, or at the 83309260Scognet * end of the list. Elements being removed from the head of the tail queue 84309260Scognet * should use the explicit macro for this purpose for optimum efficiency. 85309260Scognet * A singly-linked tail queue may only be traversed in the forward direction. 86309260Scognet * Singly-linked tail queues are ideal for applications with large datasets 87309260Scognet * and few or no removals or for implementing a FIFO queue. 88309260Scognet * 89309260Scognet * A list is headed by a single forward pointer (or an array of forward 90309260Scognet * pointers for a hash table header). The elements are doubly linked 91309260Scognet * so that an arbitrary element can be removed without a need to 92309260Scognet * traverse the list. New elements can be added to the list before 93309260Scognet * or after an existing element or at the head of the list. A list 94309260Scognet * may only be traversed in the forward direction. 95309260Scognet * 96309260Scognet * It is safe to use _FOREACH/_FOREACH_SAFE in the presence of concurrent 97309260Scognet * modifications to the list. Writers to these lists must, on the other hand, 98309260Scognet * implement writer-side synchronization. The _SWAP operations are not atomic. 99309260Scognet * This facility is currently unsupported on architectures such as the Alpha 100309260Scognet * which require load-depend memory fences. 101309260Scognet * 102309260Scognet * CK_SLIST CK_LIST CK_STAILQ 103309260Scognet * _HEAD + + + 104309260Scognet * _HEAD_INITIALIZER + + + 105309260Scognet * _ENTRY + + + 106309260Scognet * _INIT + + + 107309260Scognet * _EMPTY + + + 108309260Scognet * _FIRST + + + 109309260Scognet * _NEXT + + + 110309260Scognet * _FOREACH + + + 111309260Scognet * _FOREACH_SAFE + + + 112309260Scognet * _INSERT_HEAD + + + 113309260Scognet * _INSERT_BEFORE - + - 114309260Scognet * _INSERT_AFTER + + + 115309260Scognet * _INSERT_TAIL - - + 116309260Scognet * _REMOVE_AFTER + - + 117309260Scognet * _REMOVE_HEAD + - + 118309260Scognet * _REMOVE + + + 119309260Scognet * _SWAP + + + 120309260Scognet * _MOVE + + + 121309260Scognet */ 122309260Scognet 123309260Scognet/* 124309260Scognet * Singly-linked List declarations. 125309260Scognet */ 126309260Scognet#define CK_SLIST_HEAD(name, type) \ 127309260Scognetstruct name { \ 128339597Savg struct type *cslh_first; /* first element */ \ 129309260Scognet} 130309260Scognet 131309260Scognet#define CK_SLIST_HEAD_INITIALIZER(head) \ 132309260Scognet { NULL } 133309260Scognet 134309260Scognet#define CK_SLIST_ENTRY(type) \ 135309260Scognetstruct { \ 136339597Savg struct type *csle_next; /* next element */ \ 137309260Scognet} 138309260Scognet 139309260Scognet/* 140309260Scognet * Singly-linked List functions. 141309260Scognet */ 142309260Scognet#define CK_SLIST_EMPTY(head) \ 143339597Savg (ck_pr_load_ptr(&(head)->cslh_first) == NULL) 144309260Scognet 145309260Scognet#define CK_SLIST_FIRST(head) \ 146339597Savg (ck_pr_load_ptr(&(head)->cslh_first)) 147309260Scognet 148309260Scognet#define CK_SLIST_NEXT(elm, field) \ 149339597Savg ck_pr_load_ptr(&((elm)->field.csle_next)) 150309260Scognet 151309260Scognet#define CK_SLIST_FOREACH(var, head, field) \ 152309260Scognet for ((var) = CK_SLIST_FIRST((head)); \ 153309260Scognet (var) && (ck_pr_fence_load(), 1); \ 154309260Scognet (var) = CK_SLIST_NEXT((var), field)) 155309260Scognet 156309260Scognet#define CK_SLIST_FOREACH_SAFE(var, head, field, tvar) \ 157309260Scognet for ((var) = CK_SLIST_FIRST(head); \ 158309260Scognet (var) && (ck_pr_fence_load(), (tvar) = CK_SLIST_NEXT(var, field), 1);\ 159309260Scognet (var) = (tvar)) 160309260Scognet 161309260Scognet#define CK_SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 162339597Savg for ((varp) = &(head)->cslh_first; \ 163309260Scognet ((var) = ck_pr_load_ptr(varp)) != NULL && (ck_pr_fence_load(), 1); \ 164339597Savg (varp) = &(var)->field.csle_next) 165309260Scognet 166309260Scognet#define CK_SLIST_INIT(head) do { \ 167339597Savg ck_pr_store_ptr(&(head)->cslh_first, NULL); \ 168309260Scognet ck_pr_fence_store(); \ 169309260Scognet} while (0) 170309260Scognet 171309260Scognet#define CK_SLIST_INSERT_AFTER(a, b, field) do { \ 172339597Savg (b)->field.csle_next = (a)->field.csle_next; \ 173309260Scognet ck_pr_fence_store(); \ 174339597Savg ck_pr_store_ptr(&(a)->field.csle_next, b); \ 175309260Scognet} while (0) 176309260Scognet 177309260Scognet#define CK_SLIST_INSERT_HEAD(head, elm, field) do { \ 178339597Savg (elm)->field.csle_next = (head)->cslh_first; \ 179309260Scognet ck_pr_fence_store(); \ 180339597Savg ck_pr_store_ptr(&(head)->cslh_first, elm); \ 181309260Scognet} while (0) 182309260Scognet 183339650Savg#define CK_SLIST_INSERT_PREVPTR(prevp, slistelm, elm, field) do { \ 184339650Savg (elm)->field.csle_next = (slistelm); \ 185339650Savg ck_pr_fence_store(); \ 186339650Savg ck_pr_store_ptr(prevp, elm); \ 187339650Savg} while (0) 188339650Savg 189309260Scognet#define CK_SLIST_REMOVE_AFTER(elm, field) do { \ 190339650Savg ck_pr_store_ptr(&(elm)->field.csle_next, \ 191339597Savg (elm)->field.csle_next->field.csle_next); \ 192309260Scognet} while (0) 193309260Scognet 194309260Scognet#define CK_SLIST_REMOVE(head, elm, type, field) do { \ 195339597Savg if ((head)->cslh_first == (elm)) { \ 196309260Scognet CK_SLIST_REMOVE_HEAD((head), field); \ 197309260Scognet } else { \ 198339597Savg struct type *curelm = (head)->cslh_first; \ 199339650Savg while (curelm->field.csle_next != (elm)) \ 200339597Savg curelm = curelm->field.csle_next; \ 201309260Scognet CK_SLIST_REMOVE_AFTER(curelm, field); \ 202309260Scognet } \ 203309260Scognet} while (0) 204309260Scognet 205309260Scognet#define CK_SLIST_REMOVE_HEAD(head, field) do { \ 206339597Savg ck_pr_store_ptr(&(head)->cslh_first, \ 207339597Savg (head)->cslh_first->field.csle_next); \ 208309260Scognet} while (0) 209309260Scognet 210339650Savg#define CK_SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 211339650Savg ck_pr_store_ptr(prevptr, (elm)->field.csle_next); \ 212339650Savg} while (0) 213339650Savg 214309260Scognet#define CK_SLIST_MOVE(head1, head2, field) do { \ 215339597Savg ck_pr_store_ptr(&(head1)->cslh_first, (head2)->cslh_first); \ 216309260Scognet} while (0) 217309260Scognet 218309260Scognet/* 219309260Scognet * This operation is not applied atomically. 220309260Scognet */ 221309260Scognet#define CK_SLIST_SWAP(a, b, type) do { \ 222339597Savg struct type *swap_first = (a)->cslh_first; \ 223339597Savg (a)->cslh_first = (b)->cslh_first; \ 224339597Savg (b)->cslh_first = swap_first; \ 225309260Scognet} while (0) 226309260Scognet 227309260Scognet/* 228309260Scognet * Singly-linked Tail queue declarations. 229309260Scognet */ 230309260Scognet#define CK_STAILQ_HEAD(name, type) \ 231309260Scognetstruct name { \ 232339597Savg struct type *cstqh_first;/* first element */ \ 233339597Savg struct type **cstqh_last;/* addr of last next element */ \ 234309260Scognet} 235309260Scognet 236309260Scognet#define CK_STAILQ_HEAD_INITIALIZER(head) \ 237339597Savg { NULL, &(head).cstqh_first } 238309260Scognet 239309260Scognet#define CK_STAILQ_ENTRY(type) \ 240309260Scognetstruct { \ 241339597Savg struct type *cstqe_next; /* next element */ \ 242309260Scognet} 243309260Scognet 244309260Scognet/* 245309260Scognet * Singly-linked Tail queue functions. 246309260Scognet */ 247309260Scognet#define CK_STAILQ_CONCAT(head1, head2) do { \ 248339597Savg if ((head2)->cstqh_first != NULL) { \ 249339597Savg ck_pr_store_ptr((head1)->cstqh_last, (head2)->cstqh_first); \ 250309260Scognet ck_pr_fence_store(); \ 251339597Savg (head1)->cstqh_last = (head2)->cstqh_last; \ 252309260Scognet CK_STAILQ_INIT((head2)); \ 253309260Scognet } \ 254309260Scognet} while (0) 255309260Scognet 256339597Savg#define CK_STAILQ_EMPTY(head) (ck_pr_load_ptr(&(head)->cstqh_first) == NULL) 257309260Scognet 258339597Savg#define CK_STAILQ_FIRST(head) (ck_pr_load_ptr(&(head)->cstqh_first)) 259309260Scognet 260309260Scognet#define CK_STAILQ_FOREACH(var, head, field) \ 261309260Scognet for((var) = CK_STAILQ_FIRST((head)); \ 262309260Scognet (var) && (ck_pr_fence_load(), 1); \ 263309260Scognet (var) = CK_STAILQ_NEXT((var), field)) 264309260Scognet 265309260Scognet#define CK_STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 266309260Scognet for ((var) = CK_STAILQ_FIRST((head)); \ 267309260Scognet (var) && (ck_pr_fence_load(), (tvar) = \ 268309260Scognet CK_STAILQ_NEXT((var), field), 1); \ 269309260Scognet (var) = (tvar)) 270309260Scognet 271309260Scognet#define CK_STAILQ_INIT(head) do { \ 272339597Savg ck_pr_store_ptr(&(head)->cstqh_first, NULL); \ 273309260Scognet ck_pr_fence_store(); \ 274339597Savg (head)->cstqh_last = &(head)->cstqh_first; \ 275309260Scognet} while (0) 276309260Scognet 277309260Scognet#define CK_STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 278339597Savg (elm)->field.cstqe_next = (tqelm)->field.cstqe_next; \ 279309260Scognet ck_pr_fence_store(); \ 280339597Savg ck_pr_store_ptr(&(tqelm)->field.cstqe_next, elm); \ 281339597Savg if ((elm)->field.cstqe_next == NULL) \ 282339597Savg (head)->cstqh_last = &(elm)->field.cstqe_next; \ 283309260Scognet} while (0) 284309260Scognet 285309260Scognet#define CK_STAILQ_INSERT_HEAD(head, elm, field) do { \ 286339597Savg (elm)->field.cstqe_next = (head)->cstqh_first; \ 287309260Scognet ck_pr_fence_store(); \ 288339597Savg ck_pr_store_ptr(&(head)->cstqh_first, elm); \ 289339597Savg if ((elm)->field.cstqe_next == NULL) \ 290339597Savg (head)->cstqh_last = &(elm)->field.cstqe_next; \ 291309260Scognet} while (0) 292309260Scognet 293309260Scognet#define CK_STAILQ_INSERT_TAIL(head, elm, field) do { \ 294339597Savg (elm)->field.cstqe_next = NULL; \ 295309260Scognet ck_pr_fence_store(); \ 296339597Savg ck_pr_store_ptr((head)->cstqh_last, (elm)); \ 297339597Savg (head)->cstqh_last = &(elm)->field.cstqe_next; \ 298309260Scognet} while (0) 299309260Scognet 300309260Scognet#define CK_STAILQ_NEXT(elm, field) \ 301339597Savg (ck_pr_load_ptr(&(elm)->field.cstqe_next)) 302309260Scognet 303309260Scognet#define CK_STAILQ_REMOVE(head, elm, type, field) do { \ 304339597Savg if ((head)->cstqh_first == (elm)) { \ 305309260Scognet CK_STAILQ_REMOVE_HEAD((head), field); \ 306309260Scognet } else { \ 307339597Savg struct type *curelm = (head)->cstqh_first; \ 308339597Savg while (curelm->field.cstqe_next != (elm)) \ 309339597Savg curelm = curelm->field.cstqe_next; \ 310309260Scognet CK_STAILQ_REMOVE_AFTER(head, curelm, field); \ 311309260Scognet } \ 312309260Scognet} while (0) 313309260Scognet 314309260Scognet#define CK_STAILQ_REMOVE_AFTER(head, elm, field) do { \ 315339597Savg ck_pr_store_ptr(&(elm)->field.cstqe_next, \ 316339597Savg (elm)->field.cstqe_next->field.cstqe_next); \ 317339597Savg if ((elm)->field.cstqe_next == NULL) \ 318339597Savg (head)->cstqh_last = &(elm)->field.cstqe_next; \ 319309260Scognet} while (0) 320309260Scognet 321309260Scognet#define CK_STAILQ_REMOVE_HEAD(head, field) do { \ 322339597Savg ck_pr_store_ptr(&(head)->cstqh_first, \ 323339597Savg (head)->cstqh_first->field.cstqe_next); \ 324339597Savg if ((head)->cstqh_first == NULL) \ 325339597Savg (head)->cstqh_last = &(head)->cstqh_first; \ 326309260Scognet} while (0) 327309260Scognet 328309260Scognet#define CK_STAILQ_MOVE(head1, head2, field) do { \ 329339597Savg ck_pr_store_ptr(&(head1)->cstqh_first, (head2)->cstqh_first); \ 330339597Savg (head1)->cstqh_last = (head2)->cstqh_last; \ 331339597Savg if ((head2)->cstqh_last == &(head2)->cstqh_first) \ 332339597Savg (head1)->cstqh_last = &(head1)->cstqh_first; \ 333309260Scognet} while (0) 334309260Scognet 335309260Scognet/* 336309260Scognet * This operation is not applied atomically. 337309260Scognet */ 338309260Scognet#define CK_STAILQ_SWAP(head1, head2, type) do { \ 339309260Scognet struct type *swap_first = CK_STAILQ_FIRST(head1); \ 340339597Savg struct type **swap_last = (head1)->cstqh_last; \ 341309260Scognet CK_STAILQ_FIRST(head1) = CK_STAILQ_FIRST(head2); \ 342339597Savg (head1)->cstqh_last = (head2)->cstqh_last; \ 343309260Scognet CK_STAILQ_FIRST(head2) = swap_first; \ 344339597Savg (head2)->cstqh_last = swap_last; \ 345309260Scognet if (CK_STAILQ_EMPTY(head1)) \ 346339597Savg (head1)->cstqh_last = &(head1)->cstqh_first; \ 347309260Scognet if (CK_STAILQ_EMPTY(head2)) \ 348339597Savg (head2)->cstqh_last = &(head2)->cstqh_first; \ 349309260Scognet} while (0) 350309260Scognet 351309260Scognet/* 352309260Scognet * List declarations. 353309260Scognet */ 354309260Scognet#define CK_LIST_HEAD(name, type) \ 355309260Scognetstruct name { \ 356339597Savg struct type *clh_first; /* first element */ \ 357309260Scognet} 358309260Scognet 359309260Scognet#define CK_LIST_HEAD_INITIALIZER(head) \ 360309260Scognet { NULL } 361309260Scognet 362309260Scognet#define CK_LIST_ENTRY(type) \ 363309260Scognetstruct { \ 364339597Savg struct type *cle_next; /* next element */ \ 365339597Savg struct type **cle_prev; /* address of previous next element */ \ 366309260Scognet} 367309260Scognet 368339597Savg#define CK_LIST_FIRST(head) ck_pr_load_ptr(&(head)->clh_first) 369309260Scognet#define CK_LIST_EMPTY(head) (CK_LIST_FIRST(head) == NULL) 370339597Savg#define CK_LIST_NEXT(elm, field) ck_pr_load_ptr(&(elm)->field.cle_next) 371309260Scognet 372309260Scognet#define CK_LIST_FOREACH(var, head, field) \ 373309260Scognet for ((var) = CK_LIST_FIRST((head)); \ 374309260Scognet (var) && (ck_pr_fence_load(), 1); \ 375309260Scognet (var) = CK_LIST_NEXT((var), field)) 376309260Scognet 377309260Scognet#define CK_LIST_FOREACH_SAFE(var, head, field, tvar) \ 378309260Scognet for ((var) = CK_LIST_FIRST((head)); \ 379309260Scognet (var) && (ck_pr_fence_load(), (tvar) = CK_LIST_NEXT((var), field), 1);\ 380309260Scognet (var) = (tvar)) 381309260Scognet 382309260Scognet#define CK_LIST_INIT(head) do { \ 383339597Savg ck_pr_store_ptr(&(head)->clh_first, NULL); \ 384309260Scognet ck_pr_fence_store(); \ 385309260Scognet} while (0) 386309260Scognet 387309260Scognet#define CK_LIST_INSERT_AFTER(listelm, elm, field) do { \ 388339597Savg (elm)->field.cle_next = (listelm)->field.cle_next; \ 389339597Savg (elm)->field.cle_prev = &(listelm)->field.cle_next; \ 390309260Scognet ck_pr_fence_store(); \ 391339597Savg if ((listelm)->field.cle_next != NULL) \ 392339597Savg (listelm)->field.cle_next->field.cle_prev = &(elm)->field.cle_next;\ 393339597Savg ck_pr_store_ptr(&(listelm)->field.cle_next, elm); \ 394309260Scognet} while (0) 395309260Scognet 396309260Scognet#define CK_LIST_INSERT_BEFORE(listelm, elm, field) do { \ 397339597Savg (elm)->field.cle_prev = (listelm)->field.cle_prev; \ 398339597Savg (elm)->field.cle_next = (listelm); \ 399309260Scognet ck_pr_fence_store(); \ 400339597Savg ck_pr_store_ptr((listelm)->field.cle_prev, (elm)); \ 401339597Savg (listelm)->field.cle_prev = &(elm)->field.cle_next; \ 402309260Scognet} while (0) 403309260Scognet 404309260Scognet#define CK_LIST_INSERT_HEAD(head, elm, field) do { \ 405339597Savg (elm)->field.cle_next = (head)->clh_first; \ 406309260Scognet ck_pr_fence_store(); \ 407339597Savg if ((elm)->field.cle_next != NULL) \ 408339597Savg (head)->clh_first->field.cle_prev = &(elm)->field.cle_next; \ 409339597Savg ck_pr_store_ptr(&(head)->clh_first, elm); \ 410339597Savg (elm)->field.cle_prev = &(head)->clh_first; \ 411309260Scognet} while (0) 412309260Scognet 413309260Scognet#define CK_LIST_REMOVE(elm, field) do { \ 414339597Savg ck_pr_store_ptr((elm)->field.cle_prev, (elm)->field.cle_next); \ 415339597Savg if ((elm)->field.cle_next != NULL) \ 416339597Savg (elm)->field.cle_next->field.cle_prev = (elm)->field.cle_prev; \ 417309260Scognet} while (0) 418309260Scognet 419309260Scognet#define CK_LIST_MOVE(head1, head2, field) do { \ 420339597Savg ck_pr_store_ptr(&(head1)->clh_first, (head2)->clh_first); \ 421339597Savg if ((head1)->clh_first != NULL) \ 422339597Savg (head1)->clh_first->field.cle_prev = &(head1)->clh_first; \ 423309260Scognet} while (0) 424309260Scognet 425309260Scognet/* 426309260Scognet * This operation is not applied atomically. 427309260Scognet */ 428309260Scognet#define CK_LIST_SWAP(head1, head2, type, field) do { \ 429339597Savg struct type *swap_tmp = (head1)->clh_first; \ 430339597Savg (head1)->clh_first = (head2)->clh_first; \ 431339597Savg (head2)->clh_first = swap_tmp; \ 432339597Savg if ((swap_tmp = (head1)->clh_first) != NULL) \ 433339597Savg swap_tmp->field.cle_prev = &(head1)->clh_first; \ 434339597Savg if ((swap_tmp = (head2)->clh_first) != NULL) \ 435339597Savg swap_tmp->field.cle_prev = &(head2)->clh_first; \ 436309260Scognet} while (0) 437309260Scognet 438309260Scognet#endif /* CK_QUEUE_H */ 439