Re: [PATCH][2.5] Single linked lists for Linux, overly complicated

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Rik van Riel wrote:
> INIT_SLIST_HEAD still has the old behaviour...

I'm now after both behaviors...

#define INIT_SLIST_HEAD(name)                   \
        (name->next = NULL)

#define INIT_SLIST_LOOP(name)			\
	(name->next = name)

> > +#define slist_add_front(_new_in, _head_in)	\
> 
> > +#define slist_add(_new_in, _head_in)		\
> 
> These two seem to be exactly the same, surely you only need one ?

No, they're not.

(tab-width=8)

	slist_add
|-------------------------------|
| head		->	after	|
|				|
|	   new			|
|-------------------------------|	new->next = head->next
| head		->	after	|
|			  ^	|
|			 new	|
|-------------------------------|	head->next = new
| head	-> new	->	after	|
|-------------------------------|

	slist_add_front
|-------------------------------|
| head		->	after	|
|				|
|	   new			|
|-------------------------------|	new->next = head
| new	-> head ->	after	|
|-------------------------------|	head = new
| head	-> next	->	after	|
|-------------------------------|

(Just to have something drawn...)

> > +#define slist_del(_entry_in)				\
> 
> And what happens when you try to remove an entry from the middle
> of the list ?

Well, I can only try to preserve the pointer target, since I don't have a 
previous entry. (Thus the overly complicated slist_del.)

> Also, how do you know which list the entry is removed from ?

It's the one which previously contained it...

I don't know whether I should like the list header aproach.

It's not bad for either circular lists or such which will have to be gone 
through only once, as using slist_pop().

> Not having the head of the list in a known place (ie. a fixed
> list head) can make a list very hard to find.

But you see we have the problem that there is no such thing as a 
predeclared structure for it. The only thing we can rely on is a chain of 
structures which alltogether have a ->next field pointing to another 
structure of presumably the same type.

> You forgot to rename this define.

Yes, I've forgotten two things there. They are fixed in my file, which I 
won't post right now (in order not to pollute the list too much with 
patches. It's that fix plus a forgotten _in.)

> > If you have any objections (apart from who I am), tell me
>                               ^^^^^^^^^^^^^^^^^^^
> I guess that's why we have whois ;)

Oh, that was just for Jes Soerensen, who kept asking.

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