[PATCH][2.5] Single linked lists for Linux, overly complicated but working

[PATCH][2.5] Single linked lists for Linux, overly complicated but working

[Lightweight Patch Manager]

This is an overly complicated version,  I guess I'll have a better one
once I've got my noodles in. Wait an hour, I'll be back.

And BTW, I got the luckynet address fixed, you can send me again...

--- /dev/null	Wed Dec 31 17:00:00 1969
+++ slist-2.5/include/linux/slist.h	Thu Sep 26 09:57:25 2002
@@ -0,0 +1,139 @@
+#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 Bogk, Thunder from the hill
+ */
+
+#define INIT_SLIST_HEAD(name)			\
+	(name->next = name)
+
+#define SLIST_HEAD_INIT(name)			\
+	name
+
+#define SLIST_HEAD(type,name)			\
+	typeof(type) name = INIT_SLIST_HEAD(name)
+
+/**
+ * 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(_entry)				\
+({							\
+	typeof(_entry) _head =				\
+	    kmalloc(sizeof(_entry), GFP_KERNEL), _free;	\
+	if (_head) {					\
+	    memcpy(_head, (_entry), sizeof(_entry));	\
+	    _free = (_entry);				\
+	    (_entry) = (_entry)->next;			\
+	    kfree(_free);				\
+	    _head->next = NULL;				\
+	    _head;					\
+	} else						\
+	    NULL;					\
+})
+
+/**
+ * slist_del_init -	remove an entry from list and initialize it
+ * @head:	head to remove it from
+ * @entry:	entry to be removed
+ */
+#define slist_del_init(_entry)				\
+({							\
+	typeof(_entry) _head =				\
+	    kmalloc(sizeof(_entry), GFP_KERNEL), _free;	\
+	if (_head) {					\
+	    memcpy(_head, (_entry), sizeof(_entry));	\
+	    _free = (_entry);				\
+	    (_entry) = (_entry)->next;			\
+	    kfree(_free);				\
+	    _head->next = _head;			\
+	    _head;					\
+	} else						\
+	    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, overly complicated but working

[Nikita Danilov]

Lightweight Patch Manager writes:
 > This is an overly complicated version,  I guess I'll have a better one
 > once I've got my noodles in. Wait an hour, I'll be back.
 > 
 > And BTW, I got the luckynet address fixed, you can send me again...
 > 
 > --- /dev/null	Wed Dec 31 17:00:00 1969
 > +++ slist-2.5/include/linux/slist.h	Thu Sep 26 09:57:25 2002
 > @@ -0,0 +1,139 @@
 > +#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 Bogk, Thunder from the hill
 > + */
 > +
 > +#define INIT_SLIST_HEAD(name)			\
 > +	(name->next = name)
 > +
 > +#define SLIST_HEAD_INIT(name)			\
 > +	name
 > +
 > +#define SLIST_HEAD(type,name)			\
 > +	typeof(type) name = INIT_SLIST_HEAD(name)
 > +
 > +/**
 > + * 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)

Can these macros be updated to only evaluate their arguments once? By
use of "typeof" maybe? Otherwise, slist_add_front(foo++, bar()) is going
to lead to strange things.

 > +
 > +/**
 > + * slist_add - add a new entry

[...]

Nikita.