main/rsyslog: update to 8.18.0, and apply a new musl fix

This commit brings rsyslog up to the latest release that has some nice performance improvements and bug fixes.
This commit also includes an upstream fix from 8.19.0 (unreleased) which fixes a segfault present in all current rsyslog versions on musl.
Version 8.17 and later of rsyslog has a new dependency. It now needs libfastjson installed to run.
I created the libfastjson package earlier this month, it is in the `testing` directory. I believe libfastjson will need to be promoted from `testing` to `edge`.

3 files changed, 738 insertions, 11 deletions

diff --git a/main/rsyslog/8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch b/main/rsyslog/8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch
new file mode 100644
index 00000000000..c763780f1a1
--- /dev/null
+++ b/main/rsyslog/8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch
@@ -0,0 +1,114 @@
+From 8e4bfe19b5d971f5df8520faf8753381b58e7ca7 Mon Sep 17 00:00:00 2001
+From: Rainer Gerhards <rgerhards@adiscon.com>
+Date: Fri, 29 Apr 2016 08:09:44 +0200
+Subject: [PATCH] core: set default stack size to 4MiB
+
+Note that this is below the usual 10MiB default, but should cause
+no issues (output threads already use 4MiB stack size, for example).
+This also addresses issues introduced by micro-libc's which only
+provide very limited stack space by default.
+
+closes https://github.com/rsyslog/rsyslog/issues/996
+---
+ runtime/rsyslog.c | 7 ++++---
+ runtime/rsyslog.h | 2 +-
+ runtime/stream.c  | 4 ----
+ threads.c         | 9 +--------
+ 4 files changed, 6 insertions(+), 16 deletions(-)
+
+diff --git a/runtime/rsyslog.c b/runtime/rsyslog.c
+index c6d70d4..c23d9f7 100644
+--- a/runtime/rsyslog.c
++++ b/runtime/rsyslog.c
+@@ -35,7 +35,7 @@
+  *
+  * Module begun 2008-04-16 by Rainer Gerhards
+  *
+- * Copyright 2008-2014 Rainer Gerhards and Adiscon GmbH.
++ * Copyright 2008-2016 Rainer Gerhards and Adiscon GmbH.
+  *
+  * This file is part of the rsyslog runtime library.
+  *
+@@ -83,9 +83,9 @@
+ #include "atomic.h"
+ #include "srUtils.h"
+ 
++pthread_attr_t default_thread_attr;
+ #ifdef HAVE_PTHREAD_SETSCHEDPARAM
+ struct sched_param default_sched_param;
+-pthread_attr_t default_thread_attr;
+ int default_thr_sched_policy;
+ #endif
+ 
+@@ -145,11 +145,12 @@ rsrtInit(char **ppErrObj, obj_if_t *pObjIF)
+ 		stdlog_init(0);
+ 		stdlog_hdl = NULL;
+ #endif
++		CHKiRet(pthread_attr_init(&default_thread_attr));
++		pthread_attr_setstacksize(&default_thread_attr, 4096*1024);
+ #ifdef HAVE_PTHREAD_SETSCHEDPARAM
+ 	    	CHKiRet(pthread_getschedparam(pthread_self(),
+ 			    		      &default_thr_sched_policy,
+ 					      &default_sched_param));
+-		CHKiRet(pthread_attr_init(&default_thread_attr));
+ 		CHKiRet(pthread_attr_setschedpolicy(&default_thread_attr,
+ 			    			    default_thr_sched_policy));
+ 		CHKiRet(pthread_attr_setschedparam(&default_thread_attr,
+diff --git a/runtime/rsyslog.h b/runtime/rsyslog.h
+index 542343d..87198f3 100644
+--- a/runtime/rsyslog.h
++++ b/runtime/rsyslog.h
+@@ -532,9 +532,9 @@ typedef enum rsObjectID rsObjID;
+ #define RSFREEOBJ(x) {(x)->OID = OIDrsFreed; free(x);}
+ #endif
+ 
++extern pthread_attr_t default_thread_attr;
+ #ifdef HAVE_PTHREAD_SETSCHEDPARAM
+ extern struct sched_param default_sched_param;
+-extern pthread_attr_t default_thread_attr;
+ extern int default_thr_sched_policy;
+ #endif
+ 
+diff --git a/runtime/stream.c b/runtime/stream.c
+index ae3efaa..97b0ccd 100644
+--- a/runtime/stream.c
++++ b/runtime/stream.c
+@@ -968,11 +968,7 @@ static rsRetVal strmConstructFinalize(strm_t *pThis)
+ 		pThis->pIOBuf = pThis->asyncBuf[0].pBuf;
+ 		pThis->bStopWriter = 0;
+ 		if(pthread_create(&pThis->writerThreadID,
+-#ifdef HAVE_PTHREAD_SETSCHEDPARAM
+ 			    	  &default_thread_attr,
+-#else
+-				  NULL,
+-#endif
+ 				  asyncWriterThread, pThis) != 0)
+ 			DBGPRINTF("ERROR: stream %p cold not create writer thread\n", pThis);
+ 	} else {
+diff --git a/threads.c b/threads.c
+index b6cab1b..2d83402 100644
+--- a/threads.c
++++ b/threads.c
+@@ -235,7 +235,6 @@ static void* thrdStarter(void *arg)
+ 	ENDfunc
+ 	pthread_exit(0);
+ }
+-
+ /* Start a new thread and add it to the list of currently
+  * executing threads. It is added at the end of the list.
+  * rgerhards, 2007-12-14
+@@ -253,13 +252,7 @@ rsRetVal thrdCreate(rsRetVal (*thrdMain)(thrdInfo_t*), rsRetVal(*afterRun)(thrdI
+ 	pThis->pAfterRun = afterRun;
+ 	pThis->bNeedsCancel = bNeedsCancel;
+ 	pThis->name = ustrdup(name);
+-	pthread_create(&pThis->thrdID,
+-#ifdef HAVE_PTHREAD_SETSCHEDPARAM
+-			   &default_thread_attr,
+-#else
+-			   NULL,
+-#endif
+-			   thrdStarter, pThis);
++	pthread_create(&pThis->thrdID, &default_thread_attr, thrdStarter, pThis);
+ 	CHKiRet(llAppend(&llThrds, NULL, pThis));
+ 
+ finalize_it:
diff --git a/main/rsyslog/APKBUILD b/main/rsyslog/APKBUILD
index a5ccc9b23bc..d98dd62786c 100644
--- a/main/rsyslog/APKBUILD
+++ b/main/rsyslog/APKBUILD
@@ -1,17 +1,19 @@
 # Contributor: Francisco Guerreiro <francisg@fnop.net>
 # Contributor: Łukasz Jendrysik <scadu@yandex.com>
 # Contributor: Cameron Banta <cbanta@gmail.com>
+# Contributor: Ashley Sommer <ashleysommer@gmail.com>
 # Maintainer: Cameron Banta <cbanta@gmail.com>
 pkgname=rsyslog
-pkgver=8.16.0
+pkgver=8.18.0
 pkgrel=0
 pkgdesc="Enhanced multi-threaded syslogd with database support and more."
 url="http://www.rsyslog.com/"
 arch="all"
 license="GPLv3 LGPL3"
+depends=""
 makedepends="zlib-dev gnutls-dev mariadb-dev postgresql-dev net-snmp-dev
 	libnet-dev libgcrypt-dev libee-dev libestr-dev liblogging-dev
-	json-c-dev util-linux-dev py-docutils hiredis-dev"
+	libfastjson-dev util-linux-dev py-docutils hiredis-dev"
 subpackages="$pkgname-doc $pkgname-mysql $pkgname-pgsql $pkgname-tls
 	$pkgname-snmp $pkgname-hiredis $pkgname-dbg"
 source="http://www.rsyslog.com/files/download/$pkgname/$pkgname-$pkgver.tar.gz
@@ -20,9 +22,21 @@ source="http://www.rsyslog.com/files/download/$pkgname/$pkgname-$pkgver.tar.gz
 	$pkgname.logrotate
 	$pkgname.conf
 	musl-fix.patch
-	"
+        queue.patch
+        8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch	
+        "
 
 _builddir="$srcdir"/$pkgname-$pkgver
+prepare() {
+        local i
+        cd "$_builddir"
+        for i in $source; do
+                case $i in
+                *.patch) msg $i; patch -p1 -i "$srcdir"/$i || return 1;;
+                esac
+        done
+}
+
 build() {
 	cd "$_builddir"
 	./configure \
@@ -56,7 +70,6 @@ package() {
 
 	install -m755 -D "$srcdir"/$pkgname.initd "$pkgdir"/etc/init.d/$pkgname
 	install -m644 -D "$srcdir"/$pkgname.confd "$pkgdir"/etc/conf.d/$pkgname
-
 	install -m644 -D "$srcdir"/$pkgname.logrotate "$pkgdir"/etc/logrotate.d/$pkgname
 	install -m644 -D "$srcdir"/$pkgname.conf "$pkgdir"/etc/$pkgname.conf
 }
@@ -96,21 +109,27 @@ snmp() {
 		"$subpkgdir"/usr/lib/rsyslog/ || return 1
 }
 
-md5sums="52916045c07ebbd3ee77c39e8465bc4d  rsyslog-8.16.0.tar.gz
+md5sums="750d552bdcbf255c85f464ffbe21168a  rsyslog-8.18.0.tar.gz
 67b8afd572b4103b39b54a729b880b53  rsyslog.initd
 a34f33d8f798ab6652b347ad09656284  rsyslog.confd
 bc43debc9ffdf66bc1409025fd3d1176  rsyslog.logrotate
+bc0a9b1095f5f6ffc937cd2c9bd26dff  rsyslog.conf
 480f153508fd10d157cefc0bb898fe2d  musl-fix.patch
-bc0a9b1095f5f6ffc937cd2c9bd26dff  rsyslog.conf"
-sha256sums="4fe4f97c10899086d98b9401d7e8d2bcff61c7c3f7cde8627891e36fc6ec1b76  rsyslog-8.16.0.tar.gz
+dece4c5510e5d4f88293eff74da5bf57  queue.patch
+0d32cadf752462f45bcde9b04df9ebfc  8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch"
+sha256sums="94346237ecfa22c9f78cebc3f18d59056f5d9846eb906c75beaa7e486f02c695  rsyslog-8.18.0.tar.gz
 223d4bdb69760ef5a9a044d68434c805cd15e31fa190a86f5f283912d0baf6d6  rsyslog.initd
 f93cd477770872486185152454ce66e89302b7a8d7a112ff285ceea892dfe1f1  rsyslog.confd
 f0effc19bd1f1bfa367d65d6516c73509cb34545157b9e91cf6e437685dd3fe5  rsyslog.logrotate
+e4ebe806b5a71edaa4492033ea3a3e70810a64d3f3d4f4e9954eefcf25f2e2ed  rsyslog.conf
 5b8420570bef57aeba55965bbbddb29f966b60a33ef9e7fc5f921820274080b0  musl-fix.patch
-e4ebe806b5a71edaa4492033ea3a3e70810a64d3f3d4f4e9954eefcf25f2e2ed  rsyslog.conf"
-sha512sums="e45acc16078d83937edd7e22f916fe050b62aa057ca4dd980823850f2195213c12db36f759c528b5fe6f1b061a61e2117fca6086245bc248392cc4e61b2383dc  rsyslog-8.16.0.tar.gz
-20967235e8233588210071a7157a81fe02a1e88d7c7f55855fcc2fe34295269a6e3e3bfccb3d4dd83a6a48da28948c92d6ce47a0c5d817f6b6a4030635f4f896  musl-fix.patch
+8d6dda439c79dffac2a5d17e3d9a28355cfb8fc264175a871e27304ace259daa  queue.patch
+940dcb4a48cbb8e235cab8c35dbb10c32bc6283574fe845dcce42a428a92ee3b  8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch"
+sha512sums="6b159ba23100b4675576f5b247d2bf482bab0beaa071c26c692c99e50f202b0b272b7a64ba2b7c726390d663677b7a6d68666b06f73825e35605b13ae0930fc7  rsyslog-8.18.0.tar.gz
 9a4b184076a82e0899da79ab3749e1c67eac03f36c4460d34ed0385f4a3ffad53681a1cc25dd514e835c9399a9abd01c235743535ad549d5be7f66d9e127b9dc  rsyslog.initd
 a4d969671800227129be870b0318961b79d16365663754111a136734bbf7005abd4da24853dfdc07b3b6691ab5a7b215f0ac6c19022b4c5c8dab06165a42431b  rsyslog.confd
 d54377ddf39197656811a84272568ea761f984e19dd04fc54f372dd04a9244e66d02b26ab33073d0344d054f031660ec611f3c7a18c266e7b68cef5e2c47f06f  rsyslog.logrotate
-3bcd58b222eb7f4d8a42a0643cacb6ab44790f90c9bd550678e002bc19863d5d6a7341e5e5ba0b9292f85c6c04cd5cc42d174acdc63e8ba22022620db10f2b9b  rsyslog.conf"
+3bcd58b222eb7f4d8a42a0643cacb6ab44790f90c9bd550678e002bc19863d5d6a7341e5e5ba0b9292f85c6c04cd5cc42d174acdc63e8ba22022620db10f2b9b  rsyslog.conf
+20967235e8233588210071a7157a81fe02a1e88d7c7f55855fcc2fe34295269a6e3e3bfccb3d4dd83a6a48da28948c92d6ce47a0c5d817f6b6a4030635f4f896  musl-fix.patch
+de8b82781af2dfef67b2215782721cca2ee5db9d08ed3260f4e3390353a59bf4bd76701df682c4bf537ce817eabf79b062c4b2a3e20e4175e7d77ca08c5a700f  queue.patch
+53e1b3a219fec91bf13448398bda6239061027dbd5327260fd44d9e3b290386b43992c3a0d20e73971c5f5a682b9bd87d17ffbf42d40121d82c079970b325547  8e4bfe19b5d971f5df8520faf8753381b58e7ca7.patch"
diff --git a/main/rsyslog/queue.patch b/main/rsyslog/queue.patch
new file mode 100644
index 00000000000..863fbd24f2d
--- /dev/null
+++ b/main/rsyslog/queue.patch
@@ -0,0 +1,594 @@
+--- rsyslog-8.18.0/plugins/imptcp/imptcp.c
++++ rsyslog-8.18.0-b/plugins/imptcp/imptcp.c
+@@ -50,13 +50,13 @@
+ #include <sys/socket.h>
+ #include <sys/un.h>
+ #include <sys/epoll.h>
+-#include <sys/queue.h>
+ #include <netinet/tcp.h>
+ #include <stdint.h>
+ #include <zlib.h>
+ #if HAVE_FCNTL_H
+ #include <fcntl.h>
+ #endif
++#include "queue.h"
+ #include "rsyslog.h"
+ #include "cfsysline.h"
+ #include "prop.h"
+--- /dev/null
++++ rsyslog-8.18.0-b/plugins/imptcp/queue.h
+@@ -0,0 +1,574 @@
++/*
++ * Copyright (c) 1991, 1993
++ *	The Regents of the University of California.  All rights reserved.
++ *
++ * Redistribution and use in source and binary forms, with or without
++ * modification, are permitted provided that the following conditions
++ * are met:
++ * 1. Redistributions of source code must retain the above copyright
++ *    notice, this list of conditions and the following disclaimer.
++ * 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.
++ * 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.
++ *
++ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
++ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
++ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
++ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
++ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
++ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
++ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
++ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
++ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
++ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
++ * SUCH DAMAGE.
++ *
++ *	@(#)queue.h	8.5 (Berkeley) 8/20/94
++ */
++
++#ifndef	_SYS_QUEUE_H_
++#define	_SYS_QUEUE_H_
++
++/*
++ * This file defines five types of data structures: singly-linked lists,
++ * lists, simple queues, tail queues, and circular queues.
++ *
++ * A singly-linked list is headed by a single forward pointer. The
++ * elements are singly linked for minimum space and pointer manipulation
++ * overhead at the expense of O(n) removal for arbitrary elements. New
++ * elements can be added to the list after an existing element or at the
++ * head of the list.  Elements being removed from the head of the list
++ * should use the explicit macro for this purpose for optimum
++ * efficiency. A singly-linked list may only be traversed in the forward
++ * direction.  Singly-linked lists are ideal for applications with large
++ * datasets and few or no removals or for implementing a LIFO queue.
++ *
++ * A list is headed by a single forward pointer (or an array of forward
++ * pointers for a hash table header). The elements are doubly linked
++ * so that an arbitrary element can be removed without a need to
++ * traverse the list. New elements can be added to the list before
++ * or after an existing element or at the head of the list. A list
++ * may only be traversed in the forward direction.
++ *
++ * A simple queue is headed by a pair of pointers, one the head of the
++ * list and the other to the tail of the list. The elements are singly
++ * linked to save space, so elements can only be removed from the
++ * head of the list. New elements can be added to the list after
++ * an existing element, at the head of the list, or at the end of the
++ * list. A simple queue may only be traversed in the forward direction.
++ *
++ * A tail queue is headed by a pair of pointers, one to the head of the
++ * list and the other to the tail of the list. The elements are doubly
++ * linked so that an arbitrary element can be removed without a need to
++ * traverse the list. New elements can be added to the list before or
++ * after an existing element, at the head of the list, or at the end of
++ * the list. A tail queue may be traversed in either direction.
++ *
++ * A circle queue is headed by a pair of pointers, one to the head of the
++ * list and the other to the tail of the list. The elements are doubly
++ * linked so that an arbitrary element can be removed without a need to
++ * traverse the list. New elements can be added to the list before or after
++ * an existing element, at the head of the list, or at the end of the list.
++ * A circle queue may be traversed in either direction, but has a more
++ * complex end of list detection.
++ *
++ * For details on the use of these macros, see the queue(3) manual page.
++ */
++
++/*
++ * List definitions.
++ */
++#define	LIST_HEAD(name, type)						\
++struct name {								\
++	struct type *lh_first;	/* first element */			\
++}
++
++#define	LIST_HEAD_INITIALIZER(head)					\
++	{ NULL }
++
++#define	LIST_ENTRY(type)						\
++struct {								\
++	struct type *le_next;	/* next element */			\
++	struct type **le_prev;	/* address of previous next element */	\
++}
++
++/*
++ * List functions.
++ */
++#define	LIST_INIT(head) do {						\
++	(head)->lh_first = NULL;					\
++} while (/*CONSTCOND*/0)
++
++#define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
++	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
++		(listelm)->field.le_next->field.le_prev =		\
++		    &(elm)->field.le_next;				\
++	(listelm)->field.le_next = (elm);				\
++	(elm)->field.le_prev = &(listelm)->field.le_next;		\
++} while (/*CONSTCOND*/0)
++
++#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
++	(elm)->field.le_prev = (listelm)->field.le_prev;		\
++	(elm)->field.le_next = (listelm);				\
++	*(listelm)->field.le_prev = (elm);				\
++	(listelm)->field.le_prev = &(elm)->field.le_next;		\
++} while (/*CONSTCOND*/0)
++
++#define	LIST_INSERT_HEAD(head, elm, field) do {				\
++	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
++		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
++	(head)->lh_first = (elm);					\
++	(elm)->field.le_prev = &(head)->lh_first;			\
++} while (/*CONSTCOND*/0)
++
++#define	LIST_REMOVE(elm, field) do {					\
++	if ((elm)->field.le_next != NULL)				\
++		(elm)->field.le_next->field.le_prev = 			\
++		    (elm)->field.le_prev;				\
++	*(elm)->field.le_prev = (elm)->field.le_next;			\
++} while (/*CONSTCOND*/0)
++
++#define	LIST_FOREACH(var, head, field)					\
++	for ((var) = ((head)->lh_first);				\
++		(var);							\
++		(var) = ((var)->field.le_next))
++
++/*
++ * List access methods.
++ */
++#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
++#define	LIST_FIRST(head)		((head)->lh_first)
++#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
++
++
++/*
++ * Singly-linked List definitions.
++ */
++#define	SLIST_HEAD(name, type)						\
++struct name {								\
++	struct type *slh_first;	/* first element */			\
++}
++
++#define	SLIST_HEAD_INITIALIZER(head)					\
++	{ NULL }
++
++#define	SLIST_ENTRY(type)						\
++struct {								\
++	struct type *sle_next;	/* next element */			\
++}
++
++/*
++ * Singly-linked List functions.
++ */
++#define	SLIST_INIT(head) do {						\
++	(head)->slh_first = NULL;					\
++} while (/*CONSTCOND*/0)
++
++#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
++	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
++	(slistelm)->field.sle_next = (elm);				\
++} while (/*CONSTCOND*/0)
++
++#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
++	(elm)->field.sle_next = (head)->slh_first;			\
++	(head)->slh_first = (elm);					\
++} while (/*CONSTCOND*/0)
++
++#define	SLIST_REMOVE_HEAD(head, field) do {				\
++	(head)->slh_first = (head)->slh_first->field.sle_next;		\
++} while (/*CONSTCOND*/0)
++
++#define	SLIST_REMOVE(head, elm, type, field) do {			\
++	if ((head)->slh_first == (elm)) {				\
++		SLIST_REMOVE_HEAD((head), field);			\
++	}								\
++	else {								\
++		struct type *curelm = (head)->slh_first;		\
++		while(curelm->field.sle_next != (elm))			\
++			curelm = curelm->field.sle_next;		\
++		curelm->field.sle_next =				\
++		    curelm->field.sle_next->field.sle_next;		\
++	}								\
++} while (/*CONSTCOND*/0)
++
++#define	SLIST_FOREACH(var, head, field)					\
++	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
++
++/*
++ * Singly-linked List access methods.
++ */
++#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
++#define	SLIST_FIRST(head)	((head)->slh_first)
++#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
++
++
++/*
++ * Singly-linked Tail queue declarations.
++ */
++#define	STAILQ_HEAD(name, type)					\
++struct name {								\
++	struct type *stqh_first;	/* first element */			\
++	struct type **stqh_last;	/* addr of last next element */		\
++}
++
++#define	STAILQ_HEAD_INITIALIZER(head)					\
++	{ NULL, &(head).stqh_first }
++
++#define	STAILQ_ENTRY(type)						\
++struct {								\
++	struct type *stqe_next;	/* next element */			\
++}
++
++/*
++ * Singly-linked Tail queue functions.
++ */
++#define	STAILQ_INIT(head) do {						\
++	(head)->stqh_first = NULL;					\
++	(head)->stqh_last = &(head)->stqh_first;				\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
++	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)	\
++		(head)->stqh_last = &(elm)->field.stqe_next;		\
++	(head)->stqh_first = (elm);					\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
++	(elm)->field.stqe_next = NULL;					\
++	*(head)->stqh_last = (elm);					\
++	(head)->stqh_last = &(elm)->field.stqe_next;			\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
++	if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
++		(head)->stqh_last = &(elm)->field.stqe_next;		\
++	(listelm)->field.stqe_next = (elm);				\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_REMOVE_HEAD(head, field) do {				\
++	if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
++		(head)->stqh_last = &(head)->stqh_first;			\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_REMOVE(head, elm, type, field) do {			\
++	if ((head)->stqh_first == (elm)) {				\
++		STAILQ_REMOVE_HEAD((head), field);			\
++	} else {							\
++		struct type *curelm = (head)->stqh_first;		\
++		while (curelm->field.stqe_next != (elm))			\
++			curelm = curelm->field.stqe_next;		\
++		if ((curelm->field.stqe_next =				\
++			curelm->field.stqe_next->field.stqe_next) == NULL) \
++			    (head)->stqh_last = &(curelm)->field.stqe_next; \
++	}								\
++} while (/*CONSTCOND*/0)
++
++#define	STAILQ_FOREACH(var, head, field)				\
++	for ((var) = ((head)->stqh_first);				\
++		(var);							\
++		(var) = ((var)->field.stqe_next))
++
++#define	STAILQ_CONCAT(head1, head2) do {				\
++	if (!STAILQ_EMPTY((head2))) {					\
++		*(head1)->stqh_last = (head2)->stqh_first;		\
++		(head1)->stqh_last = (head2)->stqh_last;		\
++		STAILQ_INIT((head2));					\
++	}								\
++} while (/*CONSTCOND*/0)
++
++/*
++ * Singly-linked Tail queue access methods.
++ */
++#define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
++#define	STAILQ_FIRST(head)	((head)->stqh_first)
++#define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
++
++
++/*
++ * Simple queue definitions.
++ */
++#define	SIMPLEQ_HEAD(name, type)					\
++struct name {								\
++	struct type *sqh_first;	/* first element */			\
++	struct type **sqh_last;	/* addr of last next element */		\
++}
++
++#define	SIMPLEQ_HEAD_INITIALIZER(head)					\
++	{ NULL, &(head).sqh_first }
++
++#define	SIMPLEQ_ENTRY(type)						\
++struct {								\
++	struct type *sqe_next;	/* next element */			\
++}
++
++/*
++ * Simple queue functions.
++ */
++#define	SIMPLEQ_INIT(head) do {						\
++	(head)->sqh_first = NULL;					\
++	(head)->sqh_last = &(head)->sqh_first;				\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
++	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
++		(head)->sqh_last = &(elm)->field.sqe_next;		\
++	(head)->sqh_first = (elm);					\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
++	(elm)->field.sqe_next = NULL;					\
++	*(head)->sqh_last = (elm);					\
++	(head)->sqh_last = &(elm)->field.sqe_next;			\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
++	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
++		(head)->sqh_last = &(elm)->field.sqe_next;		\
++	(listelm)->field.sqe_next = (elm);				\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
++	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
++		(head)->sqh_last = &(head)->sqh_first;			\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
++	if ((head)->sqh_first == (elm)) {				\
++		SIMPLEQ_REMOVE_HEAD((head), field);			\
++	} else {							\
++		struct type *curelm = (head)->sqh_first;		\
++		while (curelm->field.sqe_next != (elm))			\
++			curelm = curelm->field.sqe_next;		\
++		if ((curelm->field.sqe_next =				\
++			curelm->field.sqe_next->field.sqe_next) == NULL) \
++			    (head)->sqh_last = &(curelm)->field.sqe_next; \
++	}								\
++} while (/*CONSTCOND*/0)
++
++#define	SIMPLEQ_FOREACH(var, head, field)				\
++	for ((var) = ((head)->sqh_first);				\
++		(var);							\
++		(var) = ((var)->field.sqe_next))
++
++/*
++ * Simple queue access methods.
++ */
++#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
++#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
++#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
++
++
++/*
++ * Tail queue definitions.
++ */
++#define	_TAILQ_HEAD(name, type, qual)					\
++struct name {								\
++	qual type *tqh_first;		/* first element */		\
++	qual type *qual *tqh_last;	/* addr of last next element */	\
++}
++#define TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type,)
++
++#define	TAILQ_HEAD_INITIALIZER(head)					\
++	{ NULL, &(head).tqh_first }
++
++#define	_TAILQ_ENTRY(type, qual)					\
++struct {								\
++	qual type *tqe_next;		/* next element */		\
++	qual type *qual *tqe_prev;	/* address of previous next element */\
++}
++#define TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type,)
++
++/*
++ * Tail queue functions.
++ */
++#define	TAILQ_INIT(head) do {						\
++	(head)->tqh_first = NULL;					\
++	(head)->tqh_last = &(head)->tqh_first;				\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
++	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
++		(head)->tqh_first->field.tqe_prev =			\
++		    &(elm)->field.tqe_next;				\
++	else								\
++		(head)->tqh_last = &(elm)->field.tqe_next;		\
++	(head)->tqh_first = (elm);					\
++	(elm)->field.tqe_prev = &(head)->tqh_first;			\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
++	(elm)->field.tqe_next = NULL;					\
++	(elm)->field.tqe_prev = (head)->tqh_last;			\
++	*(head)->tqh_last = (elm);					\
++	(head)->tqh_last = &(elm)->field.tqe_next;			\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
++	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
++		(elm)->field.tqe_next->field.tqe_prev = 		\
++		    &(elm)->field.tqe_next;				\
++	else								\
++		(head)->tqh_last = &(elm)->field.tqe_next;		\
++	(listelm)->field.tqe_next = (elm);				\
++	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
++	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
++	(elm)->field.tqe_next = (listelm);				\
++	*(listelm)->field.tqe_prev = (elm);				\
++	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_REMOVE(head, elm, field) do {				\
++	if (((elm)->field.tqe_next) != NULL)				\
++		(elm)->field.tqe_next->field.tqe_prev = 		\
++		    (elm)->field.tqe_prev;				\
++	else								\
++		(head)->tqh_last = (elm)->field.tqe_prev;		\
++	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
++} while (/*CONSTCOND*/0)
++
++#define	TAILQ_FOREACH(var, head, field)					\
++	for ((var) = ((head)->tqh_first);				\
++		(var);							\
++		(var) = ((var)->field.tqe_next))
++
++#define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
++	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
++		(var);							\
++		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
++
++#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 (/*CONSTCOND*/0)
++
++/*
++ * Tail queue access methods.
++ */
++#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
++#define	TAILQ_FIRST(head)		((head)->tqh_first)
++#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
++
++#define	TAILQ_LAST(head, headname) \
++	(*(((struct headname *)((head)->tqh_last))->tqh_last))
++#define	TAILQ_PREV(elm, headname, field) \
++	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
++
++
++/*
++ * Circular queue definitions.
++ */
++#define	CIRCLEQ_HEAD(name, type)					\
++struct name {								\
++	struct type *cqh_first;		/* first element */		\
++	struct type *cqh_last;		/* last element */		\
++}
++
++#define	CIRCLEQ_HEAD_INITIALIZER(head)					\
++	{ (void *)&head, (void *)&head }
++
++#define	CIRCLEQ_ENTRY(type)						\
++struct {								\
++	struct type *cqe_next;		/* next element */		\
++	struct type *cqe_prev;		/* previous element */		\
++}
++
++/*
++ * Circular queue functions.
++ */
++#define	CIRCLEQ_INIT(head) do {						\
++	(head)->cqh_first = (void *)(head);				\
++	(head)->cqh_last = (void *)(head);				\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
++	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
++	(elm)->field.cqe_prev = (listelm);				\
++	if ((listelm)->field.cqe_next == (void *)(head))		\
++		(head)->cqh_last = (elm);				\
++	else								\
++		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
++	(listelm)->field.cqe_next = (elm);				\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
++	(elm)->field.cqe_next = (listelm);				\
++	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
++	if ((listelm)->field.cqe_prev == (void *)(head))		\
++		(head)->cqh_first = (elm);				\
++	else								\
++		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
++	(listelm)->field.cqe_prev = (elm);				\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
++	(elm)->field.cqe_next = (head)->cqh_first;			\
++	(elm)->field.cqe_prev = (void *)(head);				\
++	if ((head)->cqh_last == (void *)(head))				\
++		(head)->cqh_last = (elm);				\
++	else								\
++		(head)->cqh_first->field.cqe_prev = (elm);		\
++	(head)->cqh_first = (elm);					\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
++	(elm)->field.cqe_next = (void *)(head);				\
++	(elm)->field.cqe_prev = (head)->cqh_last;			\
++	if ((head)->cqh_first == (void *)(head))			\
++		(head)->cqh_first = (elm);				\
++	else								\
++		(head)->cqh_last->field.cqe_next = (elm);		\
++	(head)->cqh_last = (elm);					\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
++	if ((elm)->field.cqe_next == (void *)(head))			\
++		(head)->cqh_last = (elm)->field.cqe_prev;		\
++	else								\
++		(elm)->field.cqe_next->field.cqe_prev =			\
++		    (elm)->field.cqe_prev;				\
++	if ((elm)->field.cqe_prev == (void *)(head))			\
++		(head)->cqh_first = (elm)->field.cqe_next;		\
++	else								\
++		(elm)->field.cqe_prev->field.cqe_next =			\
++		    (elm)->field.cqe_next;				\
++} while (/*CONSTCOND*/0)
++
++#define	CIRCLEQ_FOREACH(var, head, field)				\
++	for ((var) = ((head)->cqh_first);				\
++		(var) != (const void *)(head);				\
++		(var) = ((var)->field.cqe_next))
++
++#define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
++	for ((var) = ((head)->cqh_last);				\
++		(var) != (const void *)(head);				\
++		(var) = ((var)->field.cqe_prev))
++
++/*
++ * Circular queue access methods.
++ */
++#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
++#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
++#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
++#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
++#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
++
++#define CIRCLEQ_LOOP_NEXT(head, elm, field)				\
++	(((elm)->field.cqe_next == (void *)(head))			\
++	    ? ((head)->cqh_first)					\
++	    : (elm->field.cqe_next))
++#define CIRCLEQ_LOOP_PREV(head, elm, field)				\
++	(((elm)->field.cqe_prev == (void *)(head))			\
++	    ? ((head)->cqh_last)					\
++	    : (elm->field.cqe_prev))
++
++#endif	/* sys/queue.h */