Generic list push/pop

Generic list push/pop

[Daniel Phillips]

I took a run at writing generic single-linked list push and pop macros, to be 
used in the form:

	push_list(foo_list, foo_node);

and
	foo_node = pop_list(foo_list);

They came out predictably ugly:

#define push_list(_LIST_, _NODE_) \
	_NODE_->next = _LIST_; \
	_LIST_ =_NODE_;

#define pop_list(_LIST_) ({ \
	typeof(_LIST_) _NODE_ = _LIST_; \
	_LIST_ = _LIST_->next; \
	_NODE_; })

These work but imho, they are too ugly to live.  For one thing, they assume 
the link field is named 'next' and I don't see a nice way around that.
Before moving them to my scraps.c file I thought I'd let other people throw 
some tomatoes at them.

-- 
Daniel

Re: Generic list push/pop

[Thunder from the hill]

Hi,

On Sun, 18 Aug 2002, Daniel Phillips wrote:
> #define push_list(_LIST_, _NODE_) \
> 	_NODE_->next = _LIST_; \
> 	_LIST_ =_NODE_;
> 
> #define pop_list(_LIST_) ({ \
> 	typeof(_LIST_) _NODE_ = _LIST_; \
> 	_LIST_ = _LIST_->next; \
> 	_NODE_; })

How do we protect against:

push_list(getFuckingList(), node);
node_t node = pop_list(getFuckingList());

? Couldn't this break the _LIST_ = _LIST_->next; ?

JAQ...

			Thunder
-- 
--./../...-/. -.--/---/..-/.-./..././.-../..-. .---/..-/.../- .-
--/../-./..-/-/./--..-- ../.----./.-../.-.. --./../...-/. -.--/---/..-
.- -/---/--/---/.-./.-./---/.--/.-.-.-
--./.-/-.../.-./.././.-../.-.-.-

Re: Generic list push/pop

[Daniel Phillips]

On Sunday 18 August 2002 21:28, you wrote:
> Hi,
> 
> On Sun, 18 Aug 2002, Daniel Phillips wrote:
> > #define push_list(_LIST_, _NODE_) \
> > 	_NODE_->next = _LIST_; \
> > 	_LIST_ =_NODE_;
> > 
> > #define pop_list(_LIST_) ({ \
> > 	typeof(_LIST_) _NODE_ = _LIST_; \
> > 	_LIST_ = _LIST_->next; \
> > 	_NODE_; })
> 
> How do we protect against:
> 
> push_list(getFuckingList(), node);
> node_t node = pop_list(getFuckingList());
> 
> ? Couldn't this break the _LIST_ = _LIST_->next; ?

Yes, there are various sloppy things there, including missing parens
around args and missing wrapper around the statement.  It should also
be written to evaluate each arg exactly once.  With all that done it
will be even uglier but at least it will work reliably.

-- 
Daniel

Re: Generic list push/pop

[William Lee Irwin III]

On Sun, Aug 18, 2002 at 09:21:41PM +0200, Daniel Phillips wrote:
> I took a run at writing generic single-linked list push and pop macros, to be 
> used in the form:

Dear gawd, I've gone blind.

How's this look?


Cheers,
Bill


struct slist
{
	struct slist *next;
};


static inline void slist_add(struct slist *head, struct slist *elem)
{
	elem->next = head->next;
	head->next = elem;
}

#define slist_push(head, elem)	slist_add(head, elem)

static inline struct slist *slist_pop(struct slist *head)
{
	struct slist *elem = head->next;

	if (elem) {
		head->next = elem->next;
		elem->next = NULL;
	}
	return elem;
}

static inline int slist_remove(struct slist *head, struct slist *elem)
{
	struct slist *curr, *prev;

	for (prev = head, curr = head->next; curr; prev = curr, curr = curr->next)
		if (curr == head) {
			prev->next = curr->next;
			curr->next = NULL;
			return 1;
		}

	return 0;
}

Re: Generic list push/pop

[Daniel Phillips]

