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

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

[Thunder from the hill]

Hi,

My point is:

We don't know the parent structure. We shouldn't know it, since it takes
time. So I try to keep the address pointer stable instead of just
exchanging pointers.

That's why I'm exchanging pointers, and that's also why slist_del()
currently returns a value: because the deleted list entry would otherwise
be lost in space...

If any applicator needs to know a list header (primer), he shall produce
one and pass the first entry after the primer. We should only depend on
one single facility: the next field of the handled structure.

Also notice that we can restart list_for_each*() from any position.

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

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

[Rik van Riel]

On Thu, 26 Sep 2002, Thunder from the hill wrote:

> We don't know the parent structure. We shouldn't know it, since it takes
> time. So I try to keep the address pointer stable instead of just
> exchanging pointers.

In the case of slist_del() you HAVE to know it.

Think about removing a single entry from the middle of
the list ... the entries before and after need to stay
on the list.

Rik
-- 
A: No.
Q: Should I include quotations after my reply?

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

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

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Rik van Riel wrote:
> On Thu, 26 Sep 2002, Thunder from the hill wrote:
> In the case of slist_del() you HAVE to know it.
> 
> Think about removing a single entry from the middle of
> the list ... the entries before and after need to stay
> on the list.

2 solutions without list head:

1.
#define slist_del_next(_entry_in)			\
do {							\
	typeof(_entry_in) _entry = (_entry_in),		\
			  _next  = (_entry)->next;	\
	_entry->next = _next->next;			\
	_next->next = NULL;				\
} while (0)

2.	The previous entry points to the address that _entry has. If we 
	copy _entry somewhere else and overwrite the old _entry with 
	_entry->next, we made it without knowing the list topology. The 
	previous->next still points to the new _entry, things are fine.

My problem is just: where to put the old _entry? Anyway, since we're 
talking about list entry deletion, we could copy it nowhere and just 
overwrite it with _entry->next...

Details, details...

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

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

[David B. Stevens]

Rik,

I respectfully disagree, it is well known that systems are far more 
stable when running on empty lists, routines like this get us there faster.

Cheers,
   Dave

PS:Is it April in September?



Rik van Riel wrote:
> On Thu, 26 Sep 2002, Thunder from the hill wrote:
> 
> 
>>We don't know the parent structure. We shouldn't know it, since it takes
>>time. So I try to keep the address pointer stable instead of just
>>exchanging pointers.
> 
> 
> In the case of slist_del() you HAVE to know it.
> 
> Think about removing a single entry from the middle of
> the list ... the entries before and after need to stay
> on the list.
> 
> Rik

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

[Rik van Riel]

On Thu, 26 Sep 2002, Thunder from the hill wrote:
> On Thu, 26 Sep 2002, Rik van Riel wrote:
> > On Thu, 26 Sep 2002, Thunder from the hill wrote:
> > In the case of slist_del() you HAVE to know it.
> >
> > Think about removing a single entry from the middle of
> > the list ... the entries before and after need to stay
> > on the list.
>
> 2 solutions without list head:

Have you thought about how to _use_ a list without a list head ?

How are you going to find the list ?

regards,

Rik
-- 
A: No.
Q: Should I include quotations after my reply?

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

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

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Rik van Riel wrote:
> Have you thought about how to _use_ a list without a list head ?

Indeed, that was why I've brought this up at all...

> How are you going to find the list ?

As mentioned: either you keep a primer around, or you have some list entry 
that's getting changed all over while using list_pop(), or you have a 
circular list where you only need to keep one entry around.

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

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

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Rik van Riel wrote:
> > > In the case of slist_del() you HAVE to know it.

What about

/**
 * slist_del -  remove an entry from list
 * @buf:        a storage area, just as long as the entry
 * @entry:      entry to be removed
 */
#define slist_del(_entry_in,_buf)			\
do {							\
	typeof(_entry_in) _entry = (_entry_in),		\
			  _head = (_buf), _free;	\
	memcpy(_head, _entry, sizeof(_entry));		\
	_free = _entry;					\
	_entry = _entry->next;				\
	_head->next = NULL;				\
	(_buf) = _head;					\
} while (0)

?

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

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

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Thunder from the hill wrote:
> /**
>  * slist_del -  remove an entry from list
>  * @buf:        a storage area, just as long as the entry
>  * @entry:      entry to be removed
>  */
> #define slist_del(_entry_in,_buf)			\
> do {							\
> 	typeof(_entry_in) _entry = (_entry_in),		\
> 			  _head = (_buf), _free;	\
> 	memcpy(_head, _entry, sizeof(_entry));		\
> 	_free = _entry;					\
> 	_entry = _entry->next;				\
> 	_head->next = NULL;				\
> 	(_buf) = _head;					\
	^^^^^^^^^^^^^^^ Ignore this
> } while (0)


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

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

[Zach Brown]

> My problem is just: where to put the old _entry? Anyway, since we're 
> talking about list entry deletion, we could copy it nowhere and just 
> overwrite it with _entry->next...

honestly, I think if you're contemplating this kind of thing, you've
gone too far with the design.  it should be dirt friggin simple', like
what wli posted a while ago with struct list.  if you need more, you
really should just use list_head and be done with it.  (restartable list
walking?  why did you stop walking in the first place?  oh, you didn't
mean restartable, you meant able to start walking at an arbitrary
position?  back to list_head.. )

Here's something I'd consider using if it were in the kernel.  if others
agree, I can finalize and submit it.

( yeah, a lot of it is stinky, like the requirement that users magically
have the right member in their structs.  I have no deep love for the
interface.  at least this passes basic usage tests..)

#define TSLIST_DECLARE(type, name) 		\
	type *name = NULL

#define TSLIST_MEMBER_INIT(member) 		\
	NULL

#define INIT_TSLIST_MEMBER(member) 		\
	do {					\
		(member)->_slist_next = NULL;	\
	} while (0)

#define tslist_on_list(_head,_elem) 		\
	( (_elem)->_slist_next != NULL || _head == _elem )

#define tslist_push tslist_add

#define tslist_add(_head, _elem) 			\
	do {  						\
		BUG_ON(tslist_on_list(_head, _elem));	\
		(_elem)->_slist_next = (_head);		\
		(_head) = (_elem);			\
	} while(0)

#define tslist_pop(_head)					\
	({							\
	 	typeof(_head) _ret = _head;			\
		if ( _head ) {					\
			_ret = _head;				\
			_head = _head->_slist_next;		\
			_ret->_slist_next = NULL;		\
		}						\
		_ret;						\
	})

#define __tslist_walk_del(_start, _elem)			\
	do {							\
		typeof(_start) _pos, _prev = _start;		\
		for (; _prev && (_pos = _prev->_slist_next) ;	\
			_prev = _pos ) {			\
			if ( _pos != _elem )			\
				continue;			\
			_prev->_slist_next = (_elem)->_slist_next;\
			(_elem)->_slist_next = NULL;		\
			break;					\
		}						\
	} while (0)
		

#define tslist_del(_head, _elem) 					\
	do {  								\
		if ( _head == _elem ) {					\
			_head = (_elem)->_slist_next;			\
			(_elem)->_slist_next = NULL;			\
		} else {						\
			__tslist_walk_del(_head, _elem);		\
		}							\
	} while (0)

#define tslist_for_each(_pos, _head)				\
	for ( _pos = _head ; _pos ; _pos = _pos->_slist_next )

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

[Thunder from the hill]

Hi,

Thanks for copying me. That one almost got lost!

On Thu, 26 Sep 2002, Zach Brown wrote:
> #define TSLIST_DECLARE(type, name) 		\
> 	type *name = NULL

OK, but I'd rather use typeof() which enhances possibilities. (Imagine 
code which wouldn't know the type of something arbitrary passed.)

> #define TSLIST_MEMBER_INIT(member) 		\
> 	NULL

I'd prefer { .next = NULL; }

> #define INIT_TSLIST_MEMBER(member) 		\
> 	do {					\
> 		(member)->_slist_next = NULL;	\
> 	} while (0)

I'd still prefer calling the field ->next.

> #define tslist_on_list(_head,_elem) 		\
> 	( (_elem)->_slist_next != NULL || _head == _elem )

That doesn't give me whether the elem is on _that_ list.

> #define tslist_add(_head, _elem) 			\
> 	do {  						\
> 		BUG_ON(tslist_on_list(_head, _elem));	\
> 		(_elem)->_slist_next = (_head);		\
> 		(_head) = (_elem);			\
> 	} while(0)

That's adding to front. One should be aware of that. The other add is

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

> #define tslist_pop(_head)					\
> 	({							\
> 	 	typeof(_head) _ret = _head;			\
> 		if ( _head ) {					\
> 			_ret = _head;				\
> 			_head = _head->_slist_next;		\
> 			_ret->_slist_next = NULL;		\
> 		}						\
> 		_ret;						\
> 	})

Okay with me, except for the below reason.

> #define __tslist_walk_del(_start, _elem)			\
> 	do {							\
> 		typeof(_start) _pos, _prev = _start;		\
> 		for (; _prev && (_pos = _prev->_slist_next) ;	\
> 			_prev = _pos ) {			\
> 			if ( _pos != _elem )			\
> 				continue;			\
> 			_prev->_slist_next = (_elem)->_slist_next;\
> 			(_elem)->_slist_next = NULL;		\
> 			break;					\
> 		}						\
> 	} while (0)

This looks overly complicated. Why not something like while, but this 
weird for construct?

> #define tslist_del(_head, _elem) 					\
> 	do {  								\
> 		if ( _head == _elem ) {					\
> 			_head = (_elem)->_slist_next;			\
> 			(_elem)->_slist_next = NULL;			\
> 		} else {						\
> 			__tslist_walk_del(_head, _elem);		\
> 		}							\
> 	} while (0)

OK with me, I'll apply it to my version. Coming soon.

> #define tslist_for_each(_pos, _head)				\
> 	for ( _pos = _head ; _pos ; _pos = _pos->_slist_next )

That lacks the prefetch feature at all.

The issue overall is that you still evaluate the arguments more than once. 
That's what Nikita mentioned: you might end up somewhere outlandish.

Wait -- I'll do that.

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

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

[Zach Brown]

> > #define TSLIST_MEMBER_INIT(member) 		\
> > 	NULL
> 
> I'd prefer { .next = NULL; }

that only works if you have a proper struct for the list members, not
magical pointers that are embedded in their definition.  (also, its
pretty unacceptable that if I have a singly linked list of buffer_heads
that I need to have an entire dummy buffer_head struct allocated to be
the head.  this incongruity is what creates the special casing of the
head as a type *point on its own, while the list members are type *
pointer members in type structs).  

the explicit struct is much cleaner (as wli's post shows) and the member
approach allows hand-wavey macrosy type safety while only allowing a
particular struct to be on one list.

> I'd still prefer calling the field ->next.

arguments could be made about layering violations: that the member
name should really scream out that its going to be magically used by
macros deep in include/ somewhere.

> > #define tslist_on_list(_head,_elem) 		\
> > 	( (_elem)->_slist_next != NULL || _head == _elem )
> 
> That doesn't give me whether the elem is on _that_ list.

no, it doesn't.  it isn't meant to.

> That's adding to front. One should be aware of that. The other add is
> 
> #define slist_add(_new_in, _head_in)            \
> do {                                            \
>         typeof(_head_in) _head = (_head_in),    \
>                     _new = (_new_in);           \
>         _new->next = _head->next;               \
>         _head->next = _new;                     \
> } while (0)

which is a degenerate case of slist_add_pos(), which is more
complication than this trivial implementation needs.  have you looked at other
single linked list implementations?  like glib's?  do you really think
we need that in the kernel?

> > #define __tslist_walk_del(_start, _elem)			\
> > 	do {							\
> > 		typeof(_start) _pos, _prev = _start;		\
> > 		for (; _prev && (_pos = _prev->_slist_next) ;	\
> > 			_prev = _pos ) {			\
> > 			if ( _pos != _elem )			\
> > 				continue;			\
> > 			_prev->_slist_next = (_elem)->_slist_next;\
> > 			(_elem)->_slist_next = NULL;		\
> > 			break;					\
> > 		}						\
> > 	} while (0)
> 
> This looks overly complicated. Why not something like while, but this 
> weird for construct?

	while (A) {
		...
		B;
	}

	for ( ; A ; B ) {
	}

some people prefer to have the loop terminating invariant explicitly
expressed in the for() construct so that it isn't overlooked.  perhaps you
don't.

> That lacks the prefetch feature at all.
> 
> The issue overall is that you still evaluate the arguments more than once. 
> That's what Nikita mentioned: you might end up somewhere outlandish.

yes, both of these are mechanical refinements that don't change the API
at all.  they can wait until people have actually expressed interest in
this thing being in the kernel.  has anyone expressed real interest?

but really, as I realized the single membership limitation of this api,
it became clear to me that its too limited.  if you want to persue this,
move to the very simple struct list proposal that wli did.    

- z

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

[Thunder from the hill]

Hi,

On Fri, 27 Sep 2002, Zach Brown wrote:
> > That's adding to front. One should be aware of that. The other add is
> > 
> > #define slist_add(_new_in, _head_in)            \
> > do {                                            \
> >         typeof(_head_in) _head = (_head_in),    \
> >                     _new = (_new_in);           \
> >         _new->next = _head->next;               \
> >         _head->next = _new;                     \
> > } while (0)
> 
> which is a degenerate case of slist_add_pos(), which is more
> complication than this trivial implementation needs.  have you looked at
> other single linked list implementations?  like glib's?  do you really
> think we need that in the kernel?

Where is this complicated? I don't even have one more line than the other. 
There are two positions relative to the head where we can put the list 
members, one of which is before, the other is after.

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

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

[Thunder from the hill]

Hi,

On Thu, 26 Sep 2002, Zach Brown wrote:
> #define TSLIST_MEMBER_INIT(member) 		\
> 	NULL

My problem with this is that you could initialize anything with it, 
without even getting the notice. That's why I've preferred the named 
initializer version. I could even do

#define SLIST_HEAD_INIT(name)			\
	.next = NULL;

if you like that better, and yes, I guess it should be...

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

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

[Daniel Phillips]

On Friday 27 September 2002 02:57, Zach Brown wrote:
> #define tslist_add(_head, _elem) 			\
> 	do {  						\
> 		BUG_ON(tslist_on_list(_head, _elem));	\
> 		(_elem)->_slist_next = (_head);		\
> 		(_head) = (_elem);			\
> 	} while(0)

This evaluates _head and _elem twice each, or three times if you count
the BUG_ON.

Smaller point: why bother obfuscating the parameter names?  You will
need to do that for locals in macros but parameters should cause no
name conflicts.

-- 
Daniel

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

[Zach Brown]

> On Friday 27 September 2002 02:57, Zach Brown wrote:
> > #define tslist_add(_head, _elem) 			\
> > 	do {  						\
> > 		BUG_ON(tslist_on_list(_head, _elem));	\
> > 		(_elem)->_slist_next = (_head);		\
> > 		(_head) = (_elem);			\
> > 	} while(0)
> 
> This evaluates _head and _elem twice each, or three times if you count
> the BUG_ON.

yes, I wss saving that trivial fix for later. (its a little less trivial
in the presence of bare struct * heads, rather than full struct
instances, but still just language mechanics.)

> Smaller point: why bother obfuscating the parameter names?  You will
> need to do that for locals in macros but parameters should cause no
> name conflicts.

*shrug*  either way is fine with me.

but really, I think these are DOA.  having to define a single magical
structure member makes these more trouble than they're worth.  I've come
to prefer wli's 'struct list' approach.  It has the added benefit of
actually being sanely implementable with shared code, something
ridiculously low memory setups might appreciate.  the deltion walking
function might actually be bugger than the function-calling code
overhead :)

- z

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

[Zach Brown]

> full.  Yes, the fact that you can't sanely generalize these things shows
> that C as a language falls a few cards short of a full deck, but we knew
> that.  It makes nice kernels, it does not make art.

Here we seem to agree, too ;)

-- 
 zach

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

[Daniel Phillips]

On Monday 30 September 2002 22:04, Zach Brown wrote:
> but really, I think these are DOA.

No argument there.

> having to define a single magical
> structure member makes these more trouble than they're worth.  I've come
> to prefer wli's 'struct list' approach.  It has the added benefit of
> actually being sanely implementable with shared code, something
> ridiculously low memory setups might appreciate.

Have you tried it in a real program?  I have.  It's not nice to use.
My original response to Bill:

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

Single linked lists are so simple - just write the darn code out in
full.  Yes, the fact that you can't sanely generalize these things shows
that C as a language falls a few cards short of a full deck, but we knew
that.  It makes nice kernels, it does not make art.

-- 
Daniel

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

[Daniel Phillips]

> What is the problem these lists are intended to solve?

That's what I kept asking myself when I wrote the orginal push/pop
macros.  My conclusion was that there is no worthwhile expression of
these things in C.  Writing those macros was just something I had
to do so I could wallow in the ugliness and stop thinking "maybe
these things should be generic".

-- 
Daniel

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

[Thunder from the hill]

Hi,

On Fri, 27 Sep 2002, Peter Chubb wrote:
> What is the problem these lists are intended to solve?

Reduction of effort in the place where we only have single-direction 
lists, such as stacks and the scheduler. (That is, whereever we don't need 
to step back.)

> There's no point in adding general infrastructure that has no immediate
> uses -- it just ends up mouldering in a corner, (like the generic
> hashing code linux/ghash.h which has been in the kernel for 4 or 5
> years, and still has *no* uses.)

Wasn't it already removed?

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

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

[Arnaldo Carvalho de Melo]

Em Fri, Sep 27, 2002 at 01:56:28PM +1000, Peter Chubb escreveu:
> (like the generic hashing code linux/ghash.h which has been in the
> kernel for 4 or 5 years, and still has *no* uses.)

Hey, submit a patch removing this stuff then. If not I'll bite the bullet check
it and do it myself :-)

- Arnaldo

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

[Peter Chubb]

>>>>> "Thunder" == Thunder from the hill <thunder@lightweight.ods.org> writes:

Thunder> Hi, On Thu, 26 Sep 2002, Rik van Riel wrote:
>> Have you thought about how to _use_ a list without a list head ?

Thunder> Indeed, that was why I've brought this up at all...

What is the problem these lists are intended to solve?

There's no point in adding general infrastructure that has no
immediate uses -- it just ends up mouldering in a corner,
(like the generic hashing code linux/ghash.h which has been in the
kernel for 4 or 5 years, and still has *no* uses.)

--
Dr Peter Chubb				    peterc@gelato.unsw.edu.au
You are lost in a maze of BitKeeper repositories, all almost the same.

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

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

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

[Rik van Riel]

On Thu, 26 Sep 2002, Andreas Räcker wrote:

> +#define INIT_SLIST_HEAD(name)			\
> +	(name->next = name)
> +
> +#define SLIST_HEAD_INIT(name)			\
> +	{ .next = NULL; }
> +
> +#define SLIST_HEAD(type,name)			\
> +	typeof(type) name = SLIST_HEAD_INIT(name)

INIT_SLIST_HEAD still has the old behaviour...


> +#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 ?


> +#define slist_del(_entry_in)				\

And what happens when you try to remove an entry from the middle
of the list ?

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

> +/**
> + * 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)

Are you sure the list head _can_ be the first entry ?

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

> +/**
> + * slist_for_each_round	-	iterate over a round 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)			\

You forgot to rename this define.

> --
> Lightweight Patch Manager, without pine.
> If you have any objections (apart from who I am), tell me
                              ^^^^^^^^^^^^^^^^^^^
I guess that's why we have whois ;)

cheers,

Rik
-- 
A: No.
Q: Should I include quotations after my reply?

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

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

[Lightweight Patch Manager]

This time  I've taken care of  the various comments.  It's not exactly
been cool, but I saw where  my details conflicted. NULL is supposed to
be NULL.

One more for: slist_for_each_round()

slist_del*()  is still  overly complicated.  Shall I  resume  the easy
version of it?

--- /dev/null	Wed Dec 31 17:00:00 1969
+++ slist-2.5/include/linux/slist.h	Thu Sep 26 11:34:55 2002
@@ -0,0 +1,154 @@
+#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)			\
+	{ .next = NULL; }
+
+#define SLIST_HEAD(type,name)			\
+	typeof(type) name = SLIST_HEAD_INIT(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_in, _head_in)	\
+do {						\
+	typeof(_head_in) _head = _head_in,	\
+		    _new = _new_in;		\
+	_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_in, _head_in)		\
+do {						\
+	typeof(_head_in) _head = (_head_in),	\
+		    _new = (_new_in);		\
+	_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_in)				\
+({							\
+	typeof(_entry_in) _entry = (_entry_in), _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_in) _entry = (_entry_in), _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_in) ({			\
+	typeof(_list_in) _list = (_list_in),	\
+		    _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_round	-	iterate over a round 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 && pos != head &&		\
+	    ({ 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