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