This source file includes following definitions.
- main
- print_usage
- print_keys
- print_params
- fill_random_test
- dumb_sort
- run_test
- init_predefined_test
1
2
3
4
5
6
7 #include "../adio/include/heap-sort.h"
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11 #include <time.h>
12
13 #define PREDEF_TESTS 2
14
15 #define ALL 0
16 #define RANDOM -1
17 #define CUSTOM -2
18
19
20 #define BUILD 0
21 #define INSERT 1
22 #define EXTRACT 2
23 #define EXTRACT_INSERT 3
24
25 typedef struct {
26 char name[64];
27 int heap_size;
28 int print;
29 int verify;
30 int action_arr_sz;
31 int *action_arr;
32 int *action_count_arr;
33 ADIO_Offset *offsets;
34 ADIO_Offset *correct_order;
35 } test_params_t;
36
37 void print_usage();
38 void print_keys(ADIO_Offset* offsets, int size);
39 void print_params(test_params_t *params);
40 int run_test(test_params_t *test);
41 void fill_random_test(test_params_t *params);
42 void init_predefined_test(test_params_t *params, int index);
43 void dumb_sort(test_params_t *params);
44
45 int main(int argc, char **argv) {
46 int i, print = 1, verify = 1;
47 int adding_elements;
48 int curr_add_idx;
49 int test_type = RANDOM;
50 test_params_t predefined_tests[PREDEF_TESTS];
51 test_params_t test;
52
53
54 adding_elements = 0;
55 curr_add_idx = 0;
56 if (argc == 1) {
57 print_usage();
58 return 1;
59 }
60 i = 1;
61 while (i < argc) {
62 if (!strcmp("-A", argv[i])) {
63 adding_elements = 0;
64 test_type = ALL;
65 i++;
66 }
67 else if (!strcmp("-T", argv[i])) {
68 adding_elements = 0;
69 test_type = atoi(argv[i+1]);
70 i += 2;
71 }
72 else if (!strcmp("-r", argv[i])) {
73 adding_elements = 0;
74 test.heap_size = atoi(argv[i+1]);
75 if (test.heap_size <= 0) {
76 printf("heap size should be a positive integer\n");
77 return 1;
78 }
79 test.offsets = (ADIO_Offset *) malloc(test.heap_size*sizeof(ADIO_Offset));
80 test_type = RANDOM;
81 i += 2;
82 }
83 else if (!strcmp("-e", argv[i])) {
84 test.heap_size = argc - 2;
85 if (test.heap_size <= 0) {
86 printf("need at least one key\n");
87 return 1;
88 }
89 test.offsets = (ADIO_Offset *) malloc(test.heap_size*sizeof(ADIO_Offset));
90 adding_elements = 1;
91 test_type = CUSTOM;
92 i++;
93 }
94 else if (!strcmp("-v", argv[i])) {
95 verify = 1;
96 i++;
97 }
98 else if (!strcmp("-p", argv[i])) {
99 print = 1;
100 i++;
101 }
102 else if (!strcmp("-V", argv[i])) {
103 verify = 0;
104 i++;
105 }
106 else if (!strcmp("-P", argv[i])) {
107 print = 0;
108 i++;
109 }
110 else if (adding_elements) {
111 test.offsets[curr_add_idx] = atoi(argv[i]);
112 curr_add_idx++;
113 i++;
114 }
115 else {
116 printf("Illegal argument: %s", argv[i]);
117 print_usage();
118 return 1;
119 }
120 }
121
122 if (test_type == RANDOM) {
123 fill_random_test(&test);
124 strcpy(test.name, "RANDOMIZED TEST");
125 }
126 else if (test_type == CUSTOM)
127 strcpy(test.name, "CUSTOM TEST");
128 if ((test_type == CUSTOM) || (test_type == RANDOM)) {
129 test.print = print;
130 test.verify = verify;
131 test.action_arr_sz = 2;
132 test.action_arr = (int *) malloc(test.action_arr_sz*sizeof(int));
133 test.action_count_arr = (int *) malloc(test.action_arr_sz*sizeof(int));
134
135
136
137
138 test.action_arr[0] = INSERT;
139 test.action_count_arr[0] = test.heap_size;
140
141 test.action_arr[1] = EXTRACT;
142 test.action_count_arr[1] = test.heap_size;
143
144 if (verify) {
145 test.correct_order = (ADIO_Offset *)malloc(test.heap_size*sizeof(ADIO_Offset));
146 dumb_sort(&test);
147 }
148 if (print)
149 print_params(&test);
150 run_test(&test);
151 }
152 else {
153 if (test_type == ALL) {
154 for (i=0; i<PREDEF_TESTS; i++) {
155 predefined_tests[i].print = print;
156 predefined_tests[i].verify = verify;
157 init_predefined_test(&predefined_tests[i], i);
158 if (print)
159 print_params(&test);
160 run_test(&predefined_tests[i]);
161 }
162 }
163 else {
164 predefined_tests[test_type-1].print = print;
165 predefined_tests[test_type-1].verify = verify;
166 init_predefined_test(&predefined_tests[test_type-1], test_type-1);
167 if (print)
168 print_params(&predefined_tests[test_type-1]);
169 run_test(&predefined_tests[test_type-1]);
170 }
171 }
172
173 return 0;
174 }
175
176 void print_usage() {
177 printf(
178 "Usage: test <options>\n"
179 " -r <size> Create a random test and verify of size <size>\n"
180 " -e <keys> test with the space delimited list of keys\n"
181 " -p print parameters and keys (default)\n"
182 " -P do not print parameters and keys\n"
183 " -v verify keys (default)\n"
184 " -V do not verify keys\n"
185 );
186 }
187
188 void print_keys(ADIO_Offset *offsets, int size) {
189 int i;
190 for (i=0; i < size; i++)
191 printf("%lld ", offsets[i]);
192 }
193
194 void print_params(test_params_t *params) {
195 int i;
196 static char action_map[3][8] = {"BUILD", "INSERT", "EXTRACT"};
197
198 printf("----------------Test Parameters---------------\n");
199 printf("Actions:\n");
200 for (i=0; i<params->action_arr_sz; i++) {
201 printf("%sx%d\n", action_map[params->action_arr[i]],
202 params->action_count_arr[i]);
203 }
204
205 printf("Initial order :\n");
206 print_keys(params->offsets, params->heap_size);
207 printf("\n");
208
209 if (params->verify) {
210 printf("Expected order:\n");
211 print_keys(params->correct_order, params->heap_size);
212 printf("\n");
213 }
214 printf("----------------------------------------------\n");
215 }
216
217 void fill_random_test(test_params_t *params) {
218 int i;
219 int max_key;
220 time_t seed;
221 int order = 0;
222
223 time(&seed);
224 srand(seed);
225
226 order = 0;
227 max_key = 1;
228 while (order < 25) {
229 max_key *= 10;
230 if (!((int) (params->heap_size / max_key)))
231 break;
232 order++;
233 }
234 for (i=0; i < params->heap_size; i++)
235 params->offsets[i] = (rand() % max_key);
236 }
237
238 void dumb_sort(test_params_t *params) {
239 ADIO_Offset *offsets, tmp_offset;
240 int i, j;
241
242 offsets = params->correct_order;
243 memcpy(offsets, params->offsets, params->heap_size*sizeof(ADIO_Offset));
244 for (i=0; i < params->heap_size; i++) {
245 for (j=i; j < params->heap_size; j++) {
246 if (offsets[j] < offsets[i]) {
247 tmp_offset = offsets[i];
248 offsets[i] = offsets[j];
249 offsets[j] = tmp_offset;
250 }
251 }
252 }
253 }
254
255 int run_test(test_params_t *test) {
256 heap_t myheap;
257 ADIO_Offset *extracted;
258 int stored_proc;
259 ADIO_Offset stored_reg_max_len;
260 int i, j, k, err_flag = 0;
261 int curr_insert_idx = 0;
262 int curr_extract_idx = 0;
263
264 create_heap(&myheap, test->heap_size);
265 myheap.size = 0;
266
267 extracted = (ADIO_Offset *) malloc(test->heap_size * sizeof(ADIO_Offset));
268 for (i=0; i < test->action_arr_sz; i++) {
269 for (j=0; j<test->action_count_arr[i]; j++) {
270 switch (test->action_arr[i])
271 {
272 case BUILD:
273 myheap.size = test->heap_size;
274 for (k=0; k < test->heap_size; k++) {
275 myheap.nodes[k].offset = test->offsets[k];
276 myheap.nodes[k].proc = k;
277 }
278 build_heap(&myheap);
279 break;
280 case INSERT:
281 ADIOI_Heap_insert(&myheap, test->offsets[curr_insert_idx],
282 curr_insert_idx, curr_insert_idx);
283 curr_insert_idx++;
284 break;
285 case EXTRACT:
286 heap_extract_min(&myheap, &extracted[curr_extract_idx],
287 &stored_proc, &stored_reg_max_len);
288 if (test->verify && (extracted[curr_extract_idx] !=
289 test->correct_order[curr_extract_idx]))
290 err_flag++;
291 curr_extract_idx++;
292 break;
293 case EXTRACT_INSERT:
294 heap_extract_min(&myheap, &extracted[curr_extract_idx],
295 &stored_proc, &stored_reg_max_len);
296 if (test->verify &&(extracted[curr_extract_idx] !=
297 test->correct_order[curr_extract_idx]))
298 err_flag++;
299 curr_extract_idx++;
300
301 ADIOI_Heap_insert(&myheap, test->offsets[curr_insert_idx],
302 curr_insert_idx, curr_insert_idx);
303 curr_insert_idx++;
304 break;
305 default:
306 break;
307 }
308 }
309 }
310
311 if (test->verify) {
312 if (err_flag) {
313 printf("***%s FAILED***\n", test->name);
314 if (test->print) {
315 printf("Min extraction:\n");
316 print_keys(extracted, test->heap_size);
317 printf("\n");
318 }
319 }
320 else
321 printf("***%s PASSED***\n", test->name);
322 }
323
324 free_heap(&myheap);
325 free(extracted);
326
327 free(test->offsets);
328 if (test->verify)
329 free(test->correct_order);
330 free(test->action_arr);
331 free(test->action_count_arr);
332
333 return err_flag;
334 }
335
336 void init_predefined_test(test_params_t *params, int index) {
337
338 switch (index)
339 {
340 case 0:
341 strcpy(params->name, "TEST 1");
342 params->heap_size = 15;
343 params->action_arr_sz = 3;
344
345
346 params->action_arr =
347 (int *) malloc (params->action_arr_sz*sizeof(int));
348 params->action_count_arr =
349 (int *) malloc (params->action_arr_sz*sizeof(int));
350 params->offsets = (ADIO_Offset *) malloc(params->heap_size*sizeof(ADIO_Offset));
351 if (params->verify)
352 params->correct_order =
353 (ADIO_Offset *) malloc(params->heap_size*sizeof(ADIO_Offset));
354
355
356 params->offsets[0] = 65;
357 params->offsets[1] = 53;
358 params->offsets[2] = 51;
359 params->offsets[3] = 74;
360 params->offsets[4] = 1;
361 params->offsets[5] = 3;
362 params->offsets[6] = 86;
363 params->offsets[7] = 82;
364 params->offsets[8] = 42;
365 params->offsets[9] = 62;
366 params->offsets[10] = 33;
367 params->offsets[11] = 12;
368 params->offsets[12] = 79;
369 params->offsets[13] = 13;
370 params->offsets[14] = 28;
371
372 if (params->verify) {
373 params->correct_order[0] = 1;
374 params->correct_order[1] = 3;
375 params->correct_order[2] = 12;
376 params->correct_order[3] = 33;
377 params->correct_order[4] = 13;
378 params->correct_order[5] = 28;
379 params->correct_order[6] = 42;
380 params->correct_order[7] = 51;
381 params->correct_order[8] = 53;
382 params->correct_order[9] = 62;
383 params->correct_order[10] = 65;
384 params->correct_order[11] = 74;
385 params->correct_order[12] = 79;
386 params->correct_order[13] = 82;
387 params->correct_order[14] = 86;
388 }
389
390 params->action_arr[0] = INSERT;
391 params->action_arr[1] = EXTRACT_INSERT;
392 params->action_arr[11] = EXTRACT;
393
394 params->action_count_arr[0] = 10;
395 params->action_count_arr[1] = 5;
396 params->action_count_arr[11] = 10;
397 break;
398 case 1:
399 strcpy(params->name, "TEST 1");
400 params->heap_size = 15;
401 params->action_arr_sz = 3;
402
403
404 params->action_arr =
405 (int *) malloc (params->action_arr_sz*sizeof(int));
406 params->action_count_arr =
407 (int *) malloc (params->action_arr_sz*sizeof(int));
408 params->offsets = (ADIO_Offset *) malloc(params->heap_size*sizeof(ADIO_Offset));
409 if (params->verify)
410 params->correct_order =
411 (ADIO_Offset *) malloc(params->heap_size*sizeof(ADIO_Offset));
412
413
414 params->offsets[0] = 65;
415 params->offsets[1] = 53;
416 params->offsets[2] = 51;
417 params->offsets[3] = 74;
418 params->offsets[4] = 1;
419 params->offsets[5] = 3;
420 params->offsets[6] = 86;
421 params->offsets[7] = 82;
422 params->offsets[8] = 42;
423 params->offsets[9] = 62;
424 params->offsets[10] = 33;
425 params->offsets[11] = 12;
426 params->offsets[12] = 79;
427 params->offsets[13] = 13;
428 params->offsets[14] = 28;
429
430 if (params->verify) {
431 params->correct_order[0] = 1;
432 params->correct_order[1] = 3;
433 params->correct_order[2] = 12;
434 params->correct_order[3] = 33;
435 params->correct_order[4] = 13;
436 params->correct_order[5] = 28;
437 params->correct_order[6] = 42;
438 params->correct_order[7] = 51;
439 params->correct_order[8] = 53;
440 params->correct_order[9] = 62;
441 params->correct_order[10] = 65;
442 params->correct_order[11] = 74;
443 params->correct_order[12] = 79;
444 params->correct_order[13] = 82;
445 params->correct_order[14] = 86;
446 }
447
448 params->action_arr[0] = INSERT;
449 params->action_arr[1] = EXTRACT_INSERT;
450 params->action_arr[11] = EXTRACT;
451
452 params->action_count_arr[0] = 10;
453 params->action_count_arr[1] = 5;
454 params->action_count_arr[11] = 10;
455 break;
456 default:
457 break;
458 }
459 }