src/jemalloc/test/unit/ql.c

   1 #include "test/jemalloc_test.h"
   2
   3 /* Number of ring entries, in [2..26]. */
   4 #define NENTRIES 9
   5
   6 typedef struct list_s list_t;
   7 typedef ql_head(list_t) list_head_t;
   8
   9 struct list_s {
  10         ql_elm(list_t) link;
  11         char id;
  12 };
  13
  14 static void
  15 test_empty_list(list_head_t *head)
  16 {
  17         list_t *t;
  18         unsigned i;
  19
  20         assert_ptr_null(ql_first(head), "Unexpected element for empty list");
  21         assert_ptr_null(ql_last(head, link),
  22             "Unexpected element for empty list");
  23
  24         i = 0;
  25         ql_foreach(t, head, link) {
  26                 i++;
  27         }
  28         assert_u_eq(i, 0, "Unexpected element for empty list");
  29
  30         i = 0;
  31         ql_reverse_foreach(t, head, link) {
  32                 i++;
  33         }
  34         assert_u_eq(i, 0, "Unexpected element for empty list");
  35 }
  36
  37 TEST_BEGIN(test_ql_empty)
  38 {
  39         list_head_t head;
  40
  41         ql_new(&head);
  42         test_empty_list(&head);
  43 }
  44 TEST_END
  45
  46 static void
  47 init_entries(list_t *entries, unsigned nentries)
  48 {
  49         unsigned i;
  50
  51         for (i = 0; i < nentries; i++) {
  52                 entries[i].id = 'a' + i;
  53                 ql_elm_new(&entries[i], link);
  54         }
  55 }
  56
  57 static void
  58 test_entries_list(list_head_t *head, list_t *entries, unsigned nentries)
  59 {
  60         list_t *t;
  61         unsigned i;
  62
  63         assert_c_eq(ql_first(head)->id, entries[0].id, "Element id mismatch");
  64         assert_c_eq(ql_last(head, link)->id, entries[nentries-1].id,
  65             "Element id mismatch");
  66
  67         i = 0;
  68         ql_foreach(t, head, link) {
  69                 assert_c_eq(t->id, entries[i].id, "Element id mismatch");
  70                 i++;
  71         }
  72
  73         i = 0;
  74         ql_reverse_foreach(t, head, link) {
  75                 assert_c_eq(t->id, entries[nentries-i-1].id,
  76                     "Element id mismatch");
  77                 i++;
  78         }
  79
  80         for (i = 0; i < nentries-1; i++) {
  81                 t = ql_next(head, &entries[i], link);
  82                 assert_c_eq(t->id, entries[i+1].id, "Element id mismatch");
  83         }
  84         assert_ptr_null(ql_next(head, &entries[nentries-1], link),
  85             "Unexpected element");
  86
  87         assert_ptr_null(ql_prev(head, &entries[0], link), "Unexpected element");
  88         for (i = 1; i < nentries; i++) {
  89                 t = ql_prev(head, &entries[i], link);
  90                 assert_c_eq(t->id, entries[i-1].id, "Element id mismatch");
  91         }
  92 }
  93
  94 TEST_BEGIN(test_ql_tail_insert)
  95 {
  96         list_head_t head;
  97         list_t entries[NENTRIES];
  98         unsigned i;
  99
 100         ql_new(&head);
 101         init_entries(entries, sizeof(entries)/sizeof(list_t));
 102         for (i = 0; i < NENTRIES; i++)
 103                 ql_tail_insert(&head, &entries[i], link);
 104
 105         test_entries_list(&head, entries, NENTRIES);
 106 }
 107 TEST_END
 108
 109 TEST_BEGIN(test_ql_tail_remove)
 110 {
 111         list_head_t head;
 112         list_t entries[NENTRIES];
 113         unsigned i;
 114
 115         ql_new(&head);
 116         init_entries(entries, sizeof(entries)/sizeof(list_t));
 117         for (i = 0; i < NENTRIES; i++)
 118                 ql_tail_insert(&head, &entries[i], link);
 119
 120         for (i = 0; i < NENTRIES; i++) {
 121                 test_entries_list(&head, entries, NENTRIES-i);
 122                 ql_tail_remove(&head, list_t, link);
 123         }
 124         test_empty_list(&head);
 125 }
 126 TEST_END
 127
 128 TEST_BEGIN(test_ql_head_insert)
 129 {
 130         list_head_t head;
 131         list_t entries[NENTRIES];
 132         unsigned i;
 133
 134         ql_new(&head);
 135         init_entries(entries, sizeof(entries)/sizeof(list_t));
 136         for (i = 0; i < NENTRIES; i++)
 137                 ql_head_insert(&head, &entries[NENTRIES-i-1], link);
 138
 139         test_entries_list(&head, entries, NENTRIES);
 140 }
 141 TEST_END
 142
 143 TEST_BEGIN(test_ql_head_remove)
 144 {
 145         list_head_t head;
 146         list_t entries[NENTRIES];
 147         unsigned i;
 148
 149         ql_new(&head);
 150         init_entries(entries, sizeof(entries)/sizeof(list_t));
 151         for (i = 0; i < NENTRIES; i++)
 152                 ql_head_insert(&head, &entries[NENTRIES-i-1], link);
 153
 154         for (i = 0; i < NENTRIES; i++) {
 155                 test_entries_list(&head, &entries[i], NENTRIES-i);
 156                 ql_head_remove(&head, list_t, link);
 157         }
 158         test_empty_list(&head);
 159 }
 160 TEST_END
 161
 162 TEST_BEGIN(test_ql_insert)
 163 {
 164         list_head_t head;
 165         list_t entries[8];
 166         list_t *a, *b, *c, *d, *e, *f, *g, *h;
 167
 168         ql_new(&head);
 169         init_entries(entries, sizeof(entries)/sizeof(list_t));
 170         a = &entries[0];
 171         b = &entries[1];
 172         c = &entries[2];
 173         d = &entries[3];
 174         e = &entries[4];
 175         f = &entries[5];
 176         g = &entries[6];
 177         h = &entries[7];
 178
 179         /*
 180          * ql_remove(), ql_before_insert(), and ql_after_insert() are used
 181          * internally by other macros that are already tested, so there's no
 182          * need to test them completely.  However, insertion/deletion from the
 183          * middle of lists is not otherwise tested; do so here.
 184          */
 185         ql_tail_insert(&head, f, link);
 186         ql_before_insert(&head, f, b, link);
 187         ql_before_insert(&head, f, c, link);
 188         ql_after_insert(f, h, link);
 189         ql_after_insert(f, g, link);
 190         ql_before_insert(&head, b, a, link);
 191         ql_after_insert(c, d, link);
 192         ql_before_insert(&head, f, e, link);
 193
 194         test_entries_list(&head, entries, sizeof(entries)/sizeof(list_t));
 195 }
 196 TEST_END
 197
 198 int
 199 main(void)
 200 {
 201
 202         return (test(
 203             test_ql_empty,
 204             test_ql_tail_insert,
 205             test_ql_tail_remove,
 206             test_ql_head_insert,
 207             test_ql_head_remove,
 208             test_ql_insert));
 209 }