diff options
author | Faidon Liambotis <paravoid@debian.org> | 2021-02-07 20:47:00 +0200 |
---|---|---|
committer | Guillem Jover <guillem@hadrons.org> | 2021-02-08 04:02:16 +0100 |
commit | 467602628660326a54f7af7344d5539cf31aeea3 (patch) | |
tree | 581d4a9f6e340fca0a782449ccb7614f84eef857 | |
parent | 25f9b30678b352e8275c98e118f5beacffbb94b4 (diff) |
Update <sys/queue.h> from FreeBSD
This brings <sys/queue.h> to the most up-to-date version from FreeBSD,
incorporating 18 commits from the past 5 years (2015-02-24 - 2021-01-25):
$ git log --oneline 9090a24aed70..8d55837dc133 sys/sys/queue.h share/man/man3/queue.3
Only minimal changes compared to the FreeBSD version have been applied
(queue.3 -> queue.3bsd, _LIBBSD_ prefix).
[guillem@hadrons.org: Remove reference to kernel mode in man page. ]
Closes: !12
Signed-off-by: Guillem Jover <guillem@hadrons.org>
-rw-r--r-- | include/bsd/sys/queue.h | 236 | ||||
-rw-r--r-- | man/LIST_CLASS_ENTRY.3bsd | 1 | ||||
-rw-r--r-- | man/LIST_CLASS_HEAD.3bsd | 1 | ||||
-rw-r--r-- | man/Makefile.am | 9 | ||||
-rw-r--r-- | man/SLIST_CLASS_ENTRY.3bsd | 1 | ||||
-rw-r--r-- | man/SLIST_CLASS_HEAD.3bsd | 1 | ||||
-rw-r--r-- | man/SLIST_REMOVE_PREVPTR.3bsd | 1 | ||||
-rw-r--r-- | man/STAILQ_CLASS_ENTRY.3bsd | 1 | ||||
-rw-r--r-- | man/STAILQ_CLASS_HEAD.3bsd | 1 | ||||
-rw-r--r-- | man/TAILQ_CLASS_ENTRY.3bsd | 1 | ||||
-rw-r--r-- | man/TAILQ_CLASS_HEAD.3bsd | 1 | ||||
-rw-r--r-- | man/queue.3bsd | 153 |
12 files changed, 356 insertions, 51 deletions
diff --git a/include/bsd/sys/queue.h b/include/bsd/sys/queue.h index ac00026..d556fd4 100644 --- a/include/bsd/sys/queue.h +++ b/include/bsd/sys/queue.h @@ -1,4 +1,6 @@ /*- + * SPDX-License-Identifier: BSD-3-Clause + * * Copyright (c) 1991, 1993 * The Regents of the University of California. All rights reserved. * @@ -10,7 +12,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 4. Neither the name of the University nor the names of its contributors + * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * @@ -80,17 +82,25 @@ * * For details on the use of these macros, see the queue(3) manual page. * + * Below is a summary of implemented functions where: + * + means the macro is available + * - means the macro is not available + * s means the macro is available but is slow (runs in O(n) time) * * SLIST LIST STAILQ TAILQ * _HEAD + + + + + * _CLASS_HEAD + + + + * _HEAD_INITIALIZER + + + + * _ENTRY + + + + + * _CLASS_ENTRY + + + + * _INIT + + + + * _EMPTY + + + + + * _END + + + + * _FIRST + + + + * _NEXT + + + + * _PREV - + - + * _LAST - - + + + * _LAST_FAST - - - + * _FOREACH + + + + * _FOREACH_FROM + + + + * _FOREACH_SAFE + + + + @@ -103,14 +113,20 @@ * _INSERT_BEFORE - + - + * _INSERT_AFTER + + + + * _INSERT_TAIL - - + + - * _CONCAT - - + + + * _CONCAT s s + + * _REMOVE_AFTER + - + - * _REMOVE_HEAD + - + - - * _REMOVE + + + + + * _REMOVE s + s + * _SWAP + + + + * */ #ifdef QUEUE_MACRO_DEBUG +#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH +#define QUEUE_MACRO_DEBUG_TRACE +#define QUEUE_MACRO_DEBUG_TRASH +#endif + +#ifdef QUEUE_MACRO_DEBUG_TRACE /* Store the last 2 places the queue element or head was altered */ struct qm_trace { unsigned long lastline; @@ -120,9 +136,7 @@ struct qm_trace { }; #define TRACEBUF struct qm_trace trace; -#define TRACEBUF_INITIALIZER { __FILE__, __LINE__, NULL, 0 } , -#define TRASHIT(x) do {(x) = (void *)-1;} while (0) -#define QMD_SAVELINK(name, link) void **name = (void *)&(link) +#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , #define QMD_TRACE_HEAD(head) do { \ (head)->trace.prevline = (head)->trace.lastline; \ @@ -138,14 +152,31 @@ struct qm_trace { (elem)->trace.lastfile = __FILE__; \ } while (0) -#else +#else /* !QUEUE_MACRO_DEBUG_TRACE */ #define QMD_TRACE_ELEM(elem) #define QMD_TRACE_HEAD(head) -#define QMD_SAVELINK(name, link) #define TRACEBUF #define TRACEBUF_INITIALIZER +#endif /* QUEUE_MACRO_DEBUG_TRACE */ + +#ifdef QUEUE_MACRO_DEBUG_TRASH +#define QMD_SAVELINK(name, link) void **name = (void *)&(link) +#define TRASHIT(x) do {(x) = (void *)-1;} while (0) +#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) +#else /* !QUEUE_MACRO_DEBUG_TRASH */ +#define QMD_SAVELINK(name, link) #define TRASHIT(x) -#endif /* QUEUE_MACRO_DEBUG */ +#define QMD_IS_TRASHED(x) 0 +#endif /* QUEUE_MACRO_DEBUG_TRASH */ + +#ifdef __cplusplus +/* + * In C++ there can be structure lists and class lists: + */ +#define QUEUE_TYPEOF(type) type +#else +#define QUEUE_TYPEOF(type) struct type +#endif /* * Singly-linked List declarations. @@ -155,6 +186,11 @@ struct name { \ struct type *slh_first; /* first element */ \ } +#define SLIST_CLASS_HEAD(name, type) \ +struct name { \ + class type *slh_first; /* first element */ \ +} + #define SLIST_HEAD_INITIALIZER(head) \ { NULL } @@ -163,9 +199,37 @@ struct { \ struct type *sle_next; /* next element */ \ } +#define SLIST_CLASS_ENTRY(type) \ +struct { \ + class type *sle_next; /* next element */ \ +} + /* * Singly-linked List functions. */ +#if (defined(_KERNEL) && defined(INVARIANTS)) +#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \ + if (*(prevp) != (elm)) \ + panic("Bad prevptr *(%p) == %p != %p", \ + (prevp), *(prevp), (elm)); \ +} while (0) +#else +#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) +#endif + +#define SLIST_CONCAT(head1, head2, type, field) do { \ + QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ + if (curelm == NULL) { \ + if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ + SLIST_INIT(head2); \ + } else if (SLIST_FIRST(head2) != NULL) { \ + while (SLIST_NEXT(curelm, field) != NULL) \ + curelm = SLIST_NEXT(curelm, field); \ + SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ + SLIST_INIT(head2); \ + } \ +} while (0) + #define SLIST_EMPTY(head) ((head)->slh_first == NULL) #define SLIST_FIRST(head) ((head)->slh_first) @@ -217,7 +281,7 @@ struct { \ SLIST_REMOVE_HEAD((head), field); \ } \ else { \ - struct type *curelm = SLIST_FIRST((head)); \ + QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ while (SLIST_NEXT(curelm, field) != (elm)) \ curelm = SLIST_NEXT(curelm, field); \ SLIST_REMOVE_AFTER(curelm, field); \ @@ -234,12 +298,20 @@ struct { \ SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ } while (0) +#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ + QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ + *(prevp) = SLIST_NEXT(elm, field); \ + TRASHIT((elm)->field.sle_next); \ +} while (0) + #define SLIST_SWAP(head1, head2, type) do { \ - struct type *swap_first = SLIST_FIRST(head1); \ + QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ SLIST_FIRST(head1) = SLIST_FIRST(head2); \ SLIST_FIRST(head2) = swap_first; \ } while (0) +#define SLIST_END(head) NULL + /* * Singly-linked Tail queue declarations. */ @@ -249,6 +321,12 @@ struct name { \ struct type **stqh_last;/* addr of last next element */ \ } +#define STAILQ_CLASS_HEAD(name, type) \ +struct name { \ + class type *stqh_first; /* first element */ \ + class type **stqh_last; /* addr of last next element */ \ +} + #define STAILQ_HEAD_INITIALIZER(head) \ { NULL, &(head).stqh_first } @@ -257,6 +335,11 @@ struct { \ struct type *stqe_next; /* next element */ \ } +#define STAILQ_CLASS_ENTRY(type) \ +struct { \ + class type *stqe_next; /* next element */ \ +} + /* * Singly-linked Tail queue functions. */ @@ -315,9 +398,10 @@ struct { \ (head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0) -#define STAILQ_LAST(head, type, field) \ - (STAILQ_EMPTY((head)) ? NULL : \ - __containerof((head)->stqh_last, struct type, field.stqe_next)) +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) ? NULL : \ + __containerof((head)->stqh_last, \ + QUEUE_TYPEOF(type), field.stqe_next)) #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) @@ -327,7 +411,7 @@ struct { \ STAILQ_REMOVE_HEAD((head), field); \ } \ else { \ - struct type *curelm = STAILQ_FIRST((head)); \ + QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ while (STAILQ_NEXT(curelm, field) != (elm)) \ curelm = STAILQ_NEXT(curelm, field); \ STAILQ_REMOVE_AFTER(head, curelm, field); \ @@ -348,8 +432,8 @@ struct { \ } while (0) #define STAILQ_SWAP(head1, head2, type) do { \ - struct type *swap_first = STAILQ_FIRST(head1); \ - struct type **swap_last = (head1)->stqh_last; \ + QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ + QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ (head1)->stqh_last = (head2)->stqh_last; \ STAILQ_FIRST(head2) = swap_first; \ @@ -360,6 +444,8 @@ struct { \ (head2)->stqh_last = &STAILQ_FIRST(head2); \ } while (0) +#define STAILQ_END(head) NULL + /* * List declarations. @@ -369,6 +455,11 @@ struct name { \ struct type *lh_first; /* first element */ \ } +#define LIST_CLASS_HEAD(name, type) \ +struct name { \ + class type *lh_first; /* first element */ \ +} + #define LIST_HEAD_INITIALIZER(head) \ { NULL } @@ -378,11 +469,23 @@ struct { \ struct type **le_prev; /* address of previous next element */ \ } +#define LIST_CLASS_ENTRY(type) \ +struct { \ + class type *le_next; /* next element */ \ + class type **le_prev; /* address of previous next element */ \ +} + /* * List functions. */ #if (defined(_KERNEL) && defined(INVARIANTS)) +/* + * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) + * + * If the list is non-empty, validates that the first element of the list + * points back at 'head.' + */ #define QMD_LIST_CHECK_HEAD(head, field) do { \ if (LIST_FIRST((head)) != NULL && \ LIST_FIRST((head))->field.le_prev != \ @@ -390,6 +493,12 @@ struct { \ panic("Bad list head %p first->prev != head", (head)); \ } while (0) +/* + * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) + * + * If an element follows 'elm' in the list, validates that the next element + * points back at 'elm.' + */ #define QMD_LIST_CHECK_NEXT(elm, field) do { \ if (LIST_NEXT((elm), field) != NULL && \ LIST_NEXT((elm), field)->field.le_prev != \ @@ -397,6 +506,11 @@ struct { \ panic("Bad link elm %p next->prev != elm", (elm)); \ } while (0) +/* + * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) + * + * Validates that the previous element (or head of the list) points to 'elm.' + */ #define QMD_LIST_CHECK_PREV(elm, field) do { \ if (*(elm)->field.le_prev != (elm)) \ panic("Bad link elm %p prev->next != elm", (elm)); \ @@ -407,6 +521,23 @@ struct { \ #define QMD_LIST_CHECK_PREV(elm, field) #endif /* (_KERNEL && INVARIANTS) */ +#define LIST_CONCAT(head1, head2, type, field) do { \ + QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ + if (curelm == NULL) { \ + if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ + LIST_FIRST(head2)->field.le_prev = \ + &LIST_FIRST((head1)); \ + LIST_INIT(head2); \ + } \ + } else if (LIST_FIRST(head2) != NULL) { \ + while (LIST_NEXT(curelm, field) != NULL) \ + curelm = LIST_NEXT(curelm, field); \ + LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ + LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ + LIST_INIT(head2); \ + } \ +} while (0) + #define LIST_EMPTY(head) ((head)->lh_first == NULL) #define LIST_FIRST(head) ((head)->lh_first) @@ -462,9 +593,10 @@ struct { \ #define LIST_NEXT(elm, field) ((elm)->field.le_next) -#define LIST_PREV(elm, head, type, field) \ - ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ - __containerof((elm)->field.le_prev, struct type, field.le_next)) +#define LIST_PREV(elm, head, type, field) \ + ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ + __containerof((elm)->field.le_prev, \ + QUEUE_TYPEOF(type), field.le_next)) #define LIST_REMOVE(elm, field) do { \ QMD_SAVELINK(oldnext, (elm)->field.le_next); \ @@ -480,7 +612,7 @@ struct { \ } while (0) #define LIST_SWAP(head1, head2, type, field) do { \ - struct type *swap_tmp = LIST_FIRST((head1)); \ + QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ LIST_FIRST((head1)) = LIST_FIRST((head2)); \ LIST_FIRST((head2)) = swap_tmp; \ if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ @@ -489,6 +621,8 @@ struct { \ swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ } while (0) +#define LIST_END(head) NULL + /* * Tail queue declarations. */ @@ -499,6 +633,13 @@ struct name { \ TRACEBUF \ } +#define TAILQ_CLASS_HEAD(name, type) \ +struct name { \ + class type *tqh_first; /* first element */ \ + class type **tqh_last; /* addr of last next element */ \ + TRACEBUF \ +} + #define TAILQ_HEAD_INITIALIZER(head) \ { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } @@ -509,10 +650,23 @@ struct { \ TRACEBUF \ } +#define TAILQ_CLASS_ENTRY(type) \ +struct { \ + class type *tqe_next; /* next element */ \ + class type **tqe_prev; /* address of previous next element */ \ + TRACEBUF \ +} + /* * Tail queue functions. */ #if (defined(_KERNEL) && defined(INVARIANTS)) +/* + * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) + * + * If the tailq is non-empty, validates that the first element of the tailq + * points back at 'head.' + */ #define QMD_TAILQ_CHECK_HEAD(head, field) do { \ if (!TAILQ_EMPTY(head) && \ TAILQ_FIRST((head))->field.tqe_prev != \ @@ -520,11 +674,22 @@ struct { \ panic("Bad tailq head %p first->prev != head", (head)); \ } while (0) +/* + * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) + * + * Validates that the tail of the tailq is a pointer to pointer to NULL. + */ #define QMD_TAILQ_CHECK_TAIL(head, field) do { \ if (*(head)->tqh_last != NULL) \ panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ } while (0) +/* + * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) + * + * If an element follows 'elm' in the tailq, validates that the next element + * points back at 'elm.' + */ #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ if (TAILQ_NEXT((elm), field) != NULL && \ TAILQ_NEXT((elm), field)->field.tqe_prev != \ @@ -532,6 +697,11 @@ struct { \ panic("Bad link elm %p next->prev != elm", (elm)); \ } while (0) +/* + * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) + * + * Validates that the previous element (or head of the tailq) points to 'elm.' + */ #define QMD_TAILQ_CHECK_PREV(elm, field) do { \ if (*(elm)->field.tqe_prev != (elm)) \ panic("Bad link elm %p prev->next != elm", (elm)); \ @@ -616,7 +786,7 @@ struct { \ TAILQ_NEXT((listelm), field) = (elm); \ (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ + QMD_TRACE_ELEM(&(listelm)->field); \ } while (0) #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ @@ -626,7 +796,7 @@ struct { \ *(listelm)->field.tqe_prev = (elm); \ (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ + QMD_TRACE_ELEM(&(listelm)->field); \ } while (0) #define TAILQ_INSERT_HEAD(head, elm, field) do { \ @@ -655,11 +825,25 @@ struct { \ #define TAILQ_LAST(head, headname) \ (*(((struct headname *)((head)->tqh_last))->tqh_last)) +/* + * The FAST function is fast in that it causes no data access other + * then the access to the head. The standard LAST function above + * will cause a data access of both the element you want and + * the previous element. FAST is very useful for instances when + * you may want to prefetch the last data element. + */ +#define TAILQ_LAST_FAST(head, type, field) \ + (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next)) + #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) #define TAILQ_PREV(elm, headname, field) \ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_PREV_FAST(elm, head, type, field) \ + ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \ + __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next)) + #define TAILQ_REMOVE(head, elm, field) do { \ QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ @@ -679,8 +863,8 @@ struct { \ } while (0) #define TAILQ_SWAP(head1, head2, type, field) do { \ - struct type *swap_first = (head1)->tqh_first; \ - struct type **swap_last = (head1)->tqh_last; \ + QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ + QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ (head1)->tqh_first = (head2)->tqh_first; \ (head1)->tqh_last = (head2)->tqh_last; \ (head2)->tqh_first = swap_first; \ @@ -695,4 +879,6 @@ struct { \ (head2)->tqh_last = &(head2)->tqh_first; \ } while (0) +#define TAILQ_END(head) NULL + #endif /* !LIBBSD_SYS_QUEUE_H */ diff --git a/man/LIST_CLASS_ENTRY.3bsd b/man/LIST_CLASS_ENTRY.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/LIST_CLASS_ENTRY.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/LIST_CLASS_HEAD.3bsd b/man/LIST_CLASS_HEAD.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/LIST_CLASS_HEAD.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/Makefile.am b/man/Makefile.am index 25e9566..5dd37bf 100644 --- a/man/Makefile.am +++ b/man/Makefile.am @@ -14,6 +14,8 @@ md5.3bsd: $(srcdir)/mdX.3bsd $(AM_V_GEN) sed $(SED_MD5_SUBST) $< > $@ dist_man_MANS = \ + LIST_CLASS_ENTRY.3bsd \ + LIST_CLASS_HEAD.3bsd \ LIST_EMPTY.3bsd \ LIST_ENTRY.3bsd \ LIST_FIRST.3bsd \ @@ -54,6 +56,8 @@ dist_man_MANS = \ RB_REMOVE.3bsd \ RB_RIGHT.3bsd \ RB_ROOT.3bsd \ + SLIST_CLASS_ENTRY.3bsd \ + SLIST_CLASS_HEAD.3bsd \ SLIST_EMPTY.3bsd \ SLIST_ENTRY.3bsd \ SLIST_FIRST.3bsd \ @@ -70,6 +74,7 @@ dist_man_MANS = \ SLIST_REMOVE.3bsd \ SLIST_REMOVE_AFTER.3bsd \ SLIST_REMOVE_HEAD.3bsd \ + SLIST_REMOVE_PREVPTR.3bsd \ SLIST_SWAP.3bsd \ SPLAY_EMPTY.3bsd \ SPLAY_ENTRY.3bsd \ @@ -88,6 +93,8 @@ dist_man_MANS = \ SPLAY_REMOVE.3bsd \ SPLAY_RIGHT.3bsd \ SPLAY_ROOT.3bsd \ + STAILQ_CLASS_ENTRY.3bsd \ + STAILQ_CLASS_HEAD.3bsd \ STAILQ_CONCAT.3bsd \ STAILQ_EMPTY.3bsd \ STAILQ_ENTRY.3bsd \ @@ -108,6 +115,8 @@ dist_man_MANS = \ STAILQ_REMOVE_AFTER.3bsd \ STAILQ_REMOVE_HEAD.3bsd \ STAILQ_SWAP.3bsd \ + TAILQ_CLASS_ENTRY.3bsd \ + TAILQ_CLASS_HEAD.3bsd \ TAILQ_CONCAT.3bsd \ TAILQ_EMPTY.3bsd \ TAILQ_ENTRY.3bsd \ diff --git a/man/SLIST_CLASS_ENTRY.3bsd b/man/SLIST_CLASS_ENTRY.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/SLIST_CLASS_ENTRY.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/SLIST_CLASS_HEAD.3bsd b/man/SLIST_CLASS_HEAD.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/SLIST_CLASS_HEAD.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/SLIST_REMOVE_PREVPTR.3bsd b/man/SLIST_REMOVE_PREVPTR.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/SLIST_REMOVE_PREVPTR.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/STAILQ_CLASS_ENTRY.3bsd b/man/STAILQ_CLASS_ENTRY.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/STAILQ_CLASS_ENTRY.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/STAILQ_CLASS_HEAD.3bsd b/man/STAILQ_CLASS_HEAD.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/STAILQ_CLASS_HEAD.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/TAILQ_CLASS_ENTRY.3bsd b/man/TAILQ_CLASS_ENTRY.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/TAILQ_CLASS_ENTRY.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/TAILQ_CLASS_HEAD.3bsd b/man/TAILQ_CLASS_HEAD.3bsd new file mode 100644 index 0000000..3a5aa76 --- /dev/null +++ b/man/TAILQ_CLASS_HEAD.3bsd @@ -0,0 +1 @@ +.so man3/queue.3bsd diff --git a/man/queue.3bsd b/man/queue.3bsd index 8900f86..46a0503 100644 --- a/man/queue.3bsd +++ b/man/queue.3bsd @@ -28,35 +28,40 @@ .\" @(#)queue.3 8.2 (Berkeley) 1/24/94 .\" $FreeBSD$ .\" -.Dd June 17, 2013 +.Dd September 8, 2016 .Dt QUEUE 3bsd .Os .Sh NAME +.Nm SLIST_CLASS_ENTRY , +.Nm SLIST_CLASS_HEAD , +.Nm SLIST_CONCAT , .Nm SLIST_EMPTY , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , .Nm SLIST_FOREACH , .Nm SLIST_FOREACH_FROM , -.Nm SLIST_FOREACH_SAFE , .Nm SLIST_FOREACH_FROM_SAFE , +.Nm SLIST_FOREACH_SAFE , .Nm SLIST_HEAD , .Nm SLIST_HEAD_INITIALIZER , .Nm SLIST_INIT , .Nm SLIST_INSERT_AFTER , .Nm SLIST_INSERT_HEAD , .Nm SLIST_NEXT , +.Nm SLIST_REMOVE , .Nm SLIST_REMOVE_AFTER , .Nm SLIST_REMOVE_HEAD , -.Nm SLIST_REMOVE , .Nm SLIST_SWAP , +.Nm STAILQ_CLASS_ENTRY , +.Nm STAILQ_CLASS_HEAD , .Nm STAILQ_CONCAT , .Nm STAILQ_EMPTY , .Nm STAILQ_ENTRY , .Nm STAILQ_FIRST , .Nm STAILQ_FOREACH , .Nm STAILQ_FOREACH_FROM , -.Nm STAILQ_FOREACH_SAFE , .Nm STAILQ_FOREACH_FROM_SAFE , +.Nm STAILQ_FOREACH_SAFE , .Nm STAILQ_HEAD , .Nm STAILQ_HEAD_INITIALIZER , .Nm STAILQ_INIT , @@ -65,17 +70,20 @@ .Nm STAILQ_INSERT_TAIL , .Nm STAILQ_LAST , .Nm STAILQ_NEXT , +.Nm STAILQ_REMOVE , .Nm STAILQ_REMOVE_AFTER , .Nm STAILQ_REMOVE_HEAD , -.Nm STAILQ_REMOVE , .Nm STAILQ_SWAP , +.Nm LIST_CLASS_ENTRY , +.Nm LIST_CLASS_HEAD , +.Nm LIST_CONCAT , .Nm LIST_EMPTY , .Nm LIST_ENTRY , .Nm LIST_FIRST , .Nm LIST_FOREACH , .Nm LIST_FOREACH_FROM , -.Nm LIST_FOREACH_SAFE , .Nm LIST_FOREACH_FROM_SAFE , +.Nm LIST_FOREACH_SAFE , .Nm LIST_HEAD , .Nm LIST_HEAD_INITIALIZER , .Nm LIST_INIT , @@ -86,18 +94,20 @@ .Nm LIST_PREV , .Nm LIST_REMOVE , .Nm LIST_SWAP , +.Nm TAILQ_CLASS_ENTRY , +.Nm TAILQ_CLASS_HEAD , .Nm TAILQ_CONCAT , .Nm TAILQ_EMPTY , .Nm TAILQ_ENTRY , .Nm TAILQ_FIRST , .Nm TAILQ_FOREACH , .Nm TAILQ_FOREACH_FROM , -.Nm TAILQ_FOREACH_SAFE , .Nm TAILQ_FOREACH_FROM_SAFE , .Nm TAILQ_FOREACH_REVERSE , .Nm TAILQ_FOREACH_REVERSE_FROM , -.Nm TAILQ_FOREACH_REVERSE_SAFE , .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , +.Nm TAILQ_FOREACH_REVERSE_SAFE , +.Nm TAILQ_FOREACH_SAFE , .Nm TAILQ_HEAD , .Nm TAILQ_HEAD_INITIALIZER , .Nm TAILQ_INIT , @@ -122,52 +132,60 @@ lists and tail queues .Xr libbsd 7 for include usage.) .\" +.Fn SLIST_CLASS_ENTRY "CLASSTYPE" +.Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" +.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .Fn SLIST_HEAD "HEADNAME" "TYPE" .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" .Fn SLIST_INIT "SLIST_HEAD *head" .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" -.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" +.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" .\" +.Fn STAILQ_CLASS_ENTRY "CLASSTYPE" +.Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" .Fn STAILQ_EMPTY "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE" .Fn STAILQ_FIRST "STAILQ_HEAD *head" .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" -.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" .Fn STAILQ_HEAD "HEADNAME" "TYPE" .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" .Fn STAILQ_INIT "STAILQ_HEAD *head" .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" +.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" -.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" -.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME" +.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE" .\" +.Fn LIST_CLASS_ENTRY "CLASSTYPE" +.Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" +.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .Fn LIST_EMPTY "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" -.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" +.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" .Fn LIST_HEAD "HEADNAME" "TYPE" .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" .Fn LIST_INIT "LIST_HEAD *head" @@ -179,18 +197,20 @@ for include usage.) .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .\" +.Fn TAILQ_CLASS_ENTRY "CLASSTYPE" +.Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" .Fn TAILQ_EMPTY "TAILQ_HEAD *head" .Fn TAILQ_ENTRY "TYPE" .Fn TAILQ_FIRST "TAILQ_HEAD *head" .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" .Fn TAILQ_HEAD "HEADNAME" "TYPE" .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" .Fn TAILQ_INIT "TAILQ_HEAD *head" @@ -205,8 +225,18 @@ for include usage.) .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" .\" .Sh DESCRIPTION -These macros define and operate on four types of data structures: -singly-linked lists, singly-linked tail queues, lists, and tail queues. +These macros define and operate on four types of data structures which +can be used in both C and C++ source code: +.Bl -enum -compact -offset indent +.It +Lists +.It +Singly-linked lists +.It +Singly-linked tail queues +.It +Tail queues +.El All four structures support the following functionality: .Bl -enum -compact -offset indent .It @@ -230,6 +260,8 @@ Singly-linked lists add the following functionality: .Bl -enum -compact -offset indent .It O(n) removal of any entry in the list. +.It +O(n) concatenation of two lists. .El .Pp Singly-linked tail queues add the following functionality: @@ -277,6 +309,8 @@ Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above: .Bl -enum -compact -offset indent .It +O(n) concatenation of two lists. +.It They may be traversed backwards. .El However: @@ -308,24 +342,39 @@ than singly-linked lists. .Pp In the macro definitions, .Fa TYPE -is the name of a user defined structure, -that must contain a field of type +is the name of a user defined structure. +The structure must contain a field called +.Fa NAME +which is of type .Li SLIST_ENTRY , .Li STAILQ_ENTRY , .Li LIST_ENTRY , or -.Li TAILQ_ENTRY , -named -.Fa NAME . +.Li TAILQ_ENTRY . +In the macro definitions, +.Fa CLASSTYPE +is the name of a user defined class. +The class must contain a field called +.Fa NAME +which is of type +.Li SLIST_CLASS_ENTRY , +.Li STAILQ_CLASS_ENTRY , +.Li LIST_CLASS_ENTRY , +or +.Li TAILQ_CLASS_ENTRY . The argument .Fa HEADNAME is the name of a user defined structure that must be declared using the macros .Li SLIST_HEAD , +.Li SLIST_CLASS_HEAD , .Li STAILQ_HEAD , +.Li STAILQ_CLASS_HEAD , .Li LIST_HEAD , +.Li LIST_CLASS_HEAD , +.Li TAILQ_HEAD , or -.Li TAILQ_HEAD . +.Li TAILQ_CLASS_HEAD . See the examples below for further explanation of how these macros are used. .Sh SINGLY-LINKED LISTS @@ -367,6 +416,19 @@ evaluates to an initializer for the list .Fa head . .Pp The macro +.Nm SLIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A singly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +The macro .Nm SLIST_EMPTY evaluates to true if there are no elements in the list. .Pp @@ -474,6 +536,9 @@ The macro removes the element .Fa elm from the list. +Use of this macro should be avoided as it traverses the entire list. +A doubly-linked list should be used if this macro is needed in +high-usage code paths or to operate on long lists. .Pp The macro .Nm SLIST_SWAP @@ -690,6 +755,9 @@ The macro removes the element .Fa elm from the tail queue. +Use of this macro should be avoided as it traverses the entire list. +A doubly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long tail queues. .Pp The macro .Nm STAILQ_SWAP @@ -789,6 +857,19 @@ evaluates to an initializer for the list .Fa head . .Pp The macro +.Nm LIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +The macro .Nm LIST_EMPTY evaluates to true if there are no elements in the list. .Pp @@ -1210,6 +1291,26 @@ while (n1 != NULL) { } TAILQ_INIT(&head); .Ed +.Sh DIAGNOSTICS +When debugging +.Nm queue(3) , +it can be useful to trace queue changes. +To enable tracing, define the macro +.Va QUEUE_MACRO_DEBUG_TRACE +at compile time. +.Pp +It can also be useful to trash pointers that have been unlinked from a queue, +to detect use after removal. +To enable pointer trashing, define the macro +.Va QUEUE_MACRO_DEBUG_TRASH +at compile time. +The macro +.Fn QMD_IS_TRASHED "void *ptr" +returns true if +.Fa ptr +has been trashed by the +.Va QUEUE_MACRO_DEBUG_TRASH +option. .Sh SEE ALSO .Xr tree 3bsd .Sh HISTORY |