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