DragonFly fixes from Rumko in PR 42345.

7 files changed, 737 insertions, 49 deletions

diff --git a/sysutils/pftop/distinfo b/sysutils/pftop/distinfo
index f766e56c7f4..72f6f39bbb7 100644
--- a/sysutils/pftop/distinfo
+++ b/sysutils/pftop/distinfo
@@ -1,14 +1,16 @@
-$NetBSD: distinfo,v 1.6 2008/06/15 14:09:03 peter Exp $
+$NetBSD: distinfo,v 1.7 2010/09/18 20:48:23 wiz Exp $
 
 SHA1 (pftop-0.7.tar.gz) = 651afa532cfc8cf59c3598704deb9bf3788ac9e9
 RMD160 (pftop-0.7.tar.gz) = 0e0c09e5feeb07deba8b540233dcb946ba0b4508
 Size (pftop-0.7.tar.gz) = 59765 bytes
-SHA1 (patch-aa) = ffae9a5ab95b793fa8b677a58a2b69644da37de2
+SHA1 (patch-aa) = ff5c522223472188933a6ccbe9725190dc8ec1b5
 SHA1 (patch-ab) = 9e54f7d6f6e6c4c54f924b86080359efea9ba369
 SHA1 (patch-ac) = 4d5ffc354258fb39c0a4655457b0c78e4f5709cb
-SHA1 (patch-ad) = 658c26cef386c31fbed99a138be0a94bc9ca1278
+SHA1 (patch-ad) = ca20a6cd1dd61aab5b41e6ee22b08dee7741a542
 SHA1 (patch-ae) = 54619b846899a7c4f260191a772e41e1c07c178c
 SHA1 (patch-af) = 59b907b20fa215b3f0a1e690c9c71d2f7077e322
-SHA1 (patch-ag) = ea63b7e7a0ec078a0369b6a416a790538fa0a87d
-SHA1 (patch-ah) = b634d591b0fefdbf272970253eb2789a6d1cd6c2
+SHA1 (patch-ag) = 7b3b0a9d7ac73df9c258ae27a8c75e6556574ee8
+SHA1 (patch-ah) = 7b2acf95c6f8ce5f0c621ed6c4fcee67a403ab88
 SHA1 (patch-ai) = 629c1668eab0d819e590fb62b7afa6c85709fd15
+SHA1 (patch-aj) = 287b09d61d5e761c4f6842c37ed0b668b84beae9
+SHA1 (patch-ak) = 78622d902016fa559ae3090d9c8407337d7cd0ed
diff --git a/sysutils/pftop/patches/patch-aa b/sysutils/pftop/patches/patch-aa
index b4499afbf43..5b8e0448dd9 100644
--- a/sysutils/pftop/patches/patch-aa
+++ b/sysutils/pftop/patches/patch-aa
@@ -1,20 +1,22 @@
-$NetBSD: patch-aa,v 1.2 2008/06/15 14:09:03 peter Exp $
+$NetBSD: patch-aa,v 1.3 2010/09/18 20:48:23 wiz Exp $
 
---- Makefile.old	2007-11-07 07:34:18.000000000 +0100
-+++ Makefile	2008-06-15 00:43:41.000000000 +0200
+--- Makefile.orig	2007-11-07 07:34:18 +0100
++++ Makefile	2009-11-17 00:59:26 +0100
 @@ -6,17 +6,21 @@
  
  PROG=	pftop
  SRCS=	pftop.c cache.c engine.c
 -SRCS+=	sf-gencode.c sf-grammer.y sf-scanner.l pcap-nametoaddr.c
+-SRCS+=  bpf_optimize.c bpf_filter.c bpf_dump.c bpf_image.c
 +SRCS+=	sf-gencode.c sf-grammer.c sf-scanner.l pcap-nametoaddr.c
- SRCS+=  bpf_optimize.c bpf_filter.c bpf_dump.c bpf_image.c
++SRCS+=  bpf_optimize.c
  MAN=	pftop.8
  
 +CLEANFILES+= sf-grammer.c
 +
  CFLAGS+= -Wall -DOS_LEVEL=${OSLEVEL}
- LDADD+= -lcurses
+-LDADD+= -lcurses
++LDADD+= -lcurses -lpcap
  
 +NOGCCERROR=yes
 +
diff --git a/sysutils/pftop/patches/patch-ad b/sysutils/pftop/patches/patch-ad
index 103bac0527c..19cafd7e2ce 100644
--- a/sysutils/pftop/patches/patch-ad
+++ b/sysutils/pftop/patches/patch-ad
@@ -1,8 +1,16 @@
-$NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
+$NetBSD: patch-ad,v 1.2 2010/09/18 20:48:23 wiz Exp $
 
---- engine.c.old	2008-06-14 17:38:55.000000000 +0200
-+++ engine.c	2008-06-15 12:41:47.000000000 +0200
-@@ -22,7 +22,10 @@
+--- engine.c.orig	2007-11-07 07:35:44 +0100
++++ engine.c	2009-11-17 00:31:46 +0100
+@@ -18,11 +18,18 @@
+ 
+ 
+ #include <sys/types.h>
++#ifdef __DragonFly__
++#include "queue.h"
++#else
+ #include <sys/queue.h>
++#endif
  
  #include <ctype.h>
  #include <curses.h>
@@ -13,7 +21,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  #include <stdlib.h>
  #include <string.h>
  #include <unistd.h>
-@@ -33,6 +36,10 @@
+@@ -33,6 +40,10 @@
  #define MIN(a,b) (((a)<(b))?(a):(b))
  #endif
  
@@ -24,7 +32,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  /* circular linked list of views */
  CIRCLEQ_HEAD(view_list, view_ent) view_head =
  				  CIRCLEQ_HEAD_INITIALIZER(view_head);
-@@ -55,9 +62,6 @@
+@@ -55,9 +66,6 @@
  
  volatile sig_atomic_t gotsig_close = 0;
  volatile sig_atomic_t gotsig_resize = 0;
@@ -34,7 +42,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  
  SCREEN *screen;
  
-@@ -105,7 +109,6 @@
+@@ -105,7 +113,6 @@
  
  int
  tbprintf(char *format, ...)
@@ -42,7 +50,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  {
  	int len;
  	va_list arg;
-@@ -482,7 +485,6 @@
+@@ -482,7 +489,6 @@
  	v = ve->view;
  	
  	if ((curr_view != NULL) && (curr_mgr != v->mgr)) {
@@ -50,7 +58,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  		if (v->mgr != NULL && v->mgr->select_fn != NULL)
  			v->mgr->select_fn();
  	}
-@@ -491,7 +493,6 @@
+@@ -491,7 +497,6 @@
  	curr_view = v;
  	curr_mgr = v->mgr;
  	field_setup();
@@ -58,7 +66,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  }
  
  void
-@@ -905,12 +906,6 @@
+@@ -905,12 +910,6 @@
  }
  
  void
@@ -71,7 +79,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  setup_term(int dmax)
  {
  	max_disp = dmax;
-@@ -941,8 +936,9 @@
+@@ -941,8 +940,9 @@
  		keypad(stdscr, TRUE);
  		intrflush(stdscr, FALSE);
  
@@ -82,7 +90,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  	}
  
  	if (dmax == 0)
-@@ -970,7 +966,6 @@
+@@ -970,7 +970,6 @@
  	}
  	curr_message = NULL;
  	curr_cmd = cmd;
@@ -90,7 +98,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  	return prev;
  }
  
-@@ -987,7 +982,6 @@
+@@ -987,7 +986,6 @@
  
  int
  msgprintf(char *format, ...)
