summaryrefslogtreecommitdiffstats
path: root/meta/recipes-core/bsd-headers
diff options
context:
space:
mode:
authorKhem Raj <raj.khem@gmail.com>2016-01-08 09:05:14 +0000
committerRichard Purdie <richard.purdie@linuxfoundation.org>2016-01-24 09:40:30 +0000
commit06d020489dee672b1895f19c271eba4e17430106 (patch)
tree4b68d568fa629869baecbbf2a8d210cc476beebe /meta/recipes-core/bsd-headers
parentc2c92026e4e02364b84467464b5ff7411b771187 (diff)
downloadpoky-06d020489dee672b1895f19c271eba4e17430106.tar.gz
bsd-headers,musl: Add recipe for bsd missing features
let musl depend on these headers so they are staged along with libc (From OE-Core rev: 2cb184e4abaa69faad9f94631a3906188aa78e96) Signed-off-by: Khem Raj <raj.khem@gmail.com> Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>
Diffstat (limited to 'meta/recipes-core/bsd-headers')
-rw-r--r--meta/recipes-core/bsd-headers/bsd-headers.bb25
-rw-r--r--meta/recipes-core/bsd-headers/bsd-headers/sys-queue.h846
-rw-r--r--meta/recipes-core/bsd-headers/bsd-headers/sys-tree.h761
3 files changed, 1632 insertions, 0 deletions
diff --git a/meta/recipes-core/bsd-headers/bsd-headers.bb b/meta/recipes-core/bsd-headers/bsd-headers.bb
new file mode 100644
index 0000000000..ae659abec4
--- /dev/null
+++ b/meta/recipes-core/bsd-headers/bsd-headers.bb
@@ -0,0 +1,25 @@
1# Copyright (C) 2016 Khem Raj <raj.khem@gmail.com>
2# Released under the MIT license (see COPYING.MIT for the terms)
3
4DESCRIPTION = "bsd compatible headers"
5LICENSE = "BSD-3-Clause && BSD-2-Clause"
6SECTION = "devel"
7
8SRC_URI = "file://sys-queue.h \
9 file://sys-tree.h \
10 "
11do_configure[noexec] = "1"
12do_compile[noexec] = "1"
13
14INHIBIT_DEFAULT_DEPS = "1"
15
16S = "${WORKDIR}"
17
18do_install() {
19 install -Dm 0644 ${S}/sys-queue.h ${D}${includedir}/sys/queue.h
20 install -Dm 0644 ${S}/sys-tree.h ${D}${includedir}/sys/tree.h
21}
22#
23# We will skip parsing for non-musl systems
24#
25COMPATIBLE_HOST = ".*-musl.*"
diff --git a/meta/recipes-core/bsd-headers/bsd-headers/sys-queue.h b/meta/recipes-core/bsd-headers/bsd-headers/sys-queue.h
new file mode 100644
index 0000000000..99d01a55b1
--- /dev/null
+++ b/meta/recipes-core/bsd-headers/bsd-headers/sys-queue.h
@@ -0,0 +1,846 @@
1/* $NetBSD: queue.h,v 1.68 2014/11/19 08:10:01 uebayasi Exp $ */
2
3/*
4 * Copyright (c) 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * @(#)queue.h 8.5 (Berkeley) 8/20/94
32 */
33
34#ifndef _SYS_QUEUE_H_
35#define _SYS_QUEUE_H_
36
37/*
38 * This file defines five types of data structures: singly-linked lists,
39 * lists, simple queues, tail queues, and circular queues.
40 *
41 * A singly-linked list is headed by a single forward pointer. The
42 * elements are singly linked for minimum space and pointer manipulation
43 * overhead at the expense of O(n) removal for arbitrary elements. New
44 * elements can be added to the list after an existing element or at the
45 * head of the list. Elements being removed from the head of the list
46 * should use the explicit macro for this purpose for optimum
47 * efficiency. A singly-linked list may only be traversed in the forward
48 * direction. Singly-linked lists are ideal for applications with large
49 * datasets and few or no removals or for implementing a LIFO queue.
50 *
51 * A list is headed by a single forward pointer (or an array of forward
52 * pointers for a hash table header). The elements are doubly linked
53 * so that an arbitrary element can be removed without a need to
54 * traverse the list. New elements can be added to the list before
55 * or after an existing element or at the head of the list. A list
56 * may only be traversed in the forward direction.
57 *
58 * A simple queue is headed by a pair of pointers, one the head of the
59 * list and the other to the tail of the list. The elements are singly
60 * linked to save space, so elements can only be removed from the
61 * head of the list. New elements can be added to the list after
62 * an existing element, at the head of the list, or at the end of the
63 * list. A simple queue may only be traversed in the forward direction.
64 *
65 * A tail queue is headed by a pair of pointers, one to the head of the
66 * list and the other to the tail of the list. The elements are doubly
67 * linked so that an arbitrary element can be removed without a need to
68 * traverse the list. New elements can be added to the list before or
69 * after an existing element, at the head of the list, or at the end of
70 * the list. A tail queue may be traversed in either direction.
71 *
72 * A circle queue is headed by a pair of pointers, one to the head of the
73 * list and the other to the tail of the list. The elements are doubly
74 * linked so that an arbitrary element can be removed without a need to
75 * traverse the list. New elements can be added to the list before or after
76 * an existing element, at the head of the list, or at the end of the list.
77 * A circle queue may be traversed in either direction, but has a more
78 * complex end of list detection.
79 *
80 * For details on the use of these macros, see the queue(3) manual page.
81 */
82
83/*
84 * Include the definition of NULL only on NetBSD because sys/null.h
85 * is not available elsewhere. This conditional makes the header
86 * portable and it can simply be dropped verbatim into any system.
87 * The caveat is that on other systems some other header
88 * must provide NULL before the macros can be used.
89 */
90#ifdef __NetBSD__
91#include <sys/null.h>
92#endif
93
94#if defined(QUEUEDEBUG)
95# if defined(_KERNEL)
96# define QUEUEDEBUG_ABORT(...) panic(__VA_ARGS__)
97# else
98# include <err.h>
99# define QUEUEDEBUG_ABORT(...) err(1, __VA_ARGS__)
100# endif
101#endif
102
103/*
104 * Singly-linked List definitions.
105 */
106#define SLIST_HEAD(name, type) \
107struct name { \
108 struct type *slh_first; /* first element */ \
109}
110
111#define SLIST_HEAD_INITIALIZER(head) \
112 { NULL }
113
114#define SLIST_ENTRY(type) \
115struct { \
116 struct type *sle_next; /* next element */ \
117}
118
119/*
120 * Singly-linked List access methods.
121 */
122#define SLIST_FIRST(head) ((head)->slh_first)
123#define SLIST_END(head) NULL
124#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
125#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
126
127#define SLIST_FOREACH(var, head, field) \
128 for((var) = (head)->slh_first; \
129 (var) != SLIST_END(head); \
130 (var) = (var)->field.sle_next)
131
132#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
133 for ((var) = SLIST_FIRST((head)); \
134 (var) != SLIST_END(head) && \
135 ((tvar) = SLIST_NEXT((var), field), 1); \
136 (var) = (tvar))
137
138/*
139 * Singly-linked List functions.
140 */
141#define SLIST_INIT(head) do { \
142 (head)->slh_first = SLIST_END(head); \
143} while (/*CONSTCOND*/0)
144
145#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
146 (elm)->field.sle_next = (slistelm)->field.sle_next; \
147 (slistelm)->field.sle_next = (elm); \
148} while (/*CONSTCOND*/0)
149
150#define SLIST_INSERT_HEAD(head, elm, field) do { \
151 (elm)->field.sle_next = (head)->slh_first; \
152 (head)->slh_first = (elm); \
153} while (/*CONSTCOND*/0)
154
155#define SLIST_REMOVE_AFTER(slistelm, field) do { \
156 (slistelm)->field.sle_next = \
157 SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \
158} while (/*CONSTCOND*/0)
159
160#define SLIST_REMOVE_HEAD(head, field) do { \
161 (head)->slh_first = (head)->slh_first->field.sle_next; \
162} while (/*CONSTCOND*/0)
163
164#define SLIST_REMOVE(head, elm, type, field) do { \
165 if ((head)->slh_first == (elm)) { \
166 SLIST_REMOVE_HEAD((head), field); \
167 } \
168 else { \
169 struct type *curelm = (head)->slh_first; \
170 while(curelm->field.sle_next != (elm)) \
171 curelm = curelm->field.sle_next; \
172 curelm->field.sle_next = \
173 curelm->field.sle_next->field.sle_next; \
174 } \
175} while (/*CONSTCOND*/0)
176
177
178/*
179 * List definitions.
180 */
181#define LIST_HEAD(name, type) \
182struct name { \
183 struct type *lh_first; /* first element */ \
184}
185
186#define LIST_HEAD_INITIALIZER(head) \
187 { NULL }
188
189#define LIST_ENTRY(type) \
190struct { \
191 struct type *le_next; /* next element */ \
192 struct type **le_prev; /* address of previous next element */ \
193}
194
195/*
196 * List access methods.
197 */
198#define LIST_FIRST(head) ((head)->lh_first)
199#define LIST_END(head) NULL
200#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head))
201#define LIST_NEXT(elm, field) ((elm)->field.le_next)
202
203#define LIST_FOREACH(var, head, field) \
204 for ((var) = ((head)->lh_first); \
205 (var) != LIST_END(head); \
206 (var) = ((var)->field.le_next))
207
208#define LIST_FOREACH_SAFE(var, head, field, tvar) \
209 for ((var) = LIST_FIRST((head)); \
210 (var) != LIST_END(head) && \
211 ((tvar) = LIST_NEXT((var), field), 1); \
212 (var) = (tvar))
213
214#define LIST_MOVE(head1, head2) do { \
215 LIST_INIT((head2)); \
216 if (!LIST_EMPTY((head1))) { \
217 (head2)->lh_first = (head1)->lh_first; \
218 LIST_INIT((head1)); \
219 } \
220} while (/*CONSTCOND*/0)
221
222/*
223 * List functions.
224 */
225#if defined(QUEUEDEBUG)
226#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \
227 if ((head)->lh_first && \
228 (head)->lh_first->field.le_prev != &(head)->lh_first) \
229 QUEUEDEBUG_ABORT("LIST_INSERT_HEAD %p %s:%d", (head), \
230 __FILE__, __LINE__);
231#define QUEUEDEBUG_LIST_OP(elm, field) \
232 if ((elm)->field.le_next && \
233 (elm)->field.le_next->field.le_prev != \
234 &(elm)->field.le_next) \
235 QUEUEDEBUG_ABORT("LIST_* forw %p %s:%d", (elm), \
236 __FILE__, __LINE__); \
237 if (*(elm)->field.le_prev != (elm)) \
238 QUEUEDEBUG_ABORT("LIST_* back %p %s:%d", (elm), \
239 __FILE__, __LINE__);
240#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \
241 (elm)->field.le_next = (void *)1L; \
242 (elm)->field.le_prev = (void *)1L;
243#else
244#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
245#define QUEUEDEBUG_LIST_OP(elm, field)
246#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
247#endif
248
249#define LIST_INIT(head) do { \
250 (head)->lh_first = LIST_END(head); \
251} while (/*CONSTCOND*/0)
252
253#define LIST_INSERT_AFTER(listelm, elm, field) do { \
254 QUEUEDEBUG_LIST_OP((listelm), field) \
255 if (((elm)->field.le_next = (listelm)->field.le_next) != \
256 LIST_END(head)) \
257 (listelm)->field.le_next->field.le_prev = \
258 &(elm)->field.le_next; \
259 (listelm)->field.le_next = (elm); \
260 (elm)->field.le_prev = &(listelm)->field.le_next; \
261} while (/*CONSTCOND*/0)
262
263#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
264 QUEUEDEBUG_LIST_OP((listelm), field) \
265 (elm)->field.le_prev = (listelm)->field.le_prev; \
266 (elm)->field.le_next = (listelm); \
267 *(listelm)->field.le_prev = (elm); \
268 (listelm)->field.le_prev = &(elm)->field.le_next; \
269} while (/*CONSTCOND*/0)
270
271#define LIST_INSERT_HEAD(head, elm, field) do { \
272 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
273 if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\
274 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
275 (head)->lh_first = (elm); \
276 (elm)->field.le_prev = &(head)->lh_first; \
277} while (/*CONSTCOND*/0)
278
279#define LIST_REMOVE(elm, field) do { \
280 QUEUEDEBUG_LIST_OP((elm), field) \
281 if ((elm)->field.le_next != NULL) \
282 (elm)->field.le_next->field.le_prev = \
283 (elm)->field.le_prev; \
284 *(elm)->field.le_prev = (elm)->field.le_next; \
285 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
286} while (/*CONSTCOND*/0)
287
288#define LIST_REPLACE(elm, elm2, field) do { \
289 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
290 (elm2)->field.le_next->field.le_prev = \
291 &(elm2)->field.le_next; \
292 (elm2)->field.le_prev = (elm)->field.le_prev; \
293 *(elm2)->field.le_prev = (elm2); \
294 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
295} while (/*CONSTCOND*/0)
296
297/*
298 * Simple queue definitions.
299 */
300#define SIMPLEQ_HEAD(name, type) \
301struct name { \
302 struct type *sqh_first; /* first element */ \
303 struct type **sqh_last; /* addr of last next element */ \
304}
305
306#define SIMPLEQ_HEAD_INITIALIZER(head) \
307 { NULL, &(head).sqh_first }
308
309#define SIMPLEQ_ENTRY(type) \
310struct { \
311 struct type *sqe_next; /* next element */ \
312}
313
314/*
315 * Simple queue access methods.
316 */
317#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
318#define SIMPLEQ_END(head) NULL
319#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head))
320#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
321
322#define SIMPLEQ_FOREACH(var, head, field) \
323 for ((var) = ((head)->sqh_first); \
324 (var) != SIMPLEQ_END(head); \
325 (var) = ((var)->field.sqe_next))
326
327#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \
328 for ((var) = ((head)->sqh_first); \
329 (var) != SIMPLEQ_END(head) && \
330 ((next = ((var)->field.sqe_next)), 1); \
331 (var) = (next))
332
333/*
334 * Simple queue functions.
335 */
336#define SIMPLEQ_INIT(head) do { \
337 (head)->sqh_first = NULL; \
338 (head)->sqh_last = &(head)->sqh_first; \
339} while (/*CONSTCOND*/0)
340
341#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
342 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
343 (head)->sqh_last = &(elm)->field.sqe_next; \
344 (head)->sqh_first = (elm); \
345} while (/*CONSTCOND*/0)
346
347#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
348 (elm)->field.sqe_next = NULL; \
349 *(head)->sqh_last = (elm); \
350 (head)->sqh_last = &(elm)->field.sqe_next; \
351} while (/*CONSTCOND*/0)
352
353#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
354 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
355 (head)->sqh_last = &(elm)->field.sqe_next; \
356 (listelm)->field.sqe_next = (elm); \
357} while (/*CONSTCOND*/0)
358
359#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
360 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
361 (head)->sqh_last = &(head)->sqh_first; \
362} while (/*CONSTCOND*/0)
363
364#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
365 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
366 == NULL) \
367 (head)->sqh_last = &(elm)->field.sqe_next; \
368} while (/*CONSTCOND*/0)
369
370#define SIMPLEQ_REMOVE(head, elm, type, field) do { \
371 if ((head)->sqh_first == (elm)) { \
372 SIMPLEQ_REMOVE_HEAD((head), field); \
373 } else { \
374 struct type *curelm = (head)->sqh_first; \
375 while (curelm->field.sqe_next != (elm)) \
376 curelm = curelm->field.sqe_next; \
377 if ((curelm->field.sqe_next = \
378 curelm->field.sqe_next->field.sqe_next) == NULL) \
379 (head)->sqh_last = &(curelm)->field.sqe_next; \
380 } \
381} while (/*CONSTCOND*/0)
382
383#define SIMPLEQ_CONCAT(head1, head2) do { \
384 if (!SIMPLEQ_EMPTY((head2))) { \
385 *(head1)->sqh_last = (head2)->sqh_first; \
386 (head1)->sqh_last = (head2)->sqh_last; \
387 SIMPLEQ_INIT((head2)); \
388 } \
389} while (/*CONSTCOND*/0)
390
391#define SIMPLEQ_LAST(head, type, field) \
392 (SIMPLEQ_EMPTY((head)) ? \
393 NULL : \
394 ((struct type *)(void *) \
395 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
396
397/*
398 * Tail queue definitions.
399 */
400#define _TAILQ_HEAD(name, type, qual) \
401struct name { \
402 qual type *tqh_first; /* first element */ \
403 qual type *qual *tqh_last; /* addr of last next element */ \
404}
405#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
406
407#define TAILQ_HEAD_INITIALIZER(head) \
408 { TAILQ_END(head), &(head).tqh_first }
409
410#define _TAILQ_ENTRY(type, qual) \
411struct { \
412 qual type *tqe_next; /* next element */ \
413 qual type *qual *tqe_prev; /* address of previous next element */\
414}
415#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
416
417/*
418 * Tail queue access methods.
419 */
420#define TAILQ_FIRST(head) ((head)->tqh_first)
421#define TAILQ_END(head) (NULL)
422#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
423#define TAILQ_LAST(head, headname) \
424 (*(((struct headname *)((head)->tqh_last))->tqh_last))
425#define TAILQ_PREV(elm, headname, field) \
426 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
427#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
428
429
430#define TAILQ_FOREACH(var, head, field) \
431 for ((var) = ((head)->tqh_first); \
432 (var) != TAILQ_END(head); \
433 (var) = ((var)->field.tqe_next))
434
435#define TAILQ_FOREACH_SAFE(var, head, field, next) \
436 for ((var) = ((head)->tqh_first); \
437 (var) != TAILQ_END(head) && \
438 ((next) = TAILQ_NEXT(var, field), 1); (var) = (next))
439
440#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
441 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
442 (var) != TAILQ_END(head); \
443 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
444
445#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \
446 for ((var) = TAILQ_LAST((head), headname); \
447 (var) != TAILQ_END(head) && \
448 ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev))
449
450/*
451 * Tail queue functions.
452 */
453#if defined(QUEUEDEBUG)
454#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
455 if ((head)->tqh_first && \
456 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
457 QUEUEDEBUG_ABORT("TAILQ_INSERT_HEAD %p %s:%d", (head), \
458 __FILE__, __LINE__);
459#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
460 if (*(head)->tqh_last != NULL) \
461 QUEUEDEBUG_ABORT("TAILQ_INSERT_TAIL %p %s:%d", (head), \
462 __FILE__, __LINE__);
463#define QUEUEDEBUG_TAILQ_OP(elm, field) \
464 if ((elm)->field.tqe_next && \
465 (elm)->field.tqe_next->field.tqe_prev != \
466 &(elm)->field.tqe_next) \
467 QUEUEDEBUG_ABORT("TAILQ_* forw %p %s:%d", (elm), \
468 __FILE__, __LINE__); \
469 if (*(elm)->field.tqe_prev != (elm)) \
470 QUEUEDEBUG_ABORT("TAILQ_* back %p %s:%d", (elm), \
471 __FILE__, __LINE__);
472#define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
473 if ((elm)->field.tqe_next == NULL && \
474 (head)->tqh_last != &(elm)->field.tqe_next) \
475 QUEUEDEBUG_ABORT("TAILQ_PREREMOVE head %p elm %p %s:%d",\
476 (head), (elm), __FILE__, __LINE__);
477#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
478 (elm)->field.tqe_next = (void *)1L; \
479 (elm)->field.tqe_prev = (void *)1L;
480#else
481#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
482#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
483#define QUEUEDEBUG_TAILQ_OP(elm, field)
484#define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
485#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
486#endif
487
488#define TAILQ_INIT(head) do { \
489 (head)->tqh_first = TAILQ_END(head); \
490 (head)->tqh_last = &(head)->tqh_first; \
491} while (/*CONSTCOND*/0)
492
493#define TAILQ_INSERT_HEAD(head, elm, field) do { \
494 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
495 if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head))\
496 (head)->tqh_first->field.tqe_prev = \
497 &(elm)->field.tqe_next; \
498 else \
499 (head)->tqh_last = &(elm)->field.tqe_next; \
500 (head)->tqh_first = (elm); \
501 (elm)->field.tqe_prev = &(head)->tqh_first; \
502} while (/*CONSTCOND*/0)
503
504#define TAILQ_INSERT_TAIL(head, elm, field) do { \
505 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
506 (elm)->field.tqe_next = TAILQ_END(head); \
507 (elm)->field.tqe_prev = (head)->tqh_last; \
508 *(head)->tqh_last = (elm); \
509 (head)->tqh_last = &(elm)->field.tqe_next; \
510} while (/*CONSTCOND*/0)
511
512#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
513 QUEUEDEBUG_TAILQ_OP((listelm), field) \
514 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \
515 TAILQ_END(head)) \
516 (elm)->field.tqe_next->field.tqe_prev = \
517 &(elm)->field.tqe_next; \
518 else \
519 (head)->tqh_last = &(elm)->field.tqe_next; \
520 (listelm)->field.tqe_next = (elm); \
521 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
522} while (/*CONSTCOND*/0)
523
524#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
525 QUEUEDEBUG_TAILQ_OP((listelm), field) \
526 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
527 (elm)->field.tqe_next = (listelm); \
528 *(listelm)->field.tqe_prev = (elm); \
529 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
530} while (/*CONSTCOND*/0)
531
532#define TAILQ_REMOVE(head, elm, field) do { \
533 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
534 QUEUEDEBUG_TAILQ_OP((elm), field) \
535 if (((elm)->field.tqe_next) != TAILQ_END(head)) \
536 (elm)->field.tqe_next->field.tqe_prev = \
537 (elm)->field.tqe_prev; \
538 else \
539 (head)->tqh_last = (elm)->field.tqe_prev; \
540 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
541 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
542} while (/*CONSTCOND*/0)
543
544#define TAILQ_REPLACE(head, elm, elm2, field) do { \
545 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \
546 TAILQ_END(head)) \
547 (elm2)->field.tqe_next->field.tqe_prev = \
548 &(elm2)->field.tqe_next; \
549 else \
550 (head)->tqh_last = &(elm2)->field.tqe_next; \
551 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
552 *(elm2)->field.tqe_prev = (elm2); \
553 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
554} while (/*CONSTCOND*/0)
555
556#define TAILQ_CONCAT(head1, head2, field) do { \
557 if (!TAILQ_EMPTY(head2)) { \
558 *(head1)->tqh_last = (head2)->tqh_first; \
559 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
560 (head1)->tqh_last = (head2)->tqh_last; \
561 TAILQ_INIT((head2)); \
562 } \
563} while (/*CONSTCOND*/0)
564
565/*
566 * Singly-linked Tail queue declarations.
567 */
568#define STAILQ_HEAD(name, type) \
569struct name { \
570 struct type *stqh_first; /* first element */ \
571 struct type **stqh_last; /* addr of last next element */ \
572}
573
574#define STAILQ_HEAD_INITIALIZER(head) \
575 { NULL, &(head).stqh_first }
576
577#define STAILQ_ENTRY(type) \
578struct { \
579 struct type *stqe_next; /* next element */ \
580}
581
582/*
583 * Singly-linked Tail queue access methods.
584 */
585#define STAILQ_FIRST(head) ((head)->stqh_first)
586#define STAILQ_END(head) NULL
587#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
588#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head))
589
590/*
591 * Singly-linked Tail queue functions.
592 */
593#define STAILQ_INIT(head) do { \
594 (head)->stqh_first = NULL; \
595 (head)->stqh_last = &(head)->stqh_first; \
596} while (/*CONSTCOND*/0)
597
598#define STAILQ_INSERT_HEAD(head, elm, field) do { \
599 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
600 (head)->stqh_last = &(elm)->field.stqe_next; \
601 (head)->stqh_first = (elm); \
602} while (/*CONSTCOND*/0)
603
604#define STAILQ_INSERT_TAIL(head, elm, field) do { \
605 (elm)->field.stqe_next = NULL; \
606 *(head)->stqh_last = (elm); \
607 (head)->stqh_last = &(elm)->field.stqe_next; \
608} while (/*CONSTCOND*/0)
609
610#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
611 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
612 (head)->stqh_last = &(elm)->field.stqe_next; \
613 (listelm)->field.stqe_next = (elm); \
614} while (/*CONSTCOND*/0)
615
616#define STAILQ_REMOVE_HEAD(head, field) do { \
617 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
618 (head)->stqh_last = &(head)->stqh_first; \
619} while (/*CONSTCOND*/0)
620
621#define STAILQ_REMOVE(head, elm, type, field) do { \
622 if ((head)->stqh_first == (elm)) { \
623 STAILQ_REMOVE_HEAD((head), field); \
624 } else { \
625 struct type *curelm = (head)->stqh_first; \
626 while (curelm->field.stqe_next != (elm)) \
627 curelm = curelm->field.stqe_next; \
628 if ((curelm->field.stqe_next = \
629 curelm->field.stqe_next->field.stqe_next) == NULL) \
630 (head)->stqh_last = &(curelm)->field.stqe_next; \
631 } \
632} while (/*CONSTCOND*/0)
633
634#define STAILQ_FOREACH(var, head, field) \
635 for ((var) = ((head)->stqh_first); \
636 (var); \
637 (var) = ((var)->field.stqe_next))
638
639#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
640 for ((var) = STAILQ_FIRST((head)); \
641 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
642 (var) = (tvar))
643
644#define STAILQ_CONCAT(head1, head2) do { \
645 if (!STAILQ_EMPTY((head2))) { \
646 *(head1)->stqh_last = (head2)->stqh_first; \
647 (head1)->stqh_last = (head2)->stqh_last; \
648 STAILQ_INIT((head2)); \
649 } \
650} while (/*CONSTCOND*/0)
651
652#define STAILQ_LAST(head, type, field) \
653 (STAILQ_EMPTY((head)) ? \
654 NULL : \
655 ((struct type *)(void *) \
656 ((char *)((head)->stqh_last) - offsetof(struct type, field))))
657
658
659#ifndef _KERNEL
660/*
661 * Circular queue definitions. Do not use. We still keep the macros
662 * for compatibility but because of pointer aliasing issues their use
663 * is discouraged!
664 */
665
666/*
667 * __launder_type(): We use this ugly hack to work around the the compiler
668 * noticing that two types may not alias each other and elide tests in code.
669 * We hit this in the CIRCLEQ macros when comparing 'struct name *' and
670 * 'struct type *' (see CIRCLEQ_HEAD()). Modern compilers (such as GCC
671 * 4.8) declare these comparisons as always false, causing the code to
672 * not run as designed.
673 *
674 * This hack is only to be used for comparisons and thus can be fully const.
675 * Do not use for assignment.
676 *
677 * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix
678 * this by changing the head/tail sentinal values, but see the note above
679 * this one.
680 */
681static __inline const void * __launder_type(const void *);
682static __inline const void *
683__launder_type(const void *__x)
684{
685 __asm __volatile("" : "+r" (__x));
686 return __x;
687}
688
689#if defined(QUEUEDEBUG)
690#define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) \
691 if ((head)->cqh_first != CIRCLEQ_ENDC(head) && \
692 (head)->cqh_first->field.cqe_prev != CIRCLEQ_ENDC(head)) \
693 QUEUEDEBUG_ABORT("CIRCLEQ head forw %p %s:%d", (head), \
694 __FILE__, __LINE__); \
695 if ((head)->cqh_last != CIRCLEQ_ENDC(head) && \
696 (head)->cqh_last->field.cqe_next != CIRCLEQ_ENDC(head)) \
697 QUEUEDEBUG_ABORT("CIRCLEQ head back %p %s:%d", (head), \
698 __FILE__, __LINE__);
699#define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) \
700 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) { \
701 if ((head)->cqh_last != (elm)) \
702 QUEUEDEBUG_ABORT("CIRCLEQ elm last %p %s:%d", \
703 (elm), __FILE__, __LINE__); \
704 } else { \
705 if ((elm)->field.cqe_next->field.cqe_prev != (elm)) \
706 QUEUEDEBUG_ABORT("CIRCLEQ elm forw %p %s:%d", \
707 (elm), __FILE__, __LINE__); \
708 } \
709 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) { \
710 if ((head)->cqh_first != (elm)) \
711 QUEUEDEBUG_ABORT("CIRCLEQ elm first %p %s:%d", \
712 (elm), __FILE__, __LINE__); \
713 } else { \
714 if ((elm)->field.cqe_prev->field.cqe_next != (elm)) \
715 QUEUEDEBUG_ABORT("CIRCLEQ elm prev %p %s:%d", \
716 (elm), __FILE__, __LINE__); \
717 }
718#define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) \
719 (elm)->field.cqe_next = (void *)1L; \
720 (elm)->field.cqe_prev = (void *)1L;
721#else
722#define QUEUEDEBUG_CIRCLEQ_HEAD(head, field)
723#define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field)
724#define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field)
725#endif
726
727#define CIRCLEQ_HEAD(name, type) \
728struct name { \
729 struct type *cqh_first; /* first element */ \
730 struct type *cqh_last; /* last element */ \
731}
732
733#define CIRCLEQ_HEAD_INITIALIZER(head) \
734 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
735
736#define CIRCLEQ_ENTRY(type) \
737struct { \
738 struct type *cqe_next; /* next element */ \
739 struct type *cqe_prev; /* previous element */ \
740}
741
742/*
743 * Circular queue functions.
744 */
745#define CIRCLEQ_INIT(head) do { \
746 (head)->cqh_first = CIRCLEQ_END(head); \
747 (head)->cqh_last = CIRCLEQ_END(head); \
748} while (/*CONSTCOND*/0)
749
750#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
751 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
752 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
753 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
754 (elm)->field.cqe_prev = (listelm); \
755 if ((listelm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
756 (head)->cqh_last = (elm); \
757 else \
758 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
759 (listelm)->field.cqe_next = (elm); \
760} while (/*CONSTCOND*/0)
761
762#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
763 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
764 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
765 (elm)->field.cqe_next = (listelm); \
766 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
767 if ((listelm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
768 (head)->cqh_first = (elm); \
769 else \
770 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
771 (listelm)->field.cqe_prev = (elm); \
772} while (/*CONSTCOND*/0)
773
774#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
775 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
776 (elm)->field.cqe_next = (head)->cqh_first; \
777 (elm)->field.cqe_prev = CIRCLEQ_END(head); \
778 if ((head)->cqh_last == CIRCLEQ_ENDC(head)) \
779 (head)->cqh_last = (elm); \
780 else \
781 (head)->cqh_first->field.cqe_prev = (elm); \
782 (head)->cqh_first = (elm); \
783} while (/*CONSTCOND*/0)
784
785#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
786 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
787 (elm)->field.cqe_next = CIRCLEQ_END(head); \
788 (elm)->field.cqe_prev = (head)->cqh_last; \
789 if ((head)->cqh_first == CIRCLEQ_ENDC(head)) \
790 (head)->cqh_first = (elm); \
791 else \
792 (head)->cqh_last->field.cqe_next = (elm); \
793 (head)->cqh_last = (elm); \
794} while (/*CONSTCOND*/0)
795
796#define CIRCLEQ_REMOVE(head, elm, field) do { \
797 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
798 QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field) \
799 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
800 (head)->cqh_last = (elm)->field.cqe_prev; \
801 else \
802 (elm)->field.cqe_next->field.cqe_prev = \
803 (elm)->field.cqe_prev; \
804 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
805 (head)->cqh_first = (elm)->field.cqe_next; \
806 else \
807 (elm)->field.cqe_prev->field.cqe_next = \
808 (elm)->field.cqe_next; \
809 QUEUEDEBUG_CIRCLEQ_POSTREMOVE((elm), field) \
810} while (/*CONSTCOND*/0)
811
812#define CIRCLEQ_FOREACH(var, head, field) \
813 for ((var) = ((head)->cqh_first); \
814 (var) != CIRCLEQ_ENDC(head); \
815 (var) = ((var)->field.cqe_next))
816
817#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
818 for ((var) = ((head)->cqh_last); \
819 (var) != CIRCLEQ_ENDC(head); \
820 (var) = ((var)->field.cqe_prev))
821
822/*
823 * Circular queue access methods.
824 */
825#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
826#define CIRCLEQ_LAST(head) ((head)->cqh_last)
827/* For comparisons */
828#define CIRCLEQ_ENDC(head) (__launder_type(head))
829/* For assignments */
830#define CIRCLEQ_END(head) ((void *)(head))
831#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
832#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
833#define CIRCLEQ_EMPTY(head) \
834 (CIRCLEQ_FIRST(head) == CIRCLEQ_ENDC(head))
835
836#define CIRCLEQ_LOOP_NEXT(head, elm, field) \
837 (((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
838 ? ((head)->cqh_first) \
839 : (elm->field.cqe_next))
840#define CIRCLEQ_LOOP_PREV(head, elm, field) \
841 (((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
842 ? ((head)->cqh_last) \
843 : (elm->field.cqe_prev))
844#endif /* !_KERNEL */
845
846#endif /* !_SYS_QUEUE_H_ */
diff --git a/meta/recipes-core/bsd-headers/bsd-headers/sys-tree.h b/meta/recipes-core/bsd-headers/bsd-headers/sys-tree.h
new file mode 100644
index 0000000000..eaea56aae3
--- /dev/null
+++ b/meta/recipes-core/bsd-headers/bsd-headers/sys-tree.h
@@ -0,0 +1,761 @@
1/* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */
2/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
3/*
4 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28#ifndef _SYS_TREE_H_
29#define _SYS_TREE_H_
30
31/*
32 * This file defines data structures for different types of trees:
33 * splay trees and red-black trees.
34 *
35 * A splay tree is a self-organizing data structure. Every operation
36 * on the tree causes a splay to happen. The splay moves the requested
37 * node to the root of the tree and partly rebalances it.
38 *
39 * This has the benefit that request locality causes faster lookups as
40 * the requested nodes move to the top of the tree. On the other hand,
41 * every lookup causes memory writes.
42 *
43 * The Balance Theorem bounds the total access time for m operations
44 * and n inserts on an initially empty tree as O((m + n)lg n). The
45 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
46 *
47 * A red-black tree is a binary search tree with the node color as an
48 * extra attribute. It fulfills a set of conditions:
49 * - every search path from the root to a leaf consists of the
50 * same number of black nodes,
51 * - each red node (except for the root) has a black parent,
52 * - each leaf node is black.
53 *
54 * Every operation on a red-black tree is bounded as O(lg n).
55 * The maximum height of a red-black tree is 2lg (n+1).
56 */
57
58#define SPLAY_HEAD(name, type) \
59struct name { \
60 struct type *sph_root; /* root of the tree */ \
61}
62
63#define SPLAY_INITIALIZER(root) \
64 { NULL }
65
66#define SPLAY_INIT(root) do { \
67 (root)->sph_root = NULL; \
68} while (/*CONSTCOND*/ 0)
69
70#define SPLAY_ENTRY(type) \
71struct { \
72 struct type *spe_left; /* left element */ \
73 struct type *spe_right; /* right element */ \
74}
75
76#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
77#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
78#define SPLAY_ROOT(head) (head)->sph_root
79#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
80
81/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
82#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
83 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
84 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
85 (head)->sph_root = tmp; \
86} while (/*CONSTCOND*/ 0)
87
88#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
89 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
90 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
91 (head)->sph_root = tmp; \
92} while (/*CONSTCOND*/ 0)
93
94#define SPLAY_LINKLEFT(head, tmp, field) do { \
95 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
96 tmp = (head)->sph_root; \
97 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
98} while (/*CONSTCOND*/ 0)
99
100#define SPLAY_LINKRIGHT(head, tmp, field) do { \
101 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
102 tmp = (head)->sph_root; \
103 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
104} while (/*CONSTCOND*/ 0)
105
106#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
107 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
108 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
109 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
110 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
111} while (/*CONSTCOND*/ 0)
112
113/* Generates prototypes and inline functions */
114
115#define SPLAY_PROTOTYPE(name, type, field, cmp) \
116void name##_SPLAY(struct name *, struct type *); \
117void name##_SPLAY_MINMAX(struct name *, int); \
118struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
119struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
120 \
121/* Finds the node with the same key as elm */ \
122static __inline struct type * \
123name##_SPLAY_FIND(struct name *head, struct type *elm) \
124{ \
125 if (SPLAY_EMPTY(head)) \
126 return(NULL); \
127 name##_SPLAY(head, elm); \
128 if ((cmp)(elm, (head)->sph_root) == 0) \
129 return (head->sph_root); \
130 return (NULL); \
131} \
132 \
133static __inline __unused struct type * \
134name##_SPLAY_NEXT(struct name *head, struct type *elm) \
135{ \
136 name##_SPLAY(head, elm); \
137 if (SPLAY_RIGHT(elm, field) != NULL) { \
138 elm = SPLAY_RIGHT(elm, field); \
139 while (SPLAY_LEFT(elm, field) != NULL) { \
140 elm = SPLAY_LEFT(elm, field); \
141 } \
142 } else \
143 elm = NULL; \
144 return (elm); \
145} \
146 \
147static __unused __inline struct type * \
148name##_SPLAY_MIN_MAX(struct name *head, int val) \
149{ \
150 name##_SPLAY_MINMAX(head, val); \
151 return (SPLAY_ROOT(head)); \
152}
153
154/* Main splay operation.
155 * Moves node close to the key of elm to top
156 */
157#define SPLAY_GENERATE(name, type, field, cmp) \
158struct type * \
159name##_SPLAY_INSERT(struct name *head, struct type *elm) \
160{ \
161 if (SPLAY_EMPTY(head)) { \
162 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
163 } else { \
164 int __comp; \
165 name##_SPLAY(head, elm); \
166 __comp = (cmp)(elm, (head)->sph_root); \
167 if(__comp < 0) { \
168 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
169 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
170 SPLAY_LEFT((head)->sph_root, field) = NULL; \
171 } else if (__comp > 0) { \
172 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
173 SPLAY_LEFT(elm, field) = (head)->sph_root; \
174 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
175 } else \
176 return ((head)->sph_root); \
177 } \
178 (head)->sph_root = (elm); \
179 return (NULL); \
180} \
181 \
182struct type * \
183name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
184{ \
185 struct type *__tmp; \
186 if (SPLAY_EMPTY(head)) \
187 return (NULL); \
188 name##_SPLAY(head, elm); \
189 if ((cmp)(elm, (head)->sph_root) == 0) { \
190 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
191 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
192 } else { \
193 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
194 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
195 name##_SPLAY(head, elm); \
196 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
197 } \
198 return (elm); \
199 } \
200 return (NULL); \
201} \
202 \
203void \
204name##_SPLAY(struct name *head, struct type *elm) \
205{ \
206 struct type __node, *__left, *__right, *__tmp; \
207 int __comp; \
208\
209 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
210 __left = __right = &__node; \
211\
212 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
213 if (__comp < 0) { \
214 __tmp = SPLAY_LEFT((head)->sph_root, field); \
215 if (__tmp == NULL) \
216 break; \
217 if ((cmp)(elm, __tmp) < 0){ \
218 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
219 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
220 break; \
221 } \
222 SPLAY_LINKLEFT(head, __right, field); \
223 } else if (__comp > 0) { \
224 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
225 if (__tmp == NULL) \
226 break; \
227 if ((cmp)(elm, __tmp) > 0){ \
228 SPLAY_ROTATE_LEFT(head, __tmp, field); \
229 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
230 break; \
231 } \
232 SPLAY_LINKRIGHT(head, __left, field); \
233 } \
234 } \
235 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
236} \
237 \
238/* Splay with either the minimum or the maximum element \
239 * Used to find minimum or maximum element in tree. \
240 */ \
241void name##_SPLAY_MINMAX(struct name *head, int __comp) \
242{ \
243 struct type __node, *__left, *__right, *__tmp; \
244\
245 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
246 __left = __right = &__node; \
247\
248 while (1) { \
249 if (__comp < 0) { \
250 __tmp = SPLAY_LEFT((head)->sph_root, field); \
251 if (__tmp == NULL) \
252 break; \
253 if (__comp < 0){ \
254 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
255 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
256 break; \
257 } \
258 SPLAY_LINKLEFT(head, __right, field); \
259 } else if (__comp > 0) { \
260 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
261 if (__tmp == NULL) \
262 break; \
263 if (__comp > 0) { \
264 SPLAY_ROTATE_LEFT(head, __tmp, field); \
265 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
266 break; \
267 } \
268 SPLAY_LINKRIGHT(head, __left, field); \
269 } \
270 } \
271 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
272}
273
274#define SPLAY_NEGINF -1
275#define SPLAY_INF 1
276
277#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
278#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
279#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
280#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
281#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
282 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
283#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
284 : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
285
286#define SPLAY_FOREACH(x, name, head) \
287 for ((x) = SPLAY_MIN(name, head); \
288 (x) != NULL; \
289 (x) = SPLAY_NEXT(name, head, x))
290
291/* Macros that define a red-black tree */
292#define RB_HEAD(name, type) \
293struct name { \
294 struct type *rbh_root; /* root of the tree */ \
295}
296
297#define RB_INITIALIZER(root) \
298 { NULL }
299
300#define RB_INIT(root) do { \
301 (root)->rbh_root = NULL; \
302} while (/*CONSTCOND*/ 0)
303
304#define RB_BLACK 0
305#define RB_RED 1
306#define RB_ENTRY(type) \
307struct { \
308 struct type *rbe_left; /* left element */ \
309 struct type *rbe_right; /* right element */ \
310 struct type *rbe_parent; /* parent element */ \
311 int rbe_color; /* node color */ \
312}
313
314#define RB_LEFT(elm, field) (elm)->field.rbe_left
315#define RB_RIGHT(elm, field) (elm)->field.rbe_right
316#define RB_PARENT(elm, field) (elm)->field.rbe_parent
317#define RB_COLOR(elm, field) (elm)->field.rbe_color
318#define RB_ROOT(head) (head)->rbh_root
319#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
320
321#define RB_SET(elm, parent, field) do { \
322 RB_PARENT(elm, field) = parent; \
323 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
324 RB_COLOR(elm, field) = RB_RED; \
325} while (/*CONSTCOND*/ 0)
326
327#define RB_SET_BLACKRED(black, red, field) do { \
328 RB_COLOR(black, field) = RB_BLACK; \
329 RB_COLOR(red, field) = RB_RED; \
330} while (/*CONSTCOND*/ 0)
331
332#ifndef RB_AUGMENT
333#define RB_AUGMENT(x) do {} while (/*CONSTCOND*/ 0)
334#endif
335
336#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
337 (tmp) = RB_RIGHT(elm, field); \
338 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
339 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
340 } \
341 RB_AUGMENT(elm); \
342 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
343 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
344 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
345 else \
346 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
347 } else \
348 (head)->rbh_root = (tmp); \
349 RB_LEFT(tmp, field) = (elm); \
350 RB_PARENT(elm, field) = (tmp); \
351 RB_AUGMENT(tmp); \
352 if ((RB_PARENT(tmp, field))) \
353 RB_AUGMENT(RB_PARENT(tmp, field)); \
354} while (/*CONSTCOND*/ 0)
355
356#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
357 (tmp) = RB_LEFT(elm, field); \
358 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
359 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
360 } \
361 RB_AUGMENT(elm); \
362 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
363 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
364 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
365 else \
366 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
367 } else \
368 (head)->rbh_root = (tmp); \
369 RB_RIGHT(tmp, field) = (elm); \
370 RB_PARENT(elm, field) = (tmp); \
371 RB_AUGMENT(tmp); \
372 if ((RB_PARENT(tmp, field))) \
373 RB_AUGMENT(RB_PARENT(tmp, field)); \
374} while (/*CONSTCOND*/ 0)
375
376/* Generates prototypes and inline functions */
377#define RB_PROTOTYPE(name, type, field, cmp) \
378 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
379#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
380 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
381#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
382attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
383attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
384attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
385attr struct type *name##_RB_INSERT(struct name *, struct type *); \
386attr struct type *name##_RB_FIND(struct name *, struct type *); \
387attr struct type *name##_RB_NFIND(struct name *, struct type *); \
388attr struct type *name##_RB_NEXT(struct type *); \
389attr struct type *name##_RB_PREV(struct type *); \
390attr struct type *name##_RB_MINMAX(struct name *, int); \
391 \
392
393/* Main rb operation.
394 * Moves node close to the key of elm to top
395 */
396#define RB_GENERATE(name, type, field, cmp) \
397 RB_GENERATE_INTERNAL(name, type, field, cmp,)
398#define RB_GENERATE_STATIC(name, type, field, cmp) \
399 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
400#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
401attr void \
402name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
403{ \
404 struct type *parent, *gparent, *tmp; \
405 while ((parent = RB_PARENT(elm, field)) != NULL && \
406 RB_COLOR(parent, field) == RB_RED) { \
407 gparent = RB_PARENT(parent, field); \
408 if (parent == RB_LEFT(gparent, field)) { \
409 tmp = RB_RIGHT(gparent, field); \
410 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
411 RB_COLOR(tmp, field) = RB_BLACK; \
412 RB_SET_BLACKRED(parent, gparent, field);\
413 elm = gparent; \
414 continue; \
415 } \
416 if (RB_RIGHT(parent, field) == elm) { \
417 RB_ROTATE_LEFT(head, parent, tmp, field);\
418 tmp = parent; \
419 parent = elm; \
420 elm = tmp; \
421 } \
422 RB_SET_BLACKRED(parent, gparent, field); \
423 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
424 } else { \
425 tmp = RB_LEFT(gparent, field); \
426 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
427 RB_COLOR(tmp, field) = RB_BLACK; \
428 RB_SET_BLACKRED(parent, gparent, field);\
429 elm = gparent; \
430 continue; \
431 } \
432 if (RB_LEFT(parent, field) == elm) { \
433 RB_ROTATE_RIGHT(head, parent, tmp, field);\
434 tmp = parent; \
435 parent = elm; \
436 elm = tmp; \
437 } \
438 RB_SET_BLACKRED(parent, gparent, field); \
439 RB_ROTATE_LEFT(head, gparent, tmp, field); \
440 } \
441 } \
442 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
443} \
444 \
445attr void \
446name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
447{ \
448 struct type *tmp; \
449 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
450 elm != RB_ROOT(head)) { \
451 if (RB_LEFT(parent, field) == elm) { \
452 tmp = RB_RIGHT(parent, field); \
453 if (RB_COLOR(tmp, field) == RB_RED) { \
454 RB_SET_BLACKRED(tmp, parent, field); \
455 RB_ROTATE_LEFT(head, parent, tmp, field);\
456 tmp = RB_RIGHT(parent, field); \
457 } \
458 if ((RB_LEFT(tmp, field) == NULL || \
459 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
460 (RB_RIGHT(tmp, field) == NULL || \
461 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
462 RB_COLOR(tmp, field) = RB_RED; \
463 elm = parent; \
464 parent = RB_PARENT(elm, field); \
465 } else { \
466 if (RB_RIGHT(tmp, field) == NULL || \
467 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
468 struct type *oleft; \
469 if ((oleft = RB_LEFT(tmp, field)) \
470 != NULL) \
471 RB_COLOR(oleft, field) = RB_BLACK;\
472 RB_COLOR(tmp, field) = RB_RED; \
473 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
474 tmp = RB_RIGHT(parent, field); \
475 } \
476 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
477 RB_COLOR(parent, field) = RB_BLACK; \
478 if (RB_RIGHT(tmp, field)) \
479 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
480 RB_ROTATE_LEFT(head, parent, tmp, field);\
481 elm = RB_ROOT(head); \
482 break; \
483 } \
484 } else { \
485 tmp = RB_LEFT(parent, field); \
486 if (RB_COLOR(tmp, field) == RB_RED) { \
487 RB_SET_BLACKRED(tmp, parent, field); \
488 RB_ROTATE_RIGHT(head, parent, tmp, field);\
489 tmp = RB_LEFT(parent, field); \
490 } \
491 if ((RB_LEFT(tmp, field) == NULL || \
492 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
493 (RB_RIGHT(tmp, field) == NULL || \
494 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
495 RB_COLOR(tmp, field) = RB_RED; \
496 elm = parent; \
497 parent = RB_PARENT(elm, field); \
498 } else { \
499 if (RB_LEFT(tmp, field) == NULL || \
500 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
501 struct type *oright; \
502 if ((oright = RB_RIGHT(tmp, field)) \
503 != NULL) \
504 RB_COLOR(oright, field) = RB_BLACK;\
505 RB_COLOR(tmp, field) = RB_RED; \
506 RB_ROTATE_LEFT(head, tmp, oright, field);\
507 tmp = RB_LEFT(parent, field); \
508 } \
509 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
510 RB_COLOR(parent, field) = RB_BLACK; \
511 if (RB_LEFT(tmp, field)) \
512 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
513 RB_ROTATE_RIGHT(head, parent, tmp, field);\
514 elm = RB_ROOT(head); \
515 break; \
516 } \
517 } \
518 } \
519 if (elm) \
520 RB_COLOR(elm, field) = RB_BLACK; \
521} \
522 \
523attr struct type * \
524name##_RB_REMOVE(struct name *head, struct type *elm) \
525{ \
526 struct type *child, *parent, *old = elm; \
527 int color; \
528 if (RB_LEFT(elm, field) == NULL) \
529 child = RB_RIGHT(elm, field); \
530 else if (RB_RIGHT(elm, field) == NULL) \
531 child = RB_LEFT(elm, field); \
532 else { \
533 struct type *left; \
534 elm = RB_RIGHT(elm, field); \
535 while ((left = RB_LEFT(elm, field)) != NULL) \
536 elm = left; \
537 child = RB_RIGHT(elm, field); \
538 parent = RB_PARENT(elm, field); \
539 color = RB_COLOR(elm, field); \
540 if (child) \
541 RB_PARENT(child, field) = parent; \
542 if (parent) { \
543 if (RB_LEFT(parent, field) == elm) \
544 RB_LEFT(parent, field) = child; \
545 else \
546 RB_RIGHT(parent, field) = child; \
547 RB_AUGMENT(parent); \
548 } else \
549 RB_ROOT(head) = child; \
550 if (RB_PARENT(elm, field) == old) \
551 parent = elm; \
552 (elm)->field = (old)->field; \
553 if (RB_PARENT(old, field)) { \
554 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
555 RB_LEFT(RB_PARENT(old, field), field) = elm;\
556 else \
557 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
558 RB_AUGMENT(RB_PARENT(old, field)); \
559 } else \
560 RB_ROOT(head) = elm; \
561 RB_PARENT(RB_LEFT(old, field), field) = elm; \
562 if (RB_RIGHT(old, field)) \
563 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
564 if (parent) { \
565 left = parent; \
566 do { \
567 RB_AUGMENT(left); \
568 } while ((left = RB_PARENT(left, field)) != NULL); \
569 } \
570 goto color; \
571 } \
572 parent = RB_PARENT(elm, field); \
573 color = RB_COLOR(elm, field); \
574 if (child) \
575 RB_PARENT(child, field) = parent; \
576 if (parent) { \
577 if (RB_LEFT(parent, field) == elm) \
578 RB_LEFT(parent, field) = child; \
579 else \
580 RB_RIGHT(parent, field) = child; \
581 RB_AUGMENT(parent); \
582 } else \
583 RB_ROOT(head) = child; \
584color: \
585 if (color == RB_BLACK) \
586 name##_RB_REMOVE_COLOR(head, parent, child); \
587 return (old); \
588} \
589 \
590/* Inserts a node into the RB tree */ \
591attr struct type * \
592name##_RB_INSERT(struct name *head, struct type *elm) \
593{ \
594 struct type *tmp; \
595 struct type *parent = NULL; \
596 int comp = 0; \
597 tmp = RB_ROOT(head); \
598 while (tmp) { \
599 parent = tmp; \
600 comp = (cmp)(elm, parent); \
601 if (comp < 0) \
602 tmp = RB_LEFT(tmp, field); \
603 else if (comp > 0) \
604 tmp = RB_RIGHT(tmp, field); \
605 else \
606 return (tmp); \
607 } \
608 RB_SET(elm, parent, field); \
609 if (parent != NULL) { \
610 if (comp < 0) \
611 RB_LEFT(parent, field) = elm; \
612 else \
613 RB_RIGHT(parent, field) = elm; \
614 RB_AUGMENT(parent); \
615 } else \
616 RB_ROOT(head) = elm; \
617 name##_RB_INSERT_COLOR(head, elm); \
618 return (NULL); \
619} \
620 \
621/* Finds the node with the same key as elm */ \
622attr struct type * \
623name##_RB_FIND(struct name *head, struct type *elm) \
624{ \
625 struct type *tmp = RB_ROOT(head); \
626 int comp; \
627 while (tmp) { \
628 comp = cmp(elm, tmp); \
629 if (comp < 0) \
630 tmp = RB_LEFT(tmp, field); \
631 else if (comp > 0) \
632 tmp = RB_RIGHT(tmp, field); \
633 else \
634 return (tmp); \
635 } \
636 return (NULL); \
637} \
638 \
639/* Finds the first node greater than or equal to the search key */ \
640attr struct type * \
641name##_RB_NFIND(struct name *head, struct type *elm) \
642{ \
643 struct type *tmp = RB_ROOT(head); \
644 struct type *res = NULL; \
645 int comp; \
646 while (tmp) { \
647 comp = cmp(elm, tmp); \
648 if (comp < 0) { \
649 res = tmp; \
650 tmp = RB_LEFT(tmp, field); \
651 } \
652 else if (comp > 0) \
653 tmp = RB_RIGHT(tmp, field); \
654 else \
655 return (tmp); \
656 } \
657 return (res); \
658} \
659 \
660/* ARGSUSED */ \
661attr struct type * \
662name##_RB_NEXT(struct type *elm) \
663{ \
664 if (RB_RIGHT(elm, field)) { \
665 elm = RB_RIGHT(elm, field); \
666 while (RB_LEFT(elm, field)) \
667 elm = RB_LEFT(elm, field); \
668 } else { \
669 if (RB_PARENT(elm, field) && \
670 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
671 elm = RB_PARENT(elm, field); \
672 else { \
673 while (RB_PARENT(elm, field) && \
674 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
675 elm = RB_PARENT(elm, field); \
676 elm = RB_PARENT(elm, field); \
677 } \
678 } \
679 return (elm); \
680} \
681 \
682/* ARGSUSED */ \
683attr struct type * \
684name##_RB_PREV(struct type *elm) \
685{ \
686 if (RB_LEFT(elm, field)) { \
687 elm = RB_LEFT(elm, field); \
688 while (RB_RIGHT(elm, field)) \
689 elm = RB_RIGHT(elm, field); \
690 } else { \
691 if (RB_PARENT(elm, field) && \
692 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
693 elm = RB_PARENT(elm, field); \
694 else { \
695 while (RB_PARENT(elm, field) && \
696 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
697 elm = RB_PARENT(elm, field); \
698 elm = RB_PARENT(elm, field); \
699 } \
700 } \
701 return (elm); \
702} \
703 \
704attr struct type * \
705name##_RB_MINMAX(struct name *head, int val) \
706{ \
707 struct type *tmp = RB_ROOT(head); \
708 struct type *parent = NULL; \
709 while (tmp) { \
710 parent = tmp; \
711 if (val < 0) \
712 tmp = RB_LEFT(tmp, field); \
713 else \
714 tmp = RB_RIGHT(tmp, field); \
715 } \
716 return (parent); \
717}
718
719#define RB_NEGINF -1
720#define RB_INF 1
721
722#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
723#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
724#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
725#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
726#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
727#define RB_PREV(name, x, y) name##_RB_PREV(y)
728#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
729#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
730
731#define RB_FOREACH(x, name, head) \
732 for ((x) = RB_MIN(name, head); \
733 (x) != NULL; \
734 (x) = name##_RB_NEXT(x))
735
736#define RB_FOREACH_FROM(x, name, y) \
737 for ((x) = (y); \
738 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
739 (x) = (y))
740
741#define RB_FOREACH_SAFE(x, name, head, y) \
742 for ((x) = RB_MIN(name, head); \
743 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
744 (x) = (y))
745
746#define RB_FOREACH_REVERSE(x, name, head) \
747 for ((x) = RB_MAX(name, head); \
748 (x) != NULL; \
749 (x) = name##_RB_PREV(x))
750
751#define RB_FOREACH_REVERSE_FROM(x, name, y) \
752 for ((x) = (y); \
753 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
754 (x) = (y))
755
756#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
757 for ((x) = RB_MAX(name, head); \
758 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
759 (x) = (y))
760
761#endif /* _SYS_TREE_H_ */
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2024-05-09 13:24:00 +0000