From af875fb696a698fb28863b560b39e0e305784372 Mon Sep 17 00:00:00 2001
From: Peter Avalos <pavalos@dragonflybsd.org>
Date: Thu, 3 Mar 2011 00:49:52 -1000
Subject: [PATCH] Update queue(3) for the REMOVE_NEXT -> REMOVE_AFTER rename.

While I'm here, sync with FreeBSD:
-Remove extra note about O(n) removal.

Obtained-from: FreeBSD
---
 Makefile_upgrade.inc    |  4 ++++
 share/man/man3/Makefile |  4 ++--
 share/man/man3/queue.3  | 48 ++++++++++++++++++++---------------------
 3 files changed, 30 insertions(+), 26 deletions(-)

diff --git a/Makefile_upgrade.inc b/Makefile_upgrade.inc
index 74155781e5..a1a39f24fc 100644
--- a/Makefile_upgrade.inc
+++ b/Makefile_upgrade.inc
@@ -1568,6 +1568,10 @@ TO_REMOVE+=/usr/share/man/cat/man9/kref_init.9.gz
 TO_REMOVE+=/usr/include/dev/video/meteor/meteor_reg.h
 TO_REMOVE+=/usr/share/man/cat4/i386/meteor.4.gz
 TO_REMOVE+=/usr/share/man/man4/i386/meteor.4.gz
+TO_REMOVE+=/usr/share/man/cat3/SLIST_REMOVE_NEXT.3.gz
+TO_REMOVE+=/usr/share/man/man3/SLIST_REMOVE_NEXT.3.gz
+TO_REMOVE+=/usr/share/man/cat3/STAILQ_REMOVE_NEXT.3.gz
+TO_REMOVE+=/usr/share/man/man3/STAILQ_REMOVE_NEXT.3.gz
 
 # XXX Remove when pfsync(4) has been fixed
 TO_REMOVE+=/usr/share/man/cat4/pfsync.4.gz
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index bff944fc32..c9c29ce728 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -41,8 +41,8 @@ MLINKS+=queue.3 SLIST_INSERT_AFTER.3
 MLINKS+=queue.3 SLIST_INSERT_HEAD.3
 MLINKS+=queue.3 SLIST_NEXT.3
 MLINKS+=queue.3 SLIST_REMOVE.3
+MLINKS+=queue.3 SLIST_REMOVE_AFTER.3
 MLINKS+=queue.3 SLIST_REMOVE_HEAD.3
-MLINKS+=queue.3 SLIST_REMOVE_NEXT.3
 MLINKS+=queue.3 STAILQ_CONCAT.3
 MLINKS+=queue.3 STAILQ_EMPTY.3
 MLINKS+=queue.3 STAILQ_ENTRY.3
@@ -58,8 +58,8 @@ MLINKS+=queue.3 STAILQ_INSERT_TAIL.3
 MLINKS+=queue.3 STAILQ_LAST.3
 MLINKS+=queue.3 STAILQ_NEXT.3
 MLINKS+=queue.3 STAILQ_REMOVE.3
+MLINKS+=queue.3 STAILQ_REMOVE_AFTER.3
 MLINKS+=queue.3 STAILQ_REMOVE_HEAD.3
-MLINKS+=queue.3 STAILQ_REMOVE_NEXT.3
 MLINKS+=queue.3 TAILQ_CONCAT.3
 MLINKS+=queue.3 TAILQ_EMPTY.3
 MLINKS+=queue.3 TAILQ_ENTRY.3
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index 8daa44e433..8fe29b9313 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -30,10 +30,9 @@
 .\" SUCH DAMAGE.
 .\"
 .\"	@(#)queue.3	8.2 (Berkeley) 1/24/94
-.\" $FreeBSD: src/share/man/man3/queue.3,v 1.42 2008/05/22 14:40:03 ed Exp $
-.\" $DragonFly: src/share/man/man3/queue.3,v 1.8 2008/10/17 12:41:38 swildner Exp $
+.\" $FreeBSD: src/share/man/man3/queue.3,v 1.46 2011/01/11 13:33:42 gavin Exp $
 .\"
