1*b5677b36Schristos /* $NetBSD: list.h,v 1.1.1.1 2009/04/12 15:33:33 christos Exp $ */ 2*b5677b36Schristos 3*b5677b36Schristos /* 4*b5677b36Schristos * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 5*b5677b36Schristos * Copyright (c) 1997,1999 by Internet Software Consortium. 6*b5677b36Schristos * 7*b5677b36Schristos * Permission to use, copy, modify, and distribute this software for any 8*b5677b36Schristos * purpose with or without fee is hereby granted, provided that the above 9*b5677b36Schristos * copyright notice and this permission notice appear in all copies. 10*b5677b36Schristos * 11*b5677b36Schristos * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 12*b5677b36Schristos * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13*b5677b36Schristos * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 14*b5677b36Schristos * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15*b5677b36Schristos * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16*b5677b36Schristos * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 17*b5677b36Schristos * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18*b5677b36Schristos */ 19*b5677b36Schristos 20*b5677b36Schristos #ifndef LIST_H 21*b5677b36Schristos #define LIST_H 1 22*b5677b36Schristos #include <isc/assertions.h> 23*b5677b36Schristos 24*b5677b36Schristos #define LIST(type) struct { type *head, *tail; } 25*b5677b36Schristos #define INIT_LIST(list) \ 26*b5677b36Schristos do { (list).head = NULL; (list).tail = NULL; } while (0) 27*b5677b36Schristos 28*b5677b36Schristos #define LINK(type) struct { type *prev, *next; } 29*b5677b36Schristos #define INIT_LINK_TYPE(elt, link, type) \ 30*b5677b36Schristos do { \ 31*b5677b36Schristos (elt)->link.prev = (type *)(-1); \ 32*b5677b36Schristos (elt)->link.next = (type *)(-1); \ 33*b5677b36Schristos } while (0) 34*b5677b36Schristos #define INIT_LINK(elt, link) \ 35*b5677b36Schristos INIT_LINK_TYPE(elt, link, void) 36*b5677b36Schristos #define LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1) && \ 37*b5677b36Schristos (void *)((elt)->link.next) != (void *)(-1)) 38*b5677b36Schristos 39*b5677b36Schristos #define HEAD(list) ((list).head) 40*b5677b36Schristos #define TAIL(list) ((list).tail) 41*b5677b36Schristos #define EMPTY(list) ((list).head == NULL) 42*b5677b36Schristos 43*b5677b36Schristos #define PREPEND(list, elt, link) \ 44*b5677b36Schristos do { \ 45*b5677b36Schristos INSIST(!LINKED(elt, link));\ 46*b5677b36Schristos if ((list).head != NULL) \ 47*b5677b36Schristos (list).head->link.prev = (elt); \ 48*b5677b36Schristos else \ 49*b5677b36Schristos (list).tail = (elt); \ 50*b5677b36Schristos (elt)->link.prev = NULL; \ 51*b5677b36Schristos (elt)->link.next = (list).head; \ 52*b5677b36Schristos (list).head = (elt); \ 53*b5677b36Schristos } while (0) 54*b5677b36Schristos 55*b5677b36Schristos #define APPEND(list, elt, link) \ 56*b5677b36Schristos do { \ 57*b5677b36Schristos INSIST(!LINKED(elt, link));\ 58*b5677b36Schristos if ((list).tail != NULL) \ 59*b5677b36Schristos (list).tail->link.next = (elt); \ 60*b5677b36Schristos else \ 61*b5677b36Schristos (list).head = (elt); \ 62*b5677b36Schristos (elt)->link.prev = (list).tail; \ 63*b5677b36Schristos (elt)->link.next = NULL; \ 64*b5677b36Schristos (list).tail = (elt); \ 65*b5677b36Schristos } while (0) 66*b5677b36Schristos 67*b5677b36Schristos #define UNLINK_TYPE(list, elt, link, type) \ 68*b5677b36Schristos do { \ 69*b5677b36Schristos INSIST(LINKED(elt, link));\ 70*b5677b36Schristos if ((elt)->link.next != NULL) \ 71*b5677b36Schristos (elt)->link.next->link.prev = (elt)->link.prev; \ 72*b5677b36Schristos else { \ 73*b5677b36Schristos INSIST((list).tail == (elt)); \ 74*b5677b36Schristos (list).tail = (elt)->link.prev; \ 75*b5677b36Schristos } \ 76*b5677b36Schristos if ((elt)->link.prev != NULL) \ 77*b5677b36Schristos (elt)->link.prev->link.next = (elt)->link.next; \ 78*b5677b36Schristos else { \ 79*b5677b36Schristos INSIST((list).head == (elt)); \ 80*b5677b36Schristos (list).head = (elt)->link.next; \ 81*b5677b36Schristos } \ 82*b5677b36Schristos INIT_LINK_TYPE(elt, link, type); \ 83*b5677b36Schristos } while (0) 84*b5677b36Schristos #define UNLINK(list, elt, link) \ 85*b5677b36Schristos UNLINK_TYPE(list, elt, link, void) 86*b5677b36Schristos 87*b5677b36Schristos #define PREV(elt, link) ((elt)->link.prev) 88*b5677b36Schristos #define NEXT(elt, link) ((elt)->link.next) 89*b5677b36Schristos 90*b5677b36Schristos #define INSERT_BEFORE(list, before, elt, link) \ 91*b5677b36Schristos do { \ 92*b5677b36Schristos INSIST(!LINKED(elt, link));\ 93*b5677b36Schristos if ((before)->link.prev == NULL) \ 94*b5677b36Schristos PREPEND(list, elt, link); \ 95*b5677b36Schristos else { \ 96*b5677b36Schristos (elt)->link.prev = (before)->link.prev; \ 97*b5677b36Schristos (before)->link.prev = (elt); \ 98*b5677b36Schristos (elt)->link.prev->link.next = (elt); \ 99*b5677b36Schristos (elt)->link.next = (before); \ 100*b5677b36Schristos } \ 101*b5677b36Schristos } while (0) 102*b5677b36Schristos 103*b5677b36Schristos #define INSERT_AFTER(list, after, elt, link) \ 104*b5677b36Schristos do { \ 105*b5677b36Schristos INSIST(!LINKED(elt, link));\ 106*b5677b36Schristos if ((after)->link.next == NULL) \ 107*b5677b36Schristos APPEND(list, elt, link); \ 108*b5677b36Schristos else { \ 109*b5677b36Schristos (elt)->link.next = (after)->link.next; \ 110*b5677b36Schristos (after)->link.next = (elt); \ 111*b5677b36Schristos (elt)->link.next->link.prev = (elt); \ 112*b5677b36Schristos (elt)->link.prev = (after); \ 113*b5677b36Schristos } \ 114*b5677b36Schristos } while (0) 115*b5677b36Schristos 116*b5677b36Schristos #define ENQUEUE(list, elt, link) APPEND(list, elt, link) 117*b5677b36Schristos #define DEQUEUE(list, elt, link) UNLINK(list, elt, link) 118*b5677b36Schristos 119*b5677b36Schristos #endif /* LIST_H */ 120*b5677b36Schristos /*! \file */ 121