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