linux-kernel - Re: [RFC] list: add singly-linked list and singly-linked tail list

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20100430062559.GB21078@nowhere>
Date:	Fri, 30 Apr 2010 08:26:01 +0200
From:	Frederic Weisbecker <fweisbec@...il.com>
To:	Changli Gao <xiaosuo@...il.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Ben Hutchings <ben@...adent.org.uk>,
	linux-kernel@...r.kernel.org
Subject: Re: [RFC] list: add singly-linked list and singly-linked tail list

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 <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;
> +};



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.

--
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/