home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 347_01 / example3.c < prev    next >
C/C++ Source or Header  |  1991-10-20  |  7KB  |  220 lines
  1. /*
  2.  *  program Example3
  3.  *  purpose: test shell for threaded AVL-tree. mainly for profiling.
  4.  *
  5.  *  Usage:  EXAMPLE3 <filename>
  6.  *          file <filename> is a text file which contains a list a words,
  7.  *          one per line and left-adjusted. The list may contain duplicated
  8.  *          words.  Program reads the list, writes the words to the monitor
  9.  *          and inserts them into a threaded AVL tree.  Program pauses briefly,
  10.  *          then writes the list (with duplicates eliminated) to the monitor
  11.  *          in order.  Program pauses briefly again, and then items are
  12.  *          randomly deleted from the tree until it is empty. The tree is
  13.  *          then disposed and the program halts.
  14.  *
  15.  *          EXAMPLE3 is just like EXAMPLE1 except for use allocation &
  16.  *          deallocation routines other than "malloc" & "free".
  17.  *
  18.  *  Copyright (c) 1991  Bert C. Hughes
  19.  *                      200 N. Saratoga
  20.  *                      St.Paul, MN 55104
  21.  *                      Compuserve 71211,577
  22.  */
  23.  
  24. #if defined NDEBUG
  25.      !*&^%$!!@@@()^H??||~:~:;:=+
  26.      File "Example3.c" MUST be compiled with NDEBUG undefined,
  27.      so that the "assert()" macro/function will be included.
  28. #endif
  29.  
  30. #include <stdio.h>
  31. #include <string.h>
  32. #include <stdlib.h>
  33. #include <assert.h>
  34. #include "tavltree.h"
  35.  
  36. #if defined __TURBOC__
  37. #include <conio.h>
  38. #else
  39. #define cprintf printf
  40. #endif
  41.  
  42. void pause(void)
  43. {
  44.     int c;
  45.     cprintf("\r\nPress <ENTER> to continue...");
  46.     while (getchar() != '\n');
  47.     cprintf("\r\n");
  48. }
  49.  
  50. /*  Here are dead simple memory allocation & deallocation routines,
  51.     whose only purpose is to illustrate use of initialization function
  52.     "tavl_init" with memory allocation routines other than the standard
  53.     "malloc" and "free".  The TAVL library functions will use only these
  54.     routines to allocate/deallocate memory.
  55. */
  56.  
  57. #define BUFFER_MAX  30000
  58.  
  59. void *alloc(size_t size)
  60. {
  61.     static char membuffer[BUFFER_MAX];
  62.     static unsigned next = 0;
  63.  
  64.     if ((size + next) <= BUFFER_MAX) {
  65.         next += size;
  66.         return (membuffer+next-size);
  67.     }
  68.     else {
  69.         fprintf(stderr,"alloc: Out of memory");
  70.         exit(1);
  71.     }
  72. }
  73.  
  74. void dealloc(void *p)
  75. {
  76. /*dummy routine does nothing - this memory allocator is a one way street*/
  77. }
  78.  
  79.  
  80. void *ident(void *x)    /* function to return identifier of data node */
  81. {                       /* is required by "tavl_init".  In this very */
  82.     return x;           /* simple case, the identifier is simply what */
  83. }                       /* is being inserted into the tree - a string */
  84.  
  85.  
  86. void *cpy(const void *p)
  87. /* create a copy of data item p - which must be a string in this example. */
  88. {
  89.     int size = 1 + strlen(p);
  90.     char *s = alloc(size);
  91.     return(memcpy(s,p,size));
  92. }
  93.  
  94.  
  95. void *rdstr(void *dest, const void *src)
  96. {
  97.     return((void *)strcpy(dest,src));
  98. }
  99.  
  100. main (int argc, char *argv[])
  101. {
  102.     TAVL_treeptr tree;
  103.     TAVL_nodeptr p;
  104.     unsigned int n,i,k;
  105.     char **name;
  106.     char s[128];
  107.  
  108.     int (*cmp)() = strcmp;  /* use C library function "strcmp" to compare */
  109.                             /* identifiers of nodes */
  110.     FILE *fp;
  111.  
  112. #if defined __TURBOC__
  113.     directvideo = 0;   /* change to 1 if there is "snow" on your monitor */
  114. #endif
  115.  
  116.     /* open a file which contains a list of words, one per line */
  117.  
  118.     if (argc < 2)
  119.     strcpy(s,"SHORTLST");
  120.     else
  121.     strcpy(s,argv[1]);
  122.  
  123.     assert((fp = fopen(s,"r")) != NULL);
  124.  
  125.     /* initialize the tree */
  126.     assert((tree = tavl_init(cmp,ident,cpy,dealloc,rdstr,alloc,dealloc)));
  127.  
  128.     cprintf("First, \"%s\" will be read and words found inserted into the tree.\r\n",s);
  129.     pause();
  130.  
  131.     /* build tree of words */
  132.     while (fscanf(fp,"%s",s) != EOF)
  133.         if (tavl_insert(tree,s,NO_REPLACE) == NULL) {
  134.             cprintf("Out of memory!\r\n");
  135.             exit(0);
  136.         }
  137.  
  138.    /* check that all identifiers inserted can be found */
  139.  
  140.     cprintf("Tree is built. Next, word file will be re-read to verify that\r\nall words are in the tree and can be found.\r\n");
  141.     pause();
  142.  
  143.     fseek(fp,0,SEEK_SET);
  144.     cprintf("Testing 'Find'\r\n");
  145.  
  146.     while (fscanf(fp,"%s",s) != EOF) {
  147.         cprintf("%-10.8s",s);
  148.         assert(tavl_find(tree,s) != NULL);
  149.     }
  150.     cprintf("\r\n\nFind OK.\r\n");
  151.     cprintf("Next, data items inserted into the tree will be listed in ascending order.\r\n");
  152.  
  153.     pause();
  154.  
  155.     fclose(fp);
  156.  
  157.     cprintf("In order:\r\n");
  158.     p = tavl_reset(tree);
  159.     n = 0;
  160.     while ((p = tavl_succ(p)) != NULL) {
  161.         cprintf("%-10.8s",p->dataptr);
  162.         n++;
  163.     }
  164.     cprintf("\r\n\nNodes = %u\r\n",n);
  165.  
  166.     k = n;
  167.     p = tavl_reset(tree);
  168.  
  169.     if ((name = malloc(n * sizeof(char *))) == NULL) {
  170.         cprintf("\r\nOut of memory, can't do random deletions test.\r\n");
  171.         cprintf("Testing count in reverse direction...\r\n");
  172.         while (p = tavl_pred(p)) n--;
  173.         assert(n==0);
  174.         cprintf("Reverse direction tested & OK.\r\n");
  175.         exit(0);
  176.     }
  177.  
  178.     cprintf("\r\nNext: An array is filled for random deletions while passing through TAVLtree\r\nin reverse direction.  Words will not be written to output.\r\n");
  179.     pause();
  180.  
  181.     while ((p = tavl_pred(p)) != NULL)
  182.         *(name + --k) = p->dataptr;
  183.  
  184.     assert(k==0);
  185.  
  186.     cprintf("\r\nReverse direction tested & OK.\r\n");
  187.     cprintf("\r\nDelete test:  words to delete will be randomly selected from the array just\r\nfilled, written to screen, and then deleted from the TAVLtree.\r\n");
  188.     pause();
  189.  
  190.     randomize();
  191.  
  192.     cprintf("\r\nDelete test:\r\n");
  193.  
  194.     while (n) {
  195.         i = random(n--);            /* select random identifier to delete */
  196.         cprintf("%-10.8s",*(name + i));
  197.         tavl_delete(tree,*(name + i));     /* delete it */
  198.         for (; i < n; i++)                 /* shrink the names list */
  199.             *(name + i) = *(name + i + 1);
  200.     }
  201.  
  202.     p = tavl_reset(tree);           /* make sure the tree is empty */
  203.     if (tavl_succ(p) != NULL) {
  204.         cprintf("Can't happen: tree still conatains nodes - successor.\r\n");
  205.         exit(0);
  206.     }
  207.  
  208.     p = tavl_reset(tree);           /* make sure the tree is empty */
  209.     if (tavl_pred(p) != NULL) {
  210.         cprintf("Can't happen: tree still conatains nodes - predecessor.\r\n");
  211.         exit(0);
  212.     }
  213.  
  214.     cprintf("\r\nDelete OK.\r\n");
  215.  
  216.     tavl_destroy(tree);
  217.  
  218.     cprintf("OK - tree destroyed - bye.");
  219. }
  220.