diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -215,6 +215,7 @@ queue.3 LIST_NEXT.3 \ queue.3 LIST_PREV.3 \ queue.3 LIST_REMOVE.3 \ + queue.3 LIST_REPLACE.3 \ queue.3 LIST_SWAP.3 \ queue.3 SLIST_CLASS_ENTRY.3 \ queue.3 SLIST_CLASS_HEAD.3 \ @@ -283,6 +284,7 @@ queue.3 TAILQ_NEXT.3 \ queue.3 TAILQ_PREV.3 \ queue.3 TAILQ_REMOVE.3 \ + queue.3 TAILQ_REPLACE.3 \ queue.3 TAILQ_SWAP.3 MLINKS+= stats.3 stats_tpl_alloc.3 \ stats.3 stats_tpl_fetch_allocid.3 \ diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 --- a/share/man/man3/queue.3 +++ b/share/man/man3/queue.3 @@ -25,7 +25,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd September 8, 2016 +.Dd April 8, 2024 .Dt QUEUE 3 .Os .Sh NAME @@ -90,6 +90,7 @@ .Nm LIST_NEXT , .Nm LIST_PREV , .Nm LIST_REMOVE , +.Nm LIST_REPLACE , .Nm LIST_SWAP , .Nm TAILQ_CLASS_ENTRY , .Nm TAILQ_CLASS_HEAD , @@ -116,6 +117,7 @@ .Nm TAILQ_NEXT , .Nm TAILQ_PREV , .Nm TAILQ_REMOVE , +.Nm TAILQ_REPLACE , .Nm TAILQ_SWAP .Nd implementations of singly-linked lists, singly-linked tail queues, lists and tail queues @@ -185,6 +187,7 @@ .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME" .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME" .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .\" .Fn TAILQ_CLASS_ENTRY "CLASSTYPE" @@ -212,6 +215,7 @@ .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" .\" .Sh DESCRIPTION @@ -963,6 +967,17 @@ from the list. .Pp The macro +.Fn LIST_REPLACE +replaces the element +.Fa elm +with +.Fa new +in the list. +The element +.Fa new +must not already be on a list. +.Pp +The macro .Nm LIST_SWAP swaps the contents of .Fa head1 @@ -1221,6 +1236,17 @@ from the tail queue. .Pp The macro +.Fn TAILQ_REPLACE +replaces the element +.Fa elm +with +.Fa new +in the tail queue. +The element +.Fa new +must not already be on a list. +.Pp +The macro .Nm TAILQ_SWAP swaps the contents of .Fa head1 @@ -1235,7 +1261,7 @@ ... TAILQ_ENTRY(entry) entries; /* Tail queue. */ ... -} *n1, *n2, *n3, *np; +} *n1, *n2, *n3, *n4, *np; TAILQ_INIT(&head); /* Initialize the queue. */ @@ -1253,6 +1279,10 @@ TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ free(n2); + +n4 = malloc(sizeof(struct entry)); /* Replacement. */ +TAILQ_REPLACE(&head, n3, n4, entries); +free(n3); /* Forward traversal. */ TAILQ_FOREACH(np, &head, entries) np-> ... diff --git a/sys/sys/queue.h b/sys/sys/queue.h --- a/sys/sys/queue.h +++ b/sys/sys/queue.h @@ -110,6 +110,7 @@ * _REMOVE_AFTER + - + - * _REMOVE_HEAD + + + + * _REMOVE s + s + + * _REPLACE - + - + * _SWAP + + + + * */ @@ -609,6 +610,21 @@ TRASHIT(*oldprev); \ } while (0) +#define LIST_REPLACE(elm, elm2, field) do { \ + QMD_SAVELINK(oldnext, (elm)->field.le_next); \ + QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ + QMD_LIST_CHECK_NEXT(elm, field); \ + QMD_LIST_CHECK_PREV(elm, field); \ + LIST_NEXT((elm2), field) = LIST_NEXT((elm), field); \ + if (LIST_NEXT((elm2), field) != NULL) \ + LIST_NEXT((elm), field)->field.le_prev = \ + &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + TRASHIT(*oldnext); \ + TRASHIT(*oldprev); \ +} while (0) + #define LIST_SWAP(head1, head2, type, field) do { \ QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ LIST_FIRST((head1)) = LIST_FIRST((head2)); \ @@ -863,6 +879,24 @@ QMD_TRACE_ELEM(&(elm)->field); \ } while (0) +#define TAILQ_REPLACE(head, elm, elm2, field) do { \ + QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ + QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ + QMD_TAILQ_CHECK_NEXT(elm, field); \ + QMD_TAILQ_CHECK_PREV(elm, field); \ + TAILQ_NEXT((elm2), field) = TAILQ_NEXT((elm), field); \ + if (TAILQ_NEXT((elm2), field) != TAILQ_END(head)) \ + TAILQ_NEXT((elm2), field)->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); \ + TRASHIT(*oldnext); \ + TRASHIT(*oldprev); \ + QMD_TRACE_ELEM(&(elm)->field); \ +} while (0) + #define TAILQ_SWAP(head1, head2, type, field) do { \ QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \