Add SIMPLEQ_CONCAT and TAILQ_CONCAT for moving one queue onto the end

of another one.  Adapted from FreeBSD.  OK jmc@ dlg@ nicm@

3 files changed, 54 insertions, 7 deletions

diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index e9c34411393..e5f30719084 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.27 2014/10/13 17:27:00 millert Exp $
+#	$OpenBSD: Makefile,v 1.28 2015/11/19 13:38:07 millert Exp $
 #	@(#)Makefile	8.2 (Berkeley) 12/13/93
 
 MAN=	assert.3 bitstring.3 CMSG_DATA.3 dlfcn.3 dl_iterate_phdr.3 end.3 \
@@ -35,7 +35,7 @@ MLINKS+=queue.3 SIMPLEQ_ENTRY.3 queue.3 SIMPLEQ_HEAD.3 \
 	queue.3 SIMPLEQ_FOREACH_SAFE.3 queue.3 SIMPLEQ_INIT.3 \
 	queue.3 SIMPLEQ_INSERT_HEAD.3 queue.3 SIMPLEQ_INSERT_TAIL.3 \
 	queue.3 SIMPLEQ_INSERT_AFTER.3 queue.3 SIMPLEQ_REMOVE_HEAD.3 \
-	queue.3 SIMPLEQ_REMOVE_AFTER.3
+	queue.3 SIMPLEQ_REMOVE_AFTER.3 queue.3 SIMPLEQ_CONCAT.3
 MLINKS+=queue.3 TAILQ_ENTRY.3 queue.3 TAILQ_HEAD.3 \
 	queue.3 TAILQ_HEAD_INITIALIZER.3 queue.3 TAILQ_FIRST.3 \
 	queue.3 TAILQ_NEXT.3 queue.3 TAILQ_LAST.3 \
@@ -45,7 +45,7 @@ MLINKS+=queue.3 TAILQ_ENTRY.3 queue.3 TAILQ_HEAD.3 \
 	queue.3 TAILQ_INIT.3 \
 	queue.3 TAILQ_INSERT_AFTER.3 queue.3 TAILQ_INSERT_BEFORE.3 \
 	queue.3 TAILQ_INSERT_HEAD.3 queue.3 TAILQ_INSERT_TAIL.3 \
-	queue.3 TAILQ_REMOVE.3 queue.3 TAILQ_REPLACE.3
+	queue.3 TAILQ_REMOVE.3 queue.3 TAILQ_REPLACE.3 queue.3 TAILQ_CONCAT.3
 MLINKS+=stdarg.3 varargs.3 stdarg.3 va_arg.3 stdarg.3 va_end.3
 MLINKS+=stdarg.3 va_start.3 stdarg.3 va_copy.3
 MLINKS+=dlfcn.3 dlopen.3 dlfcn.3 dlclose.3 dlfcn.3 dlsym.3 dlfcn.3 dlctl.3 \
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index 5cc9370fee6..efaf2153161 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: queue.3,v 1.62 2015/11/10 23:48:17 jmc Exp $
+.\"	$OpenBSD: queue.3,v 1.63 2015/11/19 13:38:07 millert Exp $
 .\"	$NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $
 .\"
 .\" Copyright (c) 1993 The Regents of the University of California.
@@ -30,7 +30,7 @@
 .\"
 .\"	@(#)queue.3	8.1 (Berkeley) 12/13/93
 .\"
-.Dd $Mdocdate: November 10 2015 $
+.Dd $Mdocdate: November 19 2015 $
 .Dt SLIST_INIT 3
 .Os
 .Sh NAME
@@ -76,6 +76,7 @@
 .Nm SIMPLEQ_INSERT_TAIL ,
 .Nm SIMPLEQ_REMOVE_AFTER ,
 .Nm SIMPLEQ_REMOVE_HEAD ,
+.Nm SIMPLEQ_CONCAT ,
 .Nm TAILQ_ENTRY ,
 .Nm TAILQ_HEAD ,
 .Nm TAILQ_HEAD_INITIALIZER ,
@@ -94,7 +95,8 @@
 .Nm TAILQ_INSERT_HEAD ,
 .Nm TAILQ_INSERT_TAIL ,
 .Nm TAILQ_REMOVE ,
-.Nm TAILQ_REPLACE
+.Nm TAILQ_REPLACE ,
+.Nm TAILQ_CONCAT
 .Nd implementations of singly-linked lists, doubly-linked lists, simple queues, and tail queues
 .Sh SYNOPSIS
 .In sys/queue.h
@@ -170,6 +172,7 @@
 .Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
 .Ft void
 .Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "FIELDNAME"
+.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2"
 .Pp
 .Fn TAILQ_ENTRY "TYPE"
 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
@@ -202,6 +205,7 @@
 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
 .Ft void
 .Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME"
+.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2"
 .Sh DESCRIPTION
 These macros define and operate on four types of data structures:
 singly-linked lists, simple queues, lists, and tail queues.
@@ -678,6 +682,19 @@ macro removes the first element
 from the queue.
 .Pp
 The
+.Fn SIMPLEQ_CONCAT
+macro concatenates all the elements of the queue referenced by
+.Fa head2
+to the end of the queue referenced by
+.Fa head1 ,
+emptying
+.Fa head2
+in the process.
+This is more efficient than removing and inserting the individual elements
+as it does not actually traverse
+.Fa head2 .
+.Pp
+The
 .Fn SIMPLEQ_FIRST
 and
 .Fn SIMPLEQ_NEXT
@@ -816,6 +833,19 @@ macro replaces the list element
 with the new element
 .Fa elm2 .
 .Pp
+The
+.Fn TAILQ_CONCAT
+macro concatenates all the elements of the tail queue referenced by
+.Fa head2
+to the end of the tail queue referenced by
+.Fa head1 ,
+emptying
+.Fa head2
+in the process.
+This is more efficient than removing and inserting the individual elements
+as it does not actually traverse
+.Fa head2 .
+.Pp
 .Fn TAILQ_FOREACH
 and
 .Fn TAILQ_FOREACH_REVERSE
diff --git a/sys/sys/queue.h b/sys/sys/queue.h
index eb5bb0279d1..02cbd4de655 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: queue.h,v 1.40 2015/10/30 12:20:56 jasper Exp $	*/
+/*	$OpenBSD: queue.h,v 1.41 2015/11/19 13:38:07 millert Exp $	*/
 /*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
 
 /*
@@ -316,6 +316,14 @@ struct {								\
 		(head)->sqh_last = &(elm)->field.sqe_next;		\
 } while (0)
 
+#define SIMPLEQ_CONCAT(head1, head2) do {				\
+	if (!SIMPLEQ_EMPTY((head2))) {					\
+		*(head1)->sqh_last = (head2)->sqh_first;		\
+		(head1)->sqh_last = (head2)->sqh_last;			\
+		SIMPLEQ_INIT((head2));					\
+	}								\
+} while (0)
+
 /*
  * XOR Simple queue definitions.
  */
@@ -516,6 +524,15 @@ struct {								\
 	_Q_INVALIDATE((elm)->field.tqe_next);				\
 } while (0)
 
+#define TAILQ_CONCAT(head1, head2, field) do {				\
+	if (!TAILQ_EMPTY(head2)) {					\
+		*(head1)->tqh_last = (head2)->tqh_first;		\
+		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
+		(head1)->tqh_last = (head2)->tqh_last;			\
+		TAILQ_INIT((head2));					\
+	}								\
+} while (0)
+
 /*
  * Circular queue definitions.
  */