Home | History | Annotate | Line # | Download | only in unit 
      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