From owner-freebsd-bugs@FreeBSD.ORG Tue Feb 26 12:20:03 2008 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 862B3106566C for ; Tue, 26 Feb 2008 12:20:03 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id 7076313C4DD for ; Tue, 26 Feb 2008 12:20:03 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.14.2/8.14.2) with ESMTP id m1QCK3Kl090130 for ; Tue, 26 Feb 2008 12:20:03 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.2/8.14.1/Submit) id m1QCK3UR090129; Tue, 26 Feb 2008 12:20:03 GMT (envelope-from gnats) Resent-Date: Tue, 26 Feb 2008 12:20:03 GMT Resent-Message-Id: <200802261220.m1QCK3UR090129@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Ed Schouten Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 8ADC01065674 for ; Tue, 26 Feb 2008 12:17:43 +0000 (UTC) (envelope-from ed@hoeg.nl) Received: from palm.hoeg.nl (mx0.hoeg.nl [IPv6:2001:610:652::211]) by mx1.freebsd.org (Postfix) with ESMTP id 9700313C478 for ; Tue, 26 Feb 2008 12:17:42 +0000 (UTC) (envelope-from ed@hoeg.nl) Received: by palm.hoeg.nl (Postfix, from userid 1000) id EF88F1CC40; Tue, 26 Feb 2008 13:17:41 +0100 (CET) Message-Id: <20080226121741.EF88F1CC40@palm.hoeg.nl> Date: Tue, 26 Feb 2008 13:17:41 +0100 (CET) From: Ed Schouten To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Cc: Subject: kern/121117: [Patch] Add S{LIST,TAILQ}REMOVE_NEXT() X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: Ed Schouten List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 26 Feb 2008 12:20:03 -0000 >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@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: