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

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

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/

Hi,

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

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/

Hi,

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

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

Hi,

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

Hi,

	^^^^^^^^^^^^^^^ Ignore this

Thunder

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

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 )

Hi,

Thanks for copying me. That one almost got lost!

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

I'd prefer { .next = NULL; }

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

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

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)

Okay with me, except for the below reason.

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

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

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

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.

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.

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

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?

	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.

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

Hi,

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

Hi,

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

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

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

*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

Here we seem to agree, too ;)

 zach

No argument there.

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

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

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?