home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / c / msc51 / example / cflow.c next >
Encoding:
C/C++ Source or Header  |  1988-08-11  |  43.7 KB  |  1,236 lines
  1. #include <stdio.h>
  2. #include <ctype.h>
  3.  
  4. typedef unsigned int size_t;
  5.  
  6. extern char *strchr(char *, int);
  7. extern char *strcpy(char *, char *);
  8. extern char *strdup(char *);
  9. extern int atoi(char *);
  10. extern int strcmp(char *, char *);
  11. extern void *malloc(size_t);
  12. extern void exit(int);
  13. extern void free(void *);
  14.  
  15. int lineno;                    /* The current line number being parsed */
  16. int level;                    /* The level of quotes or comments being parsed */
  17. int parens;                    /* current parenthesis level */
  18. int braces;                    /* current curly brace level */
  19. int totalfuncs;                /* total number of functions seen */
  20.  
  21. #define PARENS(c) ( ( c == '(' ) - ( c == ')' ) )
  22. #define BRACES(c) ( ( c == '{' ) - ( c == '}' ) )
  23.  
  24. #define INITIA 0     /* Initial state of input stream machine */
  25. #define BEGCOM 1     /* Possible beginning of comment state */
  26. #define COMMEN 2     /* In comment state */
  27. #define AFTCOM 3     /* Possible end of comment state */
  28. #define DOUBQT 4     /* In double quote state */
  29. #define DBQTBS 5     /* Backslash in double quote state */
  30. #define SINGQT 6     /* In single quote state */
  31. #define SGQTBS 7     /* Backslash in single quote state */
  32. #define POUND 8     /* Preprocessor directive */
  33. #define BKSLHPND 9     /* Backslash in preprocessor directive */
  34.  
  35. #define TYPE 16         /* This character might preceed a possible return type */
  36. #define NAME 32     /* This character might preceed a possible function name */
  37.  
  38. #define HASHSIZE ( 2 << 10 )    /* Must be a power of two */
  39. #if 0
  40. #define MYBUFSIZ 15872            /* Size of buffer used on input stream */
  41. #endif
  42.  
  43. /****************************************************************/
  44. /**                                                            **/
  45. /**   ARGUMENTS: a structure capable of keeping info on the    **/
  46. /**              particular state of a file stream             **/
  47. /**                                                            **/
  48. /**   RETURN: none                                             **/
  49. /**                                                            **/
  50. /**   DESCRIPTION: SAVEPLACE saves the position in the buffer, **/
  51. /**   the line number, the current count of braces, and parens **/
  52. /**                                                            **/
  53. /**   GLOBAL VARS REFERENCED: lineno, braces, parens.          **/
  54. /**                                                            **/
  55. /**   GLOBAL VARS MODIFIED: none                               **/
  56. /**                                                            **/
  57. /****************************************************************/
  58.  
  59. #define SAVEPLACE(x) (x).lineno = lineno; (x).braces = braces; \
  60. (x).parens = parens; (x).place = ftell( fp )
  61.  
  62. /****************************************************************/
  63. /**                                                            **/
  64. /**   ARGUMENTS: a structure capable of keeping info on the    **/
  65. /**              particular state of a file stream.            **/
  66. /**                                                            **/
  67. /**   RETURN: none                                             **/
  68. /**                                                            **/
  69. /**   DESCRIPTION: RECOVERPLACE macro restores the position,   **/
  70. /**   the line number, the current count of braces, and parens **/
  71. /**   of the last time a SAVEPLACE was done to the argument.   **/
  72. /**                                                            **/
  73. /**   GLOBAL VARS REFERENCED: lineno, braces, parens.          **/
  74. /**                                                            **/
  75. /**   GLOBAL VARS MODIFIED: lineno, braces, parens, fp         **/
  76. /**                                                            **/
  77. /****************************************************************/
  78.  
  79. #define RECOVERPLACE(x) lineno = (x).lineno; braces = \
  80. (x).braces; parens = (x).parens; fseek( fp, (x).place, 0 )
  81.  
  82. /***************************************************************************/
  83. /**                                                                       **/
  84. /**  Global struct/union/enums                                            **/
  85. /**                                                                       **/
  86. /***************************************************************************/
  87.  
  88. enum relationchoice {
  89.         CALLER,
  90.         CALLEE
  91.     };
  92.  
  93. struct placeptr {
  94.         long place;            /* position as reported/used by ftell/fseek */
  95.         int parens;            /* parenthesis level to save/recover */
  96.         int braces;            /* curly brace level to save/recover */
  97.         int lineno;            /* The current line number being parsed */
  98.         };
  99.  
  100. struct func_ref_type {
  101.         char *name;                /* name of function referenced */
  102.         char *type;                /* type fo functions return */
  103.         char *pnext_func_ref;    /* pointer to next function in hashtable */
  104.         char *pcallerlist;        /* singly linked list of pointers to functions
  105.                                     callee's */
  106.         char *pcalleelist;        /* singly linked list of pointers to functions
  107.                                     caller's */
  108.         char *file_name;        /* name of file containing function reference */
  109.         int lineno;                /* line number of reference to function */
  110.         int xref;                /* cross reference of last pruning */
  111.         };
  112.  
  113.     /* hash table */
  114. struct func_ref_type *hashtbl[ HASHSIZE ] = { (struct func_ref_type *)NULL };
  115.  
  116. struct listtype {
  117.         struct func_ref_type *pelist;
  118.         char *pnext_func_ref;    /* pointer to next element of list */
  119.         char *file_name;        /* name of file where reference occoured */
  120.         int lineno;                /* line number where reference occoured */
  121.         };
  122.  
  123. struct listtype ellipses = {     /* A null list element for pruning purposes */
  124.                             (struct func_ref_type *)NULL, 
  125.                             (char *)NULL, 
  126.                             (char *)NULL, 
  127.                             0 
  128.                             };
  129.  
  130. struct placeptr last_func_name;
  131. struct placeptr last_func_ret_type;
  132.  
  133.  
  134. /***************************************************************************/
  135. /**                                                                       **/
  136. /**  Function prototypes                                                  **/
  137. /**                                                                       **/
  138. /***************************************************************************/
  139.  
  140. int mycompare( char **, char ** );
  141. int getsucc();                
  142. int hashfunc( char * );
  143. int ismember( char *, char *[] );
  144. int main( int, char *[] );
  145. int nsuccmemb( char * );
  146. int succpos( int );
  147.  
  148. static void quicksort( char *, char * );
  149. static void swap ( char *, register char *, unsigned int );
  150. struct func_ref_type *findname( char * );
  151. struct func_ref_type *makename( char * );
  152.  
  153. void addlist( struct func_ref_type *, struct func_ref_type *, char *, 
  154.             int, enum relationchoice );
  155. void dumptree( struct func_ref_type *, int, enum relationchoice );
  156. void findproc( void );
  157. void initstatemachine();
  158. void qsort( char *, unsigned int, unsigned int, int (*)( char **, char ** ) );
  159. void readtoken( char *, char * );  
  160. void sortdump( enum relationchoice );
  161.  
  162.  
  163.  
  164. /***************************************************************************/
  165. /**                                                                       **/
  166. /**  Global declarations                                                  **/
  167. /**                                                                       **/
  168. /***************************************************************************/
  169.  
  170. char *defaulttype = "int";        /* Pointer to the default return type for C */
  171. char *endofsp = "Out of space";    /* Pointer to error message */
  172. char *reswords[] = {             /* reserved words that could look like 
  173.                                                                 functions */
  174.                     "if", 
  175.                     "while", 
  176.                     "for", 
  177.                     "return",
  178.                        "sizeof", 
  179.                        "switch", 
  180.                     NULL 
  181.                     };
  182.  
  183. char alphanum[] =                 /* array of alpha numeric characters */
  184. "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789";
  185.                                 /* delimiters used by cflow */
  186. char delimits[] = " !@#$%^&*()-+=<>,.?/:;~`'|\n\\\t";
  187. char filename[ 30 ];            /* Contains the name of the current file 
  188.                                                             being scanned */
  189.                                 /* array of state transitions for input
  190.                                     state machine */
  191. char gotonextstate[ 10 ][ 128 ] = { 0 };
  192. #if 0
  193. char mybuffer[ MYBUFSIZ ];        /* Buffer for the input file */
  194. #endif
  195. char parentproc[ 2048 ];            /* Name of current parent procedure */
  196. char procname[ 2048 ];            /* Contains the name of the procedure 
  197.                                                 reference being scanned */
  198. char spceq[] = " \t\n\r";        /* whitespace */
  199. char *typename;            /* Contains the name of the return type of the  
  200.                                                 reference being scanned */
  201.  
  202. FILE *fp;                        /* File pointer used for input */
  203. int cutoff = 35;                /* Maximum depth of output ( default 35 ) */
  204. int verbose = 0;                /* Verbose flag ( 0 off, 1 on ) */
  205. enum relationchoice relationship = CALLEE;        
  206.                                 /* relationship wanted on output 
  207.                                                         ( default CALLEE ) */
  208. int xref = 0;                    /* Starting xref number */
  209.  
  210. /****************************************************************/
  211. /**                                                            **/
  212. /**   ARGUMENTS: count of command line arguments               **/
  213. /**              a pointer to the array of command line args.  **/
  214. /**                                                            **/
  215. /**   RETURN: 0 if no errors, -1 if out of memory.             **/
  216. /**                                                            **/
  217. /**   DESCRIPTION: This program scanns the flags, and sets     **/
  218. /**   appropriate flags.  After this all of the remaining args **/
  219. /**   that can be opened as files are opened and the contents  **/
  220. /**   scanned for function references.  These are put in lists **/
  221. /**   such that each function has a linked list of caller to   **/
  222. /**   that function, and of callees of that function.  On      **/
  223. /**   output either the callee tree(s) is/are printed, or the  **/
  224. /**   callers trees are printed under control of the -r flag.  **/
  225. /**   If there is more than one tree to be printed, then the   **/
  226. /**   function names, which are the roots of the trees, are    **/
  227. /**   sorted lexicographically before output.                  **/
  228. /**                                                            **/
  229. /**   GLOBAL VARS REFERENCED: verbose, cutoff, relationship    **/
  230. /**                           parens, braces, lineno, level,   **/
  231. /**                           totalfuncs                       **/
  232. /**                                                            **/
  233. /**   GLOBAL VARS MODIFIED: verbose, cutoff, relationship      **/
  234. /**                         parens, braces, lineno, level,     **/
  235. /**                         totalfuncs                         **/
  236. /**                                                            **/
  237. /****************************************************************/
  238.  
  239. int main( argc, argv )
  240.  
  241.     int argc;
  242.     char *argv[];
  243.  
  244. { 
  245.     int c;
  246.     if ( argc < 2 )
  247.         {
  248.         printf( "usage: cflow [-v][-r][-d] filelist" );
  249.         }
  250.     else
  251.         {
  252.         initstatemachine();
  253.         while ( --argc > 0 )
  254.             {                     /* for all flags/files on the command line */    
  255.             ++argv;
  256.             if ( ( c = **argv ) == '-' || c == '/' )
  257.                 {    /* we are processing a flag */
  258.                 while ( c = *(++(*argv)) )
  259.                     {
  260.                     switch( c )
  261.                         {    
  262.  
  263.                     case 'v': /* be verbose on self references */
  264.                     case 'V':
  265.                             verbose++;
  266.                             break;
  267.  
  268.                     case 'r': /* reverse the caller:callee relationship */
  269.                     case 'R':    
  270.                             relationship = CALLER;
  271.                             break;
  272.  
  273.                     case 'd': /* set the flow graph cutoff depth */
  274.                     case 'D':
  275.                             if ( isdigit(*(++(*argv))) )
  276.                                 {
  277.                                 cutoff = atoi( *argv );
  278.                                 }
  279.                             break;
  280.                         }
  281.                     }    /* End of while */
  282.                 }
  283.             else
  284.                 {    /* we are processing a file, and should be done 
  285.                         with flags */
  286.                 if ( ( fp = fopen( *argv, "rt" ) ) == NULL )
  287.                     { 
  288.                     printf( "cflow: can't open %s\n", *argv );
  289.                     }
  290.                 else
  291.                     {
  292. #if 0
  293.                     setvbuf( fp, mybuffer, _IOFBF, (unsigned int)sizeof( mybuffer ) );
  294. #endif
  295.                     puts( *argv );
  296.                     strcpy( filename, *argv );
  297.                     totalfuncs = parens = braces = level = 0;
  298.                     lineno = 1;
  299.                     SAVEPLACE( last_func_name );
  300.                     SAVEPLACE( last_func_ret_type );
  301.                     while ( succpos( '(' ) )
  302.                         {            /* we have found a begin paren */
  303.                         findproc();
  304.                         }    /* End of while */
  305.                     fclose( fp );
  306.                     }
  307.                 }
  308.             }    /* End of while */
  309.         }
  310.     if ( relationship == CALLEE )
  311.         {    /* "normal" caller:callee relationship */
  312.         if ( findname( "main" ) )
  313.             {    /* Found main */
  314.             dumptree( findname( "main" ), 0, relationship );
  315.             }
  316.         else
  317.             {    /* No main found */
  318.             sortdump( relationship );
  319.             }
  320.         }
  321.     else
  322.         {    /* reverse caller:callee relationship */
  323.         sortdump( relationship );
  324.         }
  325.     return( 0 );
  326. }
  327.  
  328.  
  329.  
  330. /****************************************************************/
  331. /**                                                            **/
  332. /**   ARGUMENTS: none                                          **/
  333. /**                                                            **/
  334. /**   RETURN: none                                             **/
  335. /**                                                            **/
  336. /**   DESCRIPTION: findproc locates the name of the function   **/
  337. /**   preceeding the parenthesis, and figures out whether we   **/
  338. /**   are looking at a function definition, or a function call **/
  339. /**   also adds to the caller, and callee list of the function **/
  340. /**   as appropriate. ( see addlist() )                        **/
  341. /**                                                            **/
  342. /**   GLOBAL VARS REFERENCED: last_func_ret_type,              **/
  343. /**                           last_func_name, alphanum,        **/
  344. /**                           procname, braces, parentproc,    **/
  345. /**                           lineno, parens, spceq,           **/
  346. /**                           defaulttype                      **/
  347. /**                                                            **/
  348. /**   GLOBAL VARS MODIFIED: none                               **/
  349. /**                                                            **/
  350. /**                                                            **/
  351. /****************************************************************/
  352.  
  353. void findproc()
  354.  
  355. {
  356.     char *thisplace;
  357.     long sizetype;
  358.     int oldlineno, oldbraces, oldparens;
  359.     struct placeptr place, typeplace, tplace;
  360.     struct func_ref_type *alist, *blist;
  361.     SAVEPLACE( place );
  362.     typeplace = last_func_ret_type;
  363.     place.place++;
  364.     RECOVERPLACE( last_func_name );
  365.     sizetype = last_func_name.place;
  366.     readtoken( alphanum, procname );
  367.     if ( ! braces )
  368.         {
  369.         strcpy( parentproc, procname );
  370.         }
  371.     if ( *procname && strchr( alphanum, *procname ) && 
  372.             ( ismember( procname, reswords ) == -1 ) )
  373.         {        /* This is a function call, prototype, or definition */
  374.         oldlineno = lineno;
  375.         oldbraces = braces;
  376.         oldparens = parens + 1;
  377.         while ( succpos( ')' ) )
  378.             {
  379.             getsucc();
  380.             if ( parens <= oldparens )
  381.                 {
  382.                 break;
  383.                 }
  384.             }
  385.         nsuccmemb( spceq ); 
  386.         if ( getsucc() != ';' || oldbraces != 0 )
  387.             {    /* This is a call or a definition */
  388.             alist = makename( parentproc );
  389.             blist = makename( procname );
  390.  
  391.             if ( oldbraces )
  392.                 {    /* This is scanning a call */
  393.                 addlist( alist, blist, filename, oldlineno, CALLEE );
  394.                 addlist( blist, alist, filename, oldlineno, CALLER );
  395.                 }
  396.             else
  397.                 {    /* This is scanning a definition */
  398.                 if ( alist->file_name )
  399.                     {
  400.                     free( alist->file_name );
  401.                     }
  402.                 alist->file_name = strdup( filename );
  403.                 alist->lineno = oldlineno;
  404.                 }
  405.             }
  406.         else
  407.             {    /* This is scanning a prototype */
  408.             RECOVERPLACE( typeplace );
  409.                         /* remove starting whitespace */
  410.             nsuccmemb( spceq ); 
  411.             SAVEPLACE( typeplace );
  412.             sizetype -= typeplace.place;
  413.             if ( ( thisplace = typename = malloc( sizetype+ 1 ) ) == NULL )
  414.                 {
  415.                 fprintf( stderr, endofsp );
  416.                 exit( -1 );
  417.                 }
  418.             for ( thisplace = typename; --sizetype >= 0L; )
  419.                 {
  420.                 *thisplace++ = (char)getsucc();
  421.                 }    /* End of for */
  422.             *thisplace = '\0';
  423.             alist = makename( procname );
  424.             if ( alist->type != defaulttype )
  425.                 {
  426.                 free( alist->type );
  427.                 }
  428.             alist->type = typename;
  429.             }
  430.         }
  431.     RECOVERPLACE( place );
  432. } 
  433.  
  434.  
  435. /****************************************************************/
  436. /**                                                            **/
  437. /**   ARGUMENTS: a token name.                                 **/
  438. /**                                                            **/
  439. /**   RETURN: a pointer to a struct func_ref_type              **/
  440. /**                                                            **/
  441. /**   DESCRIPTION: makename sets up an function reference      **/
  442. /**   structure for hash lookup later.                         **/
  443. /**                                                            **/
  444. /**   GLOBAL VARS REFERENCED: hashtbl, hashval, totalfuncs,    **/
  445. /**                           endofsp                          **/
  446. /**                                                            **/
  447. /**                                                            **/
  448. /**   GLOBAL VARS MODIFIED: hashtbl, hashval, totalfuncs       **/
  449. /**                                                            **/
  450. /****************************************************************/
  451.  
  452. struct func_ref_type *makename( nameptr )
  453.  
  454.     char *nameptr;
  455.  
  456. {
  457.     struct func_ref_type *pelist;
  458.     int hashval;
  459.     int newel = 1;
  460.     pelist = hashtbl[ hashval = hashfunc( nameptr ) ];
  461.     if ( pelist )
  462.         {
  463.         while ( ( newel = strcmp( nameptr, pelist->name ) ) &&
  464.                 pelist->pnext_func_ref )
  465.             {    
  466.             pelist = (struct func_ref_type *)pelist->pnext_func_ref;
  467.             }    /* End of while */
  468.         if ( newel )
  469.             {
  470.             if ( ( pelist->pnext_func_ref = 
  471.                     malloc( sizeof( struct func_ref_type ) ) ) == NULL )
  472.                 {
  473.                 fprintf( stderr, endofsp );
  474.                 exit( -1 );
  475.                 }
  476.             pelist = (struct func_ref_type *)(pelist->pnext_func_ref);
  477.             totalfuncs++;
  478.             }
  479.         }
  480.     else
  481.         {
  482.         if ( ( pelist = ( hashtbl[ hashval ] 
  483.             = (struct func_ref_type *)malloc( 
  484.             sizeof( struct func_ref_type ) ) ) ) == NULL )
  485.             {
  486.             fprintf( stderr, endofsp );
  487.             exit( -1 );
  488.             }
  489.         totalfuncs++;
  490.         }
  491.     if ( newel )
  492.         {    /* Initialize function name node to undefined state. */
  493.         pelist->pcallerlist = NULL;
  494.         pelist->pnext_func_ref = NULL;
  495.         pelist->type = defaulttype;
  496.         pelist->pcalleelist = NULL;
  497.         pelist->file_name = NULL;
  498.         pelist->name = strdup( nameptr );
  499.         }
  500.     if ( pelist == NULL )
  501.             {
  502.             fprintf( stderr, endofsp );
  503.             exit( -1 );
  504.             }
  505.     return( pelist );
  506. }
  507.  
  508.  
  509. /****************************************************************/
  510. /**                                                            **/
  511. /**   ARGUMENTS: a token name.                                 **/
  512. /**                                                            **/
  513. /**   RETURN: a pointer to a struct func_ref_type              **/
  514. /**                                                            **/
  515. /**   DESCRIPTION: findname returns a function reference to    **/
  516. /**   the structure whose name field matches the token name,   **/
  517. /**   or NULL in the case of no match.                         **/
  518. /**                                                            **/
  519. /**   GLOBAL VARS REFERENCED: hashval, hashfunc                **/
  520. /**                                                            **/
  521. /**   GLOBAL VARS MODIFIED: none                               **/
  522. /**                                                            **/
  523. /****************************************************************/
  524.  
  525. struct func_ref_type *findname( nameptr )
  526.  
  527.     char *nameptr;
  528.  
  529. {
  530.     struct func_ref_type *pelist;
  531.     int hashval;
  532.     pelist = hashtbl[ hashval = hashfunc( nameptr ) ];
  533.     if ( pelist )
  534.         {
  535.         while ( strcmp( nameptr, pelist->name ) &&
  536.                 pelist->pnext_func_ref )
  537.             {    
  538.             pelist = (struct func_ref_type *)pelist->pnext_func_ref;
  539.             }    /* End of while */
  540.         }
  541.     return( pelist );
  542. }
  543.  
  544.  
  545.  
  546. /****************************************************************/
  547. /**                                                            **/
  548. /**   ARGUMENTS: token to get hashed                           **/
  549. /**                                                            **/
  550. /**   RETURN: hash value.                                      **/
  551. /**                                                            **/
  552. /**   DESCRIPTION: hashfunc hashes tokens based on the sum     **/
  553. /**   of all the characters in the token.                      **/
  554. /**                                                            **/
  555. /**   GLOBAL VARS REFERENCED: hashval, hashfunc                **/
  556. /**                                                            **/
  557. /**   GLOBAL VARS MODIFIED: none                               **/
  558. /**                                                            **/
  559. /****************************************************************/
  560.  
  561. int hashfunc( token )
  562.  
  563.     char *token;
  564.  
  565. {
  566.     int retval = 0;
  567.     for ( ; *token ; retval += *token++ )
  568.         ;
  569.     return( retval & ( HASHSIZE - 1 ) );
  570. }
  571.  
  572.  
  573. /****************************************************************/
  574. /**                                                            **/
  575. /**   ARGUMENTS: Two function reference pointers, the          **/
  576. /**              filename where the reference took place.      **/
  577. /**              The line number where the reference occoured. **/
  578. /**              And the relation between the first two        **/
  579. /**              references.                                   **/
  580. /**                                                            **/
  581. /**   RETURN: void                                             **/
  582. /**                                                            **/
  583. /**   DESCRIPTION: addlist adds one function to the others     **/
  584. /**   CALLEE/CALLER list the list being chosen by the relation **/
  585. /**   being passed in.                                         **/
  586. /**                                                            **/
  587. /**   GLOBAL VARS REFERENCED: endofsp                          **/
  588. /**                                                            **/
  589. /**   GLOBAL VARS MODIFIED: none                               **/
  590. /**                                                            **/
  591. /****************************************************************/
  592.  
  593. void addlist( pafunc, pbfunc, filename, lineno, relation )
  594.  
  595.     struct func_ref_type *pafunc;
  596.     struct func_ref_type *pbfunc;
  597.     char *filename;
  598.     int lineno;
  599.     enum relationchoice relation;
  600.  
  601. {
  602.     struct listtype *listptr;
  603.     char *parentptr;
  604.     if ( ( ( relation == CALLEE ) ? 
  605.             pafunc->pcalleelist : pafunc->pcallerlist ) == NULL )
  606.         {
  607.         if ( ( listptr = (struct listtype *)malloc( 
  608.                 sizeof( struct listtype ) ) ) == NULL )
  609.             {
  610.             fprintf( stderr, endofsp );
  611.             exit( -1 );
  612.             }
  613.         if ( relation == CALLEE )
  614.             {
  615.             pafunc->pcalleelist = (char *)listptr;
  616.             }
  617.         else
  618.             {
  619.             pafunc->pcallerlist = (char *)listptr;
  620.             }
  621.         }
  622.     else
  623.         {
  624.         listptr = (struct listtype *)( relation == CALLEE ? 
  625.                             pafunc->pcalleelist : pafunc->pcallerlist );
  626.         while ( listptr->pnext_func_ref )
  627.             {    /* walk the list, and insert at the end */
  628.             listptr = (struct listtype *)listptr->pnext_func_ref;
  629.             }    /* End of while */
  630.         if ( ( listptr->pnext_func_ref = (char *)malloc( 
  631.                 sizeof( struct listtype ) ) ) == NULL )
  632.             {
  633.             fprintf( stderr, endofsp );
  634.             exit( -1 );
  635.             }
  636.         listptr = (struct listtype *)listptr->pnext_func_ref;
  637.         }
  638.     
  639.     listptr->pelist = pbfunc;
  640.     listptr->pnext_func_ref = NULL;
  641.     listptr->file_name = strdup( filename );
  642.     listptr->lineno = lineno;
  643. }
  644.  
  645.  
  646. /****************************************************************/
  647. /**                                                            **/
  648. /**   ARGUMENTS: pointer to a function reference.              **/
  649. /**              level of nesting so far.                      **/
  650. /**              relation to use.                              **/
  651. /**                                                            **/
  652. /**   RETURN: none                                             **/
  653. /**                                                            **/
  654. /**   DESCRIPTION: dumptree prints out the current nesting     **/
  655. /**   level of relation and calls itself recursively for lower **/
  656. /**   nesting levels.                                          **/
  657. /**                                                            **/
  658. /**   GLOBAL VARS REFERENCED: cutoff, verbose, ellipses        **/
  659. /**                                                            **/
  660. /**   GLOBAL VARS MODIFIED: none                               **/
  661. /**                                                            **/
  662. /****************************************************************/
  663.  
  664. void dumptree( pafunc, level, relation )
  665.  
  666.     struct func_ref_type *pafunc;
  667.     int level;
  668.     enum relationchoice relation;
  669.  
  670. {
  671.     struct listtype *roverptr;
  672.     struct listtype *beginlist;
  673.     struct func_ref_type *old_pafunc;
  674.     char *old_nextptr;
  675.     int i;
  676.     if ( pafunc && level < cutoff )
  677.         {            /* There is a branch below this level */
  678.         if ( !level )
  679.             {
  680.             printf( "%4d", level );
  681.             for ( i = 0; i <= level; i++ )
  682.                 {
  683.                 putchar( '\t' );
  684.                 }    /* End of for */
  685.  
  686.             if ( pafunc->file_name )
  687.                 {    /* a definition has been found */
  688.                 printf( "%s:%s() <%s,%d>\n", pafunc->name, pafunc->type, 
  689.                     pafunc->file_name, pafunc->lineno );
  690.                 }
  691.             else
  692.                 {
  693.                 printf( "%s:%s() <,>\n", pafunc->name, pafunc->type );
  694.                 }
  695.             level++;
  696.             }
  697.         if ( relation == CALLEE )
  698.             {
  699.             beginlist = roverptr = (struct listtype *)pafunc->pcalleelist;
  700.             }
  701.         else
  702.             {
  703.             beginlist = roverptr = (struct listtype *)pafunc->pcallerlist;
  704.             }
  705.  
  706.         while ( roverptr )
  707.             {        /* Walk the list of CALLER/CALLEE's */
  708.             if ( !verbose && beginlist != &ellipses && beginlist == roverptr )
  709.                 {
  710.                 printf( "(%3d)", xref );
  711.                 }
  712.             else
  713.                 {
  714.                 printf( "     ", xref );
  715.                 }
  716.             printf( "%4d", level );
  717.  
  718.             for ( i = 0; i <= level; i++ )
  719.                 {
  720.                 putchar( '\t' );
  721.                 }    /* End of for */
  722.  
  723.             if ( roverptr->pelist != (struct func_ref_type *)NULL )
  724.                 {
  725.                 printf( "%s:%s() <%s,%d>", roverptr->pelist->name, 
  726.                     roverptr->pelist->type, roverptr->file_name, 
  727.                     roverptr->lineno );
  728.                 }
  729.             else
  730.                 {
  731.                 printf( "...relations shown at (%1d)", pafunc->xref );
  732.                 }
  733.             old_pafunc = roverptr->pelist;
  734.             old_nextptr = roverptr->pnext_func_ref;
  735.             if ( !verbose && beginlist != &ellipses && beginlist == roverptr )
  736.                 {
  737.                 free( beginlist->file_name );
  738.                 free( beginlist );
  739.                 pafunc->xref = xref++;
  740.                 if ( relation == CALLEE )
  741.                     {
  742.                     pafunc->pcalleelist = (char *)&ellipses;
  743.                     }
  744.                 else
  745.                     {
  746.                     pafunc->pcallerlist = (char *)&ellipses;
  747.                     }
  748.                 }
  749.             putchar( '\n' );
  750.             dumptree( old_pafunc, level + 1, relation );
  751.             roverptr = (struct listtype *)old_nextptr;
  752.             }    /* End of while */
  753.         }
  754. }
  755.  
  756. /****************************************************************/
  757. /**                                                            **/
  758. /**   ARGUMENTS: none                                          **/
  759. /**                                                            **/
  760. /**   RETURN: none                                             **/
  761. /**                                                            **/
  762. /**   DESCRIPTION: initstatemachine sets up which state to go  **/
  763. /**   to given which state is currently active and which       **/
  764. /**   character has been read in.                              **/
  765. /**                                                            **/
  766. /**   GLOBAL VARS REFERENCED: gotonextstate                    **/
  767. /**                                                            **/
  768. /**   GLOBAL VARS MODIFIED: gotonextstate                      **/
  769. /**                                                            **/
  770. /****************************************************************/
  771.  
  772. void initstatemachine()
  773.  
  774. {
  775.     int character;
  776.     for ( character = 0; character < 128; character++ )
  777.         {    /* set up the majority of state jumps */
  778.         if ( !isalnum( character ) && character != '_' && character != '(' )
  779.             {
  780.             gotonextstate[ INITIA ][ character ] = NAME;
  781.             }
  782.         else
  783.             {
  784.             gotonextstate[ INITIA ][ character ] = INITIA;
  785.             }
  786.         gotonextstate[ BEGCOM ][ character ] = INITIA;
  787.         gotonextstate[ COMMEN ][ character ] = COMMEN;
  788.         gotonextstate[ AFTCOM ][ character ] = COMMEN;
  789.         gotonextstate[ DOUBQT ][ character ] = DOUBQT;
  790.         gotonextstate[ DBQTBS ][ character ] = DOUBQT;
  791.         gotonextstate[ SINGQT ][ character ] = SINGQT;
  792.         gotonextstate[ SGQTBS ][ character ] = SINGQT;
  793.         gotonextstate[ POUND ][ character ] = POUND;
  794.         gotonextstate[ BKSLHPND ][ character ] = POUND;
  795.         }    /* End of for */
  796.     /* Now set all of the exceptions */
  797.  
  798.     gotonextstate[ INITIA ][ ';' ] = TYPE;    /* preceeding beginning of a type */
  799.     gotonextstate[ INITIA ][ ',' ] = TYPE;    
  800.     gotonextstate[ INITIA ][ '{' ] = TYPE;    
  801.     gotonextstate[ INITIA ][ '}' ] = TYPE;    
  802.  
  803.     gotonextstate[ AFTCOM ][ '*' ] = AFTCOM;    /* possible end of comment */
  804.     gotonextstate[ AFTCOM ][ '/' ] = INITIA;    /* end comment is confirmed */
  805.     gotonextstate[ BEGCOM ][ '*' ] = COMMEN;    /* possible end of comment */
  806.     gotonextstate[ COMMEN ][ '*' ] = AFTCOM;    /* possible end of comment */
  807.     gotonextstate[ DOUBQT ][ '"' ] = INITIA;    /* end of double quoted stuff */
  808.     gotonextstate[ DOUBQT ][ '\\' ] = DBQTBS;    /* protect the next character */
  809.     gotonextstate[ INITIA ][ '"' ] = DOUBQT;    /* double quoted stuff */
  810.     gotonextstate[ INITIA ][ '#' ] = POUND;        /* beginning of preprcssr */
  811.     gotonextstate[ INITIA ][ '/' ] = BEGCOM;    /* beginning of comment*/
  812.     gotonextstate[ INITIA ][ '\'' ] = SINGQT;    /* single quoted stuff */
  813.     gotonextstate[ POUND ][ '\\' ] = BKSLHPND;    /* backslash in preprocessor */
  814.     gotonextstate[ POUND ][ '\n' ] = TYPE;        /* end of preprocessor */
  815.     gotonextstate[ SINGQT ][ '\'' ] = INITIA;    /* end of single quoted stuff */
  816.     gotonextstate[ SINGQT ][ '\\' ] = SGQTBS;    /* protect the next character */
  817. }
  818.  
  819.  
  820. /****************************************************************/
  821. /**                                                            **/
  822. /**   ARGUMENTS: relationship to use for outputting trees.     **/
  823. /**                                                            **/
  824. /**   RETURN: none                                             **/
  825. /**                                                            **/
  826. /**   DESCRIPTION: sortdump looks at all of the function names **/
  827. /**   and sorts them using qsort.  Then the functions are      **/
  828. /**   dumped out using dumptree with the relation wanted being **/
  829. /**   passed on to dumptree.                                   **/
  830. /**                                                            **/
  831. /**   GLOBAL VARS REFERENCED: totalfuncs, endofsp, hashtbl     **/
  832. /**                                                            **/
  833. /**   GLOBAL VARS MODIFIED: none                               **/
  834. /**                                                            **/
  835. /****************************************************************/
  836.  
  837. void sortdump( relationship )
  838.  
  839.     enum relationchoice relationship;
  840.  
  841. {
  842.     int hashlook;
  843.     struct func_ref_type **ppelist;
  844.     struct func_ref_type *pcollisionwalker;
  845.     struct func_ref_type **ppsorttable;
  846.     if ( ( ppsorttable = (struct func_ref_type **)malloc( 
  847.             sizeof(struct func_ref_type *) * ( totalfuncs + 1 ) ) ) == NULL )
  848.         {
  849.         fprintf( stderr, endofsp );
  850.         exit( -1 );
  851.         }
  852.     ppelist = ppsorttable;
  853.     for ( hashlook = 0; hashlook < HASHSIZE; hashlook++ )
  854.         {                /* for each element in the hash table */
  855.         if ( hashtbl[ hashlook ] )
  856.             {
  857.             pcollisionwalker = *ppelist = hashtbl[ hashlook ];
  858.             ppelist++;
  859.             while ( pcollisionwalker->pnext_func_ref )
  860.                 {        /* for each collision element */
  861.                 pcollisionwalker = 
  862.                     (struct func_ref_type *)pcollisionwalker->pnext_func_ref;
  863.                 *ppelist = pcollisionwalker;
  864.                 ppelist++;
  865.                 }    /* End of while */
  866.             }
  867.         }    /* End of for */
  868.     qsort( (char *)ppsorttable, totalfuncs, sizeof(struct func_ref_type *), 
  869.             mycompare );
  870.     ppelist = ppsorttable;
  871.     while ( ppelist < (ppsorttable + totalfuncs) )
  872.         {
  873.         putchar( '\n' );
  874.         dumptree( *ppelist, 0, relationship );
  875.         ppelist++;
  876.         }    /* End of while */
  877. }
  878.  
  879. /****************************************************************/
  880. /**                                                            **/
  881. /**   ARGUMENTS: pointers to two function reference nodes      **/
  882. /**                                                            **/
  883. /**   RETURN: 1, 0, or -1                                      **/
  884. /**                                                            **/
  885. /**   DESCRIPTION: compare compares the two function names in  **/
  886. /**   the structures pointed to by ppa, and ppb.  The return   **/
  887. /**   value is the result of the strcmp of these two names.    **/
  888. /**                                                            **/
  889. /**   GLOBAL VARS REFERENCED: none                             **/
  890. /**                                                            **/
  891. /**   GLOBAL VARS MODIFIED: none                               **/
  892. /**                                                            **/
  893. /****************************************************************/
  894.  
  895. int mycompare( ppa, ppb )
  896.  
  897.     char **ppa;
  898.     char **ppb;
  899.  
  900. {
  901.     return( strcmp( ((struct func_ref_type *)(*ppa))->name, 
  902.             ((struct func_ref_type *)(*ppb))->name ) );
  903. }
  904.  
  905.  
  906. /****************************************************************/
  907. /**                                                            **/
  908. /**   ARGUMENTS: none                                          **/
  909. /**                                                            **/
  910. /**   RETURN: an integer                                       **/
  911. /**                                                            **/
  912. /**   DESCRIPTION: This state machine reads in characters and  **/
  913. /**   keeps reading in characters until an initial state is    **/
  914. /**   reached, this means the character being read is not in a **/
  915. /**   comment, or quoted.  Also tags are marked to show the    **/
  916. /**   possible start of function names, and type returns.  In  **/
  917. /**   addition a count of parens and braces is made for use    **/
  918. /**   elsewhere.                                               **/
  919. /**                                                            **/
  920. /**   GLOBAL VARS REFERENCED: lineno, parens, gotonextstate,   **/
  921. /**                           braces, last_func_ret_type,      **/
  922. /**                           last_func_name                   **/
  923. /**                                                            **/
  924. /**   GLOBAL VARS MODIFIED:   lineno, parens, braces,          **/
  925. /**                           last_func_ret_type,              **/
  926. /**                           last_func_name                   **/
  927. /**                                                            **/
  928. /****************************************************************/
  929.  
  930. int getsucc()
  931.  
  932.  
  933. {
  934.     static int near    c;
  935.     static int near state = INITIA;    /* start things out in the initial state */
  936.     static int near previousstate;
  937.     do
  938.         {
  939.         if ( ( c = getc( fp ) ) == '\n' )
  940.             {
  941.             lineno++;
  942.             }
  943.         if ( c == EOF )
  944.             {
  945.             return( EOF );
  946.             }
  947.         previousstate = state & 15;
  948.         state = gotonextstate[ state & 15 ][ c ];
  949.         } while ( ( state & 15 ) != INITIA 
  950.                 || (  previousstate != INITIA && previousstate != BEGCOM ) );
  951.         /* Keep eating characters until we are out of comments and quotes */
  952.  
  953.     if ( previousstate == BEGCOM )
  954.         {    /* This is the only context sensitive area, if a '/' is seen 
  955.             followed by anything but a '*' then we must back up */
  956.         ungetc( c, fp );
  957.         return( '/' );
  958.         }
  959.     if ( state == TYPE )
  960.         {        /* Save the location of the last function return value */
  961.         SAVEPLACE( last_func_ret_type );
  962.         braces += BRACES( c );
  963.         }
  964.     else
  965.         {
  966.         parens += PARENS( c );
  967.         if ( state == NAME )
  968.             {
  969.             SAVEPLACE( last_func_name );
  970.             }
  971.         }
  972.     return( c );
  973. }
  974.  
  975.  
  976.  
  977.  
  978. /****************************************************************/
  979. /**                                                            **/
  980. /**   ARGUMENTS: character                                     **/
  981. /**                                                            **/
  982. /**   RETURN: character                                        **/
  983. /**                                                            **/
  984. /**   DESCRIPTION: succpos finds the next succesive position   **/
  985. /**   in a file that matches the character passed into it.     **/
  986. /**                                                            **/
  987. /**   GLOBAL VARS REFERENCED: none                             **/
  988. /**                                                            **/
  989. /**   GLOBAL VARS MODIFIED: none                               **/
  990. /**                                                            **/
  991. /****************************************************************/
  992.  
  993. int succpos( c )   /* Sets pointer to next position of character [c] */
  994.     int c;
  995. {
  996.     static int near tmpc;
  997.     while ( ( c != ( tmpc = getsucc() ) ) && ( tmpc != EOF    ) )
  998.         ;
  999.     if( tmpc != EOF )
  1000.         {
  1001.         ungetc( c, fp );
  1002.         return( 1 );
  1003.         }
  1004.     return( 0 );
  1005. }
  1006.  
  1007.  
  1008.  
  1009. /****************************************************************/
  1010. /**                                                            **/
  1011. /**   ARGUMENTS: character pointer                             **/
  1012. /**                                                            **/
  1013. /**   RETURN: character                                        **/
  1014. /**                                                            **/
  1015. /**   DESCRIPTION: nsuccmemb finds the next succesive character**/
  1016. /**   using getsucc that is not a member of the characters     **/
  1017. /**   pointed to by the variable passed in.                    **/
  1018. /**                                                            **/
  1019. /**   GLOBAL VARS REFERENCED: none                             **/
  1020. /**                                                            **/
  1021. /**   GLOBAL VARS MODIFIED: none                               **/
  1022. /**                                                            **/
  1023. /****************************************************************/
  1024.  
  1025. int nsuccmemb( lstr )
  1026.  
  1027.     char *lstr;
  1028. {
  1029.     int c;
  1030.     if( ( c = getsucc() ) != EOF )
  1031.         {
  1032.         while ( ( strchr( lstr, c ) != NULL ) && ( c != EOF ) )
  1033.             {
  1034.             c = getsucc();
  1035.             }    /* End of while */
  1036.         ungetc( c, fp );
  1037.         }
  1038.     return( c != EOF );
  1039. }
  1040.  
  1041.  
  1042.  
  1043. /****************************************************************/
  1044. /**                                                            **/
  1045. /**   ARGUMENTS: character pointers                            **/
  1046. /**                                                            **/
  1047. /**   RETURN: none                                             **/
  1048. /**                                                            **/
  1049. /**   DESCRIPTION: readtoken reads in characters using getsucc **/
  1050. /**   as long as the characters are members of characters      **/
  1051. /**   pointed to by plegalstr, these characters are put into   **/
  1052. /**   the place pointed to by ptokenstr, and null terminated.  **/
  1053. /**                                                            **/
  1054. /**   GLOBAL VARS REFERENCED: none                             **/
  1055. /**                                                            **/
  1056. /**   GLOBAL VARS MODIFIED: none                               **/
  1057. /**                                                            **/
  1058. /****************************************************************/
  1059.  
  1060. void readtoken( plegalstr, ptokenstr )    /* Reads token composed of
  1061.                                            *plegalstr into *ptokenstr */
  1062.     char *plegalstr;
  1063.     char *ptokenstr;
  1064.  
  1065. {
  1066.     int c;
  1067.     struct placeptr place;
  1068.     SAVEPLACE( place );
  1069.     RECOVERPLACE( place );
  1070.     while ( ( c = getsucc() ) && strchr( plegalstr, c ) && c != EOF )
  1071.         {
  1072.         *ptokenstr++ = (char )c;
  1073.         }    /* End of while */
  1074.     *ptokenstr = 0;
  1075. }
  1076.  
  1077.  
  1078. /****************************************************************/
  1079. /**                                                            **/
  1080. /**   ARGUMENTS: character pointer, and an array of character  **/
  1081. /**              pointers.                                     **/
  1082. /**                                                            **/
  1083. /**   RETURN: integer                                          **/
  1084. /**                                                            **/
  1085. /**   DESCRIPTION: ismember returns -1 if ptoken is not a      **/
  1086. /**   member of any of the characters pointed to in the array  **/
  1087. /**   plistwords,  if the ptoken is a member, the position in  **/
  1088. /**   that array is returned.                                  **/
  1089. /**                                                            **/
  1090. /**   GLOBAL VARS REFERENCED: none                             **/
  1091. /**                                                            **/
  1092. /**   GLOBAL VARS MODIFIED: none                               **/
  1093. /**                                                            **/
  1094. /****************************************************************/
  1095.  
  1096. int ismember( ptoken, plistwords )
  1097.     char *ptoken, *plistwords[];
  1098. {
  1099.     int i = 0;
  1100.     while ( *plistwords && strcmp( ptoken, *plistwords ) )
  1101.         {
  1102.         *++plistwords;
  1103.         ++i;
  1104.         }    /* End of while */
  1105.     return( ( *plistwords == NULL || strcmp( ptoken, *plistwords ) ) ? -1 : i );
  1106. }
  1107.  
  1108.  
  1109.  
  1110. static unsigned int width;
  1111. static int (*compare)( char **, char ** );
  1112.  
  1113.  
  1114.  
  1115. /****************************************************************/
  1116. /**                                                            **/
  1117. /**   ARGUMENTS:     base = (char *) pointer to base of array   **/
  1118. /**           num  = (unsigned) number of elements in the array  **/
  1119. /**       wid  = (unsigned) width in bytes of each array element **/
  1120. /**        comp = (int (*) ()) pointer to function returning      **/
  1121. /**        analog of strncmp for strings, but supplied for        **/
  1122. /**        comparing the array elements.  It accepts 2 pointers   **/
  1123. /**        to elements and returns neg if 1<2, 0 if 1=2,          **/
  1124. /**        pos if 1>2.                                            **/
  1125. /**                                                            **/
  1126. /**   RETURN: none                                             **/
  1127. /**                                                            **/
  1128. /**   DESCRIPTION: qsort quick sorts an array of elements in   **/
  1129. /**   place.                                                   **/
  1130. /**                                                            **/
  1131. /**   GLOBAL VARS REFERENCED: array starting at base           **/
  1132. /**                                                            **/
  1133. /**   GLOBAL VARS MODIFIED: array starting at base             **/
  1134. /**                                                            **/
  1135. /****************************************************************/
  1136.  
  1137. void qsort( base, num, wid, comp )
  1138.  
  1139.     char *base;
  1140.     unsigned int num;
  1141.     unsigned int wid;
  1142.     int (*comp)( char **, char ** );
  1143.  
  1144. {
  1145.     register char *q = base;
  1146.     register char *p = base + wid;
  1147.     int i = num - 1;
  1148.     int sort = 0;    /* set to non-zero if sort must be done */
  1149.             /* (some element is out of order) */
  1150.  
  1151.     if ( num )
  1152.         {
  1153.         while ( i-- ) 
  1154.             {
  1155.             if ( (*comp)( (char **)q, (char **)p ) > 0 ) 
  1156.                 {
  1157.                 sort++;
  1158.                 break;
  1159.                 }
  1160.  
  1161.             q = p;
  1162.             p += wid;
  1163.             }
  1164.         }
  1165.  
  1166.     if (sort) 
  1167.         {
  1168.         width = wid;
  1169.         compare = comp;
  1170.         quicksort( base, base + (num - 1) * width );
  1171.         }
  1172. }
  1173.  
  1174.  
  1175. static void quicksort( lo, hi )
  1176.  
  1177.     char *lo;
  1178.     char *hi;
  1179.  
  1180. {
  1181.     register char *higuy = hi + width;
  1182.     register char *loguy = lo;
  1183.  
  1184.     while ( lo < hi ) 
  1185.         {
  1186.         for ( ; ; ) 
  1187.             {
  1188.             do    {
  1189.                 loguy += width;
  1190.                 } while (loguy < hi && (*compare)( (char **)loguy, (char **)lo ) <= 0);
  1191.  
  1192.             do    {
  1193.                 higuy -= width;
  1194.                 } while (higuy > lo && (*compare)( (char **)higuy, (char **)lo ) >= 0);
  1195.  
  1196.             if (higuy <= loguy)
  1197.                 break;
  1198.  
  1199.             swap( loguy, higuy, width );
  1200.             }    /* End of for */
  1201.  
  1202.         swap( lo, higuy, width );
  1203.         if ( higuy - lo >= hi - higuy ) 
  1204.             {
  1205.             quicksort( higuy + width, hi );
  1206.             hi = higuy - width;
  1207.             loguy = lo;
  1208.             }
  1209.         else 
  1210.             {
  1211.             quicksort( lo, higuy - width );
  1212.             loguy = lo = higuy + width;
  1213.             higuy = hi + width;
  1214.             }
  1215.         }    /* End of while */
  1216. }
  1217.  
  1218.  
  1219.  
  1220. static void swap ( one, two, w )
  1221.  
  1222.     char *one;
  1223.     register char *two;
  1224.     unsigned int w;
  1225.  
  1226. {
  1227.     char temp;
  1228.  
  1229.     while ( w-- ) 
  1230.         {
  1231.         temp = *one;
  1232.         *one++ = *two;
  1233.         *two++ = temp;
  1234.         }
  1235. }
  1236.