On Thu, Sep 29, 2016 at 06:17:12PM -0400, Emilio G. Cota wrote: > AFAIK there's no "proper" (as in "same API as ccan/list") singly-linked > list implementation in CCAN. > > The appended is obviously incomplete (e.g. no debug, no deletions) but as is > it gives me a ~15% speedup when doing a BFS traversal of a large graph, whose > edges are represented as an adjacency list. > > - Should we have something like this? I tried adding a for_each macro to > lqueue but that was just too ugly to live. Yes, one could just use *next > pointers in the original code, but then there's no list_for_each, and > no trivial update path to a doubly-linked list should the need arise.
It depends a bit how much of the list interface can be duplicated. When I wrote lstack and lqueue, it was suggested I base them on a general singly linked list module. I investigated that, but got bogged down in the details of what the interface should be, and how much it could resemble the list interface. That's what I restricted myself to the more limited special purpose interfaces. But if you can pull it off, it would be a nice thing to have. > - If so, should it be a separate module, a submodule under list, or just > a header next to list.h? > I'm just dropping slist.h here due to laziness; I like the idea of having > both singly and doubly-linked list implementations under list/ though, > so that they can share code and are less likely be overlooked by > users. Interesting question. My first inclination would have been simply to have it as a separate module alongside list. But your suggestion of making it a list submodule is persuasive. > > Signed-off-by: Emilio G. Cota <c...@braap.org> > --- > ccan/list/slist.h | 195 > ++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 195 insertions(+) > create mode 100644 ccan/list/slist.h > > diff --git a/ccan/list/slist.h b/ccan/list/slist.h > new file mode 100644 > index 0000000..d0eae32 > --- /dev/null > +++ b/ccan/list/slist.h > @@ -0,0 +1,195 @@ > +/* Licensed under BSD-MIT - see LICENSE file for details */ > +#ifndef CCAN_SLIST_H > +#define CCAN_SLIST_H > +//#define CCAN_SLIST_DEBUG 1 > +#include <ccan/str/str.h> > +#include <ccan/container_of/container_of.h> > +#include <ccan/check_type/check_type.h> > + > +/** > + * struct slist_node - an entry in a singly-linked list > + * @next: next entry (self if empty) > + * > + * This is used as an entry in a singly-linked list. > + * Example: > + * struct child { > + * const char *name; > + * // Linked list of all us children. > + * struct slist_node slist; > + * }; > + */ > +struct slist_node { > + struct slist_node *next; > +}; > + > +/** > + * struct slist_head - the head of a singly-linked list > + * @h: the slist_head (containing next pointer) > + * > + * This is used as the head of a singly-linked list. > + * Example: > + * struct parent { > + * const char *name; > + * struct slist_head children; > + * unsigned int num_children; > + * }; > + */ > +struct slist_head { > + struct slist_node n; > +}; > + > +#define SLIST_LOC __FILE__ ":" stringify(__LINE__) > +#ifdef CCAN_SLIST_DEBUG > +#define slist_debug(h, loc) slist_check((h), loc) > +#define slist_debug_node(n, loc) slist_check_node((n), loc) > +#else > +#define slist_debug(h, loc) ((void)loc, h) > +#define slist_debug_node(n, loc) ((void)loc, n) > +#endif > + > +/** > + * SLIST_HEAD_INIT - initializer for an empty slist_head > + * @name: the name of the slist. > + * > + * Explicit initializer for an empty slist. > + * > + * See also: > + * SLIST_HEAD, slist_head_init() > + * > + * Example: > + * static struct slist_head my_slist = SLIST_HEAD_INIT(my_slist); > + */ > +#define SLIST_HEAD_INIT(name) { { &(name).n } } > + > +/** > + * SLIST_HEAD - define and initialize an empty slist_head > + * @name: the name of the slist. > + * > + * The SLIST_HEAD macro defines a slist_head and initializes it to an empty > + * slist. It can be prepended by "static" to define a static slist_head. > + * > + * See also: > + * SLIST_HEAD_INIT, slist_head_init() > + * > + * Example: > + * static SLIST_HEAD(my_global_slist); > + */ > +#define SLIST_HEAD(name) \ > + struct slist_head name = SLIST_HEAD_INIT(name) > + > +/** > + * slist_head_init - initialize a slist_head > + * @h: the slist_head to set to the empty slist > + * > + * Example: > + * ... > + * struct parent *parent = malloc(sizeof(*parent)); > + * > + * slist_head_init(&parent->children); > + * parent->num_children = 0; > + */ > +static inline void slist_head_init(struct slist_head *h) > +{ > + h->n.next = &h->n; > +} > + > +/** > + * 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 list. > + * > + * 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->slist); > + * parent->num_children++; > + */ > +#define slist_add(h, n) slist_add_(h, n, SLIST_LOC) > +static inline void slist_add_(struct slist_head *h, > + struct slist_node *n, > + const char *abortstr) > +{ > + n->next = h->n.next; > + h->n.next = n; > +} > + > +/** > + * slist_for_each - iterate through a slist. > + * @h: the slist_head (warning: evaluated multiple times!) > + * @i: the structure containing the slist_node > + * @member: the slist_node member of the structure > + * > + * This is a convenient wrapper to iterate @i over the entire slist. It's > + * a for loop, so you can break and continue as normal. > + * > + * Example: > + * slist_for_each(&parent->children, child, slist) > + * printf("Name: %s\n", child->name); > + */ > +#define slist_for_each(h, i, member) \ > + slist_for_each_off(h, i, slist_off_var_(i, member)) > + > +/** > + * slist_for_each_off - iterate through a slist of memory regions. > + * @h: the slist_head > + * @i: the pointer to a memory region wich contains slist node data. > + * @off: offset(relative to @i) at which slist node data resides. > + * > + * This is a low-level wrapper to iterate @i over the entire slist, used to > + * implement all oher, more high-level, for-each constructs. It's a for loop, > + * so you can break and continue as normal. > + * > + * WARNING! Being the low-level macro that it is, this wrapper doesn't know > + * nor care about the type of @i. The only assumption made is that @i points > + * to a chunk of memory that at some @offset, relative to @i, contains a > + * properly filled `struct slist_node' which in turn contains pointers to > + * memory chunks and it's turtles all the way down. With all that in mind > + * remember that given the wrong pointer/offset couple this macro will > + * happily churn all you memory untill SEGFAULT stops it, in other words > + * caveat emptor. > + * > + * It is worth mentioning that one of legitimate use-cases for that wrapper > + * is operation on opaque types with known offset for `struct slist_node' > + * member(preferably 0), because it allows you not to disclose the type of > + * @i. > + * > + * Example: > + * slist_for_each_off(&parent->children, child, > + * offsetof(struct child, slist)) > + * printf("Name: %s\n", child->name); > + */ > +#define slist_for_each_off(h, i, off) > \ > + for (i = slist_node_to_off_(slist_debug(h, SLIST_LOC)->n.next, \ > + (off)); \ > + slist_node_from_off_((void *)i, (off)) != &(h)->n; \ > + i = slist_node_to_off_(slist_node_from_off_((void *)i, \ > + (off))->next, (off))) > + > +/* Offset helper functions so we only single-evaluate. */ > +static inline void *slist_node_to_off_(struct slist_node *node, size_t off) > +{ > + return (void *)((char *)node - off); > +} > +static inline struct slist_node *slist_node_from_off_(void *ptr, size_t off) > +{ > + return (struct slist_node *)((char *)ptr + off); > +} > + > +/* Get the offset of the member, but make sure it's a slist_node. */ > +#define slist_off_(type, member) \ > + (container_off(type, member) + \ > + check_type(((type *)0)->member, struct slist_node)) > + > +#define slist_off_var_(var, member) \ > + (container_off_var(var, member) + \ > + check_type(var->member, struct slist_node)) > + > +#if HAVE_TYPEOF > +#define slist_typeof(var) typeof(var) > +#else > +#define slist_typeof(var) void * > +#endif > + > +#endif /* CCAN_SLIST_H */ -- 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
signature.asc
Description: PGP signature
_______________________________________________ ccan mailing list ccan@lists.ozlabs.org https://lists.ozlabs.org/listinfo/ccan