treetest.c

/* Notice of Copyright, License and Warranty
**
** This software is Copyright 1999, 2001 Jeffrey S. Dutky
** This software is licensed for use under the terms of the GNU Library
** General Public License (also called the LGPL), a copy of which must
** be included with any distribution of this software. You may also find
** a copy of the LGPL at the Free Software Foundation's web site at
** http://www.fsf.org/ or http://www.gnu.org.
**
** This software is provided "as is" and without any express or implied
** warranties, including, without limitation, the implied waranties of
** merchantability and fitness for a particular purpose.
*/

#include <stdio.h>
#include "searchtree.h"

int cmp(void *d1, void *d2){
   return (int)d1-(int)d2;
}

int print(FILE *f, void *k, void *d, void *n){
   if(n)
       fprintf(f,"%x ",k);
   else
       fprintf(f,"(.) ");
   return 0;
}

int main(int args, char *arg[]){
   int loops=1000, max=200, i;
   int *list, count=0, n, d, err, watch=0;
   SearchTree *tree;
   SearchNode *node;
   int changed=0;
   
   if(args>1){
       if(strcmp(arg[1],"-w")==0)
           watch=1;
       else
           loops=atoi(arg[1]);
   }
   if(args>2){
       if(watch==1)
           loops=atoi(arg[2]);
       else{
           if(strcmp(arg[2],"-w")==0)
               watch=1;
           else
               max=atoi(arg[2]);
       }
   }
   if(args>3){
       if(watch==1)
           max=atoi(arg[3]);
       else
           if(strcmp(arg[3],"-w")==0)
               watch=1;
   }
   if(loops<0 || max<0){
       printf("both loops and max must be positive integers\n");
       return 1;
   }
   printf("%d iterations, %d elements maximum\n",loops,max);
   list=(int*)calloc(max,sizeof(int));
   if(list==NULL){
       printf("Failed to Allocate Array\n");
       return 2;
   }
   tree=createTree(cmp,NULL,NULL); /* allocate tree with no freeing methods */
   if(tree==NULL){
       free(list);
       printf("Failed to Allocate Search Tree\n");
       return 3;
   }
   for(i=0; i<loops; i++){
       if(changed)
           printf(", ");
       changed=0;
       n=1+rand()%max;
       if(rand()%2){ /* insert or remove an element */
           if(rand()%2){
               if(list[n]==1){ /* remove this element */
                   list[n]=0;
                   count--;
                   printf("(%x)",n);
                   fflush(stdout);
                   err=removeNode(tree,(void*)n);
                   if(err){
                       printf("\nFailed to delete valid node: key=%x\n", n);
                       break;
                   }
               }else{ /* insert this element */
                   list[n]=1;
                   count++;
                   printf("%x",n);
                   fflush(stdout);
                   err=insertNode(tree,(void*)n,(void*)n);
                   if(err){
                       printf("\nFailed to insert new node: key=%x\n", n);
                       break;
                   }
               }
               changed=1;
           }else{
               if(list[n]==1){ /* insert existing element */
                   /*printf("!+(%x",n);*/
                   fflush(stdout);
                   err=insertNode(tree,(void*)n,(void*)n);
                   if(!err){
                       printf("\nInserted an existing node: key=%x\n", n);
                       break;
                   }
                   /*printf(")  ");*/
               }else{ /* remove nonexistant elelment */
                   /*printf("!-(%x",n);*/
                   fflush(stdout);
                   err=removeNode(tree,(void*)n);
                   if(!err){
                       printf("\nRemoved a non-existant node: key=%x\n", n);
                       break;
                   }
                   /*printf(")  ");*/
               }
           }
           if(changed){
               node=rotatedNode(tree);
               if(node)
                   printf("[%x", nodeKey(node));
               switch(treeRotated(tree)){
               case 0:
                   printf("");
                   break;
               case 1:
                   printf("+]");
                   break;
               case 2:
                   printf("++]");
                   break;
               case -1:
                   printf("-]");
                   break;
               case -2:
                   printf("--]");
                   break;
               default:
                   printf("??]");
                   break;
               }
               /* treeDump(stdout, tree, BRIEF); */
               
           }
       }else{ /* search for an element */
           if(list[n]){
               /*printf("?(%x",n);*/
               fflush(stdout);
               err=findNode(tree,(void*)n,(void**)&d);
               /*printf(")  ");*/
               if(err){
                   if(d!=n){
                       printf("\nKey/Data Mismatch: Key=%x, Data=%x\n",n,d);
                       break;
                   }
               }else{
                   printf("\nValid Item Not Found in Tree: Key=%x\n",n);
                   break;
               }
           }else{
               /*printf("#(%x",n);*/
               fflush(stdout);
               err=findNode(tree,(void*)n,(void**)&d);
               /*printf(")  ");*/
               if(err){
                   printf("\nInvalid Item Found in Tree: Key=%x\n",n);
                   break;
               }
           }
           fflush(stdout);
       }
       if(watch){
           printf("\n");
           traverseTree(stdout,tree,INORDER,print);
           printf("\n");
       }
       if(err=verifyTree(tree)){
           SearchNode *node;
           
           printf("\nInvalid Tree: %s\n",treeError(err));
           node=rotatedNode(tree);
           if(node)
               printf("node=%x (%p)\n", nodeKey(node), node);
           printf("count=%d\n",count);
           for(n=0;n<max;n++){
               if(list[n]) 
                   printf("%10x: %d\n",n,list[n]);
           }
           treeDump(stdout,tree,FULL);
           break;
       }
   }
   printf("\n%d nodes, %d lazy deletes\n",treeNodes(tree),deadNodes(tree));
   printf("%d iterations completed, %d elements in tree\n",i,count);
   deleteTree(tree);
   printf("program done.\n");
   free(list);
   return 0;
}