diff options
author | Kirk McKusick <mckusick@FreeBSD.org> | 2016-08-16 17:07:48 +0000 |
---|---|---|
committer | Kirk McKusick <mckusick@FreeBSD.org> | 2016-08-16 17:07:48 +0000 |
commit | 65d31997461adff86f191e2842413b0b07181432 (patch) | |
tree | 9a6d69bfeb87c0488ae6805fc0504ddd45d3cced /sys | |
parent | 39f7cbe9ab1fc835a08e3eb73895afdba4701719 (diff) | |
download | src-65d31997461adff86f191e2842413b0b07181432.tar.gz src-65d31997461adff86f191e2842413b0b07181432.zip |
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
Notes
Notes:
svn path=/head/; revision=304230
Diffstat (limited to 'sys')
-rw-r--r-- | sys/sys/queue.h | 38 |
1 files changed, 36 insertions, 2 deletions
diff --git a/sys/sys/queue.h b/sys/sys/queue.h index 1be9e9cc737d..f26c492af1c7 100644 --- a/sys/sys/queue.h +++ b/sys/sys/queue.h @@ -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) |