unittest_prioq.c (5208B)
1 #include <check.h> 2 3 #include <stdlib.h> 4 5 #include "prioq.h" 6 7 START_TEST(test_prioq_empty) 8 { 9 prioq pq = {0}; 10 struct prioq_elt pe; 11 12 // there's no minimum to return 13 ck_assert_int_eq(0, prioq_min(&pq,&pe)); 14 } 15 END_TEST 16 17 START_TEST(test_prioq_one_item) 18 { 19 prioq pq = {0}; 20 struct prioq_elt pe; 21 unsigned int count; 22 23 pe.dt = 12345; 24 pe.id = 77; 25 prioq_insert(&pq,&pe); 26 27 pe.dt = 0; 28 pe.id = 0; 29 30 count = 0; 31 while (prioq_min(&pq,&pe)) { 32 prioq_delmin(&pq); 33 count++; 34 // prioq_min stores priority and value in pe 35 ck_assert_int_eq(12345, pe.dt); 36 ck_assert_uint_eq(77, pe.id); 37 } 38 39 // there was exactly one entry in the queue 40 ck_assert_uint_eq(count, 1); 41 } 42 END_TEST 43 44 START_TEST(test_prioq_insert_low_priority_to_high) 45 { 46 prioq pq = {0}; 47 struct prioq_elt pe; 48 unsigned long value; 49 50 for (value = 0; value < 5; value++) { 51 long priority = 12345 + value; 52 pe.dt = priority; 53 pe.id = value; 54 ck_assert_int_ne(0, prioq_insert(&pq,&pe)); 55 } 56 57 value = 0; 58 // poison pe to make extra-sure prioq_min always overwrites 59 pe.dt = -2; pe.id = 8; 60 while (prioq_min(&pq,&pe)) { 61 prioq_delmin(&pq); 62 ck_assert_int_eq(12345 + value, pe.dt); 63 ck_assert_uint_eq(value, pe.id); 64 value++; 65 // poison pe to make extra-sure prioq_min always overwrites 66 pe.dt = -2; pe.id = 8; 67 } 68 69 // all 5 inserted entries were retrieved 70 ck_assert_uint_eq(value, 5); 71 } 72 END_TEST 73 74 START_TEST(test_prioq_insert_high_priority_to_low) 75 { 76 prioq pq = {0}; 77 struct prioq_elt pe; 78 unsigned long value; 79 80 for (value = 0; value < 5; value++) { 81 long priority = 12345 - value; 82 pe.dt = priority; 83 pe.id = value; 84 ck_assert_int_ne(0, prioq_insert(&pq,&pe)); 85 } 86 87 // poison pe to make extra-sure prioq_min always overwrites 88 pe.dt = -2; pe.id = 8; 89 while (prioq_min(&pq,&pe)) { 90 prioq_delmin(&pq); 91 value--; 92 ck_assert_int_eq(12345 - value, pe.dt); 93 ck_assert_uint_eq(value, pe.id); 94 // poison pe to make extra-sure prioq_min always overwrites 95 pe.dt = -2; pe.id = 8; 96 } 97 98 // all 5 inserted entries were retrieved 99 ck_assert_uint_eq(value, 0); 100 } 101 END_TEST 102 103 static int compare(const void *a, const void *b) { 104 return (*(int*)a - *(int*)b); 105 } 106 107 START_TEST(test_prioq_insert_all_same_priority) 108 { 109 prioq pq = {0}; 110 struct prioq_elt pe; 111 long priority; 112 unsigned int i; 113 unsigned long sorted[5]; 114 unsigned long actual[5]; 115 116 priority = 12345; 117 for (i = 0; i < 5; i++) { 118 pe.dt = priority; 119 pe.id = i; 120 ck_assert_int_ne(0, prioq_insert(&pq,&pe)); 121 sorted[i] = i; 122 } 123 124 i = 0; 125 // poison pe to make extra-sure prioq_min always overwrites 126 pe.dt = -2; pe.id = 8; 127 while (prioq_min(&pq,&pe)) { 128 prioq_delmin(&pq); 129 actual[i] = pe.id; 130 i++; 131 // poison pe to make extra-sure prioq_min always overwrites 132 pe.dt = -2; pe.id = 8; 133 } 134 // all 5 inserted entries were retrieved 135 ck_assert_uint_eq(i, 5); 136 137 // no defined ordering, but at least all the same values are present 138 qsort(actual, sizeof(actual)/sizeof(*actual), sizeof(*actual), compare); 139 for (i = 0; i < 5; i++) { 140 ck_assert_uint_eq(sorted[i], actual[i]); 141 } 142 } 143 END_TEST 144 145 START_TEST(test_prioq_insert_no_particular_order) 146 { 147 prioq pq = {0}; 148 struct prioq_elt pe; 149 unsigned int i; 150 long priority[5] = {123,234,-345,234,123}; 151 unsigned long value[5] = {77,66,88,55,99}; 152 long expected_priority[5] = {-345,123,123,234,234}; 153 unsigned long expected_value1[5] = {88,77,99,55,66}; // no defined ordering 154 unsigned long expected_value2[5] = {88,99,77,66,55}; // see also below 155 long actual_priority[5]; 156 unsigned long actual_value[5]; 157 158 for (i = 0; i < 5; i++) { 159 pe.dt = priority[i]; 160 pe.id = value[i]; 161 ck_assert_int_ne(0, prioq_insert(&pq,&pe)); 162 } 163 164 i = 0; 165 // poison pe to make extra-sure prioq_min always overwrites 166 pe.dt = -2; pe.id = 8; 167 while (prioq_min(&pq,&pe)) { 168 prioq_delmin(&pq); 169 actual_priority[i] = pe.dt; 170 actual_value[i] = pe.id; 171 i++; 172 // poison pe to make extra-sure prioq_min always overwrites 173 pe.dt = -2; pe.id = 8; 174 } 175 176 for (i = 0; i < 5; i++) { 177 ck_assert_int_eq(expected_priority[i], actual_priority[i]); 178 179 // the first value for priority 123 may be either 77 or 99 180 // for priority 234, either 55 or 66 181 unsigned long expected_value = expected_value1[i]; 182 if (expected_value != actual_value[i]) expected_value = expected_value2[i]; 183 184 ck_assert_uint_eq(expected_value, actual_value[i]); 185 } 186 } 187 END_TEST 188 189 TCase 190 *prioq_something(void) 191 { 192 TCase *tc = tcase_create("basic operations"); 193 194 tcase_add_test(tc, test_prioq_empty); 195 tcase_add_test(tc, test_prioq_one_item); 196 tcase_add_test(tc, test_prioq_insert_low_priority_to_high); 197 tcase_add_test(tc, test_prioq_insert_high_priority_to_low); 198 tcase_add_test(tc, test_prioq_insert_all_same_priority); 199 tcase_add_test(tc, test_prioq_insert_no_particular_order); 200 201 return tc; 202 } 203 204 Suite 205 *prioq_suite(void) 206 { 207 Suite *s = suite_create("notqmail prioq"); 208 209 suite_add_tcase(s, prioq_something()); 210 211 return s; 212 } 213 214 int 215 main(void) 216 { 217 int number_failed; 218 219 SRunner *sr = srunner_create(prioq_suite()); 220 srunner_run_all(sr, CK_NORMAL); 221 number_failed = srunner_ntests_failed(sr); 222 srunner_free(sr); 223 224 return number_failed; 225 }