libbsd: Branch 'master' - 6 commits
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Mon Feb 8 03:13:06 UTC 2021
configure.ac | 2
include/bsd/sys/queue.h | 236 +++++++++++++++++++++++++++++++++++++-----
man/LIST_CLASS_ENTRY.3bsd | 1
man/LIST_CLASS_HEAD.3bsd | 1
man/Makefile.am | 9 +
man/SLIST_CLASS_ENTRY.3bsd | 1
man/SLIST_CLASS_HEAD.3bsd | 1
man/SLIST_REMOVE_PREVPTR.3bsd | 1
man/STAILQ_CLASS_ENTRY.3bsd | 1
man/STAILQ_CLASS_HEAD.3bsd | 1
man/TAILQ_CLASS_ENTRY.3bsd | 1
man/TAILQ_CLASS_HEAD.3bsd | 1
man/queue.3bsd | 153 ++++++++++++++++++++++-----
src/closefrom.c | 113 ++++++++++++--------
test/strnstr.c | 4
15 files changed, 431 insertions(+), 95 deletions(-)
New commits:
commit edea268ce9367e33b8981a3c581c5ecb531944e7
Author: Guillem Jover <guillem at hadrons.org>
Date: Mon Feb 8 03:59:56 2021 +0100
Release libbsd 0.11.2
diff --git a/configure.ac b/configure.ac
index f0fe875..f100045 100644
--- a/configure.ac
+++ b/configure.ac
@@ -13,7 +13,7 @@ m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])],
LIBBSD_ABI_MAJOR=0
LIBBSD_ABI_MINOR=11
-LIBBSD_ABI_PATCH=1
+LIBBSD_ABI_PATCH=2
LIBBSD_ABI="$LIBBSD_ABI_MAJOR:$LIBBSD_ABI_MINOR:$LIBBSD_ABI_PATCH"
AC_SUBST([LIBBSD_ABI])
commit e832b7687ed42ecf0daf7c5deefa86a1445d62fd
Author: Guillem Jover <guillem at hadrons.org>
Date: Mon Feb 8 03:45:06 2021 +0100
closefrom: Use close_range() on Linux when available
Closes: !11
Based-on-patch-by: cptpcrd <cptpcrd.git at gmail.com>
Signed-off-by: Guillem Jover <guillem at hadrons.org>
diff --git a/src/closefrom.c b/src/closefrom.c
index e2e10a8..087ccad 100644
--- a/src/closefrom.c
+++ b/src/closefrom.c
@@ -19,6 +19,12 @@
#include <config.h>
+#ifdef __linux__
+# include <sys/syscall.h>
+# if defined(__NR_close_range) && !defined(SYS_close_range)
+# define SYS_close_range __NR_close_range
+# endif
+#endif
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
@@ -61,6 +67,14 @@ closefrom_close(int fd)
#endif
}
+#if defined(__linux__) && defined(SYS_close_range)
+static inline int
+sys_close_range(unsigned int fd, unsigned int max_fd, unsigned int flags)
+{
+ return syscall(SYS_close_range, fd, max_fd, flags);
+}
+#endif
+
/*
* Close all file descriptors greater than or equal to lowfd.
* This is the expensive (fallback) method.
@@ -182,11 +196,16 @@ closefrom(int lowfd)
if (lowfd < 0)
lowfd = 0;
- /* Try the fast method first, if possible. */
+ /* Try the fast methods first, if possible. */
#if defined(HAVE_FCNTL_CLOSEM)
if (fcntl(lowfd, F_CLOSEM, 0) != -1)
return;
#endif /* HAVE_FCNTL_CLOSEM */
+#if defined(__linux__) && defined(SYS_close_range)
+ if (sys_close_range(lowfd, UINT_MAX, 0) == 0)
+ return;
+#endif
+
#if defined(HAVE_PSTAT_GETPROC)
if (closefrom_pstat(lowfd) != -1)
return;
commit c4fca5bb4fcf8509cb93db6e20314f22994c093b
Author: cptpcrd <cptpcrd.git at gmail.com>
Date: Sun Feb 7 14:22:21 2021 -0500
closefrom: Handle lowfd < 0 properly
More important if close_range() is going to be used, since casting
negative values to 'unsigned int' might hide the errors.
[guillem at hadrons.org: Minor coding style fix. ]
Signed-off-by: Guillem Jover <guillem at hadrons.org>
diff --git a/src/closefrom.c b/src/closefrom.c
index be38813..e2e10a8 100644
--- a/src/closefrom.c
+++ b/src/closefrom.c
@@ -179,6 +179,9 @@ closefrom_procfs(int lowfd)
void
closefrom(int lowfd)
{
+ if (lowfd < 0)
+ lowfd = 0;
+
/* Try the fast method first, if possible. */
#if defined(HAVE_FCNTL_CLOSEM)
if (fcntl(lowfd, F_CLOSEM, 0) != -1)
commit a1f79978e8c60720d1b4217d3ada638ceb6593a5
Author: Guillem Jover <guillem at hadrons.org>
Date: Mon Feb 8 02:52:50 2021 +0100
closefrom: Import some changes from sudo
Take most of the changes done in sudo, but preserve the existing local
changes and refactoring.
In addition, refactor pstat implementation into closefrom_pstat(), so
that the code is easier to read, and requires no conditional
declarations.
diff --git a/src/closefrom.c b/src/closefrom.c
index 962af79..be38813 100644
--- a/src/closefrom.c
+++ b/src/closefrom.c
@@ -1,6 +1,8 @@
/*
- * Copyright (c) 2004-2005, 2007, 2010, 2012-2014
- * Todd C. Miller <Todd.Miller at courtesan.com>
+ * SPDX-License-Identifier: ISC
+ *
+ * Copyright (c) 2004-2005, 2007, 2010, 2012-2015, 2017-2018
+ * Todd C. Miller <Todd.Miller at sudo.ws>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
@@ -17,19 +19,11 @@
#include <config.h>
-#include <sys/types.h>
-#include <unistd.h>
-#include <stdio.h>
-#ifdef STDC_HEADERS
-# include <stdlib.h>
-# include <stddef.h>
-#else
-# ifdef HAVE_STDLIB_H
-# include <stdlib.h>
-# endif
-#endif /* STDC_HEADERS */
+#include <errno.h>
#include <fcntl.h>
#include <limits.h>
+#include <stdlib.h>
+#include <unistd.h>
#ifdef HAVE_PSTAT_GETPROC
# include <sys/param.h>
# include <sys/pstat.h>
@@ -56,10 +50,6 @@
# define OPEN_MAX 256
#endif
-#if defined(HAVE_FCNTL_CLOSEM) && !defined(HAVE_DIRFD)
-# define closefrom closefrom_fallback
-#endif
-
static inline void
closefrom_close(int fd)
{
@@ -81,46 +71,46 @@ closefrom_fallback(int lowfd)
long fd, maxfd;
/*
- * Fall back on sysconf() or getdtablesize(). We avoid checking
- * resource limits since it is possible to open a file descriptor
- * and then drop the rlimit such that it is below the open fd.
+ * Fall back on sysconf(_SC_OPEN_MAX) or getdtablesize(). This is
+ * equivalent to checking the RLIMIT_NOFILE soft limit. It is
+ * possible for there to be open file descriptors past this limit
+ * but there is not much we can do about that since the hard limit
+ * may be RLIM_INFINITY (LLONG_MAX or ULLONG_MAX on modern systems).
*/
#ifdef HAVE_SYSCONF
maxfd = sysconf(_SC_OPEN_MAX);
#else
maxfd = getdtablesize();
#endif /* HAVE_SYSCONF */
- if (maxfd < 0)
+ if (maxfd < OPEN_MAX)
maxfd = OPEN_MAX;
+ /* Make sure we did not get RLIM_INFINITY as the upper limit. */
+ if (maxfd > INT_MAX)
+ maxfd = INT_MAX;
+
for (fd = lowfd; fd < maxfd; fd++)
closefrom_close(fd);
}
-/*
- * Close all file descriptors greater than or equal to lowfd.
- * We try the fast way first, falling back on the slow method.
- */
-#if defined(HAVE_FCNTL_CLOSEM)
-void
-closefrom(int lowfd)
-{
- if (fcntl(lowfd, F_CLOSEM, 0) == -1)
- closefrom_fallback(lowfd);
-}
-#elif defined(HAVE_PSTAT_GETPROC)
-void
-closefrom(int lowfd)
+#if defined(HAVE_PSTAT_GETPROC)
+static int
+closefrom_pstat(int lowfd)
{
- struct pst_status pstat;
+ struct pst_status pst;
int fd;
- if (pstat_getproc(&pstat, sizeof(pstat), 0, getpid()) != -1) {
- for (fd = lowfd; fd <= pstat.pst_highestfd; fd++)
+ /*
+ * EOVERFLOW is not a fatal error for the fields we use.
+ * See the "EOVERFLOW Error" section of pstat_getvminfo(3).
+ */
+ if (pstat_getproc(&pst, sizeof(pst), 0, getpid()) != -1 ||
+ errno == EOVERFLOW) {
+ for (fd = lowfd; fd <= pst.pst_highestfd; fd++)
(void)close(fd);
- } else {
- closefrom_fallback(lowfd);
+ return 0;
}
+ return -1;
}
#elif defined(HAVE_DIRFD)
static int
@@ -135,8 +125,8 @@ closefrom_procfs(int lowfd)
int ret = 0;
int i;
- /* Use /proc/self/fd (or /dev/fd on FreeBSD) if it exists. */
-# if defined(__FreeBSD__) || defined(__FreeBSD_kernel__) || defined(__APPLE__)
+ /* Use /proc/self/fd (or /dev/fd on macOS) if it exists. */
+# ifdef __APPLE__
path = "/dev/fd";
# else
path = "/proc/self/fd";
@@ -180,13 +170,28 @@ closefrom_procfs(int lowfd)
return ret;
}
+#endif
+/*
+ * Close all file descriptors greater than or equal to lowfd.
+ * We try the fast way first, falling back on the slow method.
+ */
void
closefrom(int lowfd)
{
- if (closefrom_procfs(lowfd) == 0)
+ /* Try the fast method first, if possible. */
+#if defined(HAVE_FCNTL_CLOSEM)
+ if (fcntl(lowfd, F_CLOSEM, 0) != -1)
+ return;
+#endif /* HAVE_FCNTL_CLOSEM */
+#if defined(HAVE_PSTAT_GETPROC)
+ if (closefrom_pstat(lowfd) != -1)
+ return;
+#elif defined(HAVE_DIRFD)
+ if (closefrom_procfs(lowfd) != -1)
return;
+#endif /* HAVE_DIRFD */
+ /* Do things the slow way. */
closefrom_fallback(lowfd);
}
-#endif /* HAVE_FCNTL_CLOSEM */
commit 467602628660326a54f7af7344d5539cf31aeea3
Author: Faidon Liambotis <paravoid at debian.org>
Date: Sun Feb 7 20:47:00 2021 +0200
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 at hadrons.org: Remove reference to kernel mode in man page. ]
Closes: !12
Signed-off-by: Guillem Jover <guillem at hadrons.org>
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
commit 25f9b30678b352e8275c98e118f5beacffbb94b4
Author: Guillem Jover <guillem at hadrons.org>
Date: Sun Feb 7 23:24:51 2021 +0100
test: Improve code coverage for strnstr(3) unit tests
diff --git a/test/strnstr.c b/test/strnstr.c
index 6cef281..3d89fa8 100644
--- a/test/strnstr.c
+++ b/test/strnstr.c
@@ -35,11 +35,15 @@ main(int argc, char **argv)
assert(strnstr(large, "", strlen(large)) == large);
+ assert(strnstr(large, "far", strlen(large)) == NULL);
assert(strnstr(large, "quux", strlen(large)) == NULL);
assert(strnstr(large, small, 4) == NULL);
assert(strnstr(large, small, strlen(large)) == (large + 4));
+ assert(strnstr("quux", large, strlen("quux")) == NULL);
+ assert(strnstr("foo", large, strlen("foo")) == NULL);
+
return 0;
}
More information about the libbsd
mailing list