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 <[email protected]>
----
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
On Fri, Apr 30, 2010 at 01:36:35PM +0800, Changli Gao wrote:
> 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.
What callsites do you have in mind?
> Signed-off-by: Changli Gao <[email protected]>
> ----
> 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;
> +};
I would rather call that a stack and change the prefix:
struct stack_top {
struct stack_top *next;
}
And have helpers named like stack_push(), stack_pop(), etc...
> +
> +#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;
> +};
Well. It's like list_head with a lowered memory footprint but
the loss of beeing able to insert elements in the middle.
Why not, but it depends on which callsites waiting to be converted
you have in mind.
Thanks.