home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / c / hce.lha / HCE / Examples / CLIB / Cflow / Cflow.c next >
Encoding:
C/C++ Source or Header  |  1992-09-02  |  20.8 KB  |  836 lines
  1. /* CFLOW.C - A C Function Call Chart Generator
  2.  *
  3.  * Version 1.00         December 21st, 1986
  4.  *
  5.  * SYNOPSIS:
  6.  *
  7.  * CFLOW accepts C source code via the standard input and
  8.  * produces a listing of the hierarchy of C function calls
  9.  * on the standard output. Recursive functions are explicitly
  10.  * identified in the listing. The command line format is:
  11.  *
  12.  *      CFLOW < source_file
  13.  *
  14.  * The output listing identifies all functions in the source
  15.  * code and the functions they call (#include files are not
  16.  * recognized). If only specific functions are of interest,
  17.  * (e.g. - fcn1, fcn2, fcn3), a listing for these functions
  18.  * only and the functions they call can be specified with the
  19.  * command line:
  20.  *
  21.  *      CFLOW < source_file fcn1 fcn2 fcn3
  22.  *
  23.  * MODIFICATIONS:
  24.  *
  25.  *   V1.00        - beta test release
  26.  *
  27.  * Adapted from:  "CALLS.C"
  28.  *                The C Programming Tutor
  29.  *                L.A. Wortman & T.O. Sidebottom
  30.  *                Prentice Hall Publishing
  31.  *
  32.  * Adaptation by: Ian Ashdown
  33.  *                byHeart Software
  34.  *                620 Ballantree Road
  35.  *                West Vancouver, B.C.
  36.  *                Canada V7S 1W3
  37.  *
  38.  * USAGE: CFLOW [function_name ...]
  39.  *
  40.  * DIAGNOSTICS:
  41.  *
  42.  * Exit status is 0 if no problems encountered, 2 otherwise.
  43.  *
  44.  * BUGS:
  45.  *
  46.  * Identifiers are limited to 32 characters in length.
  47.  * Recursive calling depth is set at 25.
  48.  *
  49.  **********************************************************************
  50.  *                          LAST CHANGES                              *
  51.  **********************************************************************
  52.  *
  53.  * 14 June, 1994 - Jason Petty
  54.  *
  55.  * Now checks if called from CLI or if invalid file, shows usage then exits
  56.  * with an error status. Does not use 'stdin' for input but instead
  57.  * requires user to specify a filename on the command line.
  58.  *
  59.  * To clear things up a bit here's the Usage:
  60.  *
  61.  *            CFLOW <source_filename> <function name 1> <funcn2> <funcn3>
  62.  *
  63.  * If called:  CFLOW <filename>
  64.  * without function name then the default is to list 'main()'. 
  65.  *
  66.  * Changes marked VANSOFT.
  67.  */
  68.  
  69. /*** INCLUDE FILES ***/
  70.  
  71. #include <stdio.h>
  72.  
  73. /*** DEFINITIONS ***/
  74.  
  75. #define BOOL            int
  76. #define DEFINED         1       /* Result of find_next() */
  77. #define DEFINING        0       /* Result of find_next() */
  78. #define FALSE           0
  79. #define HASH_TABLE_FULL -1      /* Indicates hash table overflow */
  80. #define HT_SIZE         1009    /* Must be a prime number */
  81. #define INDENT          "    "  /* Default output indentation */
  82. #define INDENT_SIZE     4       /* Number of spaces in indentation */
  83. #define MAXDEPTH        25      /* Maximum recursive-calling depth */
  84. #define MAXSYMLEN       32      /* Maximum significant characters
  85.                                    in a symbol */
  86. #define PGWIDTH         80      /* Default output page width */
  87. #define TRUE            1
  88.  
  89. /*** CODE MACROS ***/
  90.  
  91. #define GENERATE_NEW_INDEX(x,y)  (((x+y*y) % HT_SIZE)+1)
  92.  
  93. /*** TYPEDEFS ***/
  94.  
  95. typedef struct itype
  96. {
  97.   struct ntype *name_defn;      /* Name for this instance */
  98.   struct itype *next_callee;    /* Next instance called */
  99. }
  100. INSTANCE,
  101. *P_INSTANCE;
  102.  
  103. typedef struct ntype
  104. {
  105.   char fcn_name[MAXSYMLEN];    /* Unique function name */
  106.   int call_cnt,                /* Number of times function called */
  107.       first_num;               /* Line when function name first printed */
  108.   struct ntype *next_pname;    /* Next function name in the list */
  109.   P_INSTANCE first_callee;     /* Pointer to instance describing the
  110.                                 * first call for this function */
  111. }
  112. NAME,
  113. *P_NAME;
  114.  
  115. /*** GLOBAL VARIABLES ***/
  116.  
  117. int line_cnt = 0,       /* Line count */
  118.     maxact_index = 0,   /* Indexes active list from 0 to MAXDEPTH */
  119.     tabs_page = (PGWIDTH-MAXSYMLEN)/INDENT_SIZE,  /* Tabs per page */
  120.     bkt_cnt = 0;        /* Keeps track of the nesting of brackets. A
  121.                          * function found when "bkt_cnt" is zero
  122.                          * must be its DEFINING occurrence, since
  123.                          * function invocations must always appear
  124.                          * within some block of code. */
  125. char *hash_table[HT_SIZE];
  126. BOOL terse = TRUE;
  127. P_NAME name_head = NULL,
  128.        active_list[MAXDEPTH];      /* Used by output() to avoid */
  129.                                    /* infinite recursion */
  130.  
  131. FILE *infile=NULL;          /* Don't use stdin. Added, VANSOFT. */
  132. char *malloc();
  133. void usage();
  134.  
  135.  
  136. void usage(op) /* Added. VANSOFT. */
  137. int op;
  138. {
  139.  printf("\n\nCFLOW V1.0 - 21.12.86.\n");
  140.  printf("Authors:  L.A. Wortman, T.O. Sidebottom & Ian Ashdown.\n\n");
  141.  
  142.  printf("SYNOPSIS:\n");
  143.  printf("CFLOW accepts C source code via the standard input and\n");
  144.  printf("produces a listing of the hierarchy of C function calls\n");
  145.  printf("on the standard output. Recursive functions are explicitly\n");
  146.  printf("identified in the listing.\n\n");
  147.  
  148.  printf("USAGE:  CFLOW <source_file> <function_name1> <funcn2> <funcn3>\n\n");
  149.  
  150.  if(!op) /* exit error. */
  151.     exit(10);
  152. }
  153.  
  154. /*** MAIN BODY OF CODE ***/
  155.  
  156. int main(argc,argv)
  157. int argc;
  158. char *argv[];
  159. {
  160.   int actlist_index,
  161.       arg_index = 2,
  162.       fcn_use,
  163.       hashtbl_index;
  164.   char id[MAXSYMLEN];
  165.   P_NAME pcaller,
  166.          pname,
  167.          look_for(),
  168.          find_name();
  169.   BOOL insert_word();
  170.   void new_fcn(),
  171.        output(),
  172.        error();
  173.  
  174.      if(!argc)     /* May have been run from Workbench. VANSOFT. */
  175.         exit(10);
  176.      if(argc <= 1) /* Not enough args. VANSOFT. */
  177.         usage(NULL);
  178.  
  179.      if(!(infile = fopen(argv[1], "r"))) /* Added, VANSOFT. */
  180.            {
  181.             usage(1);  /* 1 = don't 'exit()' yet. */
  182.             fprintf(stdout, "%s: Can't access %s!\n\n",argv[0],argv[1]);
  183.             exit(10);  /* exit error. */ 
  184.             }
  185.  
  186.   /* Initialize the hash table */
  187.  
  188.   for(hashtbl_index = 0; hashtbl_index < HT_SIZE; hashtbl_index++)
  189.     hash_table[hashtbl_index] = NULL;
  190.  
  191.   /* The following are keywords that look like function calls in C */
  192.  
  193.   insert_word("for");
  194.   insert_word("if");
  195.   insert_word("return");
  196.   insert_word("sizeof");
  197.   insert_word("switch");
  198.   insert_word("while");
  199.  
  200.   /* Initialize the active list */
  201.  
  202.   for(actlist_index = 0; actlist_index < MAXDEPTH; )
  203.     active_list[actlist_index++] = NULL;
  204.  
  205.   /* Parse the input stream and build the appropriate tables */
  206.  
  207.   pcaller = NULL;
  208.   while((fcn_use = find_next(id,pcaller)) != EOF)
  209.     if(fcn_use == DEFINING)
  210.       pcaller = find_name(id);
  211.     else
  212.       new_fcn(id,pcaller);
  213.  
  214.   /* If there are any command line arguments, they are the names
  215.    * of the functions from which to begin the call charts.
  216.    */
  217.  
  218.   if(arg_index < argc)
  219.   {
  220.     do
  221.     {
  222.       if(pname = look_for(argv[arg_index]))
  223.       {
  224.         output(pname,NULL);
  225.         putchar('\n');
  226.       }
  227.       else
  228.         printf("\007\nERROR: Function %s not found.\n",
  229.             argv[arg_index]);
  230.     }
  231.     while((++arg_index) < argc)
  232.       ;
  233.   }
  234.   else
  235.   {
  236.     /* Print beginning with "main", if there is one */
  237.  
  238.     if(pname = look_for("main"))
  239.     {
  240.       output(pname,NULL);
  241.       putchar('\n');
  242.       pname->call_cnt = 1;  /* Don't print "main" again later */
  243.     }
  244.  
  245.     /* Now print all functions not called by anyone else */
  246.  
  247.     for(pname = name_head; pname; pname = pname->next_pname)
  248.       if(pname->call_cnt == NULL)
  249.       {
  250.         output(pname,NULL);
  251.         putchar('\n');
  252.       }
  253.  
  254.     /* Finally, print any mutually recursive functions */
  255.  
  256.     for(pname = name_head; pname; pname = pname->next_pname)
  257.       if(pname->first_num == NULL)
  258.       {
  259.         output(pname,NULL);
  260.         putchar('\n');
  261.       }
  262.   }
  263. }
  264.  
  265. /*** FUNCTIONS ***/
  266.  
  267. /* FIND_NEXT() - Sets its argument to the name of the next function
  268.  *               found in the input stream. It returns as its value
  269.  *               DEFINING if this is the defining occurrence of the
  270.  *               function, DEFINED if it is simply an invocation of
  271.  *               the function, and EOF if the input stream is
  272.  *               exhausted.
  273.  */
  274.  
  275. int find_next(id,cur_fcn)
  276. char *id;
  277. P_NAME cur_fcn;
  278. {
  279.   int cur_ch;
  280.   BOOL find_word(),
  281.        is_valid(),
  282.        seen();
  283.   void scan(),
  284.        error();
  285.  
  286.   while(TRUE)
  287.   {
  288.     cur_ch = getc(infile);
  289.     if(is_valid(cur_ch))
  290.     {
  291.       ungetc(cur_ch,infile);
  292.       scan(id);
  293.     }
  294.     else
  295.     {
  296.       switch(cur_ch)
  297.       {
  298.         case '\t':      /* Skip over white space */
  299.         case ' ':
  300.           break;
  301.         case '\n':      /* Skip over preprocessor lines */
  302.           if((cur_ch = getc(infile)) == EOF)
  303.             return EOF;
  304.           else if(cur_ch == '#')
  305.           {
  306.             while((cur_ch = getc(infile)) != '\n')
  307.               if(cur_ch == '\\')
  308.                 getc(infile); /* Continuation */
  309.           }
  310.           else
  311.             ungetc(cur_ch,infile);
  312.           break;
  313.         case '\'':      /* Skip over character literals */              
  314.           id[0] = '\0';
  315.           while((cur_ch = getc(infile)) != '\'')
  316.             if(cur_ch == '\\')
  317.               getc(infile);   /* Continuation */
  318.           break;
  319.         case '\"':      /* Skip over string literals */
  320.           while((cur_ch = getc(infile)) != '\"')
  321.             if(cur_ch == '\\')
  322.               getc(infile);     /* Continuation */
  323.           break;
  324.         case '\\':
  325.           id[0] = '\0';
  326.           getc(infile);
  327.           break;
  328.         case '{':
  329.           bkt_cnt++;
  330.           id[0] = '\0';
  331.           break;
  332.         case '}':
  333.           bkt_cnt--;
  334.           if(bkt_cnt < 0)
  335.             error("Brackets are not properly nested.");
  336.           id[0] = '\0';
  337.           break;
  338.         case '(':
  339.           if(id[0] == '\0')
  340.             break;               /* No function name was found */
  341.           if(!find_word(id))     /* Ignore any words in hash table */
  342.           {
  343.             if(bkt_cnt == NULL)  /* Not within body of a function */
  344.               return DEFINING;
  345.             else if(!seen(id,cur_fcn))
  346.               return DEFINED;   /* Ignore multiples occurrences within
  347.                                  * a function */
  348.           }
  349.           id[0] = '\0';
  350.           break;
  351.         case EOF:
  352.           return EOF;
  353.         case '/':
  354.           if((cur_ch = getc(infile)) == '*')  /* Skip over comments */
  355.           {
  356.             while(TRUE)
  357.             {
  358.               while(getc(infile) != '*')
  359.                 ;
  360.               if((cur_ch = getc(infile)) == '/')
  361.                 break;
  362.               ungetc(cur_ch,infile);
  363.             }
  364.           }
  365.           else
  366.             ungetc(cur_ch,infile);  /* Must be delimit identifiers */
  367.           break;
  368.         default:
  369.           id[0] = '\0';
  370.           break;
  371.       }
  372.     }
  373.   }
  374. }
  375.  
  376. /* SCAN() - Scans the input stream until a token is found that
  377.  *          might be the name of a function. It returns the atom
  378.  *          found.
  379.  */
  380.  
  381. void scan(token)
  382. char *token;
  383. {
  384.   int cur_ch,
  385.       str_index;
  386.   BOOL is_valid();
  387.   void error();
  388.  
  389.   for(str_index = 0; cur_ch = getc(infile),is_valid(cur_ch); )
  390.   {
  391.     token[str_index++] = cur_ch;
  392.     if(str_index >= MAXSYMLEN)
  393.       error("Symbol name too long.");
  394.   }
  395.   token[str_index] = '\0';
  396.   ungetc(cur_ch,infile);
  397. }
  398.  
  399. /* FIND_WORD() - Looks up an identifier in the hash table and returns
  400.  *               TRUE or FALSE to indicate the presence or absence of
  401.  *               the identifier.
  402.  */
  403.  
  404. BOOL find_word(word)
  405. char *word;
  406. {
  407.   int hashtbl_index;
  408.  
  409.   hashtbl_index = hash(word);
  410.   if((hashtbl_index == HASH_TABLE_FULL) ||
  411.       (hash_table[hashtbl_index] == NULL))
  412.     return FALSE;
  413.   else
  414.     return TRUE;
  415. }
  416.  
  417. /* SEEN() - Determines if the argument string "check_id" has already
  418.  *          been seen as the argument function.
  419.  */
  420.  
  421. BOOL seen(check_id,cur_fcn)
  422. char *check_id;
  423. P_NAME cur_fcn;
  424. {
  425.   P_INSTANCE pinstance;
  426.  
  427.   for(pinstance = cur_fcn->first_callee; pinstance != NULL;
  428.       pinstance = pinstance->next_callee)
  429.     if(!strcmp(check_id,(pinstance->name_defn)->fcn_name))
  430.       return TRUE;
  431.  
  432.   return FALSE;
  433. }
  434.  
  435. /* FIND_NAME() - Returns a pointer to the argument name on the
  436.  *               linked list of names. If the name is not there,
  437.  *               a new "name" is created.
  438.  */
  439.  
  440. P_NAME find_name(name)
  441. char *name;
  442. {
  443.   P_NAME last_pname = NULL,
  444.          pname,
  445.          new_pname,
  446.          add_name();
  447.   int strtest;
  448.  
  449.   /* Search for the name in the current list of known, defined
  450.    * functions. Since the names are inserted in sorted order, stop
  451.    * when we have passed the new name in the list.
  452.    */
  453.  
  454.   for(pname = name_head;
  455.       pname != NULL &&
  456.       (strtest = strcmp(name,pname->fcn_name)) >= NULL;
  457.       last_pname = pname,pname = pname->next_pname)
  458.     if(!strtest)
  459.       return pname;
  460.  
  461.   /* Name not found, so add it */
  462.  
  463.   new_pname = add_name();
  464.   strcpy(new_pname->fcn_name,name);
  465.  
  466.   /* Link the new name entry into the appropriate place in the chain */ 
  467.  
  468.   new_pname->next_pname = pname;
  469.   if(!last_pname)
  470.     name_head = new_pname;
  471.   else
  472.     last_pname->next_pname = new_pname;
  473.  
  474.   return new_pname;
  475. }
  476.  
  477. /* ADD_NAME() - Allocate storage for a name entry */
  478.  
  479. P_NAME add_name()
  480. {
  481.   P_NAME pname;
  482.   char *malloc();
  483.   void error();
  484.  
  485.   if(!(pname = (NAME *)malloc(sizeof(NAME))))
  486.     error("Ran out of memory.");
  487.  
  488.   /* Initialize the new entry */
  489.  
  490.   pname->fcn_name[0] = '\0';
  491.   pname->call_cnt = 0;
  492.   pname->first_num = 0;
  493.   pname->first_callee = NULL;
  494.   pname->next_pname = NULL;
  495.  
  496.   return pname;
  497. }
  498.  
  499. /* NEW_FCN() - Creates an instance for a function use. */
  500.  
  501. void new_fcn(name,pcaller)
  502. char *name;
  503. P_NAME pcaller;
  504. {
  505.   P_INSTANCE pinstance,
  506.              new_pinstance,
  507.              add_instance();
  508.   P_NAME pname,
  509.          find_name();
  510.   
  511.   /* Create the new instance and link it with a name that
  512.    * describes it.
  513.    */
  514.  
  515.   pinstance = pcaller->first_callee;
  516.   pname = find_name(name);
  517.   new_pinstance = add_instance();
  518.   new_pinstance->name_defn = pname;
  519.  
  520.   if(pinstance != NULL)
  521.   {
  522.     /* Run down the callee chain until a NULL link is found */
  523.  
  524.     for(;pinstance->next_callee != NULL;
  525.         pinstance = pinstance->next_callee)
  526.       ;         /* No body */
  527.  
  528.     /* Now add the instance to the callee chain */
  529.  
  530.     pinstance->next_callee = new_pinstance;
  531.   }
  532.   else
  533.     pcaller->first_callee = new_pinstance;
  534.  
  535.   /* Increment the callee's call count */
  536.  
  537.   (pname->call_cnt)++;
  538. }
  539.  
  540. /* ADD_INSTANCE() - Allocate storage for an instance. */
  541.  
  542. P_INSTANCE add_instance()
  543. {
  544.   P_INSTANCE pinstance;
  545.   char *malloc();
  546.   void error();
  547.  
  548.   if(!(pinstance = (INSTANCE *)malloc(sizeof(INSTANCE))))
  549.     error("Ran out of memory.");
  550.  
  551.   pinstance->name_defn = NULL;
  552.   pinstance->next_callee = NULL;
  553.  
  554.   return pinstance;
  555. }
  556.  
  557. /* LOOK_FOR() - Looks for its argument name on the linked list
  558.  *              of names. If found, it returns a pointer to the
  559.  *              entry; otherwise it returns NULL.
  560.  */
  561.  
  562. P_NAME look_for(name)
  563. char *name;
  564. {
  565.   P_NAME pname;
  566.  
  567.   for(pname = name_head; pname != NULL; pname = pname->next_pname)
  568.     if(!strcmp(name,pname->fcn_name))
  569.       return pname;
  570.  
  571.   return NULL;
  572. }
  573.  
  574. /* OUTPUT() - A recursive routine that prints one tab for each
  575.  *            level of nesting, then the name of the function
  576.  *            called, followed by the next function called at the
  577.  *            same level. In doing this, it invokes itself to
  578.  *            output the names of the functions called by the
  579.  *            current function. It maintains an active list of
  580.  *            functions currently being output by the different
  581.  *            levels of recursion, and if it finds itself being
  582.  *            asked to output one which is already active, it
  583.  *            terminates, marking that call with an asterisk.
  584.  */
  585.  
  586. void output(pname,cur_tab)
  587. P_NAME pname;
  588. int cur_tab;
  589. {
  590.   int loop_cnt,
  591.       num_tabs,
  592.       tab_cnt;
  593.   P_INSTANCE pinstance;
  594.   BOOL page_overflow,
  595.        make_active();
  596.   void backup(),
  597.        output();
  598.  
  599.   num_tabs = cur_tab;
  600.   line_cnt++;
  601.   printf("\n%4d",line_cnt);
  602.   if(!make_active(pname))
  603.     putchar('*');       /* Calls nested too deep */
  604.   else
  605.   {
  606.     for(tab_cnt = 0; num_tabs > tabs_page; tab_cnt++)
  607.       num_tabs -= tabs_page;
  608.     for(loop_cnt = 0; loop_cnt < tab_cnt; loop_cnt++)
  609.       putchar('<');
  610.     putchar(' ');
  611.     for(loop_cnt = 0; loop_cnt < num_tabs; loop_cnt++)
  612.       printf(INDENT);
  613.  
  614.     if(isactive(pname))  /* Recursive call */
  615.       printf("%s [recursive]",pname->fcn_name);
  616.     else
  617.     {
  618.       pinstance = pname->first_callee;
  619.       if(pinstance != NULL)
  620.       {
  621.         printf("%s",pname->fcn_name);
  622.         if(!terse || (pname->first_num == 0))
  623.         {
  624.           cur_tab++;
  625.           if(pname->first_num == 0)
  626.             pname->first_num = line_cnt;
  627.           if((cur_tab > tabs_page) &&
  628.               (cur_tab % tabs_page == 1) &&
  629.               (pinstance->next_callee != NULL))
  630.           {
  631.             printf("\n- - - - - - - - - - - - - - - - -");
  632.             printf(" - - - - - - - - - - - - - - - - -");
  633.             page_overflow = TRUE;
  634.           }
  635.           else
  636.             page_overflow = FALSE;
  637.  
  638.           for(; pinstance != NULL; pinstance = pinstance->next_callee)
  639.             output(pinstance->name_defn,cur_tab);
  640.  
  641.           if(page_overflow)
  642.           {
  643.             printf("\n- - - - - - - - - - - - - - - - -");
  644.             printf(" - - - - - - - - - - - - - - - - -");
  645.             page_overflow = FALSE;
  646.           }
  647.         }
  648.         else if(pinstance != NULL)
  649.           printf(" ... [see line %d]",pname->first_num);
  650.       }
  651.       else  /* Library, external or macro call */
  652.         printf("%s",pname->fcn_name);
  653.     }
  654.     backup();
  655.     if(pname->first_num == 0)
  656.       pname->first_num = line_cnt;
  657.   }
  658. }
  659.  
  660. /* MAKE_ACTIVE() - Puts a pointer to the argument "cur_name"
  661.  *                 into the "active_list". FALSE is returned if
  662.  *                 the argument fails because the function nesting
  663.  *                 is too deep; otherwise TRUE is returned.
  664.  */
  665.  
  666. BOOL make_active(cur_name)
  667. P_NAME cur_name;
  668. {
  669.   if(maxact_index < MAXDEPTH)
  670.   {
  671.     active_list[maxact_index++] = cur_name;
  672.     return TRUE;
  673.   }
  674.   else
  675.     return FALSE;
  676. }
  677.  
  678. /* ISACTIVE() - Checks if its argument is already on the active
  679.  *              list.
  680.  */
  681.  
  682. BOOL isactive(cur_name)
  683. P_NAME cur_name;
  684. {
  685.   int actlist_index;
  686.  
  687.   for(actlist_index = 0; actlist_index < maxact_index - 1;
  688.       actlist_index++)
  689.     if(cur_name == active_list[actlist_index])
  690.       return TRUE;
  691.  
  692.   return FALSE;
  693. }
  694.  
  695. /* BACKUP() - Pops an item from the active stack. */
  696.  
  697. void backup()
  698. {
  699.   void  error();
  700.  
  701.   if(!(maxact_index > 0))
  702.     error("Recursion depth exceeds permissible number of levels.");
  703.   active_list[maxact_index--] = NULL;
  704. }
  705.  
  706. /* COPY() - Copies a string and returns the address of the copy */
  707.  
  708. char *copy(old_str)
  709. char *old_str;
  710. {
  711.   char *new_str,
  712.        *str_ptr,
  713.        *malloc();
  714.  
  715.   /* Allocate a string able to hold the length of the string plus one
  716.    * for the terminator.
  717.    */
  718.  
  719.   str_ptr = new_str = malloc(strlen(old_str) + 1);
  720.  
  721.   /* Copy the the string and return a pointer to it */
  722.  
  723.   while(*new_str++ = *old_str++)
  724.     ;
  725.  
  726.   return str_ptr;
  727. }
  728.  
  729. /* ERROR() - Report any errors detected and return 2 to parent
  730.  *           process.
  731.  */
  732.  
  733. void error(message)
  734. char *message;
  735. {
  736.   fprintf(stderr,"\007\nERROR: %s\n",message);
  737.   exit(2);
  738. }
  739.  
  740. /* HASH() - Generates a unique hash table index for the argument 
  741.  *          identifier. The value of HASH_TABLE_FULL is returned
  742.  *          if the hash table overflows.
  743.  */
  744.  
  745. int hash(word)
  746. char *word;
  747. {
  748.   int hashtbl_index,
  749.       init_index,
  750.       probe_cnt = 0;
  751.  
  752.   hashtbl_index = init_index = transform(word);
  753.   if(hash_table[hashtbl_index] == NULL)
  754.     ;   /* Got it */
  755.   else  /* Have we found the correct index? */
  756.     if(!strcmp(word,hash_table[hashtbl_index]))
  757.       ; /* Direct hit */
  758.     else        /* Collision - generate indices */
  759.       for(; probe_cnt < (HT_SIZE/2); probe_cnt++)
  760.       {
  761.         hashtbl_index = GENERATE_NEW_INDEX(init_index,probe_cnt);
  762.         if((hash_table[hashtbl_index] == NULL) ||
  763.             !strcmp(word,hash_table[hashtbl_index]))
  764.           break;        /* We've got it */
  765.       }
  766.   if(probe_cnt >= (HT_SIZE/2))
  767.     return HASH_TABLE_FULL;
  768.   return hashtbl_index;
  769. }
  770.  
  771. /* INSERT_WORD() - Inserts an identifier into the hash table and
  772.  *                 returns TRUE. If the hash table overflows, FALSE
  773.  *                 is returned.
  774.  */
  775.  
  776. BOOL insert_word(word)
  777. char *word;
  778. {
  779.   int hashtbl_index;
  780.  
  781.   if((hashtbl_index = hash(word)) == HASH_TABLE_FULL)
  782.     return FALSE;
  783.  
  784.   /* Add word to the hash table if it is not already present */
  785.  
  786.   if(hash_table[hashtbl_index] == NULL)
  787.     hash_table[hashtbl_index] = copy(word);
  788.  
  789.   return TRUE;
  790. }
  791.  
  792. /* IS_VALID() - Returns 1 if 'ch' is a valid character to begin a C
  793.  *             token, 0 otherwise.
  794.  */
  795.  
  796. BOOL is_valid(ch)
  797. char ch;
  798. {
  799.   return (isalpha(ch) || ch == '_') ? 1 : 0;
  800. }
  801.  
  802. /* TRANSFORM() - Converts an identifier into an integer within the
  803.  *               index range of the hash table. A polynomial is
  804.  *               generated and reduced modulo HT_SIZE to produce
  805.  *               this number.
  806.  */
  807.  
  808. int transform(word)
  809. char word[];
  810. {
  811.   int term = 0,
  812.       wordindex;
  813.  
  814.   for(wordindex = strlen(word)-1; wordindex >= 0; wordindex--)
  815.     term = (257 * term) + word[wordindex];
  816.   term = term < 0 ? -term : term;
  817.   return term % HT_SIZE;
  818. }
  819.  
  820. /*
  821.  * Returns true if the character c is alpha.
  822.  */
  823.  
  824. isalpha(c)
  825. char c;
  826. {
  827.  if ( ('A' <= c && c <= 'Z')
  828.    || ('a' <= c && c <= 'z') )
  829.    return 1;
  830.  return 0;
  831. }
  832.  
  833. /* End of CFLOW.C */
  834.  
  835.  
  836.