From: Sebastian Huber <sebastian.huber@embedded-brains.de>
To: newlib@sourceware.org
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).
Date: Tue, 04 Apr 2017 08:35:00 -0000 [thread overview]
Message-ID: <1491294889-9721-5-git-send-email-sebastian.huber@embedded-brains.de> (raw)
In-Reply-To: <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
next prev parent reply other threads:[~2017-04-04 8:35 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-04 8:35 [PATCH 1/8] Add new FOREACH_FROM variants of the queue(3) FOREACH macros which can optionally start the traversal from a previously found element by passing the element in as "var". Passing a NULL "var" retains the same semantics as the regular FOREACH macros Sebastian Huber
2017-04-04 8:35 ` [PATCH 7/8] queue.3: Document existing QMD_* macros Sebastian Huber
2017-04-04 8:35 ` [PATCH 8/8] Renumber copyright clause 4 Sebastian Huber
2017-04-04 8:35 ` [PATCH 4/8] Make the system queue header file fully usable within C++ programs by adding macros to define class lists Sebastian Huber
2017-04-04 8:35 ` [PATCH 6/8] queue(3): Enhance queue debugging macros Sebastian Huber
2017-04-04 8:35 ` [PATCH 3/8] Pass macro arguments properly Sebastian Huber
2017-04-04 8:35 ` Sebastian Huber [this message]
2017-04-04 8:35 ` [PATCH 2/8] Fix order of arguments in the TRACEBUF_INITIALIZER macro so that we can define QUEUE_MACRO_DEBUG to debug list problems Sebastian Huber
2017-04-04 9:53 ` [PATCH 1/8] Add new FOREACH_FROM variants of the queue(3) FOREACH macros which can optionally start the traversal from a previously found element by passing the element in as "var". Passing a NULL "var" retains the same semantics as the regular FOREACH macros Corinna Vinschen
2017-04-04 9:56 ` Sebastian Huber
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1491294889-9721-5-git-send-email-sebastian.huber@embedded-brains.de \
--to=sebastian.huber@embedded-brains.de \
--cc=newlib@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).