| 1 | #include "unit-test.h" |
| 2 | #include "prio-queue.h" |
| 3 | |
| 4 | static int intcmp(const void *va, const void *vb, void *data UNUSED) |
| 5 | { |
| 6 | const int *a = va, *b = vb; |
| 7 | return *a - *b; |
| 8 | } |
| 9 | |
| 10 | |
| 11 | #define MISSING -1 |
| 12 | #define DUMP -2 |
| 13 | #define STACK -3 |
| 14 | #define GET -4 |
| 15 | #define REVERSE -5 |
| 16 | #define REPLACE -6 |
| 17 | |
| 18 | static int show(int *v) |
| 19 | { |
| 20 | return v ? *v : MISSING; |
| 21 | } |
| 22 | |
| 23 | static void test_prio_queue(int *input, size_t input_size, |
| 24 | int *result, size_t result_size) |
| 25 | { |
| 26 | struct prio_queue pq = { intcmp }; |
| 27 | size_t j = 0; |
| 28 | |
| 29 | for (size_t i = 0; i < input_size; i++) { |
| 30 | void *peek, *get; |
| 31 | switch(input[i]) { |
| 32 | case GET: |
| 33 | peek = prio_queue_peek(&pq); |
| 34 | get = prio_queue_get(&pq); |
| 35 | cl_assert(peek == get); |
| 36 | cl_assert(j < result_size); |
| 37 | cl_assert_equal_i(result[j], show(get)); |
| 38 | j++; |
| 39 | break; |
| 40 | case DUMP: |
| 41 | while ((peek = prio_queue_peek(&pq))) { |
| 42 | get = prio_queue_get(&pq); |
| 43 | cl_assert(peek == get); |
| 44 | cl_assert(j < result_size); |
| 45 | cl_assert_equal_i(result[j], show(get)); |
| 46 | j++; |
| 47 | } |
| 48 | break; |
| 49 | case STACK: |
| 50 | pq.compare = NULL; |
| 51 | break; |
| 52 | case REVERSE: |
| 53 | prio_queue_reverse(&pq); |
| 54 | break; |
| 55 | case REPLACE: |
| 56 | get = prio_queue_get(&pq); |
| 57 | cl_assert(i + 1 < input_size); |
| 58 | cl_assert(input[i + 1] >= 0); |
| 59 | cl_assert(j < result_size); |
| 60 | cl_assert_equal_i(result[j], show(get)); |
| 61 | j++; |
| 62 | prio_queue_put(&pq, &input[++i]); |
| 63 | break; |
| 64 | default: |
| 65 | prio_queue_put(&pq, &input[i]); |
| 66 | break; |
| 67 | } |
| 68 | } |
| 69 | cl_assert_equal_i(j, result_size); |
| 70 | clear_prio_queue(&pq); |
| 71 | } |
| 72 | |
| 73 | #define TEST_INPUT(input, result) \ |
| 74 | test_prio_queue(input, ARRAY_SIZE(input), result, ARRAY_SIZE(result)) |
| 75 | |
| 76 | void test_prio_queue__basic(void) |
| 77 | { |
| 78 | TEST_INPUT(((int []){ 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP }), |
| 79 | ((int []){ 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10 })); |
| 80 | } |
| 81 | |
| 82 | void test_prio_queue__mixed(void) |
| 83 | { |
| 84 | TEST_INPUT(((int []){ 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP }), |
| 85 | ((int []){ 2, 3, 4, 1, 5, 6 })); |
| 86 | } |
| 87 | |
| 88 | void test_prio_queue__empty(void) |
| 89 | { |
| 90 | TEST_INPUT(((int []){ 1, 2, GET, GET, GET, 1, 2, GET, GET, GET }), |
| 91 | ((int []){ 1, 2, MISSING, 1, 2, MISSING })); |
| 92 | } |
| 93 | |
| 94 | void test_prio_queue__replace(void) |
| 95 | { |
| 96 | TEST_INPUT(((int []){ REPLACE, 6, 2, 4, REPLACE, 5, 7, GET, |
| 97 | REPLACE, 1, DUMP }), |
| 98 | ((int []){ MISSING, 2, 4, 5, 1, 6, 7 })); |
| 99 | } |
| 100 | |
| 101 | void test_prio_queue__stack(void) |
| 102 | { |
| 103 | TEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }), |
| 104 | ((int []){ 3, 2, 6, 4, 5, 1, 8 })); |
| 105 | } |
| 106 | |
| 107 | void test_prio_queue__reverse_stack(void) |
| 108 | { |
| 109 | TEST_INPUT(((int []){ STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP }), |
| 110 | ((int []){ 1, 2, 3, 4, 5, 6 })); |
| 111 | } |
| 112 | |
| 113 | void test_prio_queue__replace_stack(void) |
| 114 | { |
| 115 | TEST_INPUT(((int []){ STACK, 8, 1, 5, REPLACE, 4, 6, 2, 3, DUMP }), |
| 116 | ((int []){ 5, 3, 2, 6, 4, 1, 8 })); |
| 117 | } |