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