![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to heap_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib|
Return to heap_test.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib |
1.1 misho 1: /*
2: * BIRD Library -- Universal Heap Macros Tests
3: *
4: * (c) 2015 CZ.NIC z.s.p.o.
5: *
6: * Can be freely distributed and used under the terms of the GNU GPL.
7: */
8:
9: #include "test/birdtest.h"
10: #include "sysdep/config.h"
11: #include "lib/heap.h"
12:
13: #define MAX_NUM 1000
14: #define SPECIAL_KEY -3213
15:
16: #define MY_CMP(x, y) ((x) < (y))
17:
18: #define MY_HEAP_SWAP(heap,a,b,t) \
19: do { \
20: bt_debug("swap(%u %u) ", a, b); \
21: HEAP_SWAP(heap,a,b,t); \
22: } while(0)
23:
24: static int heap[MAX_NUM+1];
25: static uint num;
26:
27: /*
28: * A valid heap must follow these rules:
29: * - `num >= 0`
30: * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
31: */
32: static int
33: is_heap_valid(int heap[], uint num)
34: {
35: uint i;
36:
37: if (num > MAX_NUM)
38: return 0;
39:
40: for (i = 2; i <= num; i++)
41: if (heap[i] < heap[i / 2])
42: return 0;
43:
44: return 1;
45: }
46:
47: static void
48: show_heap(void)
49: {
50: uint i;
51: bt_debug("\n");
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!");
56: bt_debug("\n");
57: }
58:
59: static void
60: init_heap(void)
61: {
62: uint i;
63: num = 0;
64: heap[0] = SPECIAL_KEY; /* heap[0] should be unused */
65: for (i = 1; i <= MAX_NUM; i++)
66: heap[i] = 0;
67: }
68:
69: static int
70: t_heap_insert(void)
71: {
72: uint i;
73:
74: init_heap();
75:
76: for (i = MAX_NUM; i >= 1; i--)
77: {
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);
81: show_heap();
82: bt_assert(is_heap_valid(heap, num));
83: }
84:
85: return 1;
86: }
87:
88: static int
89: t_heap_increase_decrease(void)
90: {
91: uint i;
92:
93: t_heap_insert();
94:
95: for (i = 1; i <= MAX_NUM; i++)
96: {
97: if ((int)i > heap[i])
98: {
99: bt_debug("inc %u ", i);
100: heap[i] = i;
101: HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
102: }
103: else if ((int)i < heap[i])
104: {
105: bt_debug("dec %u ", i);
106: heap[i] = i;
107: HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
108: }
109: show_heap();
110: bt_assert(is_heap_valid(heap, num));
111: }
112:
113: return 1;
114: }
115:
116: static int
117: t_heap_delete(void)
118: {
119: uint i;
120:
121: t_heap_insert();
122:
123: for (i = 1; i <= num; i++)
124: {
125: bt_debug("del at pos %u ", i);
126: HEAP_DELETE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
127: show_heap();
128: bt_assert(is_heap_valid(heap, num));
129: }
130:
131: return 1;
132: }
133:
134: static int
135: t_heap_0(void)
136: {
137: init_heap();
138: t_heap_insert();
139: t_heap_increase_decrease();
140: t_heap_delete();
141:
142: return heap[0] == SPECIAL_KEY;
143: }
144:
145: static int
146: t_heap_insert_random(void)
147: {
148: int i, j;
149: int expected[MAX_NUM+1];
150:
151: init_heap();
152:
153: for (i = 1; i <= MAX_NUM; i++)
154: {
155: heap[i] = expected[i] = bt_random();
156: HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
157: show_heap();
158: bt_assert(is_heap_valid(heap, num));
159: }
160:
161: for (i = 1; i <= MAX_NUM; i++)
162: for (j = 1; j <= MAX_NUM; j++)
163: if(expected[i] == heap[j])
164: break;
165: else if (j == MAX_NUM)
166: {
167: show_heap();
168: bt_abort_msg("Did not find a number %d in heap.", expected[i]);
169: }
170:
171: return 1;
172: }
173:
174: int
175: main(int argc, char *argv[])
176: {
177: bt_init(argc, argv);
178:
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?");
184:
185: return bt_exit_value();
186: }