pintos-os.org Git - openvswitch/blob - tests/test-list.c

   1 /* A non-exhaustive test for some of the functions and macros declared in
   2  * list.h. */
   3
   4 #include <config.h>
   5 #include "list.h"
   6 #include <string.h>
   7
   8 #undef NDEBUG
   9 #include <assert.h>
  10
  11 /* Sample list element. */
  12 struct element {
  13     int value;
  14     struct list node;
  15 };
  16
  17 /* Puts the 'n' values in 'values' into 'elements', and then puts those
  18  * elements in order into 'list'. */
  19 static void
  20 make_list(struct list *list, struct element elements[],
  21           int values[], size_t n)
  22 {
  23     size_t i;
  24
  25     list_init(list);
  26     for (i = 0; i < n; i++) {
  27         elements[i].value = i;
  28         list_push_back(list, &elements[i].node);
  29         values[i] = i;
  30     }
  31 }
  32
  33 /* Verifies that 'list' contains exactly the 'n' values in 'values', in the
  34  * specified order. */
  35 static void
  36 check_list(struct list *list, const int values[], size_t n)
  37 {
  38     struct element *e;
  39     size_t i;
  40
  41     i = 0;
  42     LIST_FOR_EACH (e, struct element, node, list) {
  43         assert(i < n);
  44         assert(e->value == values[i]);
  45         i++;
  46     }
  47     assert(&e->node == list);
  48     assert(i == n);
  49
  50     i = 0;
  51     LIST_FOR_EACH_REVERSE (e, struct element, node, list) {
  52         assert(i < n);
  53         assert(e->value == values[n - i - 1]);
  54         i++;
  55     }
  56     assert(&e->node == list);
  57     assert(i == n);
  58
  59     assert(list_is_empty(list) == !n);
  60     assert(list_size(list) == n);
  61 }
  62
  63 #if 0
  64 /* Prints the values in 'list', plus 'name' as a title. */
  65 static void
  66 print_list(const char *name, struct list *list)
  67 {
  68     struct element *e;
  69
  70     printf("%s:", name);
  71     LIST_FOR_EACH (e, struct element, node, list) {
  72         printf(" %d", e->value);
  73     }
  74     printf("\n");
  75 }
  76 #endif
  77
  78 /* Tests basic list construction. */
  79 static void
  80 test_list_construction(void)
  81 {
  82     enum { MAX_ELEMS = 100 };
  83     size_t n;
  84
  85     for (n = 0; n <= MAX_ELEMS; n++) {
  86         struct element elements[MAX_ELEMS];
  87         int values[MAX_ELEMS];
  88         struct list list;
  89
  90         make_list(&list, elements, values, n);
  91         check_list(&list, values, n);
  92     }
  93 }
  94
  95 /* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current
  96  * element of a list.  */
  97 static void
  98 test_list_for_each_safe(void)
  99 {
 100     enum { MAX_ELEMS = 10 };
 101     size_t n;
 102     unsigned long int pattern;
 103
 104     for (n = 0; n <= MAX_ELEMS; n++) {
 105         for (pattern = 0; pattern < 1ul << n; pattern++) {
 106             struct element elements[MAX_ELEMS];
 107             int values[MAX_ELEMS];
 108             struct list list;
 109             struct element *e, *next;
 110             size_t values_idx, n_remaining;
 111             int i;
 112
 113             make_list(&list, elements, values, n);
 114
 115             i = 0;
 116             values_idx = 0;
 117             n_remaining = n;
 118             LIST_FOR_EACH_SAFE (e, next, struct element, node, &list) {
 119                 assert(i < n);
 120                 if (pattern & (1ul << i)) {
 121                     list_remove(&e->node);
 122                     n_remaining--;
 123                     memmove(&values[values_idx], &values[values_idx + 1],
 124                             sizeof *values * (n_remaining - values_idx));
 125                 } else {
 126                     values_idx++;
 127                 }
 128                 check_list(&list, values, n_remaining);
 129                 i++;
 130             }
 131             assert(i == n);
 132             assert(&e->node == &list);
 133
 134             for (i = 0; i < n; i++) {
 135                 if (pattern & (1ul << i)) {
 136                     n_remaining++;
 137                 }
 138             }
 139             assert(n == n_remaining);
 140         }
 141     }
 142 }
 143
 144 static void
 145 run_test(void (*function)(void))
 146 {
 147     function();
 148     printf(".");
 149 }
 150
 151 int
 152 main(void)
 153 {
 154     run_test(test_list_construction);
 155     run_test(test_list_for_each_safe);
 156     printf("\n");
 157     return 0;
 158 }
 159