Date: Tue, 26 Feb 2008 13:17:41 +0100 (CET) From: Ed Schouten <ed@fxq.nl> To: FreeBSD-gnats-submit@FreeBSD.org Subject: kern/121117: [Patch] Add S{LIST,TAILQ}REMOVE_NEXT() Message-ID: <20080226121741.EF88F1CC40@palm.hoeg.nl> Resent-Message-ID: <200802261220.m1QCK3UR090129@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>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:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20080226121741.EF88F1CC40>