On Monday 19 August 2002 14:05, William Lee Irwin III wrote:
> On Sun, Aug 18, 2002 at 09:21:41PM +0200, Daniel Phillips wrote:
> > I took a run at writing generic single-linked list push and pop macros, to be 
> > used in the form:
> 
> Dear gawd, I've gone blind.
> 
> How's this look?

Unfortunately, not good.  You get code like:

	foo = (struct mylist *) slist_pop((slist *) &somelist->next);

So type safety goes out the window, and you gain some niceness in the
definition in exchange for ugliness in usage, the wrong tradeoff imho.

> struct slist
> {
> 	struct slist *next;
> };
> 
> 
> static inline void slist_add(struct slist *head, struct slist *elem)
> {
> 	elem->next = head->next;
> 	head->next = elem;
> }
> 
> #define slist_push(head, elem)	slist_add(head, elem)
> 
> static inline struct slist *slist_pop(struct slist *head)
> {
> 	struct slist *elem = head->next;
> 
> 	if (elem) {
> 		head->next = elem->next;
> 		elem->next = NULL;
> 	}
> 	return elem;
> }

-- 
Daniel

Re: Generic list push/pop

[Thunder from the hill]

Hi,

On Mon, 19 Aug 2002, William Lee Irwin III wrote:
> How's this look?

Doesn't solve the typeness. Anyway, this work had already been done by 
Thomas 'Dent' Mirlacher. We might want to work on that.

=== BEGIN INCLUDEDE MESSAGE ===
From:     "Thomas 'Dent' Mirlacher" <dent@cosy.sbg.ac.at>
To:       "Thunder from the hill" <thunder@ngforever.de>
Date:     2002-06-09 15:45:53
Subject:  [PATCH] adding slist.h: simple single-linked-list helper functions

hi,

this patch adds slist.h, a header-file providing simple single-linked-list
helper functions.

especially slist_for_each will improve:
	o readability
	o performance (due to the use of prefetch())
wherever it's used

please apply,

	tm

diff -Nru a/include/linux/slist.h b/include/linux/slist.h
--- /dev/null   Wed Dec 31 16:00:00 1969
+++ b/include/linux/slist.h     Sun Jun  9 22:32:55 2002
@@ -0,0 +1,57 @@
+#ifndef _LINUX_SLIST_H
+#define _LINUX_SLIST_H
+
+#if defined(__KERNEL__)
+
+#include <linux/prefetch.h>
+
+/*
+ * Simple single linked list helper-functions.
+ * (taken from list.h)
+ */
+
+/**
+ * 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->next;             \
+} 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.
+ */
+
+#define slist_add(_new, _head)         \
+do {                                   \
+       _new->next = _head->next;       \
+       _head->next = _new;             \
+} while (0)
+
+
+/**
+ * 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, prefetch(pos->next); pos; \
+               pos = pos->next, prefetch(pos->next))
+
+
+#endif /* __KERNEL__ */
+
+#endif

-- 
in some way i do, and in some way i don't.
=== END INCLUDED MESSAGE ===

			Thunder
-- 
--./../...-/. -.--/---/..-/.-./..././.-../..-. .---/..-/.../- .-
--/../-./..-/-/./--..-- ../.----./.-../.-.. --./../...-/. -.--/---/..-
.- -/---/--/---/.-./.-./---/.--/.-.-.-
--./.-/-.../.-./.././.-../.-.-.-

Re: Generic list push/pop

[Daniel Phillips]

On Tuesday 20 August 2002 15:08, Thunder from the hill wrote:
> ...Anyway, this work had already been done by 
> Thomas 'Dent' Mirlacher. We might want to work on that.
>
> [...]
>
> +#define slist_add_front(_new, _head)   \
> +do {                                   \
> +       _new->next = _head;             \
> +       _head = _new->next;             \
> +} while (0)

The second line is equivalent to _head = _head.

> +#define slist_add(_new, _head)         \
> +do {                                   \
> +       _new->next = _head->next;       \
> +       _head->next = _new;             \
> +} while (0)

I don't see the point of this.  Why doesn't the caller just push_list onto
head->next?

Anyway, since I went to the trouble of writing versions of push/pop_list
that at least avoid multiple argument evaluation, here they are in all their
glorious ugliness:

