[ccan] [PATCH 1/4] queue: Simple queue implementation

David Gibson david at gibson.dropbear.id.au
Wed Jul 16 01:23:39 EST 2014


On Sun, Jul 13, 2014 at 10:21:29PM +0930, Paul 'Rusty' Russell wrote:
> David Gibson <david at gibson.dropbear.id.au> writes:
> > On Tue, Jul 08, 2014 at 08:20:38PM +0930, Paul 'Rusty' Russell wrote:
> >> Cody P Schafer <dev at codyps.com> writes:
> >> > On Mon, Jul 7, 2014 at 8:51 AM, David Gibson
> >> > <david at gibson.dropbear.id.au> wrote:
> >> >> This new module provides a simple queue implementation as a singly linked
> >> >> (circular) list.
> >> >>
> >> >> Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
> >> >
> >> > I've been looking for a singly-linked list for places where I don't
> >> > necessarily need a doubly linked one (as provided by ccan/list).
> >> 
> >> Yes, an slist module is a tempting thought.  At risk of making David
> >> rewrite everything :)
> >
> > Yeah.. I am tempted to say "patches welcome" to that...
> 
> Always a good idea!  Here's my first cut of slist-like-list.h.
> 
> I'm not entirely happy with the result.  A single linked list
> implemented as a head-including chain is quite limited.  If you
> implement it as a pointer to the tail of a ring of nodes, you can
> view the tail and append to the list, but there are more branches
> since you have to test for NULL in the empty case...

Yeah, this is the thing.  Of all the variants of a doubly linked list,
the version used in list.h is a moderately clear winner.  It does all
the operations of the other variants, with very few tradeoffs in
either performance, space usage, or ugliness.

For singly linked lists it's a lot murkier.  You can't (efficiently)
implement all the obvious operations for an abstract ordered list, so
you have to chose which ones make sense.  Stack and queue are both
easily implemented, but the natural approaches don't give you the same
list structure.  And stack is so simple that it's barely worth
wrapping the pointer manipulations at all.

That's kind of why I decided to just implement a module with the queue
operations emphasised, rather than trying to make a more general
singly linked list.

[snip]
> +/**
> + * slist_add - add an entry at the start of a linked list.
> + * @h: the slist_head to add the node to
> + * @n: the slist_node to add to the slist.
> + *
> + * The slist_node does not need to be initialized; it will be overwritten.
> + * Example:
> + *	struct child *child = malloc(sizeof(*child));
> + *
> + *	child->name = "marvin";
> + *	slist_add(&parent->children, &child->list);
> + *	parent->num_children++;
> + */
> +#define slist_add(h, n) slist_add_(h, n, SLIST_LOC)

So, you have add at start, but not add at end, which you need for a
queue.

[snip]
> +/**
> + * slist_pop - remove the first entry in a list
> + * @h: the slist_head
> + * @type: the type of the entry
> + * @member: the slist_node member of the type
> + *
> + * If the list is empty, returns NULL.
> + *
> + * Example:
> + *	struct child *one;
> + *	one = slist_pop(&parent->children, struct child, list);
> + *	if (!one)
> + *		printf("Empty list!\n");
> + */
> +#define slist_pop(h, type, member)					\
> +	((type *)slist_pop_((h), slist_off_(type, member)))

pop without push is a bit odd, even though push would just be an alias
for add.

[snip]

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20140716/619afaa7/attachment.sig>


More information about the ccan mailing list