]>
git.ipfire.org Git - thirdparty/bird.git/blob - lib/heap_test.c
2 * BIRD Library -- Universal Heap Macros Tests
4 * (c) 2015 CZ.NIC z.s.p.o.
6 * Can be freely distributed and used under the terms of the GNU GPL.
9 #include "test/birdtest.h"
10 #include "sysdep/config.h"
14 #define SPECIAL_KEY -3213
16 #define MY_CMP(x, y) ((x) < (y))
18 #define MY_HEAP_SWAP(heap,a,b,t) \
20 bt_debug("swap(%u %u) ", a, b); \
21 HEAP_SWAP(heap,a,b,t); \
24 static int heap
[MAX_NUM
+1];
28 * A valid heap must follow these rules:
30 * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
33 is_heap_valid(int heap
[], uint num
)
40 for (i
= 2; i
<= num
; i
++)
41 if (heap
[i
] < heap
[i
/ 2])
52 bt_debug("numbers %u; ", num
);
53 for (i
= 0; i
<= num
; i
++)
54 bt_debug("%d ", heap
[i
]);
55 bt_debug(is_heap_valid(heap
, num
) ? "OK" : "NON-VALID HEAP!");
64 heap
[0] = SPECIAL_KEY
; /* heap[0] should be unused */
65 for (i
= 1; i
<= MAX_NUM
; i
++)
76 for (i
= MAX_NUM
; i
>= 1; i
--)
78 bt_debug("ins %u at pos %u ", i
, MAX_NUM
- i
);
79 heap
[MAX_NUM
- i
+ 1] = i
;
80 HEAP_INSERT(heap
, ++num
, int, MY_CMP
, MY_HEAP_SWAP
);
82 bt_assert(is_heap_valid(heap
, num
));
89 t_heap_increase_decrease(void)
95 for (i
= 1; i
<= MAX_NUM
; i
++)
99 bt_debug("inc %u ", i
);
101 HEAP_INCREASE(heap
, num
, int, MY_CMP
, MY_HEAP_SWAP
, i
);
103 else if ((int)i
< heap
[i
])
105 bt_debug("dec %u ", i
);
107 HEAP_INCREASE(heap
, num
, int, MY_CMP
, MY_HEAP_SWAP
, i
);
110 bt_assert(is_heap_valid(heap
, num
));
123 for (i
= 1; i
<= num
; i
++)
125 bt_debug("del at pos %u ", i
);
126 HEAP_DELETE(heap
, num
, int, MY_CMP
, MY_HEAP_SWAP
, i
);
128 bt_assert(is_heap_valid(heap
, num
));
139 t_heap_increase_decrease();
142 return (heap
[0] == SPECIAL_KEY
) ? BT_SUCCESS
: BT_FAILURE
;
146 t_heap_insert_random(void)
149 int expected
[MAX_NUM
+1];
153 for (i
= 1; i
<= MAX_NUM
; i
++)
155 heap
[i
] = expected
[i
] = bt_random();
156 HEAP_INSERT(heap
, ++num
, int, MY_CMP
, MY_HEAP_SWAP
);
158 bt_assert(is_heap_valid(heap
, num
));
161 for (i
= 1; i
<= MAX_NUM
; i
++)
162 for (j
= 1; j
<= MAX_NUM
; j
++)
163 if(expected
[i
] == heap
[j
])
165 else if (j
== MAX_NUM
)
168 bt_abort_msg("Did not find a number %d in heap.", expected
[i
]);
175 main(int argc
, char *argv
[])
179 bt_test_suite(t_heap_insert
, "Inserting a descending sequence of numbers (the worst case)");
180 bt_test_suite(t_heap_insert_random
, "Inserting pseudo-random numbers");
181 bt_test_suite(t_heap_increase_decrease
, "Increasing/Decreasing");
182 bt_test_suite(t_heap_delete
, "Deleting");
183 bt_test_suite(t_heap_0
, "Is a heap[0] really unused?");
185 return bt_exit_value();