1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/qr.h" 4 5 /* Number of ring entries, in [2..26]. */ 6 #define NENTRIES 9 7 /* Split index, in [1..NENTRIES). */ 8 #define SPLIT_INDEX 5 9 10 typedef struct ring_s ring_t; 11 12 struct ring_s { 13 qr(ring_t) link; 14 char id; 15 }; 16 17 static void 18 init_entries(ring_t *entries) { 19 unsigned i; 20 21 for (i = 0; i < NENTRIES; i++) { 22 qr_new(&entries[i], link); 23 entries[i].id = 'a' + i; 24 } 25 } 26 27 static void 28 test_independent_entries(ring_t *entries) { 29 ring_t *t; 30 unsigned i, j; 31 32 for (i = 0; i < NENTRIES; i++) { 33 j = 0; 34 qr_foreach(t, &entries[i], link) { 35 j++; 36 } 37 assert_u_eq(j, 1, 38 "Iteration over single-element ring should visit precisely " 39 "one element"); 40 } 41 for (i = 0; i < NENTRIES; i++) { 42 j = 0; 43 qr_reverse_foreach(t, &entries[i], link) { 44 j++; 45 } 46 assert_u_eq(j, 1, 47 "Iteration over single-element ring should visit precisely " 48 "one element"); 49 } 50 for (i = 0; i < NENTRIES; i++) { 51 t = qr_next(&entries[i], link); 52 assert_ptr_eq(t, &entries[i], 53 "Next element in single-element ring should be same as " 54 "current element"); 55 } 56 for (i = 0; i < NENTRIES; i++) { 57 t = qr_prev(&entries[i], link); 58 assert_ptr_eq(t, &entries[i], 59 "Previous element in single-element ring should be same as " 60 "current element"); 61 } 62 } 63 64 TEST_BEGIN(test_qr_one) { 65 ring_t entries[NENTRIES]; 66 67 init_entries(entries); 68 test_independent_entries(entries); 69 } 70 TEST_END 71 72 static void 73 test_entries_ring(ring_t *entries) { 74 ring_t *t; 75 unsigned i, j; 76 77 for (i = 0; i < NENTRIES; i++) { 78 j = 0; 79 qr_foreach(t, &entries[i], link) { 80 assert_c_eq(t->id, entries[(i+j) % NENTRIES].id, 81 "Element id mismatch"); 82 j++; 83 } 84 } 85 for (i = 0; i < NENTRIES; i++) { 86 j = 0; 87 qr_reverse_foreach(t, &entries[i], link) { 88 assert_c_eq(t->id, entries[(NENTRIES+i-j-1) % 89 NENTRIES].id, "Element id mismatch"); 90 j++; 91 } 92 } 93 for (i = 0; i < NENTRIES; i++) { 94 t = qr_next(&entries[i], link); 95 assert_c_eq(t->id, entries[(i+1) % NENTRIES].id, 96 "Element id mismatch"); 97 } 98 for (i = 0; i < NENTRIES; i++) { 99 t = qr_prev(&entries[i], link); 100 assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id, 101 "Element id mismatch"); 102 } 103 } 104 105 TEST_BEGIN(test_qr_after_insert) { 106 ring_t entries[NENTRIES]; 107 unsigned i; 108 109 init_entries(entries); 110 for (i = 1; i < NENTRIES; i++) { 111 qr_after_insert(&entries[i - 1], &entries[i], link); 112 } 113 test_entries_ring(entries); 114 } 115 TEST_END 116 117 TEST_BEGIN(test_qr_remove) { 118 ring_t entries[NENTRIES]; 119 ring_t *t; 120 unsigned i, j; 121 122 init_entries(entries); 123 for (i = 1; i < NENTRIES; i++) { 124 qr_after_insert(&entries[i - 1], &entries[i], link); 125 } 126 127 for (i = 0; i < NENTRIES; i++) { 128 j = 0; 129 qr_foreach(t, &entries[i], link) { 130 assert_c_eq(t->id, entries[i+j].id, 131 "Element id mismatch"); 132 j++; 133 } 134 j = 0; 135 qr_reverse_foreach(t, &entries[i], link) { 136 assert_c_eq(t->id, entries[NENTRIES - 1 - j].id, 137 "Element id mismatch"); 138 j++; 139 } 140 qr_remove(&entries[i], link); 141 } 142 test_independent_entries(entries); 143 } 144 TEST_END 145 146 TEST_BEGIN(test_qr_before_insert) { 147 ring_t entries[NENTRIES]; 148 ring_t *t; 149 unsigned i, j; 150 151 init_entries(entries); 152 for (i = 1; i < NENTRIES; i++) { 153 qr_before_insert(&entries[i - 1], &entries[i], link); 154 } 155 for (i = 0; i < NENTRIES; i++) { 156 j = 0; 157 qr_foreach(t, &entries[i], link) { 158 assert_c_eq(t->id, entries[(NENTRIES+i-j) % 159 NENTRIES].id, "Element id mismatch"); 160 j++; 161 } 162 } 163 for (i = 0; i < NENTRIES; i++) { 164 j = 0; 165 qr_reverse_foreach(t, &entries[i], link) { 166 assert_c_eq(t->id, entries[(i+j+1) % NENTRIES].id, 167 "Element id mismatch"); 168 j++; 169 } 170 } 171 for (i = 0; i < NENTRIES; i++) { 172 t = qr_next(&entries[i], link); 173 assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id, 174 "Element id mismatch"); 175 } 176 for (i = 0; i < NENTRIES; i++) { 177 t = qr_prev(&entries[i], link); 178 assert_c_eq(t->id, entries[(i+1) % NENTRIES].id, 179 "Element id mismatch"); 180 } 181 } 182 TEST_END 183 184 static void 185 test_split_entries(ring_t *entries) { 186 ring_t *t; 187 unsigned i, j; 188 189 for (i = 0; i < NENTRIES; i++) { 190 j = 0; 191 qr_foreach(t, &entries[i], link) { 192 if (i < SPLIT_INDEX) { 193 assert_c_eq(t->id, 194 entries[(i+j) % SPLIT_INDEX].id, 195 "Element id mismatch"); 196 } else { 197 assert_c_eq(t->id, entries[(i+j-SPLIT_INDEX) % 198 (NENTRIES-SPLIT_INDEX) + SPLIT_INDEX].id, 199 "Element id mismatch"); 200 } 201 j++; 202 } 203 } 204 } 205 206 TEST_BEGIN(test_qr_meld_split) { 207 ring_t entries[NENTRIES]; 208 unsigned i; 209 210 init_entries(entries); 211 for (i = 1; i < NENTRIES; i++) { 212 qr_after_insert(&entries[i - 1], &entries[i], link); 213 } 214 215 qr_split(&entries[0], &entries[SPLIT_INDEX], ring_t, link); 216 test_split_entries(entries); 217 218 qr_meld(&entries[0], &entries[SPLIT_INDEX], ring_t, link); 219 test_entries_ring(entries); 220 221 qr_meld(&entries[0], &entries[SPLIT_INDEX], ring_t, link); 222 test_split_entries(entries); 223 224 qr_split(&entries[0], &entries[SPLIT_INDEX], ring_t, link); 225 test_entries_ring(entries); 226 227 qr_split(&entries[0], &entries[0], ring_t, link); 228 test_entries_ring(entries); 229 230 qr_meld(&entries[0], &entries[0], ring_t, link); 231 test_entries_ring(entries); 232 } 233 TEST_END 234 235 int 236 main(void) { 237 return test( 238 test_qr_one, 239 test_qr_after_insert, 240 test_qr_remove, 241 test_qr_before_insert, 242 test_qr_meld_split); 243 } 244