#define push_list(list, node) do { \
	typeof(list) *_LIST_ = &(list), _NODE_ = (node); \
	_NODE_->next = *_LIST_; \
	*_LIST_ = _NODE_; } while (0)

#define pop_list(list) ({ \
	typeof(list) *_LIST_ = &(list), _NODE_ = *_LIST_; \
	*_LIST_ = (*_LIST_)->next; \
	_NODE_; })

It's unecessary to obfuscate the macro parameter names.  On the other hand, 
if somebody passes in an expression that happens to contain one of the 
obfuscated local variable names, bad things will happen.  On the third hand, 
if somebody does that they probably need bad things to happen to them.

This problem arises only because of C's idiotic policy of entering the new 
local symbol before parsing the initializer, and there is nothing you can do 
about it[1] except to avoid using obfuscated variable names in normal code, 
and check carefully for nested obfuscated variables every time you write a 
macro.

The other problems with these constructions are:

  - How do we know gcc will successfully optimize these things to the
    same code you'd get if you simply wrote the two required assignments
    out in full?  The local variables should disappear early in constant 
    expression evaluation, but do they always?

  - We assume the link field is named 'next'.

  - They are ugly (but I don't care.  If you need to feast your eyes on
    ugly, look at any pgtable.h)

As promised, I moved them to my scraps.c and just wrote the code out in full.

[1] If we uniformly adopt the convention of encoding the name of the macro 
into any locals declared in macros, plus a convention to indicate the end of 
name, I suppose we could gaurantee uniqueness.  Or we can just keep muddling 
along as usual (more likely).

-- 
Daniel

Re: Generic list push/pop

[Thunder from the hill]

Hi,

On Tue, 20 Aug 2002, Daniel Phillips wrote:
> > +#define slist_add_front(_new, _head)   \
> > +do {                                   \
> > +       _new->next = _head;             \
> > +       _head = _new->next;             \
> > +} while (0)
> 
> The second line is equivalent to _head = _head.

I see. Is there something we'll need to do? Or is it just for the day?

> > +#define slist_add(_new, _head)         \
> > +do {                                   \
> > +       _new->next = _head->next;       \
> > +       _head->next = _new;             \
> > +} while (0)
> 
> I don't see the point of this.  Why doesn't the caller just push_list onto
> head->next?

Because we still want to keep up the old list? If _head->next was NULL, no 
matter, we've added. If not, we've just inserted.

> #define push_list(list, node) do { \
> 	typeof(list) *_LIST_ = &(list), _NODE_ = (node); \
> 	_NODE_->next = *_LIST_; \
> 	*_LIST_ = _NODE_; } while (0)
> 
> #define pop_list(list) ({ \
> 	typeof(list) *_LIST_ = &(list), _NODE_ = *_LIST_; \
> 	*_LIST_ = (*_LIST_)->next; \
> 	_NODE_; })

I'd rather call them push_slist, pop_slist (or as above). Think of the 
millions of innocent people mixing lists and lists...

> On the third hand, if somebody does that they probably need bad things
> to happen to them.

This is perfect evolution. You end up having better code-checking, and a 
third hand.

>   - How do we know gcc will successfully optimize these things to the
>     same code you'd get if you simply wrote the two required assignments
>     out in full?  The local variables should disappear early in constant 
>     expression evaluation, but do they always?

We shall have a look at the assembler output.

>   - We assume the link field is named 'next'.

Must be forced then. Is it really that bad?

>   - They are ugly (but I don't care.  If you need to feast your eyes on
>     ugly, look at any pgtable.h)

We shall comment on them to reduce uglyness.

Summary:
 - We shall do it
 - We shall force it
 - We shall consider using slist names.

			Thunder
-- 
--./../...-/. -.--/---/..-/.-./..././.-../..-. .---/..-/.../- .-
--/../-./..-/-/./--..-- ../.----./.-../.-.. --./../...-/. -.--/---/..-
.- -/---/--/---/.-./.-./---/.--/.-.-.-
--./.-/-.../.-./.././.-../.-.-.-