-.Dd April 8, 2009
+.Dd March 3, 2011
 .Dt QUEUE 3
 .Os
 .Sh NAME
@@ -49,8 +48,8 @@
 .Nm SLIST_INSERT_AFTER ,
 .Nm SLIST_INSERT_HEAD ,
 .Nm SLIST_NEXT ,
+.Nm SLIST_REMOVE_AFTER ,
 .Nm SLIST_REMOVE_HEAD ,
-.Nm SLIST_REMOVE_NEXT ,
 .Nm SLIST_REMOVE ,
 .Nm STAILQ_CONCAT ,
 .Nm STAILQ_EMPTY ,
@@ -66,8 +65,8 @@
 .Nm STAILQ_INSERT_TAIL ,
 .Nm STAILQ_LAST ,
 .Nm STAILQ_NEXT ,
+.Nm STAILQ_REMOVE_AFTER ,
 .Nm STAILQ_REMOVE_HEAD ,
-.Nm STAILQ_REMOVE_NEXT ,
 .Nm STAILQ_REMOVE ,
 .Nm LIST_EMPTY ,
 .Nm LIST_ENTRY ,
@@ -118,8 +117,8 @@ lists and tail queues
 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
-.Fn SLIST_REMOVE_NEXT "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 .\"
 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
@@ -136,8 +135,8 @@ lists and tail queues
 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
+.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
-.Fn STAILQ_REMOVE_NEXT "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 .\"
 .Fn LIST_EMPTY "LIST_HEAD *head"
@@ -189,7 +188,6 @@ O(1) removal of an entry from the head of the list.
 Forward traversal through the list.
 .El
 .Pp
-O(n) removal of any entry in the list.
 Singly-linked lists are the simplest of the four data structures
 and support only the above functionality.
 Singly-linked lists are ideal for applications with large datasets
@@ -392,6 +390,14 @@ The macro
 returns the next element in the list.
 .Pp
 The macro
+.Nm SLIST_REMOVE_AFTER
+removes the element after
+.Fa elm
+from the list. Unlike
+.Fa SLIST_REMOVE ,
+this macro does not traverse the entire list.
+.Pp
+The macro
 .Nm SLIST_REMOVE_HEAD
 removes the element
 .Fa elm
@@ -403,14 +409,6 @@ this macro instead of the generic
 macro.
 .Pp
 The macro
-.Nm SLIST_REMOVE_NEXT
-removes the element after
-.Fa elm
-from the list. Unlike
-.Fa SLIST_REMOVE ,
-this macro does not traverse the entire list.
-.Pp
-The macro
 .Nm SLIST_REMOVE
 removes the element
 .Fa elm
@@ -576,6 +574,14 @@ The macro
 returns the next item on the tail queue, or NULL this item is the last.
 .Pp
 The macro
+.Nm STAILQ_REMOVE_AFTER
+removes the element after
+.Fa elm
+from the tail queue. Unlike
+.Fa STAILQ_REMOVE ,
+this macro does not traverse the entire tail queue.
+.Pp
+The macro
 .Nm STAILQ_REMOVE_HEAD
 removes the element at the head of the tail queue.
 For optimum efficiency,
@@ -585,14 +591,6 @@ use this macro explicitly rather than the generic
 macro.
 .Pp
 The macro
-.Nm STAILQ_REMOVE_NEXT
-removes the element after
-.Fa elm
-from the tail queue. Unlike
-.Fa STAILQ_REMOVE ,
-this macro does not traverse the entire tail queue.
-.Pp
-The macro
 .Nm STAILQ_REMOVE
 removes the element
 .Fa elm
@@ -1010,6 +1008,8 @@ while (n1 != NULL) {
 }
 TAILQ_INIT(&head);
 .Ed
+.Sh SEE ALSO
+.Xr tree 3
 .Sh HISTORY
 The
 .Nm queue
-- 
2.41.0