home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / tools / crossref / cref / cref.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-11-26  |  14.2 KB  |  494 lines
  1. /* CREF - C cross-reference utility
  2.  
  3.     Author: Jeff Taylor, The Toolsmith (c) copyright 1982, 1985.
  4.     Environment: C; UNIX 4.2 BSD.
  5.     Algorithms:
  6.       Modified algorithm T from "The Art of Computer Programming," Vol. 1,
  7.          p. 317, by D.E.Knuth used in tree_walk().
  8.     History:
  9.       22 November 1982 - removed recursion from lookup().
  10.       16 December 1982 - remove recursion from tree_walk().
  11.       26 March 1985 - port to DECUS C.
  12.       27 March 1985 - line # list made a circular queue: insert(), list_file().
  13.            reserved word search changed to binary search: keyword().
  14.       28 March 1985 - port to UNIX 4.2 BSD.
  15. */
  16. /* start of new comment block */
  17. /* MORE CODING HISTORY (and the beat goes on) */
  18. /* Coding History --------------------------------------------------------| */
  19. /* |  Date    | Who | What                                                | */
  20. /* |==========|=====|=====================================================| */
  21. /* | 11/23/88 | KRG | Transcribed from Dr. Dobbs' TOOLBOOK OF C, with     | */
  22. /* |          |     | minimum modifications as required for porting to    | */
  23. /* |          |     | MicroSoft C 5.1 (5.0 okay, too)                     | */
  24. /* |----------|-----|-----------------------------------------------------| */
  25. /* | 11/25/88 | KRG | Added some formatting to output (list_file()).      | */
  26. /* |----------|-----|-----------------------------------------------------| */
  27. /* | 11/26/88 | KRG | Completed slightly lacking keyword list (oops).     | */
  28. /* |----------|-----|-----------------------------------------------------| */
  29. /* |   /  /   |     |                                                     | */
  30. /* |----------|-----|-----------------------------------------------------| */
  31. /* end of new comment block */
  32.  
  33. #include <stdio.h>
  34. #include <ctype.h>
  35. #include <malloc.h>     /* 881123 KRG */
  36. #include <string.h>     /* 881123 KRG */
  37. #include "style.h"
  38.  
  39. #define lower(c)        (isupper(c)? tolower(c) : (c))
  40. #define streq(a, b)     (strcmp(a, b) == 0)
  41. #define WIDTH           80      /* width of output device */
  42.  
  43. struct instance
  44.     {
  45.     struct instance *next;
  46.     int line;
  47.     };
  48.  
  49. union ptr
  50.     {
  51.     struct node *files;
  52.     struct instance *lines;
  53.     };
  54.     
  55. struct node
  56.     {
  57.     struct node *right, *left;  
  58.     union ptr p;
  59.     char *name;
  60.     };
  61.     
  62. struct node *symbol_root = NULL;
  63. struct node *file_root= NULL;
  64. int line_count = 0;
  65.  
  66. #define ID 'a'  /* identifier */
  67. #define INTEGER '0'     /* integer */
  68.  
  69. /************************************
  70.  *  Symbol Table handling routines  *   
  71.  ***********************************/
  72.  
  73.  /* lookup - install name at or below root */
  74.  struct node **lookup (root, name)
  75.     /*register*/ struct node **root;
  76.     /*register*/ char *name;
  77.     {
  78.     register int cond;
  79.     
  80.     #ifdef RECURSIVE
  81.         if (*root != NULL)
  82.             {
  83.             if ((cond = lexcmp(name, (*root)->name)) != 0)
  84.                 root = lookup((cond < 0)? &(*root)->left : &(*root)->right, 
  85.                     name);
  86.             }
  87.     #else
  88.         while (*root != NULL && (cond = lexcmp(name, (*root)->name)))
  89.             root = (cond < 0)? &(*root)->left : &(*root)->right;
  90.     #endif
  91.         
  92.     return(root);
  93.     }
  94.     
  95. /* add - insert entry for "name" in tree at "root" */
  96. struct node *add (name)
  97.     char *name;
  98.     {
  99.     /* char *malloc(); */
  100.     register struct node *r;
  101.     
  102.     r = (struct node *) malloc(sizeof(struct node));
  103.     r->left = r->right = NULL;
  104.     r->p.lines = NULL;
  105.     r->name = name;
  106.     return (r);
  107.     }
  108.     
  109. /* tree_walk - call 'ftn' for each node in inorder */
  110. void tree_walk (root, ftn)
  111.     /*register*/ struct node *root;
  112.     /*register*/ void (*ftn)();
  113.     {
  114.     
  115.     #ifdef RECURSIVE
  116.         if (root != NULL)
  117.             {
  118.             tree_walk(root->left, ftn);
  119.             (*ftn)(root);
  120.             tree_walk(root->right, ftn);
  121.             }
  122.     #else
  123.         register struct node *stack, *tmp;
  124.         
  125.         stack = NULL;       /* stack initially empty */
  126.         for ( ; ; )
  127.             {
  128.             if (root != NULL)
  129.                 {
  130.                 tmp = root;
  131.                 root = root->left;      /* move to left */
  132.                 tmp->left = stack; 
  133.                 stack = tmp;            /* push tmp */
  134.                 }
  135.             else if (stack != NULL)     /* stack not empty */
  136.                 {
  137.                 root = stack;
  138.                 stack = stack->left;    /* pop */
  139.                 (*ftn)(root);           /* visit node */
  140.                 root = root->right;     /* move right */
  141.                 }
  142.             else
  143.                 break;                  /* stack is empty */
  144.             }
  145.     #endif
  146.     }
  147.     
  148. /* insert - add 'line_no' to the circular list, 'origin' */
  149. struct instance *insert (origin, line_no)
  150.     /*register*/ struct instance *origin;
  151.     int line_no;
  152.     {
  153.     /* char *malloc(); */
  154.     register struct instance *t;
  155.     
  156.     if (origin == NULL || origin->line != line_no)
  157.         {
  158.         t = (struct instance *)malloc(sizeof(struct instance));
  159.         if (origin == NULL)
  160.             origin = t;
  161.         t->line = line_no;
  162.         t->next = origin->next;
  163.         origin->next = t;
  164.         origin = t;
  165.         }
  166.     return (origin);
  167.     }
  168.     
  169. /* use - log an occurrence of "name" in "file" at "line" */
  170. void use (name, file, line)
  171.     char *name, *file;
  172.     int line;
  173.     {
  174.     char *newcpy();
  175.     register struct node **ft, **nt;
  176.     
  177.     if (*(nt = lookup(&symbol_root, name)) == NULL)
  178.         *nt = add(newcpy(name));
  179.     if (*(nt = lookup(&((*nt)->p.files), file)) == NULL)
  180.         {
  181.         if (*(ft = lookup(&file_root, file)) == NULL)
  182.             *ft = add(newcpy(file));
  183.         *nt = add((*ft)->name);
  184.         }
  185.     (*nt)->p.lines = insert((*nt)->p.lines, line);
  186.     }
  187.     
  188. /* get_name -extract file name from line */
  189. void get_name (line, file)
  190.     /*register*/ char *line;
  191.     char *file;
  192.     {
  193.     void copy_until();
  194.     register char *delim;
  195.     
  196.     while (*line == ' ' || *line == '\t')
  197.         ++line;
  198.     if (*line != '\n')      /* if none, use "file" as is */
  199.         {
  200.         if (*line == '"')
  201.             {
  202.             delim = "\"\n";
  203.             ++line;
  204.             }
  205.         else if (*line == '<')
  206.             {
  207.             delim = ">\n";
  208.             ++line;
  209.             }
  210.         else
  211.             delim = "\t\n";
  212.         copy_until(file, line, delim);
  213.         }
  214.     }
  215.     
  216. /* new_line - return pointer to the next line */
  217. char *new_line()
  218.     {
  219.     static char line[MAXLINE+1];
  220.     
  221.     ++line_count;
  222.     return(fgets(line, MAXLINE, stdin));
  223.     }
  224.     
  225. /* white_space - tests for blanks, tabs and comments */
  226. /* NOTE: \n is NOT counted as 'white space' in this program; it is used as
  227.     a token class. 881125 KRG */
  228.  
  229. boolean white_space(s)
  230.     /*register*/ char **s;
  231.     {
  232.     
  233.     if (**s == ' ' || **s == '\t')
  234.         return(TRUE);
  235.     if (**s == '/' && *(*s+1) == '*')   /* comment */
  236.         {
  237.         while (*++*s != '/')
  238.             {
  239.             while (*++*s != '*')
  240.                 {
  241.                 if (**s == EOS) 
  242.                     {
  243.                     if ((*s = new_line()) != NULL)
  244.                         --*s;    /* because of pre-increment of inner loop */
  245.                     else
  246.                         {
  247.                         fprintf(stderr, "unexpected EOF\n");
  248.                         return (FALSE);
  249.                         }
  250.                     }
  251.                 }
  252.             }
  253.         return (TRUE);
  254.         }
  255.     return(FALSE);
  256.     }
  257.  
  258. /* ishex - is 'c' a hexadecimal digit? */
  259. boolean ishex(c)
  260.     /*register*/ char c;
  261.     {
  262.     return (isxdigit(c));
  263.     }
  264.     
  265. /* get_token - strip leading token from s */
  266. char get_token(s, t)
  267.     /*register*/ char **s, *t;
  268.     {
  269.     char esc();
  270.     register char class;
  271.     
  272.     while (white_space(s))
  273.         ++*s;
  274.     if (isalpha(**s) || **s == '_')     /* identifier */
  275.         {
  276.         class = ID;
  277.         do
  278.             *t++ = *(*s)++;
  279.         while (isdigit(**s) || isalpha(**s) || **s == '_');
  280.         }
  281.     else if (**s == '\"' || **s == '\'')    /* string or literal */
  282.         {
  283.         class = **s;
  284.         do
  285.             {
  286.             esc(s);
  287.             ++*s;
  288.             if (**s == EOS)
  289.                 {
  290.                 if ((*s = new_line()) == NULL)
  291.                     goto out;                   /* aaaargh!  KRG */
  292.                 }
  293.             }
  294.         while (**s != class);
  295.         ++*s;
  296.         }
  297.     else if (isdigit(**s))
  298.         {
  299.         do
  300.             {
  301.             class = *++*s;
  302.             class = lower(class);
  303.             }
  304.         while (ishex(class) || class == 'x' || class == 'l' || class == '.');
  305.         class = INTEGER;
  306.         }
  307.     else
  308.         class = *(*s)++;
  309.         
  310.     out:
  311.     
  312.     *t = EOS;
  313.     return(class);
  314.     }
  315.     
  316. static char *reserved[] = 
  317.     {
  318.     "auto", "break", "case", "char", "const", "continue", "default", "do",
  319.     "double", "else", "enum", "extern", "float", "for", "goto", "if", "int",
  320.     "long", "register", "return", "short", "signed", "sizeof", "static",
  321.     "struct", "switch", "typedef", "union", "unsigned", "void", "volatile",
  322.     "while"
  323.     };
  324.     
  325. /* keyword - is "s" a reserved word in C */
  326. boolean keyword (s)
  327.     char *s;
  328.     {
  329.     register int cond;      /* condition code of lexcmp */
  330.     register int mid;
  331.     int hi, lo;
  332.     
  333.     /* binary search; reserved[] must be in alphabetical order */
  334.     lo = 0; hi = sizeof(reserved) / sizeof(char *) - 1;
  335.     while (lo <= hi)
  336.         {
  337.         mid = (hi + lo) / 2;
  338.         if ((cond = lexcmp(s, reserved[mid])) == 0)
  339.             return(TRUE);
  340.         if (cond < 0)
  341.             hi = mid - 1;
  342.         else
  343.             lo = mid + 1;
  344.         }
  345.     return (FALSE);
  346.     }
  347.     
  348. /* xref - cross reference */
  349. void xref(file)
  350.     /*register*/ char *file;
  351.     {
  352.     /* int atoi(); */
  353.     register char class;
  354.     char *s, token[MAXLINE+1];
  355.     
  356.     line_count = 0;
  357.     while ((s = new_line()) != NULL)
  358.         {
  359.         if ((class = get_token(&s, token)) != '#')
  360.             {
  361.             while (class != '\n')
  362.                 {
  363.                 if (class == ID && !keyword(token))
  364.                     use(token, file, line_count);
  365.                 class = get_token(&s, token);
  366.                 }
  367.             }
  368.         else if (get_token (&s, token) == ID)
  369.             {
  370.             if (streq(token, "include"))
  371.                 {
  372.                 get_name(s, token);
  373.                 use(token, file, line_count);
  374.                 }
  375.             else if (streq(token, "define"))
  376.                 {
  377.                 get_token(&s, token);
  378.                 use(token, file, line_count);
  379.                 while (class != '\n')               /* 881125 KRG; This is to */
  380.                     class = get_token(&s, token);   /* take care of comments  */
  381.                                                     /* starting on the same   */
  382.                                                     /* line as a #define,     */
  383.                                                     /* like above. */
  384.                 }
  385.             else if (streq(token, "ifdef") || streq(token, "ifndef"))
  386.                 {
  387.                 get_token(&s, token);
  388.                 use(token, file, line_count);
  389.                 }
  390.             else if (streq(token, "line"))
  391.                 {
  392.                 if (get_token(&s, token) == INTEGER)
  393.                     line_count = atoi(token);
  394.                 else
  395.                     fprintf(stderr, "#line %s\n", token);
  396.                 }
  397.             else
  398.                 ;   /* ignore #else, #endif, etc. */
  399.             }       
  400.         }
  401.     }
  402.     
  403. /* putp - output a partial line to stdout */
  404. unsigned putp(s)
  405.     /*register*/ char *s;
  406.     {
  407.     register unsigned n;
  408.     
  409.     for (n = 0; *s != EOS; ++n)
  410.         putchar(*s++);
  411.     return(n);
  412.     }
  413.  
  414. /* list_file - print lines within a file */
  415. #define FNAMELEN    14  /*  max UNIX filename length. KRG */
  416. #define MAGIC   18      /*  numbers are bad, but 18 = 4 + 14; 4 for left
  417.                             margin, 14 for max UNIX filename length. KRG */
  418.  
  419. void list_file(ft)
  420.     /*register*/ struct node *ft;
  421.     {
  422.     char *itoa();
  423.     register unsigned b;
  424.     register struct instance *it;
  425.     char buf[5];
  426.     char margin[MAGIC + 1];         /*  makes it easier to prints formatted
  427.                                         things with the putp() function. KRG */
  428.  
  429.     b = putp("    ");
  430.     sprintf(margin,"%-*s", FNAMELEN, ft->name);
  431.     b += putp(margin);
  432.     /* print line numbers */
  433.     it = ft->p.lines = ft->p.lines->next;   /* move 'lines' to start */
  434.     do
  435.         {
  436.         if (b == 0)
  437.             {
  438.             memset(margin, ' ', sizeof(margin));
  439.             margin[MAGIC] = EOS;
  440.             b = putp(margin);
  441.             }
  442.         b += putp("   ");
  443. /*      b += itoa(it->line, buf) - buf;     */  /* <- old line */
  444.         b += strlen(itoa(it->line, buf, 10));   /* <- new line */ /* [1] */
  445.         putp(buf);
  446.         if (b > WIDTH - 8)          /* leave margin on right */
  447.             {
  448.             putp("\n");
  449.             b = 0;
  450.             }
  451.         it = it->next;
  452.         }
  453.     while (it != ft->p.lines);
  454.     if (b > 6)  /* non-blank line */
  455.         putp("\n");
  456.     }
  457.     
  458. /* print_xref - dump cross reference table to stdout */
  459. void print_xref(nt)
  460.     struct node *nt;
  461.     {
  462.     
  463.     putp("\n"); putp(nt->name); putp("\n");
  464.     tree_walk(nt->p.files, list_file);
  465.     }
  466.     
  467. main (argc, argv)
  468.     /*register*/ int argc;
  469.     /*register*/ char **argv;
  470.     {
  471.     /* FILE *freopen(); */
  472.     
  473.     if (argc <= 1)
  474.         xref("<stdin>");
  475.     else
  476.         {
  477.         while (--argc > 0)
  478.             {
  479.             if (freopen(*++argv, "r", stdin) == NULL)
  480.                 fprintf(stderr, "can't open %s\n", *argv);
  481.             else
  482.                 xref(*argv);
  483.             }
  484.         }
  485.     tree_walk(symbol_root, print_xref);
  486.     }
  487.     
  488.  
  489. /* [1] itoa() differs from the function in strcref.c by the last parameter;
  490.    Microsoft requires the last argument to specify the radix of the function.
  491.    Also, Taylor's itoa returned the pointer to the END of the string, not the
  492.    beginning, so strlen() had to come to the rescue.
  493. */
  494.