@@ -98,7 +106,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  {
  	static char buf[1024];
  	int len;
-@@ -1085,28 +1079,21 @@
+@@ -1085,28 +1083,21 @@
  	if (curr_message != NULL) {
  		if (ch > 0) {
  			curr_message = NULL;
@@ -127,7 +135,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  		break;
  	case 'v':
  		/* FALLTHROUGH */
-@@ -1124,49 +1111,40 @@
+@@ -1124,49 +1115,40 @@
  		/* FALLTHROUGH */
  	case CTRL_N:
  		dispstart++;
@@ -178,7 +186,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  		set_view_hotkey(ch);
  }
  
-@@ -1177,43 +1155,15 @@
+@@ -1177,43 +1159,15 @@
  	signal(SIGINT, sig_close);
  	signal(SIGQUIT, sig_close);
  	signal(SIGWINCH, sig_resize);
@@ -223,7 +231,7 @@ $NetBSD: patch-ad,v 1.1 2008/06/15 14:09:03 peter Exp $
  		if (gotsig_close)
  			break;
  		if (gotsig_resize) {
-@@ -1221,13 +1171,31 @@
+@@ -1221,13 +1175,31 @@
  				endwin();
  			setup_term(max_disp);
  			gotsig_resize = 0;
diff --git a/sysutils/pftop/patches/patch-ag b/sysutils/pftop/patches/patch-ag
index 0b9a6d6f4ad..978d789dded 100644
--- a/sysutils/pftop/patches/patch-ag
+++ b/sysutils/pftop/patches/patch-ag
@@ -1,8 +1,8 @@
-$NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
+$NetBSD: patch-ag,v 1.2 2010/09/18 20:48:23 wiz Exp $
 
---- pftop.c.old	2008-06-14 17:41:08.000000000 +0200
-+++ pftop.c	2008-06-15 12:42:06.000000000 +0200
-@@ -40,7 +40,11 @@
+--- pftop.c.orig	2007-11-07 07:36:46 +0100
++++ pftop.c	2009-11-16 23:37:03 +0100
+@@ -40,21 +40,41 @@
  #include <netinet/in.h>
  #define TCPSTATES
  #include <netinet/tcp_fsm.h>
@@ -14,7 +14,29 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  #include <arpa/inet.h>
  
  #ifdef HAVE_ALTQ
-@@ -55,6 +59,7 @@
++#ifdef __DragonFly__
++#include <net/altq/altq.h>
++#include <net/altq/altq_cbq.h>
++#include <net/altq/altq_priq.h>
++#include <net/altq/altq_hfsc.h>
++#else
+ #include <altq/altq.h>
+ #include <altq/altq_cbq.h>
+ #include <altq/altq_priq.h>
+ #include <altq/altq_hfsc.h>
+ #endif
+ 
++#ifdef ALTQT_FAIRQ
++#ifdef __DragonFly__
++#include <net/altq/altq_fairq.h>
++#else
++#include <altq/altq_fairq.h>
++#endif
++#endif
++#endif
++
+ #include <ctype.h>
+ #include <curses.h>
  #include <err.h>
  #include <errno.h>
  #include <fcntl.h>
@@ -22,7 +44,17 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  #include <netdb.h>
  #include <signal.h>
  #include <stdio.h>
-@@ -736,7 +741,7 @@
+@@ -371,6 +391,9 @@
+ 	class_stats_t		cbq_stats;
+ 	struct priq_classstats	priq_stats;
+ 	struct hfsc_classstats	hfsc_stats;
++#ifdef ALTQT_FAIRQ
++	struct fairq_classstats fairq_stats;
++#endif
+ };
+ 
+ struct queue_stats {
+@@ -736,7 +759,7 @@
  	} else {
  		num_states = 0;
  		for (n = 0; n<num_states_all; n++)
@@ -31,7 +63,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  			    sizeof(pf_state_t), sizeof(pf_state_t)) > 0)
  				state_ord[num_states++] = n;
  	}
-@@ -828,7 +833,7 @@
+@@ -828,7 +851,7 @@
  		tbprintf(" PAUSED");
  
  	if (rawmode)
