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