pkgsrc-Bugs archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
pkg/42345: [PATCH] sysutils/pftop on DragonFly BSD
>Number: 42345
>Category: pkg
>Synopsis: [PATCH] sysutils/pftop on DragonFly BSD
>Confidential: no
>Severity: serious
>Priority: medium
>Responsible: pkg-manager
>State: open
>Class: support
>Submitter-Id: net
>Arrival-Date: Thu Nov 19 00:25:00 +0000 2009
>Originator: Rumko
>Release: /
>Organization:
>Environment:
DragonFly rumko.rumko.net 2.5.1-DEVELOPMENT DragonFly
v2.5.1.263.g5f3dd-DEVELOPMENT #35: Mon Nov 16 10:47:50 CET 2009
root%rumko.rumko.net@localhost:/usr/obj/usr/src/sys/MYPRECIOUS i386
>Description:
With the attached patch (also available on
http://www.rumko.net/pkgsrc/0001-Make-pftop-compile-on-DragonFly.patch) pftop
compiles and works on DragonFly BSD and with the help of ASau on
#pkgsrc@freenode, it was tested that even after these changes the package still
compiles on NetBSD as well.
>How-To-Repeat:
>Fix:
From 7bd7faad18fd61d4563a4c0b6fe693384eaed2ca Mon Sep 17 00:00:00 2001
From: Rumko <rumcic%gmail.com@localhost>
Date: Tue, 17 Nov 2009 01:41:24 +0100
Subject: [PATCH] Make pftop compile on DragonFly.
Some changes taken from FreeBSD's ports.
---
sysutils/pftop/distinfo | 10 +-
sysutils/pftop/patches/patch-aa | 10 +-
sysutils/pftop/patches/patch-ad | 40 ++--
sysutils/pftop/patches/patch-ag | 91 ++++++-
sysutils/pftop/patches/patch-ah | 25 ++-
sysutils/pftop/patches/patch-aj | 36 +++
sysutils/pftop/patches/patch-ak | 532 +++++++++++++++++++++++++++++++++++++++
7 files changed, 700 insertions(+), 44 deletions(-)
create mode 100644 sysutils/pftop/patches/patch-aj
create mode 100644 sysutils/pftop/patches/patch-ak
diff --git a/sysutils/pftop/distinfo b/sysutils/pftop/distinfo
index f766e56..6c0fccd 100644
--- a/sysutils/pftop/distinfo
+++ b/sysutils/pftop/distinfo
@@ -3,12 +3,14 @@ $NetBSD: distinfo,v 1.6 2008/06/15 14:09:03 peter 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) = 27c44b5072edd3c9013d8d1d54c940cd72186b88
+SHA1 (patch-ah) = 16540a8a23be6bd94b35758ba8c9a6c0809b2688
SHA1 (patch-ai) = 629c1668eab0d819e590fb62b7afa6c85709fd15
+SHA1 (patch-aj) = a2f03707b59ca390ed460ab7be0ae8299526b655
+SHA1 (patch-ak) = 4b3d9401989e0591d3baf3c1ca744ea6f57fee6c
diff --git a/sysutils/pftop/patches/patch-aa b/sysutils/pftop/patches/patch-aa
index b4499af..3ebb2ba 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 $
---- 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 103bac0..3ca1f62 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 $
---- 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 0b9a6d6..d45356c 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 $
---- 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,34 @@
#include <netinet/in.h>
#define TCPSTATES
#include <netinet/tcp_fsm.h>
@@ -14,7 +14,22 @@ $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>
++#include <net/altq/altq_fairq.h>
++#else
+ #include <altq/altq.h>
+ #include <altq/altq_cbq.h>
+ #include <altq/altq_priq.h>
+ #include <altq/altq_hfsc.h>
+ #endif
++#endif
+
+ #include <ctype.h>
+ #include <curses.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
@@ -22,7 +37,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 +384,9 @@
+ class_stats_t cbq_stats;
+ struct priq_classstats priq_stats;
+ struct hfsc_classstats hfsc_stats;
++#ifdef __DragonFly__
++ struct fairq_classstats fairq_stats;
++#endif
+ };
+
+ struct queue_stats {
+@@ -736,7 +752,7 @@
} else {
num_states = 0;
for (n = 0; n<num_states_all; n++)
@@ -31,7 +56,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 +844,7 @@
tbprintf(" PAUSED");
if (rawmode)
@@ -40,7 +65,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 +859,10 @@
len = columns - strlen(tmp_buf);
if (len < 0)
len = 0;
@@ -52,7 +77,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
tb_end();
-@@ -1244,7 +1252,6 @@
+@@ -1244,7 +1263,6 @@
FLD_ANCHOR->max_width = mx;
FLD_ANCHOR->norm_width = nx;
field_setup();
@@ -60,7 +85,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
}
#endif
-@@ -1279,7 +1286,6 @@
+@@ -1279,7 +1297,6 @@
FLD_LABEL->norm_width = nw;
FLD_LABEL->max_width = mw;
field_setup();
@@ -68,7 +93,45 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
}
#endif
-@@ -2041,11 +2047,9 @@
+@@ -1924,6 +1941,10 @@
+ node->altq.scheduler == ALTQT_HFSC
+ )
+ print_fld_bw(FLD_BANDW, (double)node->altq.bandwidth);
++#ifdef __DragonFly__
++ 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 +2013,26 @@
+
node->qstats_last.data.hfsc_stats.xmit_cnt.bytes, interval);
+ }
+ break;
++#ifdef __DragonFly__
++ 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 +2082,9 @@
if (cachestates) {
show_field(FLD_SI);
show_field(FLD_SP);
@@ -80,7 +143,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
field_setup();
}
-@@ -2105,8 +2109,10 @@
+@@ -2105,8 +2144,10 @@
line++;
mvprintw(line++, 6, "press any key to continue ...");
@@ -93,7 +156,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
-@@ -2142,7 +2148,6 @@
+@@ -2142,7 +2183,6 @@
del = atoi(cmdbuf);
if (del > 0) {
delay = del;
@@ -101,7 +164,7 @@ $NetBSD: patch-ag,v 1.1 2008/06/15 14:09:04 peter Exp $
}
}
-@@ -2175,7 +2180,6 @@
+@@ -2175,7 +2215,6 @@
/* FALLTHROUGH */
case 'h':
show_help();
@@ -109,7 +172,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 +2388,6 @@
if (rawmode && countmax == 0)
countmax = 1;
diff --git a/sysutils/pftop/patches/patch-ah b/sysutils/pftop/patches/patch-ah
index edfa240..a845b72 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 $
---- 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 2009-11-17 01:03:45 +0100
+@@ -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,19 @@ $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;
+@@ -733,13 +741,17 @@
b1 = gen_proto(IPPROTO_ESP);
break;
@@ -42,7 +55,7 @@ $NetBSD: patch-ah,v 1.1 2008/06/15 14:09:04 peter Exp $
default:
sf_error("Unknown protocol abbreviation");
-@@ -1560,7 +1567,7 @@
+@@ -1560,7 +1572,7 @@
/* NOTREACHED */
}
diff --git a/sysutils/pftop/patches/patch-aj b/sysutils/pftop/patches/patch-aj
new file mode 100644
index 0000000..6e568df
--- /dev/null
+++ b/sysutils/pftop/patches/patch-aj
@@ -0,0 +1,36 @@
+--- 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 0000000..a12c430
--- /dev/null
+++ b/sysutils/pftop/patches/patch-ak
@@ -0,0 +1,532 @@
+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_ */
--
1.6.4
Home |
Main Index |
Thread Index |
Old Index