svn commit: r304230 - in head: share/man/man3 sys/sys
Kirk McKusick
mckusick at FreeBSD.org
Tue Aug 16 17:07:49 UTC 2016
Author: mckusick
Date: Tue Aug 16 17:07:48 2016
New Revision: 304230
URL: https://svnweb.freebsd.org/changeset/base/304230
Log:
Add two new macros, SLIST_CONCAT and LIST_CONCAT. Note in both the
queue.h header file and in the queue.3 manual page that they are O(n)
so should be used only in low-usage paths with short lists (otherwise
an STAILQ or TAILQ should be used).
Reviewed by: kib
Modified:
head/share/man/man3/queue.3
head/sys/sys/queue.h
Modified: head/share/man/man3/queue.3
==============================================================================
--- head/share/man/man3/queue.3 Tue Aug 16 17:05:15 2016 (r304229)
+++ head/share/man/man3/queue.3 Tue Aug 16 17:07:48 2016 (r304230)
@@ -28,12 +28,13 @@
.\" @(#)queue.3 8.2 (Berkeley) 1/24/94
.\" $FreeBSD$
.\"
-.Dd June 24, 2015
+.Dd August 15, 2016
.Dt QUEUE 3
.Os
.Sh NAME
.Nm SLIST_CLASS_ENTRY ,
.Nm SLIST_CLASS_HEAD ,
+.Nm SLIST_CONCAT ,
.Nm SLIST_EMPTY ,
.Nm SLIST_ENTRY ,
.Nm SLIST_FIRST ,
@@ -75,6 +76,7 @@
.Nm STAILQ_SWAP ,
.Nm LIST_CLASS_ENTRY ,
.Nm LIST_CLASS_HEAD ,
+.Nm LIST_CONCAT ,
.Nm LIST_EMPTY ,
.Nm LIST_ENTRY ,
.Nm LIST_FIRST ,
@@ -125,6 +127,7 @@ lists and tail queues
.\"
.Fn SLIST_CLASS_ENTRY "CLASSTYPE"
.Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
+.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME"
.Fn SLIST_EMPTY "SLIST_HEAD *head"
.Fn SLIST_ENTRY "TYPE"
.Fn SLIST_FIRST "SLIST_HEAD *head"
@@ -168,6 +171,7 @@ lists and tail queues
.\"
.Fn LIST_CLASS_ENTRY "CLASSTYPE"
.Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
+.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
.Fn LIST_EMPTY "LIST_HEAD *head"
.Fn LIST_ENTRY "TYPE"
.Fn LIST_FIRST "LIST_HEAD *head"
@@ -249,6 +253,8 @@ Singly-linked lists add the following fu
.Bl -enum -compact -offset indent
.It
O(n) removal of any entry in the list.
+.It
+O(n) concatenation of two lists.
.El
.Pp
Singly-linked tail queues add the following functionality:
@@ -296,6 +302,8 @@ Linked lists are the simplest of the dou
They add the following functionality over the above:
.Bl -enum -compact -offset indent
.It
+O(n) concatenation of two lists.
+.It
They may be traversed backwards.
.El
However:
@@ -401,6 +409,19 @@ evaluates to an initializer for the list
.Fa head .
.Pp
The macro
+.Nm SLIST_CONCAT
+concatenates the list headed by
+.Fa head2
+onto the end of the one headed by
+.Fa head1
+removing all entries from the former.
+Use of this macro should be avoided as it traverses the entirety of the
+.Fa head1
+list.
+A singly-linked tail queue should be used if this macro is needed in
+high-usage code paths or to operate on long lists.
+.Pp
+The macro
.Nm SLIST_EMPTY
evaluates to true if there are no elements in the list.
.Pp
@@ -508,6 +529,9 @@ The macro
removes the element
.Fa elm
from the list.
+Use of this macro should be avoided as it traverses the entire list.
+A doubly-linked list should be used if this macro is needed in
+high-usage code paths or to operate on long lists.
.Pp
The macro
.Nm SLIST_SWAP
@@ -724,6 +748,9 @@ The macro
removes the element
.Fa elm
from the tail queue.
+Use of this macro should be avoided as it traverses the entire list.
+A doubly-linked tail queue should be used if this macro is needed in
+high-usage code paths or to operate on long tail queues.
.Pp
The macro
.Nm STAILQ_SWAP
@@ -823,6 +850,19 @@ evaluates to an initializer for the list
.Fa head .
.Pp
The macro
+.Nm LIST_CONCAT
+concatenates the list headed by
+.Fa head2
+onto the end of the one headed by
+.Fa head1
+removing all entries from the former.
+Use of this macro should be avoided as it traverses the entirety of the
+.Fa head1
+list.
+A tail queue should be used if this macro is needed in
+high-usage code paths or to operate on long lists.
+.Pp
+The macro
.Nm LIST_EMPTY
evaluates to true if there are no elements in the list.
.Pp
Modified: head/sys/sys/queue.h
==============================================================================
--- head/sys/sys/queue.h Tue Aug 16 17:05:15 2016 (r304229)
+++ head/sys/sys/queue.h Tue Aug 16 17:07:48 2016 (r304230)
@@ -76,6 +76,10 @@
*
* For details on the use of these macros, see the queue(3) manual page.
*
+ * Below is a summary of implemented functions where:
+ * + means the macro is available
+ * - means the macro is not available
+ * s means the macro is available but is slow (runs in O(n) time)
*
* SLIST LIST STAILQ TAILQ
* _HEAD + + + +
@@ -101,10 +105,10 @@
* _INSERT_BEFORE - + - +
* _INSERT_AFTER + + + +
* _INSERT_TAIL - - + +
- * _CONCAT - - + +
+ * _CONCAT s s + +
* _REMOVE_AFTER + - + -
* _REMOVE_HEAD + - + -
- * _REMOVE + + + +
+ * _REMOVE s + s +
* _SWAP + + + +
*
*/
@@ -183,6 +187,19 @@ struct { \
/*
* Singly-linked List functions.
*/
+#define SLIST_CONCAT(head1, head2, type, field) do { \
+ QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \
+ if (curelm == NULL) { \
+ if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \
+ SLIST_INIT(head2); \
+ } else if (SLIST_FIRST(head2) != NULL) { \
+ while (SLIST_NEXT(curelm, field) != NULL) \
+ curelm = SLIST_NEXT(curelm, field); \
+ SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \
+ SLIST_INIT(head2); \
+ } \
+} while (0)
+
#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
#define SLIST_FIRST(head) ((head)->slh_first)
@@ -447,6 +464,23 @@ struct { \
#define QMD_LIST_CHECK_PREV(elm, field)
#endif /* (_KERNEL && INVARIANTS) */
+#define LIST_CONCAT(head1, head2, type, field) do { \
+ QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
+ if (curelm == NULL) { \
+ if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
+ LIST_FIRST(head2)->field.le_prev = \
+ &LIST_FIRST((head1)); \
+ LIST_INIT(head2); \
+ } \
+ } else if (LIST_FIRST(head2) != NULL) { \
+ while (LIST_NEXT(curelm, field) != NULL) \
+ curelm = LIST_NEXT(curelm, field); \
+ LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
+ LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
+ LIST_INIT(head2); \
+ } \
+} while (0)
+
#define LIST_EMPTY(head) ((head)->lh_first == NULL)
#define LIST_FIRST(head) ((head)->lh_first)
More information about the svn-src-head
mailing list