From 9b45107fb76e038ecffe66464d935246ad887e84 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 25 Apr 2008 18:28:03 -0700 Subject: [PATCH] Improve list traversal macros. Make LIST_FOR_EACH[_SAFE] variable take logically correct value upon loop termination. Also, add regression tests for linked list routines, to ensure that this change does not break code. Also, add new macro LIST_FOR_EACH_REVERSE. --- Makefile.am | 2 +- configure.ac | 1 + include/list.h | 20 +++--- tests/.gitignore | 3 + tests/Makefile.am | 8 +++ tests/test-list.c | 158 ++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 181 insertions(+), 11 deletions(-) create mode 100644 tests/.gitignore create mode 100644 tests/Makefile.am create mode 100644 tests/test-list.c diff --git a/Makefile.am b/Makefile.am index 6306ab4c..7ebc633e 100644 --- a/Makefile.am +++ b/Makefile.am @@ -3,4 +3,4 @@ SUBDIRS = lib datapath secchan controller if HAVE_IF_PACKET SUBDIRS += switch endif -SUBDIRS += utilities man include third-party +SUBDIRS += utilities tests man include third-party diff --git a/configure.ac b/configure.ac index 5fa1ce98..5d0a23ac 100644 --- a/configure.ac +++ b/configure.ac @@ -88,6 +88,7 @@ controller/Makefile utilities/Makefile secchan/Makefile switch/Makefile +tests/Makefile datapath/tests/Makefile third-party/Makefile datapath/linux-2.6/Makefile diff --git a/include/list.h b/include/list.h index 03f4b48c..602c549b 100644 --- a/include/list.h +++ b/include/list.h @@ -70,18 +70,18 @@ struct list *list_back(struct list *); size_t list_size(const struct list *); bool list_is_empty(const struct list *); -#define LIST_ELEM__(ELEM, STRUCT, MEMBER, LIST) \ - (ELEM != LIST ? CONTAINER_OF(ELEM, STRUCT, MEMBER) : NULL) #define LIST_FOR_EACH(ITER, STRUCT, MEMBER, LIST) \ - for (ITER = LIST_ELEM__((LIST)->next, STRUCT, MEMBER, LIST); \ - ITER != NULL; \ - ITER = LIST_ELEM__((ITER)->MEMBER.next, STRUCT, MEMBER, LIST)) + for (ITER = CONTAINER_OF((LIST)->next, STRUCT, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ITER = CONTAINER_OF((ITER)->MEMBER.next, STRUCT, MEMBER)) +#define LIST_FOR_EACH_REVERSE(ITER, STRUCT, MEMBER, LIST) \ + for (ITER = CONTAINER_OF((LIST)->prev, STRUCT, MEMBER); \ + &(ITER)->MEMBER != (LIST); \ + ITER = CONTAINER_OF((ITER)->MEMBER.prev, STRUCT, MEMBER)) #define LIST_FOR_EACH_SAFE(ITER, NEXT, STRUCT, MEMBER, LIST) \ - for (ITER = LIST_ELEM__((LIST)->next, STRUCT, MEMBER, LIST); \ - (ITER != NULL \ - ? (NEXT = LIST_ELEM__((ITER)->MEMBER.next, \ - STRUCT, MEMBER, LIST), 1) \ - : 0); \ + for (ITER = CONTAINER_OF((LIST)->next, STRUCT, MEMBER); \ + (NEXT = CONTAINER_OF((ITER)->MEMBER.next, STRUCT, MEMBER), \ + &(ITER)->MEMBER != (LIST)); \ ITER = NEXT) #endif /* list.h */ diff --git a/tests/.gitignore b/tests/.gitignore new file mode 100644 index 00000000..af650d2b --- /dev/null +++ b/tests/.gitignore @@ -0,0 +1,3 @@ +/Makefile +/Makefile.in +/test-list diff --git a/tests/Makefile.am b/tests/Makefile.am new file mode 100644 index 00000000..91e11a5b --- /dev/null +++ b/tests/Makefile.am @@ -0,0 +1,8 @@ +include ../Make.vars + +TESTS = test-list + +check_PROGRAMS = test-list + +test_list_SOURCES = test-list.c +test_list_LDADD = ../lib/libopenflow.la diff --git a/tests/test-list.c b/tests/test-list.c new file mode 100644 index 00000000..b9599dbf --- /dev/null +++ b/tests/test-list.c @@ -0,0 +1,158 @@ +/* A non-exhaustive test for some of the functions and macros declared in + * list.h. */ + +#include "list.h" +#include + +#undef NDEBUG +#include + +/* Sample list element. */ +struct element { + int value; + struct list node; +}; + +/* Puts the 'n' values in 'values' into 'elements', and then puts those + * elements in order into 'list'. */ +static void +make_list(struct list *list, struct element elements[], + int values[], size_t n) +{ + size_t i; + + list_init(list); + for (i = 0; i < n; i++) { + elements[i].value = i; + list_push_back(list, &elements[i].node); + values[i] = i; + } +} + +/* Verifies that 'list' contains exactly the 'n' values in 'values', in the + * specified order. */ +static void +check_list(struct list *list, const int values[], size_t n) +{ + struct element *e; + size_t i; + + i = 0; + LIST_FOR_EACH (e, struct element, node, list) { + assert(i < n); + assert(e->value == values[i]); + i++; + } + assert(&e->node == list); + assert(i == n); + + i = 0; + LIST_FOR_EACH_REVERSE (e, struct element, node, list) { + assert(i < n); + assert(e->value == values[n - i - 1]); + i++; + } + assert(&e->node == list); + assert(i == n); + + assert(list_is_empty(list) == !n); + assert(list_size(list) == n); +} + +#if 0 +/* Prints the values in 'list', plus 'name' as a title. */ +static void +print_list(const char *name, struct list *list) +{ + struct element *e; + + printf("%s:", name); + LIST_FOR_EACH (e, struct element, node, list) { + printf(" %d", e->value); + } + printf("\n"); +} +#endif + +/* Tests basic list construction. */ +static void +test_list_construction(void) +{ + enum { MAX_ELEMS = 100 }; + size_t n; + + for (n = 0; n <= MAX_ELEMS; n++) { + struct element elements[MAX_ELEMS]; + int values[MAX_ELEMS]; + struct list list; + + make_list(&list, elements, values, n); + check_list(&list, values, n); + } +} + +/* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current + * element of a list. */ +static void +test_list_for_each_safe(void) +{ + enum { MAX_ELEMS = 10 }; + size_t n; + unsigned long int pattern; + + for (n = 0; n <= MAX_ELEMS; n++) { + for (pattern = 0; pattern < 1ul << n; pattern++) { + struct element elements[MAX_ELEMS]; + int values[MAX_ELEMS]; + struct list list; + struct element *e, *next; + size_t values_idx, n_remaining; + int i; + + make_list(&list, elements, values, n); + + i = 0; + values_idx = 0; + n_remaining = n; + LIST_FOR_EACH_SAFE (e, next, struct element, node, &list) { + assert(i < n); + if (pattern & (1ul << i)) { + list_remove(&e->node); + n_remaining--; + memmove(&values[values_idx], &values[values_idx + 1], + sizeof *values * (n_remaining - values_idx)); + } else { + values_idx++; + } + check_list(&list, values, n_remaining); + i++; + } + assert(i == n); + assert(&e->node == &list); + + for (i = 0; i < n; i++) { + if (pattern & (1ul << i)) { + n_remaining++; + } + } + assert(n == n_remaining); + } + } +} + +static void +run_test(void (*function)(void)) +{ + function(); + printf("."); +} + +int +main(void) +{ + run_test(test_list_construction); + run_test(test_list_for_each_safe); + printf("\n"); + return 0; +} + -- 2.30.2