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