kern/121117: [Patch] Add S{LIST,TAILQ}REMOVE_NEXT()

[Ed Schouten]

>Number:         121117
>Category:       kern
>Synopsis:       [Patch] Add S{LIST,TAILQ}REMOVE_NEXT()
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    freebsd-bugs
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          change-request
>Submitter-Id:   current-users
>Arrival-Date:   Tue Feb 26 12:20:02 UTC 2008
>Closed-Date:
>Last-Modified:
>Originator:     Ed Schouten
>Release:        FreeBSD 6.3-STABLE i386
>Organization:
>Environment:
System: FreeBSD palm.hoeg.nl 6.3-STABLE FreeBSD 6.3-STABLE #0: Fri Feb 1 16:35:28 CET 2008 root at palm.hoeg.nl:/usr/obj/usr/src/sys/PALM i386
>Description:
Removing a block in a single linked list, where you only know the
address of the block itself is of course an O(n) operation, where n is
the amount of blocks that precede. Removing blocks from these lists
could be O(1) when you already know the address of the previous block.

OpenBSD already has an SLIST_REMOVE_NEXT(), so we'd better introduce
SLIST_REMOVE_NEXT() and STAILQ_REMOVE_NEXT(), which does exactly what it
says - remove the next object from the list.
>How-To-Repeat:
Invent some kind of buffer scheme where you want to remove blocks in the
middle of the list, where you already know the address of the previous
block.

The TTY outq code in the Perforce mpsafetty branch already needs this
functionality.
>Fix:
The following patch is based on work from my Perforce branch. It moves
some already existing code in the S{LIST,TAILQ}_REMOVE() macros to
separate ones.

--- share/man/man3/queue.3
+++ share/man/man3/queue.3
@@ -48,6 +48,7 @@
 .Nm SLIST_INSERT_HEAD ,
 .Nm SLIST_NEXT ,
 .Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE_NEXT ,
 .Nm SLIST_REMOVE ,
 .Nm STAILQ_CONCAT ,
 .Nm STAILQ_EMPTY ,
@@ -64,6 +65,7 @@
 .Nm STAILQ_LAST ,
 .Nm STAILQ_NEXT ,
 .Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE_NEXT ,
 .Nm STAILQ_REMOVE ,
 .Nm LIST_EMPTY ,
 .Nm LIST_ENTRY ,
@@ -114,6 +116,7 @@
 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE_NEXT "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"
@@ -131,6 +134,7 @@
 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 .Fn STAILQ_NEXT "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"
@@ -387,6 +391,14 @@
 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
@@ -561,6 +573,14 @@
 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
--- sys/sys/queue.h
+++ sys/sys/queue.h
@@ -97,6 +97,7 @@
  * _INSERT_TAIL			-	-	+	+
  * _CONCAT			-	-	+	+
  * _REMOVE_HEAD			+	-	+	-
+ * _REMOVE_NEXT			+	-	+	-
  * _REMOVE			+	+	+	+
  *
  */
@@ -195,12 +196,16 @@
 		struct type *curelm = SLIST_FIRST((head));		\
 		while (SLIST_NEXT(curelm, field) != (elm))		\
 			curelm = SLIST_NEXT(curelm, field);		\
-		SLIST_NEXT(curelm, field) =				\
-		    SLIST_NEXT(SLIST_NEXT(curelm, field), field);	\
+		SLIST_REMOVE_NEXT(curelm, field);			\
 	}								\
 	TRASHIT((elm)->field.sle_next);					\
 } while (0)
 
+#define SLIST_REMOVE_NEXT(elm, field) do {				\
+	SLIST_NEXT(elm, field) =					\
+	    SLIST_NEXT(SLIST_NEXT(elm, field), field);			\
+} while (0)
+
 #define	SLIST_REMOVE_HEAD(head, field) do {				\
 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
 } while (0)
@@ -287,9 +292,7 @@
 		struct type *curelm = STAILQ_FIRST((head));		\
 		while (STAILQ_NEXT(curelm, field) != (elm))		\
 			curelm = STAILQ_NEXT(curelm, field);		\
-		if ((STAILQ_NEXT(curelm, field) =			\
-		     STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
-			(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
+		STAILQ_REMOVE_NEXT(head, curelm, field);		\
 	}								\
 	TRASHIT((elm)->field.stqe_next);				\
 } while (0)
@@ -300,6 +303,12 @@
 		(head)->stqh_last = &STAILQ_FIRST((head));		\
 } while (0)
 
+#define STAILQ_REMOVE_NEXT(head, elm, field) do {			\
+	if ((STAILQ_NEXT(elm, field) =					\
+	     STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
+		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
+} while (0)
+
 /*
  * List declarations.
  */
>Release-Note:
>Audit-Trail:
>Unformatted: