[13] | 1 | /* |
---|
| 2 | * Revision Control Information |
---|
| 3 | * |
---|
| 4 | * /projects/hsis/CVS/utilities/avl/avl_bench1.c,v |
---|
| 5 | * rajeev |
---|
| 6 | * 1.3 |
---|
| 7 | * 1995/08/08 22:36:26 |
---|
| 8 | * |
---|
| 9 | */ |
---|
| 10 | #include <stdio.h> |
---|
| 11 | #include "array.h" |
---|
| 12 | #include "avl.h" |
---|
| 13 | #include "util.h" |
---|
| 14 | |
---|
| 15 | #define MAX_WORD 1024 |
---|
| 16 | |
---|
| 17 | extern long random(); |
---|
| 18 | |
---|
| 19 | /* ARGSUSED */ |
---|
| 20 | main(argc, argv) |
---|
| 21 | char *argv; |
---|
| 22 | { |
---|
| 23 | array_t *words; |
---|
| 24 | avl_tree *table; |
---|
| 25 | char word[MAX_WORD], *tempi, *tempj; |
---|
| 26 | register int i, j; |
---|
| 27 | long time; |
---|
| 28 | #ifdef TEST |
---|
| 29 | avl_generator *gen; |
---|
| 30 | char *key; |
---|
| 31 | #endif |
---|
| 32 | |
---|
| 33 | /* read the words */ |
---|
| 34 | words = array_alloc(char *, 1000); |
---|
| 35 | while (gets(word) != NIL(char)) { |
---|
| 36 | array_insert_last(char *, words, util_strsav(word)); |
---|
| 37 | if (array_n(words) == 100000) break; |
---|
| 38 | } |
---|
| 39 | |
---|
| 40 | /* scramble them */ |
---|
| 41 | for(i = array_n(words)-1; i >= 1; i--) { |
---|
| 42 | j = random() % i; |
---|
| 43 | tempi = array_fetch(char *, words, i); |
---|
| 44 | tempj = array_fetch(char *, words, j); |
---|
| 45 | array_insert(char *, words, i, tempj); |
---|
| 46 | array_insert(char *, words, j, tempi); |
---|
| 47 | } |
---|
| 48 | |
---|
| 49 | #ifdef TEST |
---|
| 50 | (void) printf("Initial data is\n"); |
---|
| 51 | for(i = array_n(words)-1; i >= 0; i--) { |
---|
| 52 | (void) printf("%s\n", array_fetch(char *, words, i)); |
---|
| 53 | } |
---|
| 54 | #endif |
---|
| 55 | |
---|
| 56 | /* time putting them into an avl tree */ |
---|
| 57 | time = util_cpu_time(); |
---|
| 58 | table = avl_init_table(strcmp); |
---|
| 59 | for(i = array_n(words)-1; i >= 0; i--) { |
---|
| 60 | (void) avl_insert(table, array_fetch(char *, words, i), NIL(char)); |
---|
| 61 | } |
---|
| 62 | (void) printf("Elapsed time for insert of %d objects was %s\n", |
---|
| 63 | array_n(words), util_print_time(util_cpu_time() - time)); |
---|
| 64 | |
---|
| 65 | #ifdef TEST |
---|
| 66 | (void) printf("Sorted data is\n"); |
---|
| 67 | avl_foreach_item(table, gen, AVL_FORWARD, &key, NIL(char *)) { |
---|
| 68 | (void) printf("%s\n", key); |
---|
| 69 | } |
---|
| 70 | #endif |
---|
| 71 | return 0; |
---|
| 72 | } |
---|