@@ -40,7 +72,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  	else
  		mvprintw(0, 0, "%s", tmp_buf);
  
-@@ -843,7 +848,10 @@
+@@ -843,7 +866,10 @@
  		len = columns - strlen(tmp_buf);
  		if (len < 0)
  			len = 0;
@@ -52,7 +84,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  	}
  
  	tb_end();
-@@ -1244,7 +1252,6 @@
+@@ -1244,7 +1270,6 @@
  		FLD_ANCHOR->max_width = mx;
  		FLD_ANCHOR->norm_width = nx;
  		field_setup();
@@ -60,7 +92,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  	}
  }
  #endif
-@@ -1279,7 +1286,6 @@
+@@ -1279,7 +1304,6 @@
  			FLD_LABEL->norm_width = nw;
  			FLD_LABEL->max_width = mw;
  			field_setup();
@@ -68,7 +100,45 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  		}
  	}
  #endif
-@@ -2041,11 +2047,9 @@
+@@ -1924,6 +1948,10 @@
+ 	    node->altq.scheduler == ALTQT_HFSC
+ 		)
+ 		print_fld_bw(FLD_BANDW, (double)node->altq.bandwidth);
++#ifdef ALTQT_FAIRQ
++	if (node->altq.scheduler == ALTQT_FAIRQ)
++		print_fld_bw(FLD_BANDW, (double)node->altq.bandwidth);
++#endif
+ 	
+ 	if (node->altq.priority != DEFAULT_PRIORITY)
+ 		print_fld_uint(FLD_PRIO,
+@@ -1992,6 +2020,26 @@
+ 					node->qstats_last.data.hfsc_stats.xmit_cnt.bytes, interval);
+ 		}
+ 		break;
++#ifdef ALTQT_FAIRQ
++	case ALTQT_FAIRQ:
++		print_fld_str(FLD_SCHED, "fairq");
++		print_fld_size(FLD_PKTS,
++				node->qstats.data.fairq_stats.xmit_cnt.packets);
++		print_fld_size(FLD_BYTES,
++				node->qstats.data.fairq_stats.xmit_cnt.bytes);
++		print_fld_size(FLD_DROPP,
++				node->qstats.data.fairq_stats.drop_cnt.packets);
++		print_fld_size(FLD_DROPB,
++				node->qstats.data.fairq_stats.drop_cnt.bytes);
++		print_fld_size(FLD_QLEN, node->qstats.data.fairq_stats.qlength);
++		if (interval > 0) {
++			pps = calc_pps(node->qstats.data.fairq_stats.xmit_cnt.packets,
++					node->qstats_last.data.fairq_stats.xmit_cnt.packets, interval);
++			bps = calc_rate(node->qstats.data.fairq_stats.xmit_cnt.bytes,
++					node->qstats_last.data.fairq_stats.xmit_cnt.bytes, interval);
++		}
++		break;
++#endif
+ 	}
+ 
+ 	/* if (node->altq.scheduler != ALTQT_HFSC && interval > 0) { */
+@@ -2041,11 +2089,9 @@
  	if (cachestates) {
  		show_field(FLD_SI);
  		show_field(FLD_SP);
@@ -80,7 +150,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  	}
  	field_setup();
  }
-@@ -2105,8 +2109,10 @@
+@@ -2105,8 +2151,10 @@
  	line++;
  	mvprintw(line++, 6, "press any key to continue ...");
  
@@ -93,7 +163,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  }
  
  
-@@ -2142,7 +2148,6 @@
+@@ -2142,7 +2190,6 @@
  	del = atoi(cmdbuf);
  	if (del > 0) {
  		delay = del;
@@ -101,7 +171,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  	}
  }
  
-@@ -2175,7 +2180,6 @@
+@@ -2175,7 +2222,6 @@
  		/* FALLTHROUGH */
  	case 'h':
  		show_help();
@@ -109,7 +179,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
  		break;
  	case 'n':
  		command_set(&cm_count, NULL);
-@@ -2349,8 +2353,6 @@
+@@ -2349,8 +2395,6 @@
  	if (rawmode && countmax == 0)
  		countmax = 1;
  
diff --git a/sysutils/pftop/patches/patch-ah b/sysutils/pftop/patches/patch-ah
index edfa2403609..6ace5c3bdd9 100644
--- a/sysutils/pftop/patches/patch-ah
+++ b/sysutils/pftop/patches/patch-ah
@@ -1,13 +1,14 @@
-$NetBSD: patch-ah,v 1.1 2008/06/15 14:09:04 peter Exp $
+$NetBSD: patch-ah,v 1.2 2010/09/18 20:48:23 wiz Exp $
 
---- sf-gencode.c.old	2008-06-14 17:44:52.000000000 +0200
-+++ sf-gencode.c	2008-06-15 01:19:43.000000000 +0200
-@@ -32,8 +32,11 @@
+--- sf-gencode.c.orig	2007-11-07 07:34:18 +0100
++++ sf-gencode.c	2010-09-16 01:35:22 +0200
+@@ -32,8 +32,12 @@
  #include <netinet/in.h>
  #include <netinet/if_ether.h>
  
 -#include <net/if_pflog.h>
 +#ifdef __DragonFly__
++#include <sys/param.h>
 +#include <net/pf/pfvar.h>
 +#else
  #include <net/pfvar.h>
@@ -15,7 +16,7 @@ $NetBSD: patch-ah,v 1.1 2008/06/15 14:09:04 peter Exp $
  
  #include <netdb.h>
  #include <stdlib.h>
-@@ -44,7 +47,7 @@
+@@ -44,7 +48,7 @@
  
  #define INET6
  
@@ -24,7 +25,30 @@ $NetBSD: patch-ah,v 1.1 2008/06/15 14:09:04 peter Exp $
  #include <pcap-namedb.h>
  #include "sf-gencode.h"
  
