[PATCH][2.5] Single linked lists for Linux

[PATCH][2.5] Single linked lists for Linux

[Lightweight Patch Manager]

This introduces single linked lists,  as figured out by us four. Works
fine with userspace test applications,  should work fine with e.g. the
scheduler. Breaks nothing. Must get adopted.

--- /dev/null	Wed Dec 31 17:00:00 1969
+++ slist-2.5/include/linux/slist.h	Wed Sep 25 14:49:24 2002
@@ -0,0 +1,103 @@
+#ifdef __KERNEL__
+#ifndef _LINUX_SLIST_H
+#define _LINUX_SLIST_H
+
+#include <asm/processor.h>
+
+/*
+ * Type-safe single linked list helper-functions.
+ * (originally taken from list.h)
+ *
+ * Thomas 'Dent' Mirlacher, Daniel Phillips, Andreas Borgk,
+ * Thunder from the hill
+ */
+
+/**
+ * slist_add_front - add a new entry at the first slot, moving the old head
+ *		     to the second slot
+ * @new:	new entry to be added
+ * @head:	head of the single linked list
+ *
+ * Insert a new entry before the specified head.
+ * This is good for implementing stacks.
+ */
+
+#define slist_add_front(_new, _head)		\
+do {						\
+	(_new)->next = (_head);			\
+	(_head) = (_new);			\
+} while (0)
+
+
+
+/**
+ * slist_add - add a new entry
+ * @new:       new entry to be added
+ * @head:      head of the single linked list
+ *
+ * Insert a new entry before the specified head.
+ * This is good for implementing stacks.
+ *
+ * Careful: if you do this concurrently, _head
+ * might get into nirvana...
+ */
+#define slist_add(_new, _head)			\
+do {						\
+	(_new)->next = (_head)->next;		\
+	(_head)->next = (_new);			\
+	(_new) = (_head);			\
+} while (0)
+
+/**
+ * slist_del -	remove an entry from list
+ * @head:	head to remove it from
+ * @entry:	entry to be removed
+ */
+#define slist_del(_head, _entry)		\
+do {						\
+	(_head)->next = (_entry)->next;		\
+	(_entry)->next = NULL;			\
+}
+
+/**
+ * slist_del_single -	untag a list from an entry
+ * @list:	list entry to be untagged
+ */
+#define slist_del_single(_list)			\
+	(_list)->next = NULL
+
+/**
+ * slist_pop	-	pop out list entry
+ * @list:	entry to be popped out
+ *
+ * Pop out an entry from a list.
+ */
+#define slist_pop(_list) ({			\
+	typeof(_list) _NODE_ = _list;		\
+	if (_list) {				\
+	    (_list) = (_list)->next;		\
+	    _NODE_->next = NULL;		\
+	}					\
+	_NODE_; })
+
+/**
+ * slist_for_each	-	iterate over a list
+ * @pos:	the pointer to use as a loop counter.
+ * @head:	the head for your list (this is also the first entry).
+ */
+#define slist_for_each(pos, head)				\
+	for (pos = head; pos && ({ prefetch(pos->next); 1; });	\
+	    pos = pos->next)
+
+/**
+ * slist_for_each_del	-	iterate over a list, popping off entries
+ * @pos:       the pointer to use as a loop counter.
+ * @head:      the head for your list (this is also the first entry).
+ */
+#define slist_for_each_del(pos, head)			\
+	for (pos = slist_pop(head); pos &&		\
+    	    ({ prefetch(pos->next); 1; });		\
+	    pos = slist_pop(head))
+
+#endif /* _LINUX_SLIST_H */
+#endif /* __KERNEL__ */

-- 
Lightweight Patch Manager, without pine.
If you have any objections (apart from who I am), tell me

Re: [PATCH][2.5] Single linked lists for Linux

[Rik van Riel]

On Wed, 25 Sep 2002, Lightweight Patch Manager wrote:

> This introduces single linked lists, as figured out by us four. Works
> fine with userspace test applications, should work fine with e.g. the
> scheduler. Breaks nothing. Must get adopted.

Where is the SLIST_HEAD macro and other goodies to be able
to use this thing in the same way we use list.h ?

Rik
-- 
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Spamtraps of the month:  september@surriel.com trac@trac.org

Re: [PATCH][2.5] Single linked lists for Linux

