This is the mail archive of the
newlib@sourceware.org
mailing list for the newlib project.
[PATCH 5/8] 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).
- From: Sebastian Huber <sebastian dot huber at embedded-brains dot de>
- To: newlib at sourceware dot org
- Date: Tue, 4 Apr 2017 10:34:46 +0200
- Subject: [PATCH 5/8] 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).
- Authentication-results: sourceware.org; auth=none
- References: <1491294889-9721-1-git-send-email-sebastian.huber@embedded-brains.de>
From: mckusick <mckusick@FreeBSD.org>
Reviewed by: kib
---
newlib/libc/include/sys/queue.h | 38 ++++++++++++++++++++++++++++++++++++--
1 file changed, 36 insertions(+), 2 deletions(-)
diff --git a/newlib/libc/include/sys/queue.h b/newlib/libc/include/sys/queue.h
index d6c821f..46bb69f 100644
--- a/newlib/libc/include/sys/queue.h
+++ b/newlib/libc/include/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)
@@ -452,6 +469,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)
--
1.8.4.5