Home | History | Annotate | Line # | Download | only in unit 
      1 #include "test/jemalloc_test.h"
      2 
      3 #include "jemalloc/internal/ql.h"
      4 
      5 /* Number of ring entries, in [2..26]. */
      6 #define NENTRIES 9
      7 
      8 typedef struct list_s list_t;
      9 typedef ql_head(list_t) list_head_t;
     10 
     11 struct list_s {
     12 	ql_elm(list_t) link;
     13 	char id;
     14 };
     15 
     16 static void
     17 test_empty_list(list_head_t *head) {
     18 	list_t *t;
     19 	unsigned i;
     20 
     21 	expect_true(ql_empty(head), "Unexpected element for empty list");
     22 	expect_ptr_null(ql_first(head), "Unexpected element for empty list");
     23 	expect_ptr_null(ql_last(head, link),
     24 	    "Unexpected element for empty list");
     25 
     26 	i = 0;
     27 	ql_foreach(t, head, link) {
     28 		i++;
     29 	}
     30 	expect_u_eq(i, 0, "Unexpected element for empty list");
     31 
     32 	i = 0;
     33 	ql_reverse_foreach(t, head, link) {
     34 		i++;
     35 	}
     36 	expect_u_eq(i, 0, "Unexpected element for empty list");
     37 }
     38 
     39 TEST_BEGIN(test_ql_empty) {
     40 	list_head_t head;
     41 
     42 	ql_new(&head);
     43 	test_empty_list(&head);
     44 }
     45 TEST_END
     46 
     47 static void
     48 init_entries(list_t *entries, unsigned nentries) {
     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 	list_t *t;
     60 	unsigned i;
     61 
     62 	expect_false(ql_empty(head), "List should not be empty");
     63 	expect_c_eq(ql_first(head)->id, entries[0].id, "Element id mismatch");
     64 	expect_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 		expect_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 		expect_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 		expect_c_eq(t->id, entries[i+1].id, "Element id mismatch");
     83 	}
     84 	expect_ptr_null(ql_next(head, &entries[nentries-1], link),
     85 	    "Unexpected element");
     86 
     87 	expect_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 		expect_c_eq(t->id, entries[i-1].id, "Element id mismatch");
     91 	}
     92 }
     93 
     94 TEST_BEGIN(test_ql_tail_insert) {
     95 	list_head_t head;
     96 	list_t entries[NENTRIES];
     97 	unsigned i;
     98 
     99 	ql_new(&head);
    100 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    101 	for (i = 0; i < NENTRIES; i++) {
    102 		ql_tail_insert(&head, &entries[i], link);
    103 	}
    104 
    105 	test_entries_list(&head, entries, NENTRIES);
    106 }
    107 TEST_END
    108 
    109 TEST_BEGIN(test_ql_tail_remove) {
    110 	list_head_t head;
    111 	list_t entries[NENTRIES];
    112 	unsigned i;
    113 
    114 	ql_new(&head);
    115 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    116 	for (i = 0; i < NENTRIES; i++) {
    117 		ql_tail_insert(&head, &entries[i], link);
    118 	}
    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 	list_head_t head;
    130 	list_t entries[NENTRIES];
    131 	unsigned i;
    132 
    133 	ql_new(&head);
    134 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    135 	for (i = 0; i < NENTRIES; i++) {
    136 		ql_head_insert(&head, &entries[NENTRIES-i-1], link);
    137 	}
    138 
    139 	test_entries_list(&head, entries, NENTRIES);
    140 }
    141 TEST_END
    142 
    143 TEST_BEGIN(test_ql_head_remove) {
    144 	list_head_t head;
    145 	list_t entries[NENTRIES];
    146 	unsigned i;
    147 
    148 	ql_new(&head);
    149 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    150 	for (i = 0; i < NENTRIES; i++) {
    151 		ql_head_insert(&head, &entries[NENTRIES-i-1], link);
    152 	}
    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 	list_head_t head;
    164 	list_t entries[8];
    165 	list_t *a, *b, *c, *d, *e, *f, *g, *h;
    166 
    167 	ql_new(&head);
    168 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    169 	a = &entries[0];
    170 	b = &entries[1];
    171 	c = &entries[2];
    172 	d = &entries[3];
    173 	e = &entries[4];
    174 	f = &entries[5];
    175 	g = &entries[6];
    176 	h = &entries[7];
    177 
    178 	/*
    179 	 * ql_remove(), ql_before_insert(), and ql_after_insert() are used
    180 	 * internally by other macros that are already tested, so there's no
    181 	 * need to test them completely.  However, insertion/deletion from the
    182 	 * middle of lists is not otherwise tested; do so here.
    183 	 */
    184 	ql_tail_insert(&head, f, link);
    185 	ql_before_insert(&head, f, b, link);
    186 	ql_before_insert(&head, f, c, link);
    187 	ql_after_insert(f, h, link);
    188 	ql_after_insert(f, g, link);
    189 	ql_before_insert(&head, b, a, link);
    190 	ql_after_insert(c, d, link);
    191 	ql_before_insert(&head, f, e, link);
    192 
    193 	test_entries_list(&head, entries, sizeof(entries)/sizeof(list_t));
    194 }
    195 TEST_END
    196 
    197 static void
    198 test_concat_split_entries(list_t *entries, unsigned nentries_a,
    199     unsigned nentries_b) {
    200 	init_entries(entries, nentries_a + nentries_b);
    201 
    202 	list_head_t head_a;
    203 	ql_new(&head_a);
    204 	for (unsigned i = 0; i < nentries_a; i++) {
    205 		ql_tail_insert(&head_a, &entries[i], link);
    206 	}
    207 	if (nentries_a == 0) {
    208 		test_empty_list(&head_a);
    209 	} else {
    210 		test_entries_list(&head_a, entries, nentries_a);
    211 	}
    212 
    213 	list_head_t head_b;
    214 	ql_new(&head_b);
    215 	for (unsigned i = 0; i < nentries_b; i++) {
    216 		ql_tail_insert(&head_b, &entries[nentries_a + i], link);
    217 	}
    218 	if (nentries_b == 0) {
    219 		test_empty_list(&head_b);
    220 	} else {
    221 		test_entries_list(&head_b, entries + nentries_a, nentries_b);
    222 	}
    223 
    224 	ql_concat(&head_a, &head_b, link);
    225 	if (nentries_a + nentries_b == 0) {
    226 		test_empty_list(&head_a);
    227 	} else {
    228 		test_entries_list(&head_a, entries, nentries_a + nentries_b);
    229 	}
    230 	test_empty_list(&head_b);
    231 
    232 	if (nentries_b == 0) {
    233 		return;
    234 	}
    235 
    236 	list_head_t head_c;
    237 	ql_split(&head_a, &entries[nentries_a], &head_c, link);
    238 	if (nentries_a == 0) {
    239 		test_empty_list(&head_a);
    240 	} else {
    241 		test_entries_list(&head_a, entries, nentries_a);
    242 	}
    243 	test_entries_list(&head_c, entries + nentries_a, nentries_b);
    244 }
    245 
    246 TEST_BEGIN(test_ql_concat_split) {
    247 	list_t entries[NENTRIES];
    248 
    249 	test_concat_split_entries(entries, 0, 0);
    250 
    251 	test_concat_split_entries(entries, 0, 1);
    252 	test_concat_split_entries(entries, 1, 0);
    253 
    254 	test_concat_split_entries(entries, 0, NENTRIES);
    255 	test_concat_split_entries(entries, 1, NENTRIES - 1);
    256 	test_concat_split_entries(entries, NENTRIES / 2,
    257 	    NENTRIES - NENTRIES / 2);
    258 	test_concat_split_entries(entries, NENTRIES - 1, 1);
    259 	test_concat_split_entries(entries, NENTRIES, 0);
    260 }
    261 TEST_END
    262 
    263 TEST_BEGIN(test_ql_rotate) {
    264 	list_head_t head;
    265 	list_t entries[NENTRIES];
    266 	unsigned i;
    267 
    268 	ql_new(&head);
    269 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    270 	for (i = 0; i < NENTRIES; i++) {
    271 		ql_tail_insert(&head, &entries[i], link);
    272 	}
    273 
    274 	char head_id = ql_first(&head)->id;
    275 	for (i = 0; i < NENTRIES; i++) {
    276 		assert_c_eq(ql_first(&head)->id, head_id, "");
    277 		ql_rotate(&head, link);
    278 		assert_c_eq(ql_last(&head, link)->id, head_id, "");
    279 		head_id++;
    280 	}
    281 	test_entries_list(&head, entries, NENTRIES);
    282 }
    283 TEST_END
    284 
    285 TEST_BEGIN(test_ql_move) {
    286 	list_head_t head_dest, head_src;
    287 	list_t entries[NENTRIES];
    288 	unsigned i;
    289 
    290 	ql_new(&head_src);
    291 	ql_move(&head_dest, &head_src);
    292 	test_empty_list(&head_src);
    293 	test_empty_list(&head_dest);
    294 
    295 	init_entries(entries, sizeof(entries)/sizeof(list_t));
    296 	for (i = 0; i < NENTRIES; i++) {
    297 		ql_tail_insert(&head_src, &entries[i], link);
    298 	}
    299 	ql_move(&head_dest, &head_src);
    300 	test_empty_list(&head_src);
    301 	test_entries_list(&head_dest, entries, NENTRIES);
    302 }
    303 TEST_END
    304 
    305 int
    306 main(void) {
    307 	return test(
    308 	    test_ql_empty,
    309 	    test_ql_tail_insert,
    310 	    test_ql_tail_remove,
    311 	    test_ql_head_insert,
    312 	    test_ql_head_remove,
    313 	    test_ql_insert,
    314 	    test_ql_concat_split,
    315 	    test_ql_rotate,
    316 	    test_ql_move);
    317 }
    318