[Mark Mielke]

On Wed, Sep 25, 2002 at 08:56:08PM +0000, Lightweight Patch Manager wrote:
> +#define slist_add_front(_new, _head)		\
> +do {						\
> +	(_new)->next = (_head);			\
> +	(_head) = (_new);			\
> +} while (0)

I suppose it isn't a serious issue, but is it necessary to repeat
'_new' and '_head' in #define?

> +/**
> + * slist_del -	remove an entry from list
> + * @head:	head to remove it from
> + * @entry:	entry to be removed
> + */
> +#define slist_del(_head, _entry)		\
> +do {						\
> +	(_head)->next = (_entry)->next;		\
> +	(_entry)->next = NULL;			\
> +}

Did you miss "while (0)"?

> +#define slist_del_single(_list)			\
> +	(_list)->next = NULL

Perhaps an outer ()?

mark

-- 
mark@mielke.cc/markm@ncf.ca/markm@nortelnetworks.com __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/

Re: [PATCH][2.5] Single linked lists for Linux

[Thunder from the hill]

Hi,

On Wed, 25 Sep 2002, Rik van Riel wrote:
> Where is the SLIST_HEAD macro and other goodies to be able
> to use this thing in the same way we use list.h ?

To come, once I know what you think about it.

			Thunder
-- 
assert(typeof((fool)->next) == typeof(fool));	/* wrong */

Re: [PATCH][2.5] Single linked lists for Linux

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Peter Chubb wrote:
> +/**
> + * slist_del -	remove an entry from list
> + * @head:	head to remove it from
> + * @entry:	entry to be removed
> + */
> +#define slist_del(_head, _entry)		\
> +do {						\
> +	(_head)->next = (_entry)->next;		\
> +	(_entry)->next = NULL;			\
> +}

What about

#define slist_del(_head)			\
do {						\
	typeof(_head) _entry = (_head)->next;	\
	(_head)->next = _entry->next;		\
	_entry->next = NULL;			\
} while (0)

> static inline int slist_del(struct slist *head, struct slist *entry)

I don't want to inline (just like once, with list.h) because I want any 
type to match here...

			Thunder
-- 
assert(typeof((fool)->next) == typeof(fool));	/* wrong */

Re: [PATCH][2.5] Single linked lists for Linux

[Rik van Riel]

On Thu, 26 Sep 2002, Peter Chubb wrote:

> +#define slist_del(_head, _entry)		\
>
> This only works if head->next == entry otherwise you lose half your
> list.  Also, none of this is SMP-safe.

Oh boy, this is the material bad jokes are made from ...

Q: How many lightweight patch managers does it take to do a
   singly linked list list_del ?
A: 4, two to hold down the list head, one to chop off the tail
   and another one to sweep the lost entries under the carpet.

Sorry, but I couldn't resist this one ;)

cheers,

Rik
-- 
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Spamtraps of the month:  september@surriel.com trac@trac.org

Re: [PATCH][2.5] Single linked lists for Linux

[Zwane Mwaikambo]

On Thu, 26 Sep 2002, Peter Chubb wrote:

> This only works if head->next == entry otherwise you lose half your
> list.  Also, none of this is SMP-safe.
> 
> I think you need something like this (but with locking!)

Should you really be having locking in a primitive like that? That 
shouldn't be taken care of at that level.

	Zwane
-- 
function.linuxpower.ca

[PATCH][2.5] Single linked lists for Linux

[Peter Chubb]

+
+/**
+ * slist_del -	remove an entry from list
+ * @head:	head to remove it from
+ * @entry:	entry to be removed
+ */
+#define slist_del(_head, _entry)		\
+do {						\
+	(_head)->next = (_entry)->next;		\
+	(_entry)->next = NULL;			\
+}
+

This only works if head->next == entry otherwise you lose half your
list.  Also, none of this is SMP-safe.

I think you need something like this (but with locking!)

/*
 * remove entry from list starting at head
 * Return 0 if successful, non-zero otherwise.
 */
static inline int slist_del(struct slist *head, struct slist *entry)
{
	struct slist **p;
	for (p = &head->next; *p; p = &(*p)->next)
	    if (*p == entry) {
	       *p = entry->next;
	       entry->next = NULL;
	       return 0;
        }
        return -1;
}

Peter C