| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1272605795-15765-1-git-send-email-xiaosuo@gmail.com>
Date: Fri, 30 Apr 2010 13:36:35 +0800
From: Changli Gao <xiaosuo@...il.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: Peter Zijlstra <peterz@...radead.org>,
Frederic Weisbecker <fweisbec@...il.com>,
Ben Hutchings <ben@...adent.org.uk>,
linux-kernel@...r.kernel.org, Changli Gao <xiaosuo@...il.com>
Subject: [RFC] list: add singly-linked list and singly-linked tail list
add singly-linked list and singly-linked tail list.
these two lists are also used widely in the kernel as doubly-linked list, so I
am trying to add some APIs for these two lists to eliminate the duplicate code.
Signed-off-by: Changli Gao <xiaosuo@...il.com>
----
include/linux/list.h | 186 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 186 insertions(+)
diff --git a/include/linux/list.h b/include/linux/list.h
index 8392884..048a579 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -706,4 +706,190 @@ static inline void hlist_move_list(struct hlist_head *old,
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = n)
+/* singly-linked list */
+
+struct slist_head {
+ struct slist_head *next;
+};
+
+#define slist_entry(ptr, type, member) \
+ container_of(ptr, type, member)
+
+#define SLIST_HEAD_INIT { .next = NULL }
+#define SLIST_HEAD(name) struct slist_head name = SLIST_HEAD_INIT
+
+static inline void INIT_SLIST_HEAD(struct slist_head *h)
+{
+ h->next = NULL;
+}
+
+static inline bool slist_empty(struct slist_head *h)
+{
+ return h->next == NULL;
+}
+
+static inline void slist_push(struct slist_head *n, struct slist_head *h)
+{
+ n->next = h->next;
+ h->next = n;
+}
+
+static inline struct slist_head *slist_pop(struct slist_head *h)
+{
+ struct slist_head *n;
+
+ n = h->next;
+ if (n)
+ h->next = n->next;
+
+ return n;
+}
+
+static inline struct slist_head *slist_pop_init(struct slist_head *h)
+{
+ struct slist_head *n = slist_pop(h);
+
+ if (n)
+ INIT_SLIST_HEAD(n);
+
+ return n;
+}
+
+static inline void __slist_splice(struct slist_head *first,
+ struct slist_head *to)
+{
+ struct slist_head **ptail;
+
+ for (ptail = &to->next; *ptail; ptail = &(*ptail)->next)
+ ;
+ *ptail = first;
+}
+
+static inline void slist_splice_init(struct slist_head *from,
+ struct slist_head *to)
+{
+
+ if (from->next != NULL) {
+ __slist_splice(from->next, to);
+ INIT_SLIST_HEAD(from);
+ }
+}
+
+#define slist_for_each(pos, head) \
+ for (pos = (head)->next; pos && ({ prefetch(pos->next); 1; }); \
+ pos = pos->next)
+
+#define slist_for_each_entry(tpos, pos, head, member) \
+ for (pos = (head)->next; \
+ pos && ({ prefetch(pos->next); 1; }) && \
+ ({ tpos = slist_entry(pos, typeof(*tpos), member); 1; }); \
+ pos = pos->next)
+
+#define slist_del(pos, n, ppos) \
+ do { \
+ *ppos = pos->next; \
+ n = container_of(ppos, struct slist_head, next); \
+ } while (0)
+
+#define slist_for_each_safe(pos, n, ppos, head) \
+ for (ppos = &(head)->next; (n = pos = *ppos); ppos = &n->next)
+
+#define slist_for_each_entry_safe(tpos, pos, n, ppos, head, member) \
+ for (ppos = &(head)->next; \
+ (n = pos = *ppos) && \
+ ({ tpos = slist_entry(pos, typeof(*tpos), member); 1; }); \
+ ppos = &n->next)
+
+/* singly-linked tail list */
+
+struct tlist_head {
+ struct slist_head *next;
+ struct slist_head **ptail;
+};
+
+#define TLIST_HEAD_INIT(name) { .next = NULL, .ptail = &(name).next }
+#define TLIST_HEAD(name) struct tlist_head name = TLIST_HEAD_INIT(name)
+
+static inline void INIT_TLIST_HEAD(struct tlist_head *h)
+{
+ h->next = NULL;
+ h->ptail = &h->next;
+}
+
+static inline bool tlist_empty(struct tlist_head *h)
+{
+ return h->next == NULL;
+}
+
+static inline void tlist_append(struct slist_head *n, struct tlist_head *h)
+{
+ *(h->ptail) = n;
+ h->ptail = &n->next;
+}
+
+static inline void tlist_push(struct slist_head *n, struct tlist_head *h)
+{
+ n->next = h->next;
+ h->next = n;
+ if (h->ptail == &h->next)
+ h->ptail = &n->next;
+}
+
+static inline struct slist_head *tlist_pop(struct tlist_head *h)
+{
+ struct slist_head *n = h->next;
+
+ if (n) {
+ h->next = n->next;
+ if (n->next == NULL)
+ h->ptail = &h->next;
+ }
+
+ return n;
+}
+
+static inline struct slist_head *tlist_pop_init(struct tlist_head *h)
+{
+ struct slist_head *n = tlist_pop(h);
+
+ if (n)
+ INIT_SLIST_HEAD(n);
+
+ return n;
+}
+
+static inline void tlist_splice_init(struct tlist_head *from,
+ struct tlist_head *to)
+{
+ if (!tlist_empty(from)) {
+ *(to->ptail) = from->next;
+ to->ptail = from->ptail;
+ INIT_TLIST_HEAD(from);
+ }
+}
+
+static inline void tlist_splice_to_slist_init(struct tlist_head *from,
+ struct slist_head *to)
+{
+ if (!tlist_empty(from)) {
+ __slist_splice(from->next, to);
+ INIT_TLIST_HEAD(from);
+ }
+}
+
+#define tlist_for_each slist_for_each
+
+#define tlist_for_each_entry slist_for_each_entry
+
+#define tlist_for_each_safe slist_for_each_safe
+
+#define tlist_for_each_entry_safe slist_for_each_entry_safe
+
+#define tlist_del(pos, n, ppos, head) \
+ do { \
+ slist_del(pos, n, ppos); \
+ if (pos->next == NULL) \
+ (head)->ptail = ppos; \
+ } while (0)
+
#endif
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists