fix musl compile, patches from AlpineLinux

17 files changed, 936 insertions, 0 deletions

diff --git a/package/nfs-utils/patches/patch-configure_ac b/package/nfs-utils/patches/patch-configure_ac
new file mode 100644
index 000000000..e21eb4210
--- /dev/null
+++ b/package/nfs-utils/patches/patch-configure_ac
@@ -0,0 +1,26 @@
+--- nfs-utils-1.3.0.orig/configure.ac	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/configure.ac	2014-05-17 21:03:27.077197789 +0200
+@@ -247,9 +247,6 @@ AC_CHECK_FUNC([connect], ,
+ AC_CHECK_FUNC([getaddrinfo], ,
+               [AC_MSG_ERROR([Function 'getaddrinfo' not found.])])
+ 
+-AC_CHECK_FUNC([getrpcbynumber], ,
+-              [AC_MSG_ERROR([Function 'getrpcbynumber' not found.])])
+-
+ AC_CHECK_FUNC([getservbyname], ,
+               [AC_MSG_ERROR([Function 'getservbyname' not found.])])
+ 
+@@ -408,12 +405,11 @@ AC_FUNC_STAT
+ AC_FUNC_VPRINTF
+ AC_CHECK_FUNCS([alarm atexit dup2 fdatasync ftruncate getcwd \
+                gethostbyaddr gethostbyname gethostname getmntent \
+-               getnameinfo getrpcbyname getifaddrs \
++               getnameinfo getrpcbyname getrpcbynumber getrpcbynumber_r getifaddrs \
+                gettimeofday hasmntopt inet_ntoa innetgr memset mkdir pathconf \
+                ppoll realpath rmdir select socket strcasecmp strchr strdup \
+                strerror strrchr strtol strtoul sigprocmask])
+ 
+-
+ dnl *************************************************************
+ dnl Check for data sizes
+ dnl *************************************************************
diff --git a/package/nfs-utils/patches/patch-support_export_hostname_c b/package/nfs-utils/patches/patch-support_export_hostname_c
new file mode 100644
index 000000000..56aa13139
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_export_hostname_c
@@ -0,0 +1,65 @@
+--- nfs-utils-1.3.0.orig/support/export/hostname.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/export/hostname.c	2014-05-17 21:47:07.085632108 +0200
+@@ -91,7 +91,7 @@ host_ntop(const struct sockaddr *sap, ch
+  * Returns address info structure, or NULL if an error occurs.  Caller
+  * must free the returned structure with freeaddrinfo(3).
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *
+ host_pton(const char *paddr)
+ {
+@@ -153,7 +153,7 @@ host_pton(const char *paddr)
+  * if no information is available for @hostname.  Caller must free the
+  * returned structure with freeaddrinfo(3).
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *
+ host_addrinfo(const char *hostname)
+ {
+@@ -199,7 +199,7 @@ host_addrinfo(const char *hostname)
+  * the string.
+  */
+ #ifdef HAVE_GETNAMEINFO
+-__attribute_malloc__
++__attribute__((__malloc__))
+ char *
+ host_canonname(const struct sockaddr *sap)
+ {
+@@ -234,7 +234,7 @@ host_canonname(const struct sockaddr *sa
+ 	return strdup(buf);
+ }
+ #else	/* !HAVE_GETNAMEINFO */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ char *
+ host_canonname(const struct sockaddr *sap)
+ {
+@@ -266,7 +266,7 @@ host_canonname(const struct sockaddr *sa
+  *
+  * Caller must free the returned structure with freeaddrinfo(3).
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *
+ host_reliable_addrinfo(const struct sockaddr *sap)
+ {
+@@ -313,7 +313,7 @@ out_free_hostname:
+  * Caller must free the returned structure with freeaddrinfo(3).
+  */
+ #ifdef HAVE_GETNAMEINFO
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *
+ host_numeric_addrinfo(const struct sockaddr *sap)
+ {
+@@ -361,7 +361,7 @@ host_numeric_addrinfo(const struct socka
+ 	return ai;
+ }
+ #else	/* !HAVE_GETNAMEINFO */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *
+ host_numeric_addrinfo(const struct sockaddr *sap)
+ {
diff --git a/package/nfs-utils/patches/patch-support_include_conffile_h b/package/nfs-utils/patches/patch-support_include_conffile_h
new file mode 100644
index 000000000..308a40a4f
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_include_conffile_h
@@ -0,0 +1,20 @@
+--- nfs-utils-1.3.0.orig/support/include/conffile.h	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/include/conffile.h	2014-05-17 21:52:16.997590916 +0200
+@@ -33,7 +33,7 @@
+ #ifndef _CONFFILE_H_
+ #define _CONFFILE_H_
+ 
+-#include <sys/queue.h>
++#include "queue.h"
+ #include <ctype.h>
+ 
+ struct conf_list_node {
+@@ -49,7 +49,7 @@ struct conf_list {
+ extern char    *conf_path;
+ 
+ extern int      conf_begin(void);
+-extern int      conf_decode_base64(u_int8_t *, u_int32_t *, u_char *);
++extern int      conf_decode_base64(uint8_t *, uint32_t *, unsigned char *);
+ extern int      conf_end(int, int);
+ extern void     conf_free_list(struct conf_list *);
+ extern struct sockaddr *conf_get_address(char *, char *);
diff --git a/package/nfs-utils/patches/patch-support_include_exportfs_h b/package/nfs-utils/patches/patch-support_include_exportfs_h
new file mode 100644
index 000000000..c58c0c3ec
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_include_exportfs_h
@@ -0,0 +1,23 @@
+--- nfs-utils-1.3.0.orig/support/include/exportfs.h	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/include/exportfs.h	2014-05-17 21:47:07.085632108 +0200
+@@ -156,15 +156,15 @@ int				secinfo_addflavor(struct flav_inf
+ 
+ char *				host_ntop(const struct sockaddr *sap,
+ 						char *buf, const size_t buflen);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *		host_pton(const char *paddr);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *		host_addrinfo(const char *hostname);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ char *				host_canonname(const struct sockaddr *sap);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *		host_reliable_addrinfo(const struct sockaddr *sap);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ struct addrinfo *		host_numeric_addrinfo(const struct sockaddr *sap);
+ 
+ int				rmtab_read(void);
diff --git a/package/nfs-utils/patches/patch-support_include_sockaddr_h b/package/nfs-utils/patches/patch-support_include_sockaddr_h
new file mode 100644
index 000000000..52b564bd3
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_include_sockaddr_h
@@ -0,0 +1,10 @@
+--- nfs-utils-1.3.0.orig/support/include/sockaddr.h	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/include/sockaddr.h	2014-05-17 21:40:15.148504458 +0200
+@@ -27,6 +27,7 @@
+ #ifdef HAVE_LIBIO_H
+ #include <libio.h>
+ #endif
++#include <stdlib.h>
+ #include <stdbool.h>
+ #include <sys/socket.h>
+ #include <netinet/in.h>
diff --git a/package/nfs-utils/patches/patch-support_nfs_conffile_c b/package/nfs-utils/patches/patch-support_nfs_conffile_c
new file mode 100644
index 000000000..0c59eea59
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_nfs_conffile_c
@@ -0,0 +1,42 @@
+--- nfs-utils-1.3.0.orig/support/nfs/conffile.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/nfs/conffile.c	2014-05-17 21:30:36.886783421 +0200
+@@ -72,10 +72,10 @@ TAILQ_HEAD (conf_trans_head, conf_trans)
+ /*
+  * Radix-64 Encoding.
+  */
+-static const u_int8_t bin2asc[]
++static const uint8_t bin2asc[]
+   = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+ 
+-static const u_int8_t asc2bin[] =
++static const uint8_t asc2bin[] =
+ {
+   255, 255, 255, 255, 255, 255, 255, 255,
+   255, 255, 255, 255, 255, 255, 255, 255,
+@@ -109,10 +109,10 @@ LIST_HEAD (conf_bindings, conf_binding)
+ 
+ static char *conf_addr;
+ 
+-static __inline__ u_int8_t
++static __inline__ uint8_t
+ conf_hash(char *s)
+ {
+-	u_int8_t hash = 0;
++	uint8_t hash = 0;
+ 
+ 	while (*s) {
+ 		hash = ((hash << 1) | (hash >> 7)) ^ tolower (*s);
+@@ -603,10 +603,10 @@ cleanup:
+ 
+ /* Decode a PEM encoded buffer.  */
+ int
+-conf_decode_base64 (u_int8_t *out, u_int32_t *len, u_char *buf)
++conf_decode_base64 (uint8_t *out, uint32_t *len, unsigned char *buf)
+ {
+-	u_int32_t c = 0;
+-	u_int8_t c1, c2, c3, c4;
++	uint32_t c = 0;
++	uint8_t c1, c2, c3, c4;
+ 
+ 	while (*buf) {
+ 		if (*buf > 127 || (c1 = asc2bin[*buf]) == 255)
diff --git a/package/nfs-utils/patches/patch-support_nfs_svc_create_c b/package/nfs-utils/patches/patch-support_nfs_svc_create_c
new file mode 100644
index 000000000..0b2ccbe44
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_nfs_svc_create_c
@@ -0,0 +1,11 @@
+--- nfs-utils-1.3.0.orig/support/nfs/svc_create.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/nfs/svc_create.c	2014-05-17 21:47:07.089632108 +0200
+@@ -113,7 +113,7 @@ svc_create_find_xprt(const struct sockad
+  *
+  * Otherwise NULL is returned if an error occurs.
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct addrinfo *
+ svc_create_bindaddr(struct netconfig *nconf, const uint16_t port)
+ {
diff --git a/package/nfs-utils/patches/patch-support_nfs_svc_socket_c b/package/nfs-utils/patches/patch-support_nfs_svc_socket_c
new file mode 100644
index 000000000..0e2d99b87
--- /dev/null
+++ b/package/nfs-utils/patches/patch-support_nfs_svc_socket_c
@@ -0,0 +1,17 @@
+--- nfs-utils-1.3.0.orig/support/nfs/svc_socket.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/support/nfs/svc_socket.c	2014-05-17 21:03:27.077197789 +0200
+@@ -42,8 +42,14 @@ int getservport(u_long number, const cha
+ 	struct servent servbuf, *servp = NULL;
+ 	int ret;
+ 
++#if HAVE_GETRPCBYNUMBER_R
+ 	ret = getrpcbynumber_r(number, &rpcbuf, rpcdata, sizeof rpcdata,
+ 				&rpcp);
++#else
++	rpcp = getrpcbynumber(number);
++	ret = 0;
++#endif
++
+ 	if (ret == 0 && rpcp != NULL) {
+ 		/* First try name.  */
+ 		ret = getservbyname_r(rpcp->r_name, proto, &servbuf, servdata,
diff --git a/package/nfs-utils/patches/patch-utils_exportfs_exportfs_c b/package/nfs-utils/patches/patch-utils_exportfs_exportfs_c
new file mode 100644
index 000000000..b9cdac29f
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_exportfs_exportfs_c
@@ -0,0 +1,13 @@
+--- nfs-utils-1.3.0.orig/utils/exportfs/exportfs.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/exportfs/exportfs.c	2014-05-17 21:20:01.548725048 +0200
+@@ -12,6 +12,10 @@
+ #include <config.h>
+ #endif
+ 
++#ifndef _GNU_SOURCE
++#define _GNU_SOURCE
++#endif
++
+ #include <sys/types.h>
+ #include <sys/stat.h>
+ #include <sys/vfs.h>
diff --git a/package/nfs-utils/patches/patch-utils_mountd_cache_c b/package/nfs-utils/patches/patch-utils_mountd_cache_c
new file mode 100644
index 000000000..440f46d82
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_mountd_cache_c
@@ -0,0 +1,22 @@
+--- nfs-utils-1.3.0.orig/utils/mountd/cache.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/mountd/cache.c	2014-05-17 21:57:07.653571824 +0200
+@@ -11,6 +11,10 @@
+ #include <config.h>
+ #endif
+ 
++#ifndef _GNU_SOURCE
++#define _GNU_SOURCE
++#endif
++
+ #include <sys/types.h>
+ #include <sys/select.h>
+ #include <sys/stat.h>
+@@ -1339,7 +1343,7 @@ static int cache_export_ent(char *domain
+ 		 */
+ 		struct stat stb;
+ 		size_t l = strlen(exp->e_path);
+-		__dev_t dev;
++		dev_t dev;
+ 
+ 		if (strlen(path) <= l || path[l] != '/' ||
+ 		    strncmp(exp->e_path, path, l) != 0)
diff --git a/package/nfs-utils/patches/patch-utils_mountd_v4root_c b/package/nfs-utils/patches/patch-utils_mountd_v4root_c
new file mode 100644
index 000000000..420744173
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_mountd_v4root_c
@@ -0,0 +1,11 @@
+--- nfs-utils-1.3.0.orig/utils/mountd/v4root.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/mountd/v4root.c	2014-05-17 21:59:01.129569213 +0200
+@@ -13,7 +13,7 @@
+ 
+ #include <sys/types.h>
+ #include <sys/stat.h>
+-#include <sys/queue.h>
++#include "queue.h"
+ #include <stdio.h>
+ #include <stdlib.h>
+ #include <ctype.h>
diff --git a/package/nfs-utils/patches/patch-utils_nfsstat_nfsstat_c b/package/nfs-utils/patches/patch-utils_nfsstat_nfsstat_c
new file mode 100644
index 000000000..333d35322
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_nfsstat_nfsstat_c
@@ -0,0 +1,11 @@
+--- nfs-utils-1.3.0.orig/utils/nfsstat/nfsstat.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/nfsstat/nfsstat.c	2014-05-17 21:57:15.697571551 +0200
+@@ -336,7 +336,7 @@ main(int argc, char **argv)
+ 
+ 	struct sigaction act = {
+ 		.sa_handler = unpause,
+-		.sa_flags = SA_ONESHOT,
++		.sa_flags = SA_RESETHAND,
+ 	};
+ 
+ 	if ((progname = strrchr(argv[0], '/')))
diff --git a/package/nfs-utils/patches/patch-utils_statd_hostname_c b/package/nfs-utils/patches/patch-utils_statd_hostname_c
new file mode 100644
index 000000000..c0863e42b
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_statd_hostname_c
@@ -0,0 +1,29 @@
+--- nfs-utils-1.3.0.orig/utils/statd/hostname.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/statd/hostname.c	2014-05-17 21:47:07.089632108 +0200
+@@ -105,7 +105,7 @@ statd_present_address(const struct socka
+  * Look up the hostname; report exceptional errors.  Caller must
+  * call freeaddrinfo(3) if a valid addrinfo is returned.
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct addrinfo *
+ get_addrinfo(const char *hostname, const struct addrinfo *hint)
+ {
+@@ -184,7 +184,7 @@ get_nameinfo(const struct sockaddr *sap,
+  * We won't monitor peers that don't have a reverse map.  The canonical
+  * name gives us a key for our monitor list.
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ char *
+ statd_canonical_name(const char *hostname)
+ {
+@@ -234,7 +234,7 @@ statd_canonical_name(const char *hostnam
+  * NULL if some error occurs.  Caller must free the returned
+  * list with freeaddrinfo(3).
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct addrinfo *
+ statd_canonical_list(const char *hostname)
+ {
diff --git a/package/nfs-utils/patches/patch-utils_statd_rmtcall_c b/package/nfs-utils/patches/patch-utils_statd_rmtcall_c
new file mode 100644
index 000000000..eab15c5a7
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_statd_rmtcall_c
@@ -0,0 +1,13 @@
+--- nfs-utils-1.3.0.orig/utils/statd/rmtcall.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/statd/rmtcall.c	2014-05-17 22:00:46.441569123 +0200
+@@ -90,8 +90,10 @@ statd_get_socket(void)
+ 					__func__);
+ 			break;
+ 		}
++#if 0
+ 		se = getservbyport(sin.sin_port, "udp");
+ 		if (se == NULL)
++#endif
+ 			break;
+ 		/* rather not use that port, try again */
+ 
diff --git a/package/nfs-utils/patches/patch-utils_statd_sm-notify_c b/package/nfs-utils/patches/patch-utils_statd_sm-notify_c
new file mode 100644
index 000000000..76bef0d37
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_statd_sm-notify_c
@@ -0,0 +1,38 @@
+--- nfs-utils-1.3.0.orig/utils/statd/sm-notify.c	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/statd/sm-notify.c	2014-05-17 21:47:07.089632108 +0200
+@@ -74,7 +74,7 @@ static int		record_pid(void);
+ 
+ static struct nsm_host *	hosts = NULL;
+ 
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct addrinfo *
+ smn_lookup(const char *name)
+ {
+@@ -149,7 +149,7 @@ smn_get_hostname(const struct sockaddr *
+  * if the canonical name doesn't exist or cannot be determined.
+  * The caller must free the result with free(3).
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static char *
+ smn_verify_my_name(const char *name)
+ {
+@@ -189,7 +189,7 @@ smn_verify_my_name(const char *name)
+ 	return retval;
+ }
+ 
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct nsm_host *
+ smn_alloc_host(const char *hostname, const char *mon_name,
+ 		const char *my_name, const time_t timestamp)
+@@ -343,7 +343,7 @@ static int smn_socket(void)
+  * If admin specified a source address or srcport, then convert those
+  * to a sockaddr and return it.   Otherwise, return an ANYADDR address.
+  */
+-__attribute_malloc__
++__attribute__((__malloc__))
+ static struct addrinfo *
+ smn_bind_address(const char *srcaddr, const char *srcport)
+ {
diff --git a/package/nfs-utils/patches/patch-utils_statd_statd_h b/package/nfs-utils/patches/patch-utils_statd_statd_h
new file mode 100644
index 000000000..73625326a
--- /dev/null
+++ b/package/nfs-utils/patches/patch-utils_statd_statd_h
@@ -0,0 +1,11 @@
+--- nfs-utils-1.3.0.orig/utils/statd/statd.h	2014-03-25 16:12:07.000000000 +0100
++++ nfs-utils-1.3.0/utils/statd/statd.h	2014-05-17 21:47:07.089632108 +0200
+@@ -25,7 +25,7 @@
+ extern _Bool	statd_matchhostname(const char *hostname1, const char *hostname2);
+ extern _Bool	statd_present_address(const struct sockaddr *sap, char *buf,
+ 					const size_t buflen);
+-__attribute_malloc__
++__attribute__((__malloc__))
+ extern char *	statd_canonical_name(const char *hostname);
+ 
+ extern void	my_svc_run(void);
diff --git a/package/nfs-utils/src/support/include/queue.h b/package/nfs-utils/src/support/include/queue.h
new file mode 100644
index 000000000..daf4553d3
--- /dev/null
+++ b/package/nfs-utils/src/support/include/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 */