X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Flist%2Flist.h;h=5c9aa2a689ca38af5a03c5c7c928381bf7b3c443;hp=5b4f81c965725d473f7cfc6df52812c21fc7cfc4;hb=578da7e7b6265153fa0519035fc52a086a711ac0;hpb=f940ee9ccd07eb8821dcbd7a31b5374e38a4c16b;ds=sidebyside diff --git a/ccan/list/list.h b/ccan/list/list.h index 5b4f81c9..5c9aa2a6 100644 --- a/ccan/list/list.h +++ b/ccan/list/list.h @@ -1,7 +1,10 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ #ifndef CCAN_LIST_H #define CCAN_LIST_H #include +#include #include +#include /** * struct list_node - an entry in a doubly-linked list @@ -94,17 +97,34 @@ struct list_node *list_check_node(const struct list_node *n, #endif /** - * LIST_HEAD - define and initalize an empty list_head + * LIST_HEAD_INIT - initializer for an empty list_head + * @name: the name of the list. + * + * Explicit initializer for an empty list. + * + * See also: + * LIST_HEAD, list_head_init() + * + * Example: + * static struct list_head my_list = LIST_HEAD_INIT(my_list); + */ +#define LIST_HEAD_INIT(name) { { &name.n, &name.n } } + +/** + * LIST_HEAD - define and initialize an empty list_head * @name: the name of the list. * * The LIST_HEAD macro defines a list_head and initializes it to an empty * list. It can be prepended by "static" to define a static list_head. * + * See also: + * LIST_HEAD_INIT, list_head_init() + * * Example: * static LIST_HEAD(my_global_list); */ #define LIST_HEAD(name) \ - struct list_head name = { { &name.n, &name.n } } + struct list_head name = LIST_HEAD_INIT(name) /** * list_head_init - initialize a list_head @@ -164,9 +184,30 @@ static inline void list_add_tail(struct list_head *h, struct list_node *n) } /** - * list_del - delete an entry from a linked list. + * list_empty - is a list empty? + * @h: the list_head + * + * If the list is empty, returns true. + * + * Example: + * assert(list_empty(&parent->children) == (parent->num_children == 0)); + */ +static inline bool list_empty(const struct list_head *h) +{ + (void)list_debug(h); + return h->n.next == &h->n; +} + +/** + * list_del - delete an entry from an (unknown) linked list. * @n: the list_node to delete from the list. * + * Note that this leaves @n in an undefined state; it can be added to + * another list, but not deleted again. + * + * See also: + * list_del_from() + * * Example: * list_del(&child->list); * parent->num_children--; @@ -183,18 +224,33 @@ static inline void list_del(struct list_node *n) } /** - * list_empty - is a list empty? - * @h: the list_head + * list_del_from - delete an entry from a known linked list. + * @h: the list_head the node is in. + * @n: the list_node to delete from the list. * - * If the list is empty, returns true. + * This explicitly indicates which list a node is expected to be in, + * which is better documentation and can catch more bugs. + * + * See also: list_del() * * Example: - * assert(list_empty(&parent->children) == (parent->num_children == 0)); + * list_del_from(&parent->children, &child->list); + * parent->num_children--; */ -static inline bool list_empty(const struct list_head *h) +static inline void list_del_from(struct list_head *h, struct list_node *n) { - (void)list_debug(h); - return h->n.next == &h->n; +#ifdef CCAN_LIST_DEBUG + { + /* Thorough check: make sure it was in list! */ + struct list_node *i; + for (i = h->n.next; i != n; i = i->next) + assert(i != &h->n); + } +#endif /* CCAN_LIST_DEBUG */ + + /* Quick test that catches a surprising number of bugs. */ + assert(!list_empty(h)); + list_del(n); } /** @@ -224,8 +280,15 @@ static inline bool list_empty(const struct list_head *h) * struct child *first; * first = list_top(&parent->children, struct child, list); */ -#define list_top(h, type, member) \ - (list_empty(h) ? NULL : list_entry((h)->n.next, type, member)) +#define list_top(h, type, member) \ + ((type *)list_top_((h), list_off_(type, member))) + +static inline const void *list_top_(const struct list_head *h, size_t off) +{ + if (list_empty(h)) + return NULL; + return (const char *)h->n.next - off; +} /** * list_tail - get the last entry in a list @@ -240,11 +303,18 @@ static inline bool list_empty(const struct list_head *h) * last = list_tail(&parent->children, struct child, list); */ #define list_tail(h, type, member) \ - (list_empty(h) ? NULL : list_entry((h)->n.prev, type, member)) + ((type *)list_tail_((h), list_off_(type, member))) + +static inline const void *list_tail_(const struct list_head *h, size_t off) +{ + if (list_empty(h)) + return NULL; + return (const char *)h->n.prev - off; +} /** * list_for_each - iterate through a list. - * @h: the list_head + * @h: the list_head (warning: evaluated multiple times!) * @i: the structure containing the list_node * @member: the list_node member of the structure * @@ -260,6 +330,24 @@ static inline bool list_empty(const struct list_head *h) &i->member != &(h)->n; \ i = container_of_var(i->member.next, i, member)) +/** + * list_for_each_rev - iterate through a list backwards. + * @h: the list_head + * @i: the structure containing the list_node + * @member: the list_node member of the structure + * + * This is a convenient wrapper to iterate @i over the entire list. It's + * a for loop, so you can break and continue as normal. + * + * Example: + * list_for_each_rev(&parent->children, child, list) + * printf("Name: %s\n", child->name); + */ +#define list_for_each_rev(h, i, member) \ + for (i = container_of_var(list_debug(h)->n.prev, i, member); \ + &i->member != &(h)->n; \ + i = container_of_var(i->member.prev, i, member)) + /** * list_for_each_safe - iterate through a list, maybe during deletion * @h: the list_head @@ -283,4 +371,10 @@ static inline bool list_empty(const struct list_head *h) nxt = container_of_var(i->member.next, i, member); \ &i->member != &(h)->n; \ i = nxt, nxt = container_of_var(i->member.next, i, member)) + +/* Get the offset of the member, but make sure it's a list_node. */ +#define list_off_(type, member) \ + (container_off(type, member) + \ + check_type(((type *)0)->member, struct list_node)) + #endif /* CCAN_LIST_H */