diff options
| -rw-r--r-- | include/list.h | 160 | ||||
| -rw-r--r-- | test/list.c | 164 |
2 files changed, 324 insertions, 0 deletions
diff --git a/include/list.h b/include/list.h index 5933b973d..7825dce52 100644 --- a/include/list.h +++ b/include/list.h @@ -278,4 +278,164 @@ list_is_empty(struct list *head) &pos->member != (head); \ pos = tmp, tmp = __container_of(pos->member.next, tmp, member)) + + +/* NULL-Terminated List Interface + * + * The interface below does _not_ use the struct list as described above. + * It is mainly for legacy structures that cannot easily be switched to + * struct list. + * + * This interface is for structs like + * struct foo { + * [...] + * struct foo *next; + * [...] + * }; + * + * The position and field name of "next" are arbitrary. + */ + +/** + * Init the element as null-terminated list. + * + * Example: + * struct foo *list = malloc(); + * nt_list_init(list, next); + * + * @param list The list element that will be the start of the list + * @param member Member name of the field pointing to next struct + */ +#define nt_list_init(_list, _member) \ + (_list)->_member = NULL + +/** + * Returns the next element in the list or NULL on termination. + * + * Example: + * struct foo *element = list; + * while ((element = nt_list_next(element, next)) { } + * + * This macro is not safe for node deletion. Use list_for_each_entry_safe + * instead. + * + * @param list The list or current element. + * @param member Member name of the field pointing to next struct. + */ +#define nt_list_next(_list, _member) \ + (_list)->_member + +/** + * Iterate through each element in the list. + * + * Example: + * struct foo *iterator; + * nt_list_for_each_entry(iterator, list, next) { + * [modify iterator] + * } + * + * @param entry Assigned to the current list element + * @param list The list to iterate through. + * @param member Member name of the field pointing to next struct. + */ +#define nt_list_for_each_entry(_entry, _list, _member) \ + for (_entry = _list; _entry; _entry = (_entry)->_member) + +/** + * Iterate through each element in the list, keeping a backup pointer to the + * element. This macro allows for the deletion of a list element while + * looping through the list. + * + * See nt_list_for_each_entry for more details. + * + * @param entry Assigned to the current list element + * @param tmp The pointer to the next element + * @param list The list to iterate through. + * @param member Member name of the field pointing to next struct. + */ +#define nt_list_for_each_entry_safe(_entry, _tmp, _list, _member) \ + for (_entry = _list, _tmp = (_entry) ? (_entry)->_member : NULL;\ + _entry; \ + _entry = _tmp, _tmp = (_tmp) ? (_tmp)->_member: NULL) + + +/** + * Append the element to the end of the list. This macro may be used to + * merge two lists. + * + * Example: + * struct foo *elem = malloc(...); + * nt_list_init(elem, next) + * nt_list_append(elem, list, struct foo, next); + * + * Resulting list order: + * list_item_0 -> list_item_1 -> ... -> elem_item_0 -> elem_item_1 ... + * + * @param entry An entry (or list) to append to the list + * @param list The list to append to. This list must be a valid list, not + * NULL. + * @param type The list type + * @param member Member name of the field pointing to next struct + */ +#define nt_list_append(_entry, _list, _type, _member) \ + do { \ + _type *__iterator = _list; \ + while (__iterator->_member) { __iterator = __iterator->_member;}\ + __iterator->_member = _entry; \ + } while (0) + +/** + * Insert the element at the next position in the list. This macro may be + * used to insert a list into a list. + * + * struct foo *elem = malloc(...); + * nt_list_init(elem, next) + * nt_list_insert(elem, list, struct foo, next); + * + * Resulting list order: + * list_item_0 -> elem_item_0 -> elem_item_1 ... -> list_item_1 -> ... + * + * @param entry An entry (or list) to append to the list + * @param list The list to insert to. This list must be a valid list, not + * NULL. + * @param type The list type + * @param member Member name of the field pointing to next struct + */ +#define nt_list_insert(_entry, _list, _type, _member) \ + do { \ + nt_list_append((_list)->_member, _entry, _type, _member); \ + (_list)->_member = _entry; \ + } while (0) + +/** + * Delete the entry from the list by iterating through the list and + * removing any reference from the list to the entry. + * + * Example: + * struct foo *elem = <assign to right element> + * nt_list_del(elem, list, struct foo, next); + * + * @param entry The entry to delete from the list. entry is always + * re-initialized as a null-terminated list. + * @param list The list containing the entry, set to the new list without + * the removed entry. + * @param type The list type + * @param member Member name of the field pointing to the next entry + */ +#define nt_list_del(_entry, _list, _type, _member) \ + do { \ + _type *__e = _entry; \ + if (__e == NULL) break; \ + if ((_list) == __e) { \ + _list = __e->_member; \ + } else { \ + _type *__prev = _list; \ + while (__prev->_member && __prev->_member != __e) \ + __prev = nt_list_next(__prev, _member); \ + if (__prev->_member) \ + __prev->_member = __e->_member; \ + } \ + nt_list_init(__e, _member); \ + } while(0) + #endif diff --git a/test/list.c b/test/list.c index b101c7619..f7d7bffce 100644 --- a/test/list.c +++ b/test/list.c @@ -29,6 +29,7 @@ #include <list.h> #include <string.h> #include <assert.h> +#include <stdlib.h> struct parent { int a; @@ -161,6 +162,164 @@ test_list_for_each(void) } } +struct foo { + char a; + struct foo *next; + char b; +}; + +static void +test_nt_list_init(void) +{ + struct foo foo; + + foo.a = 10; + foo.b = 20; + nt_list_init(&foo, next); + + assert(foo.a == 10); + assert(foo.b == 20); + assert(foo.next == NULL); + assert(nt_list_next(&foo, next) == NULL); +} + +static void +test_nt_list_append(void) +{ + int i; + struct foo *foo = calloc(10, sizeof(struct foo)); + struct foo *item; + + for (item = foo, i = 1; i <= 10; i++, item++) + { + item->a = i; + item->b = i * 2; + nt_list_init(item, next); + + if (item != foo) + nt_list_append(item, foo, struct foo, next); + } + + /* Test using nt_list_next */ + for (item = foo, i = 1; i <= 10; i++, item = nt_list_next(item, next)) + { + assert(item->a = i); + assert(item->b = i * 2); + } + + /* Test using nt_list_for_each_entry */ + i = 1; + nt_list_for_each_entry(item, foo, next) { + assert(item->a = i); + assert(item->b = i * 2); + i++; + } + assert(i == 11); +} + +static void +test_nt_list_insert(void) +{ + int i; + struct foo *foo = calloc(10, sizeof(struct foo)); + struct foo *item; + + foo->a = 10; + foo->b = 20; + nt_list_init(foo, next); + + for (item = &foo[1], i = 9; i > 0; i--, item++) + { + item->a = i; + item->b = i * 2; + nt_list_init(item, next); + nt_list_insert(item, foo, struct foo, next); + } + + /* Test using nt_list_next */ + for (item = foo, i = 10; i > 0; i--, item = nt_list_next(item, next)) + { + assert(item->a = i); + assert(item->b = i * 2); + } + + /* Test using nt_list_for_each_entry */ + i = 1; + nt_list_for_each_entry(item, foo, next) { + assert(item->a = i); + assert(item->b = i * 2); + i++; + } + assert(i == 11); +} + +static void +test_nt_list_delete(void) +{ + int i = 1; + struct foo *list = calloc(10, sizeof(struct foo)); + struct foo *foo = list; + struct foo *item, *tmp; + struct foo *empty_list = foo; + + nt_list_init(empty_list, next); + nt_list_del(empty_list, empty_list, struct foo, next); + assert(!empty_list); + + for (item = foo, i = 1; i <= 10; i++, item++) + { + item->a = i; + item->b = i * 2; + nt_list_init(item, next); + + if (item != foo) + nt_list_append(item, foo, struct foo, next); + } + + i = 0; + nt_list_for_each_entry(item, foo, next) { + i++; + } + assert(i == 10); + + /* delete last item */ + nt_list_del(&foo[9], foo, struct foo, next); + i = 0; + nt_list_for_each_entry(item, foo, next) { + assert(item->a != 10); /* element 10 is gone now */ + i++; + } + assert(i == 9); /* 9 elements left */ + + /* delete second item */ + nt_list_del(foo->next, foo, struct foo, next); + assert(foo->next->a == 3); + + i = 0; + nt_list_for_each_entry(item, foo, next) { + assert(item->a != 10); /* element 10 is gone now */ + assert(item->a != 2); /* element 2 is gone now */ + i++; + } + assert(i == 8); /* 9 elements left */ + + item = foo; + /* delete first item */ + nt_list_del(foo, foo, struct foo, next); + assert(item != foo); + assert(item->next == NULL); + assert(foo->a == 3); + assert(foo->next->a == 4); + + nt_list_for_each_entry_safe(item, tmp, foo, next) { + nt_list_del(item, foo, struct foo, next); + } + + assert(!foo); + assert(!item); + + free(list); +} int main(int argc, char** argv) { @@ -169,5 +328,10 @@ int main(int argc, char** argv) test_list_del(); test_list_for_each(); + test_nt_list_init(); + test_nt_list_append(); + test_nt_list_insert(); + test_nt_list_delete(); + return 0; } |