home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / TURBOPAS / XREF.ZIP / XREF.C
Encoding:
C/C++ Source or Header  |  1987-05-04  |  4.6 KB  |  239 lines
  1. /*
  2. TITLE: XREF - Cross Reference;
  3. VERSION: 1.0;
  4. DATE: 07/31/1986;
  5. DESCRIPTION:
  6.  "Cross reference text from stdin to stdout.
  7.  Optimized name storage allocation.";
  8. KEYWORDS: binary tree, name, reference, symbol, xref;
  9. SYSTEM: CP/M, any;
  10. FILENAME: XREF.C;
  11. WARNINGS: "Assumes 16-bit pointers.";
  12. SEE-ALSO: none;
  13. AUTHORS: Mark Antony Washburn;
  14. COMPILERS: Small-C, any C compiler; 
  15. REFERENCES:
  16.  AUTHORS: Nickolas Wirth;
  17.  TITLE: "Algorithms+Data Structures=Programs";
  18.  CITATION: "p.206"
  19. ENDREF;
  20. */
  21.  
  22. #include <A:STDIO.H>  /* find STDIO.H */
  23.  
  24. #define MEMOVERHEAD (1024)  /* leave room for stack */
  25.  
  26. #define MAXWORDLEN 79  /* maximum name length - 1 */
  27. #define MAXWORDBUF 80  /* maximum name length */ 
  28. #define NUMPERLINE 14  /* assumes 80 columns */
  29. #define MAXLINENUM 9999  /* maximum number of source lines */
  30.  
  31. #define DNLEFT 0  /* name node structure definitions */ 
  32. #define DNRIGHT 2
  33. #define DNFIRST 4
  34. #define DNLAST 6
  35. #define DNID 8
  36.  
  37. #define DRLINE 0  /* reference link list structure definitions */
  38. #define DRNEXT 2
  39. #define DRLN 4
  40.  
  41. char *membtm,*memtop;  /* pointers to bottom and top of memory */
  42.  
  43. char *root;  /* root node pointer */
  44. char *nword;  /* global name node pointer */ 
  45. /* left and right node pointers, first and last reference links */
  46. int *nleft,*nright,*nfirst,*nlast;
  47. int *rline,*rnext;  /* global pointers reference instance */
  48.  
  49. int c;  /* current char */
  50. int k;  /* current word index */
  51. int n;  /* current line number */
  52. char id[MAXWORDBUF];  /* current word */
  53.  
  54. /*
  55. **  ouput character to stdout, then fetch next character
  56. **  from stdin
  57. */
  58. outcinc() {
  59.   putchar(c);
  60.   c = getchar(c);
  61.   }
  62.  
  63. /*
  64. ** output a string to stdout
  65. */
  66. outstr(l) char *l; {
  67.   fputs(l, stdout);
  68.   }
  69.  
  70. /*
  71. **  output a right justified integer to stdout
  72. */
  73. outdec(i) int i; {
  74.   char l[5];
  75.   itod(i, l, 5);
  76.   fputs(l, stdout);
  77.   }
  78.  
  79. /*
  80. **  get as much memory as possible for symbol tree
  81. */
  82. initmem() {
  83.   int max;
  84.   max = avail(YES);
  85.   max -= MEMOVERHEAD;
  86.   membtm = malloc(max);
  87.   memtop = membtm + max;
  88.   }
  89.  
  90. /* 
  91. **  get memory for next entry, otherwise abort
  92. */
  93. getmem(i) int i; {
  94.   char *memp;
  95.   if(memtop > membtm + i)  {
  96.     memp = membtm;
  97.     membtm += i;
  98.     return(memp);
  99.     }
  100.   else {
  101.     fputs("Not enough memory", stderr);
  102.     abort(2);
  103.     }
  104.   }
  105.  
  106. /*
  107. **  assign node pointers
  108. */
  109. nodeptrs(w) char *w; {
  110.   nleft = w;
  111.   nright = w + DNRIGHT;
  112.   nfirst = w + DNFIRST;
  113.   nlast = w + DNLAST;
  114.   nword = w + DNID;
  115.   }
  116.  
  117. /*
  118. **  assign reference pointers
  119. */
  120. refptrs(x) char *x; {
  121.   rline = x;
  122.   rnext = x + DRNEXT;
  123.   }
  124.  
  125. /*
  126. **  if id is a new node then insert word and reference 
  127. **  otherwise insert next reference
  128. */
  129. insert(w) char *w; {
  130.   int *x, *lnode;
  131.   int i;
  132.   if(w == NULL) {
  133.     w = getmem(DNID + k);
  134.     nodeptrs(w);
  135.     strcpy(nword, id);
  136.     *nleft = NULL;
  137.     *nright = NULL;
  138.     refptrs(getmem(DRLN));
  139.     *rline = n;
  140.     *rnext = NULL;
  141.     *nfirst = rline;
  142.     *nlast = rline;
  143.     if(root == NULL) root = w;
  144.     else return(w);
  145.     }
  146.   else {
  147.     nodeptrs(w);
  148.     i = strcmp(id, nword);
  149.     if(i == 0) {
  150.       x = getmem(DRLN);
  151.       refptrs(x);
  152.       *rline = n;
  153.       *rnext = NULL;
  154.       refptrs(*nlast);
  155.       *rnext = x;
  156.       *nlast = x;
  157.       }
  158.     else if(i < 0) {
  159.       lnode = nleft;
  160.       x = insert(*nleft);
  161.       if(x != NULL) *lnode = x;
  162.       }
  163.     else {
  164.       lnode = nright;
  165.       x = insert(*nright);
  166.       if(x != NULL) *lnode = x;
  167.       }
  168.     }
  169.     return(NULL);
  170.   }
  171.  
  172. /*
  173. ** print a word with its references 
  174. */
  175. pword(w) char *w; {
  176.   int l;
  177.   int *t2;
  178.   outstr("\n\n");
  179.   outstr(w + DNID);
  180.   outstr("\n");
  181.   t2 = w + DNFIRST;
  182.   t2 = *t2;
  183.   l = 0;
  184.   do {
  185.     if(l == NUMPERLINE) {
  186.       outstr("\n");
  187.       l = 0;
  188.       }
  189.     ++l;
  190.     outstr(" ");
  191.     outdec(*t2);
  192.     ++t2;
  193.     t2 = *t2;
  194.     } while (t2 != NULL);
  195.   }
  196.  
  197. /*
  198. **  print the cross reference tree
  199. */ 
  200. ptree(w) char *w; {
  201.   int *wl, *wr;
  202.   if(w != NULL) {
  203.     wl = w + DNLEFT;
  204.     wr = w + DNRIGHT;
  205.     ptree(*wl);
  206.     pword(w);
  207.     ptree(*wr);
  208.     }
  209.   }
  210.  
  211. main() {
  212.   char l2[5];
  213.   initmem();
  214.   root = NULL;
  215.   n = 0;
  216.   c = getchar();
  217.   while(c != EOF) {
  218.     ++n;
  219.     if(n > MAXLINENUM) n = 0;
  220.     outdec(n);
  221.     outstr(": ");
  222.     while(c != '\n') {
  223.       if(isalpha(c)) {
  224.         k = 0;
  225.         do {
  226.           if(k < MAXWORDLEN) id[k++] = c;
  227.           outcinc();
  228.           } while(isalnum(c));
  229.         id[k++] = '\0';
  230.         insert(root);
  231.         }
  232.       else outcinc();
  233.       if(c == EOF) break;
  234.       }
  235.     if(c != EOF) outcinc();
  236.     }
  237.   ptree(root);
  238.   }
  239.