-@@ -733,13 +736,17 @@
+@@ -60,7 +64,11 @@
+ static char sf_errbuf[PFTOP_ERRBUF_SIZE];
+ 
+ /* VARARGS */
++#ifdef __DragonFly__
++void
++#else
+ __dead void
++#endif
+ sf_error(const char *fmt, ...)
+ {
+ 	va_list ap;
+@@ -482,8 +490,10 @@
+ 	const static int gwy_off = offsetof(pf_state_t, gwy.addr.v4);
+ 	const static int ext_off = offsetof(pf_state_t, ext.addr.v4);
+ 
++#if !defined(__DragonFly__)
+ 	addr = ntohl(addr);
+ 	mask = ntohl(mask);
++#endif
+ 
+ 	switch (dir) {
+ 
+@@ -733,13 +743,17 @@
  		b1 = gen_proto(IPPROTO_ESP);
  		break;
  
@@ -42,7 +66,17 @@ $NetBSD: patch-ah,v 1.1 2008/06/15 14:09:04 peter Exp $
  
  	default:
  		sf_error("Unknown protocol abbreviation");
-@@ -1560,7 +1567,7 @@
+@@ -756,7 +770,9 @@
+ 	const static int gwy_off = offsetof(pf_state_t, gwy.port);
+ 	const static int ext_off = offsetof(pf_state_t, ext.port);
+ 
++#if !defined(__DragonFly__)
+ 	port = ntohs(port);
++#endif
+ 
+ 	switch (dir) {
+ 
+@@ -1560,7 +1576,7 @@
  		/* NOTREACHED */
  	}
  
diff --git a/sysutils/pftop/patches/patch-aj b/sysutils/pftop/patches/patch-aj
new file mode 100644
index 00000000000..a2c6bbd9842
--- /dev/null
+++ b/sysutils/pftop/patches/patch-aj
@@ -0,0 +1,38 @@
+$NetBSD: patch-aj,v 1.1 2010/09/18 20:48:23 wiz Exp $
+
+--- sf-gencode.h.orig	2009-11-16 23:47:42 +0100
++++ sf-gencode.h	2009-11-16 23:47:54 +0100
+@@ -169,8 +169,13 @@
+ struct arth  *gen_loadexpire(void);
+ 
+ void bpf_optimize(struct block **);
++#ifdef __DragonFly__
++void bpf_error(const char *, ...)
++    __attribute__((volatile, __format__ (printf, 1, 2)));
++#else
+ __dead void bpf_error(const char *, ...)
+     __attribute__((volatile, __format__ (printf, 1, 2)));
++#endif
+ 
+ void finish_parse(struct block *);
+ char *sdup(const char *);
+@@ -184,11 +189,19 @@
+ #define JT(b)  ((b)->et.succ)
+ #define JF(b)  ((b)->ef.succ)
+ 
++#ifdef __DragonFly__
++void sf_error(const char *fmt, ...);
++#else
+ __dead void sf_error(const char *fmt, ...);
++#endif
+ const char *sf_get_error(void);
+ int sf_compile(struct bpf_program *, char *, int, bpf_u_int32);
+ void sf_freecode(struct bpf_program *);
++#ifdef __DragonFly__
++void bpf_dump(const struct bpf_program *, int);
++#else
+ void bpf_dump(struct bpf_program *, int);
++#endif
+ 
+ extern int no_optimize;
+ 
diff --git a/sysutils/pftop/patches/patch-ak b/sysutils/pftop/patches/patch-ak
new file mode 100644
index 00000000000..7e037712141
--- /dev/null
+++ b/sysutils/pftop/patches/patch-ak
@@ -0,0 +1,534 @@
+$NetBSD: patch-ak,v 1.1 2010/09/18 20:48:24 wiz Exp $
+
+Taken from FreeBSD ports.
+
+--- /dev/null	2009-11-17 00:30:11 +0100
++++ queue.h	2009-11-17 00:31:32 +0100
+@@ -0,0 +1,527 @@
++/*	$OpenBSD: queue.h,v 1.32 2007/04/30 18:42:34 pedro Exp $	*/
++/*	NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp 	*/
++
++/*
++ * 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	_QUEUE_H_
++#define	_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 before or 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.
++ */
++
++#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
++#define _Q_INVALIDATE(a) (a) = ((void *)-1)
++#else
++#define _Q_INVALIDATE(a)
++#endif
++
++/*
++ * 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 access methods.
++ */
++#define	SLIST_FIRST(head)	((head)->slh_first)
++#define	SLIST_END(head)		NULL
++#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
++#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
++
++#define	SLIST_FOREACH(var, head, field)					\
++	for((var) = SLIST_FIRST(head);					\
++	    (var) != SLIST_END(head);					\
++	    (var) = SLIST_NEXT(var, field))
++
++#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
++	for ((varp) = &SLIST_FIRST((head));				\
++	    ((var) = *(varp)) != SLIST_END(head);			\
++	    (varp) = &SLIST_NEXT((var), field))
++
++/*
++ * Singly-linked List functions.
++ */
++#define	SLIST_INIT(head) {						\
++	SLIST_FIRST(head) = SLIST_END(head);				\
++}
++
++#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
++	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
++	(slistelm)->field.sle_next = (elm);				\
++} while (0)
++
++#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
++	(elm)->field.sle_next = (head)->slh_first;			\
++	(head)->slh_first = (elm);					\
++} while (0)
++
++#define	SLIST_REMOVE_NEXT(head, elm, field) do {			\
++	(elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;	\
++} while (0)
++
++#define	SLIST_REMOVE_HEAD(head, field) do {				\
++	(head)->slh_first = (head)->slh_first->field.sle_next;		\
++} while (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;		\
++		_Q_INVALIDATE((elm)->field.sle_next);			\
++	}								\
++} while (0)
++
++/*
++ * 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 access methods
++ */
++#define	LIST_FIRST(head)		((head)->lh_first)
++#define	LIST_END(head)			NULL
++#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
++#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
++
++#define LIST_FOREACH(var, head, field)					\
++	for((var) = LIST_FIRST(head);					\
++	    (var)!= LIST_END(head);					\
++	    (var) = LIST_NEXT(var, field))
++
++/*
++ * List functions.
++ */
++#define	LIST_INIT(head) do {						\
++	LIST_FIRST(head) = LIST_END(head);				\
++} while (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 (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 (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 (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;			\
++	_Q_INVALIDATE((elm)->field.le_prev);				\
++	_Q_INVALIDATE((elm)->field.le_next);				\
++} while (0)
++
++#define LIST_REPLACE(elm, elm2, field) do {				\
++	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
++		(elm2)->field.le_next->field.le_prev =			\
++		    &(elm2)->field.le_next;				\
++	(elm2)->field.le_prev = (elm)->field.le_prev;			\
++	*(elm2)->field.le_prev = (elm2);				\
++	_Q_INVALIDATE((elm)->field.le_prev);				\
++	_Q_INVALIDATE((elm)->field.le_next);				\
++} while (0)
++
++/*
++ * 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 access methods.
++ */
++#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
++#define	SIMPLEQ_END(head)	    NULL
++#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
++#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
++
++#define SIMPLEQ_FOREACH(var, head, field)				\
++	for((var) = SIMPLEQ_FIRST(head);				\
++	    (var) != SIMPLEQ_END(head);					\
++	    (var) = SIMPLEQ_NEXT(var, field))
++
++/*
++ * Simple queue functions.
++ */
++#define	SIMPLEQ_INIT(head) do {						\
++	(head)->sqh_first = NULL;					\
++	(head)->sqh_last = &(head)->sqh_first;				\
++} while (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 (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 (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 (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 (0)
++
++/*
++ * Tail queue definitions.
++ */
++#define TAILQ_HEAD(name, type)						\
++struct name {								\
++	struct type *tqh_first;	/* first element */			\
++	struct type **tqh_last;	/* addr of last next element */		\
++}
++
++#define TAILQ_HEAD_INITIALIZER(head)					\
++	{ NULL, &(head).tqh_first }
++
++#define TAILQ_ENTRY(type)						\
++struct {								\
++	struct type *tqe_next;	/* next element */			\
++	struct type **tqe_prev;	/* address of previous next element */	\
++}
++
++/* 
++ * tail queue access methods 
++ */
++#define	TAILQ_FIRST(head)		((head)->tqh_first)
++#define	TAILQ_END(head)			NULL
++#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
++#define TAILQ_LAST(head, headname)					\
++	(*(((struct headname *)((head)->tqh_last))->tqh_last))
++/* XXX */
++#define TAILQ_PREV(elm, headname, field)				\
++	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
++#define	TAILQ_EMPTY(head)						\
++	(TAILQ_FIRST(head) == TAILQ_END(head))
++
++#define TAILQ_FOREACH(var, head, field)					\
++	for((var) = TAILQ_FIRST(head);					\
++	    (var) != TAILQ_END(head);					\
++	    (var) = TAILQ_NEXT(var, field))
++
++#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
++	for((var) = TAILQ_LAST(head, headname);				\
++	    (var) != TAILQ_END(head);					\
++	    (var) = TAILQ_PREV(var, headname, field))
++
++/*
++ * Tail queue functions.
++ */
++#define	TAILQ_INIT(head) do {						\
++	(head)->tqh_first = NULL;					\
++	(head)->tqh_last = &(head)->tqh_first;				\
++} while (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 (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 (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 (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 (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;			\
++	_Q_INVALIDATE((elm)->field.tqe_prev);				\
++	_Q_INVALIDATE((elm)->field.tqe_next);				\
++} while (0)
++
++#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
++	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
++		(elm2)->field.tqe_next->field.tqe_prev =		\
++		    &(elm2)->field.tqe_next;				\
++	else								\
++		(head)->tqh_last = &(elm2)->field.tqe_next;		\
++	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
++	*(elm2)->field.tqe_prev = (elm2);				\
++	_Q_INVALIDATE((elm)->field.tqe_prev);				\
++	_Q_INVALIDATE((elm)->field.tqe_next);				\
++} while (0)
++
++/*
++ * 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)					\
++	{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
++
++#define CIRCLEQ_ENTRY(type)						\
++struct {								\
++	struct type *cqe_next;		/* next element */		\
++	struct type *cqe_prev;		/* previous element */		\
++}
++
++/*
++ * Circular queue access methods 
++ */
++#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
++#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
++#define	CIRCLEQ_END(head)		((void *)(head))
++#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
++#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
++#define	CIRCLEQ_EMPTY(head)						\
++	(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
++
++#define CIRCLEQ_FOREACH(var, head, field)				\
++	for((var) = CIRCLEQ_FIRST(head);				\
++	    (var) != CIRCLEQ_END(head);					\
++	    (var) = CIRCLEQ_NEXT(var, field))
++
++#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
++	for((var) = CIRCLEQ_LAST(head);					\
++	    (var) != CIRCLEQ_END(head);					\
++	    (var) = CIRCLEQ_PREV(var, field))
++
++/*
++ * Circular queue functions.
++ */
++#define	CIRCLEQ_INIT(head) do {						\
++	(head)->cqh_first = CIRCLEQ_END(head);				\
++	(head)->cqh_last = CIRCLEQ_END(head);				\
++} while (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 == CIRCLEQ_END(head))		\
++		(head)->cqh_last = (elm);				\
++	else								\
++		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
++	(listelm)->field.cqe_next = (elm);				\
++} while (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 == CIRCLEQ_END(head))		\
++		(head)->cqh_first = (elm);				\
++	else								\
++		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
++	(listelm)->field.cqe_prev = (elm);				\
++} while (0)
++
++#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
++	(elm)->field.cqe_next = (head)->cqh_first;			\
++	(elm)->field.cqe_prev = CIRCLEQ_END(head);			\
++	if ((head)->cqh_last == CIRCLEQ_END(head))			\
++		(head)->cqh_last = (elm);				\
++	else								\
++		(head)->cqh_first->field.cqe_prev = (elm);		\
++	(head)->cqh_first = (elm);					\
++} while (0)
++
++#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
++	(elm)->field.cqe_next = CIRCLEQ_END(head);			\
++	(elm)->field.cqe_prev = (head)->cqh_last;			\
++	if ((head)->cqh_first == CIRCLEQ_END(head))			\
++		(head)->cqh_first = (elm);				\
++	else								\
++		(head)->cqh_last->field.cqe_next = (elm);		\
++	(head)->cqh_last = (elm);					\
++} while (0)
++
++#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
++	if ((elm)->field.cqe_next == CIRCLEQ_END(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 == CIRCLEQ_END(head))			\
++		(head)->cqh_first = (elm)->field.cqe_next;		\
++	else								\
++		(elm)->field.cqe_prev->field.cqe_next =			\
++		    (elm)->field.cqe_next;				\
++	_Q_INVALIDATE((elm)->field.cqe_prev);				\
++	_Q_INVALIDATE((elm)->field.cqe_next);				\
++} while (0)
++
++#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {			\
++	if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==		\
++	    CIRCLEQ_END(head))						\
++		(head).cqh_last = (elm2);				\
++	else								\
++		(elm2)->field.cqe_next->field.cqe_prev = (elm2);	\
++	if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==		\
++	    CIRCLEQ_END(head))						\
++		(head).cqh_first = (elm2);				\
++	else								\
++		(elm2)->field.cqe_prev->field.cqe_next = (elm2);	\
++	_Q_INVALIDATE((elm)->field.cqe_prev);				\
++	_Q_INVALIDATE((elm)->field.cqe_next);				\
++} while (0)
++
++#endif	/* !_SYS_QUEUE_H_ */