diff options
| -rw-r--r-- | CMakeLists.txt | 2 | ||||
| -rw-r--r-- | safe_list.c | 114 | ||||
| -rw-r--r-- | safe_list.h | 56 |
3 files changed, 171 insertions, 1 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index f8388ad..c574bf7 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -19,7 +19,7 @@ IF(JSONC_FOUND) INCLUDE_DIRECTORIES(${JSONC_INCLUDE_DIRS}) ENDIF() -SET(SOURCES avl.c avl-cmp.c blob.c blobmsg.c uloop.c usock.c ustream.c ustream-fd.c vlist.c utils.c) +SET(SOURCES avl.c avl-cmp.c blob.c blobmsg.c uloop.c usock.c ustream.c ustream-fd.c vlist.c utils.c safe_list.c) ADD_LIBRARY(ubox SHARED ${SOURCES}) 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; +} diff --git a/safe_list.h b/safe_list.h new file mode 100644 index 0000000..f9fd741 --- /dev/null +++ b/safe_list.h @@ -0,0 +1,56 @@ +/* + * 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. + */ + +/* + * 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 + */ + +#ifndef __LIBUBOX_SAFE_LIST_H +#define __LIBUBOX_SAFE_LIST_H + +#include <stdbool.h> +#include "list.h" +#include "utils.h" + +struct safe_list; +struct safe_list_terator; + +struct safe_list { + struct list_head list; + struct safe_list_iterator *i; +}; + +int safe_list_for_each(struct safe_list *list, + int (*cb)(void *ctx, struct safe_list *list), + void *ctx); + +void safe_list_add(struct safe_list *list, struct safe_list *head); +void safe_list_del(struct safe_list *list); + +#define INIT_SAFE_LIST(_head) \ + do { \ + INIT_LIST_HEAD(_head.list); \ + (_head)->i = NULL; \ + } while (0) + +#define SAFE_LIST_INIT(_name) { LIST_HEAD_INIT(_name.list), NULL } +#define SAFE_LIST(_name) struct safe_list _name = SAFE_LIST_INIT(_name) + +#endif |