diff options
author | Felix Fietkau <nbd@openwrt.org> | 2013-03-18 06:58:54 +0400 |
---|---|---|
committer | Felix Fietkau <nbd@openwrt.org> | 2013-03-18 08:47:53 +0400 |
commit | 7c11f6e91338eb73a1015606e55798d09369b2e8 (patch) | |
tree | 15a38d87883f82e9ad3dcdf6e26b9b4547201da3 /safe_list.c | |
parent | 00a833c5b6f44c8cf2a7a9838de32d0dc5400a90 (diff) |
safe_list: add a new linked list variant
Use this linked list implementation as a replacement for list.h if you
want to allow deleting arbitrary list entries from within one or more
recursive iterator calling context
Signed-off-by: Felix Fietkau <nbd@openwrt.org>
Diffstat (limited to 'safe_list.c')
-rw-r--r-- | safe_list.c | 114 |
1 files changed, 114 insertions, 0 deletions
diff --git a/safe_list.c b/safe_list.c new file mode 100644 index 0000000..d9f211f --- /dev/null +++ b/safe_list.c @@ -0,0 +1,114 @@ +/* + * safe_list - linked list protected against recursive iteration with deletes + * + * Copyright (C) 2013 Felix Fietkau <nbd@openwrt.org> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "safe_list.h" + +struct safe_list_iterator { + struct safe_list_iterator **head; + struct safe_list_iterator *next_i; + struct safe_list *next; +}; + +static void +__safe_list_set_iterator(struct safe_list *list, + struct safe_list_iterator *i) +{ + struct safe_list_iterator *next_i; + struct safe_list *next; + + next = list_entry(list->list.next, struct safe_list, list); + next_i = next->i; + + next->i = i; + i->next = next; + i->head = &next->i; + + i->next_i = next_i; + if (next_i) + next_i->head = &i->next_i; +} + +static void +__safe_list_del_iterator(struct safe_list_iterator *i) +{ + *i->head = i->next_i; + if (i->next_i) + i->next_i->head = i->head; +} + +static void +__safe_list_move_iterator(struct safe_list *list, + struct safe_list_iterator *i) +{ + __safe_list_del_iterator(i); + __safe_list_set_iterator(list, i); +} + +int safe_list_for_each(struct safe_list *head, + int (*cb)(void *ctx, struct safe_list *list), + void *ctx) +{ + struct safe_list_iterator i; + struct safe_list *cur; + int ret = 0; + + for (cur = list_entry(head->list.next, struct safe_list, list), + __safe_list_set_iterator(cur, &i); + cur != head; + cur = i.next, __safe_list_move_iterator(cur, &i)) { + ret = cb(ctx, cur); + if (ret) + break; + } + + __safe_list_del_iterator(&i); + return ret; +} + +void safe_list_add(struct safe_list *list, struct safe_list *head) +{ + list->i = NULL; + list_add_tail(&list->list, &head->list); +} + +void safe_list_del(struct safe_list *list) +{ + struct safe_list_iterator *i, *next_i, **tail; + struct safe_list *next; + + next = list_entry(list->list.next, struct safe_list, list); + list_del(&list->list); + + if (!list->i) + return; + + next_i = next->i; + tail = &next->i; + + for (i = list->i; i; i = i->next_i) { + tail = &i->next_i; + i->next = next; + } + + next->i = list->i; + list->i->head = &next->i; + *tail = next_i; + next_i->head = tail; + + list->i = NULL; +} |