X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Flist%2Flist.h;h=90989c5fc04b6bd8436361dcda42f8f5f0ce7853;hp=3153d550824b9b8dd7940b02e4bb414cbffb2aa9;hb=0201703d51e85e5c3eeeef558176c1ed61369ad8;hpb=004098abe240de40e5c652b181bae92fd05f8a67 diff --git a/ccan/list/list.h b/ccan/list/list.h index 3153d550..90989c5f 100644 --- a/ccan/list/list.h +++ b/ccan/list/list.h @@ -1,8 +1,10 @@ /* Licensed under BSD-MIT - see LICENSE file for details */ #ifndef CCAN_LIST_H #define CCAN_LIST_H +//#define CCAN_LIST_DEBUG 1 #include #include +#include #include #include @@ -88,12 +90,13 @@ struct list_head *list_check(const struct list_head *h, const char *abortstr); struct list_node *list_check_node(const struct list_node *n, const char *abortstr); +#define LIST_LOC __FILE__ ":" stringify(__LINE__) #ifdef CCAN_LIST_DEBUG -#define list_debug(h) list_check((h), __func__) -#define list_debug_node(n) list_check_node((n), __func__) +#define list_debug(h, loc) list_check((h), loc) +#define list_debug_node(n, loc) list_check_node((n), loc) #else -#define list_debug(h) (h) -#define list_debug_node(n) (n) +#define list_debug(h, loc) (h) +#define list_debug_node(n, loc) (n) #endif /** @@ -142,6 +145,48 @@ static inline void list_head_init(struct list_head *h) h->n.next = h->n.prev = &h->n; } +/** + * list_node_init - initialize a list_node + * @n: the list_node to link to itself. + * + * You don't need to use this normally! But it lets you list_del(@n) + * safely. + */ +static inline void list_node_init(struct list_node *n) +{ + n->next = n->prev = n; +} + +/** + * list_add_after - add an entry after an existing node in a linked list + * @h: the list_head to add the node to (for debugging) + * @p: the existing list_node to add the node after + * @n: the new list_node to add to the list. + * + * The existing list_node must already be a member of the list. + * The new list_node does not need to be initialized; it will be overwritten. + * + * Example: + * struct child c1, c2, c3; + * LIST_HEAD(h); + * + * list_add_tail(&h, &c1.list); + * list_add_tail(&h, &c3.list); + * list_add_after(&h, &c1.list, &c2.list); + */ +#define list_add_after(h, p, n) list_add_after_(h, p, n, LIST_LOC) +static inline void list_add_after_(struct list_head *h, + struct list_node *p, + struct list_node *n, + const char *abortstr) +{ + n->next = p->next; + n->prev = p; + p->next->prev = n; + p->next = n; + (void)list_debug(h, abortstr); +} + /** * list_add - add an entry at the start of a linked list. * @h: the list_head to add the node to @@ -155,13 +200,40 @@ static inline void list_head_init(struct list_head *h) * list_add(&parent->children, &child->list); * parent->num_children++; */ -static inline void list_add(struct list_head *h, struct list_node *n) +#define list_add(h, n) list_add_(h, n, LIST_LOC) +static inline void list_add_(struct list_head *h, + struct list_node *n, + const char *abortstr) +{ + list_add_after_(h, &h->n, n, abortstr); +} + +/** + * list_add_before - add an entry before an existing node in a linked list + * @h: the list_head to add the node to (for debugging) + * @p: the existing list_node to add the node before + * @n: the new list_node to add to the list. + * + * The existing list_node must already be a member of the list. + * The new list_node does not need to be initialized; it will be overwritten. + * + * Example: + * list_head_init(&h); + * list_add_tail(&h, &c1.list); + * list_add_tail(&h, &c3.list); + * list_add_before(&h, &c3.list, &c2.list); + */ +#define list_add_before(h, p, n) list_add_before_(h, p, n, LIST_LOC) +static inline void list_add_before_(struct list_head *h, + struct list_node *p, + struct list_node *n, + const char *abortstr) { - n->next = h->n.next; - n->prev = &h->n; - h->n.next->prev = n; - h->n.next = n; - (void)list_debug(h); + n->next = p; + n->prev = p->prev; + p->prev->next = n; + p->prev = n; + (void)list_debug(h, abortstr); } /** @@ -174,13 +246,12 @@ static inline void list_add(struct list_head *h, struct list_node *n) * list_add_tail(&parent->children, &child->list); * parent->num_children++; */ -static inline void list_add_tail(struct list_head *h, struct list_node *n) +#define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC) +static inline void list_add_tail_(struct list_head *h, + struct list_node *n, + const char *abortstr) { - n->next = &h->n; - n->prev = h->n.prev; - h->n.prev->next = n; - h->n.prev = n; - (void)list_debug(h); + list_add_before_(h, &h->n, n, abortstr); } /** @@ -192,12 +263,34 @@ static inline void list_add_tail(struct list_head *h, struct list_node *n) * Example: * assert(list_empty(&parent->children) == (parent->num_children == 0)); */ -static inline bool list_empty(const struct list_head *h) +#define list_empty(h) list_empty_(h, LIST_LOC) +static inline bool list_empty_(const struct list_head *h, const char* abortstr) { - (void)list_debug(h); + (void)list_debug(h, abortstr); return h->n.next == &h->n; } +/** + * list_empty_nodebug - is a list empty (and don't perform debug checks)? + * @h: the list_head + * + * If the list is empty, returns true. + * This differs from list_empty() in that if CCAN_LIST_DEBUG is set it + * will NOT perform debug checks. Only use this function if you REALLY + * know what you're doing. + * + * Example: + * assert(list_empty_nodebug(&parent->children) == (parent->num_children == 0)); + */ +#ifndef CCAN_LIST_DEBUG +#define list_empty_nodebug(h) list_empty(h) +#else +static inline bool list_empty_nodebug(const struct list_head *h) +{ + return h->n.next == &h->n; +} +#endif + /** * list_del - delete an entry from an (unknown) linked list. * @n: the list_node to delete from the list. @@ -206,15 +299,16 @@ static inline bool list_empty(const struct list_head *h) * another list, but not deleted again. * * See also: - * list_del_from() + * list_del_from(), list_del_init() * * Example: * list_del(&child->list); * parent->num_children--; */ -static inline void list_del(struct list_node *n) +#define list_del(n) list_del_(n, LIST_LOC) +static inline void list_del_(struct list_node *n, const char* abortstr) { - (void)list_debug_node(n); + (void)list_debug_node(n, abortstr); n->next->prev = n->prev; n->prev->next = n->next; #ifdef CCAN_LIST_DEBUG @@ -223,6 +317,27 @@ static inline void list_del(struct list_node *n) #endif } +/** + * list_del_init - delete a node, and reset it so it can be deleted again. + * @n: the list_node to be deleted. + * + * list_del(@n) or list_del_init() again after this will be safe, + * which can be useful in some cases. + * + * See also: + * list_del_from(), list_del() + * + * Example: + * list_del_init(&child->list); + * parent->num_children--; + */ +#define list_del_init(n) list_del_init_(n, LIST_LOC) +static inline void list_del_init_(struct list_node *n, const char *abortstr) +{ + list_del_(n, abortstr); + list_node_init(n); +} + /** * list_del_from - delete an entry from a known linked list. * @h: the list_head the node is in. @@ -253,6 +368,39 @@ static inline void list_del_from(struct list_head *h, struct list_node *n) list_del(n); } +/** + * list_swap - swap out an entry from an (unknown) linked list for a new one. + * @o: the list_node to replace from the list. + * @n: the list_node to insert in place of the old one. + * + * Note that this leaves @o in an undefined state; it can be added to + * another list, but not deleted/swapped again. + * + * See also: + * list_del() + * + * Example: + * struct child x1, x2; + * LIST_HEAD(xh); + * + * list_add(&xh, &x1.list); + * list_swap(&x1.list, &x2.list); + */ +#define list_swap(o, n) list_swap_(o, n, LIST_LOC) +static inline void list_swap_(struct list_node *o, + struct list_node *n, + const char* abortstr) +{ + (void)list_debug_node(o, abortstr); + *n = *o; + n->next->prev = n; + n->prev->next = n; +#ifdef CCAN_LIST_DEBUG + /* Catch use-after-del. */ + o->next = o->prev = NULL; +#endif +} + /** * list_entry - convert a list_node back into the structure containing it. * @n: the list_node @@ -374,7 +522,7 @@ static inline const void *list_tail_(const struct list_head *h, size_t off) * 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); \ + for (i = container_of_var(list_debug(h, LIST_LOC)->n.prev, i, member); \ &i->member != &(h)->n; \ i = container_of_var(i->member.prev, i, member)) @@ -414,7 +562,8 @@ static inline const void *list_tail_(const struct list_head *h, size_t off) * printf("No second child!\n"); */ #define list_next(h, i, member) \ - ((list_typeof(i))list_entry_or_null(list_debug(h), \ + ((list_typeof(i))list_entry_or_null(list_debug(h, \ + __FILE__ ":" stringify(__LINE__)), \ (i)->member.next, \ list_off_var_((i), member))) @@ -432,7 +581,8 @@ static inline const void *list_tail_(const struct list_head *h, size_t off) * printf("Can't go back to first child?!\n"); */ #define list_prev(h, i, member) \ - ((list_typeof(i))list_entry_or_null(list_debug(h), \ + ((list_typeof(i))list_entry_or_null(list_debug(h, \ + __FILE__ ":" stringify(__LINE__)), \ (i)->member.prev, \ list_off_var_((i), member))) @@ -451,11 +601,14 @@ static inline const void *list_tail_(const struct list_head *h, size_t off) * assert(list_empty(&parent->children)); * parent->num_children = 0; */ -static inline void list_append_list(struct list_head *to, - struct list_head *from) +#define list_append_list(t, f) list_append_list_(t, f, \ + __FILE__ ":" stringify(__LINE__)) +static inline void list_append_list_(struct list_head *to, + struct list_head *from, + const char *abortstr) { - struct list_node *from_tail = list_debug(from)->n.prev; - struct list_node *to_tail = list_debug(to)->n.prev; + struct list_node *from_tail = list_debug(from, abortstr)->n.prev; + struct list_node *to_tail = list_debug(to, abortstr)->n.prev; /* Sew in head and entire list. */ to->n.prev = from_tail; @@ -481,11 +634,13 @@ static inline void list_append_list(struct list_head *to, * assert(list_empty(&parent->children)); * parent->num_children = 0; */ -static inline void list_prepend_list(struct list_head *to, - struct list_head *from) +#define list_prepend_list(t, f) list_prepend_list_(t, f, LIST_LOC) +static inline void list_prepend_list_(struct list_head *to, + struct list_head *from, + const char *abortstr) { - struct list_node *from_tail = list_debug(from)->n.prev; - struct list_node *to_head = list_debug(to)->n.next; + struct list_node *from_tail = list_debug(from, abortstr)->n.prev; + struct list_node *to_head = list_debug(to, abortstr)->n.next; /* Sew in head and entire list. */ to->n.next = &from->n; @@ -498,6 +653,24 @@ static inline void list_prepend_list(struct list_head *to, list_head_init(from); } +/* internal macros, do not use directly */ +#define list_for_each_off_dir_(h, i, off, dir) \ + for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \ + (off)); \ + list_node_from_off_((void *)i, (off)) != &(h)->n; \ + i = list_node_to_off_(list_node_from_off_((void *)i, (off))->dir, \ + (off))) + +#define list_for_each_safe_off_dir_(h, i, nxt, off, dir) \ + for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \ + (off)), \ + nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \ + (off)); \ + list_node_from_off_(i, (off)) != &(h)->n; \ + i = nxt, \ + nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \ + (off))) + /** * list_for_each_off - iterate through a list of memory regions. * @h: the list_head @@ -528,10 +701,7 @@ static inline void list_prepend_list(struct list_head *to, * printf("Name: %s\n", child->name); */ #define list_for_each_off(h, i, off) \ - for (i = list_node_to_off_(list_debug(h)->n.next, (off)); \ - list_node_from_off_((void *)i, (off)) != &(h)->n; \ - i = list_node_to_off_(list_node_from_off_((void *)i, (off))->next, \ - (off))) + list_for_each_off_dir_((h),(i),(off),next) /** * list_for_each_safe_off - iterate through a list of memory regions, maybe @@ -550,14 +720,7 @@ static inline void list_prepend_list(struct list_head *to, * printf("Name: %s\n", child->name); */ #define list_for_each_safe_off(h, i, nxt, off) \ - for (i = list_node_to_off_(list_debug(h)->n.next, (off)), \ - nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \ - (off)); \ - list_node_from_off_(i, (off)) != &(h)->n; \ - i = nxt, \ - nxt = list_node_to_off_(list_node_from_off_(i, (off))->next, \ - (off))) - + list_for_each_safe_off_dir_((h),(i),(nxt),(off),next) /* Other -off variants. */ #define list_entry_off(n, type, off) \