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