Skip navigation.

Xref

The compiler used was BDSC created by Leor Zolman. A recent tool of Leor is STLFilt: An STL Error Message Decryptor for C++.

See http://www.bdsoft.com/tools/stlfilt.html.

Given a piece of text, this program creates an alphabetical list of words in the text followed by the linenumbers where the words occur.

I wrote this program to get experience with datastructures like list and tree.

The main entry of this program is not function main() but program(), because the program uses my library bdsstdio that provides IO-redirection.

Download: xref.tar.gz

See also xref's successor, WordIndex.

 

/*

%cc1 xref.c
%clink bdsstdio xref list tree queue
%era xref.com
%ren xref.com=bdsstdio.com

*/

/*

   XREF.C

   Program to make cross-reference of words to linenumbers.


   (c) Copyright 1987 M.J. Moene.

   Version: 0.00
   Date   : 20 Mar 1987
   Disk   : DIS.C


   Example: D>xref file1 file2 >output

*/

#include <bdsstdio.h>			/* Standard IO header		     */

#define PROGNAME "Xref"			/* Program name for error report     */


/*----------------------------------------------------- global variables ------
*/

#define SPACE  30000			/* 25k string space		     */

char space[SPACE],
     *savail;


#define LNODE  struct _LNODE		/* Typedef			     */
#define LNODES 1000			/* Maximum of linenumbers to collect */

LNODE					/* Structure of list with 	     */
   {					/* line (page) numbers		     */
      LNODE *next;
      int   line;
   };

LNODE lnode[LNODES+1],			/* List nodes			     */
      *lavail;				/* Internal: next free list node     */


#define TNODE  struct _TNODE		/* Typedef			     */
#define TNODES 800			/* Maximum number of different words */

TNODE					/* Structure of tree with words and  */
   {					/*   queue with linenumbers          */
      TNODE *left,*right;		/* Tree structure for sorting words  */
      LNODE *front,*rear;		/* Queue with line (page) numbers    */
      char  *word;			/* Word				     */
   };

TNODE tnode[TNODES+1],			/* Tree nodes			     */
      *tavail,				/* Internal: next free tree node     */
      *tree;				/* Tree root node		     */


char sbuf[MAXLINE];			/* General use string		     */



int  tcase,				/* Case conversion tag		     */
     page,				/* Current line (page) number	     */
     lpp,				/* lines per page  (default 1) 	     */
     lin;				/* Current line number		     */


/*------------------------------------------------------- function types ------
*/

char  *nextword();			/* Split input stream to words	     */

char  *getspace();			/* Get bytes free space		     */

TNODE *gettnode(),			/* Get treenode			     */
      *lookup(),			/* Get existing nodepointer or NULL  */
      *winstall();			/* Install word in tree		     */

LNODE *getlnode(),			/* Get listnode			     */
      *linstall();			/* Install linenumber in list	     */

FILE  *efopen();			/* fopen() with error check	     */

char  *strupr(),			/* String to uppercase		     */
      *strlowr(),			/* String to lowercase		     */
      *(*wordconv)();			/* Word case conversion function     */


/*-------------------------------------------------------------- program ------
**
**
**
*/

program(argc,argv)			/* main()			     */
int argc;
char *argv[];
{
   FILE *fp;
   int  i;

   reset();				/* Initialize list & tree storage    */
					/*   and global variables	     */

   tcase=FALSE;				/* No case conversion		     */
   lpp=1;				/* Initialize defaults of options    */


   while (argc>1 && argv[1][0] == '-')	/* Process options		     */
   {
      switch(argv[1][1])
      {
	 case 'H': opterr();
		   break; 
         case 'L': tcase=TRUE;
 		   wordconv=strlowr;
                   break;
         case 'U': tcase=TRUE;
 		   wordconv=strupr;
                   break;
         case 'P': lpp=atoi(&argv[1][2]);
                   break;
         default : fprintf(stderr,"error: unknown option -%c\n",argv[1][1]);
		   opterr();
      }
      argc--;
      argv++;
   }


   if (argc == 1) 			/* No filenames in argument list     */
   {					/* Use standard input		     */
      getwords(stdin);
      printwords();
   }
   else
      for (i=1; i<argc; i++)		/* Process files in argument list    */
      {
         fp=efopen(argv[i],"r");

         getwords(fp);
         printwords();

         putchar('\n');
         fclose(fp);

         reset();
      }
}


/*--------------------------------------------------------------- opterr ------
**
**
*/

opterr()
{
   fprintf(stderr,"\n%s options:\n\n",PROGNAME);
   fprintf(stderr,"-H : this help message\n");
   fprintf(stderr,"-L : convert words to lowercase\n");
   fprintf(stderr,"-U : convert words to uppercase\n");
   fprintf(stderr,"-Pn: set pagelength to n (default 1)");
   fprintf(stderr,"\n\nExample: >xref -p96 file1.typ file2.typ >xref.out\n");
   exit(-1);
}
   

/*------------------------------------------------------------- getwords ------
**
**
**
**
*/

getwords(fp)				/* Collect words & linenumbers	     */
FILE *fp;
{
   int status;
   char *wrd;

   status=OK;

   while ((wrd= nextword(fp)) != NULL && status==OK) 
      status=addline(wrd,page);
   if (status==ERROR) error("addline returned error\n","");
}


char *nextword(fp)			/* Split input stream into words     */
FILE *fp;
{
   char *p;
   int  c;

   p=sbuf;

   while ((c=getc(fp)) != EOF && !isalpha(c)) 
      if (c=='\n') 
      {
         lin++;
         page=lin/lpp + 1;
      }

   if (c==EOF) return NULL;

   do
   {
      *p++=c;
   }
   while ((c=getc(fp)) != EOF && (isalpha(c) || isdigit(c) || c=='_'));
   *p='\0';
   ungetc(c,fp);

   return tcase==TRUE ? (*wordconv)(sbuf) : sbuf;
}


addline(wrd,lin)			/* Add word (if not already in tree) */
char *wrd;				/* Add linenumber (if not in list    */
int  lin;
{
   TNODE *tp;
   LNODE *lp;

   tp=NULL;

   tp=lookup(wrd);
   if (tp==NULL) tp=winstall(wrd);
   if (tp==NULL) return ERROR;

   if (lin > tp->rear->line)
   {
      if ((lp=linstall(lin)) == NULL) return ERROR;
      append(&(tp->front),lp);
   }
   return OK;
}


TNODE *lookup(wrd)			/* Locate treenode with "wrd" ;      */
char *wrd;				/* if no such node return NULL	     */
{
   char buf[MAXLINE+1];
   TNODE *np1,*np2,*locate();
   int wordcmp();

   np1=gettnode();
   np1->word=buf;
   strncpy(np1->word,wrd,MAXLINE);

   np2=locate(tree,np1,wordcmp);

   freetnode(np1);
   return np2;
}


TNODE *winstall(wrd)			/* Install "wrd" in tree	     */
char *wrd;
{
   TNODE *p;
   int wordcmp();

   p=gettnode();
   if (p == NULL) return NULL;

   p->word=getspace(strlen(wrd)+1);
   if (p->word == NULL) return NULL;

   strcpy(p->word,wrd);

   p->left =NULL;
   p->right=NULL;
   p->front=NULL;
   p->rear =NULL;

   place(&tree,&p,wordcmp);

   return p;
}


wordcmp(tp,np)				/* Case sensitive wordcompare	     */
TNODE *tp,*np;
{
   return strcmp(tp->word,np->word);
}


/*----------------------------------------------------------- printwords ------
**
**
**
*/

printwords()				/* Print list of collected words     */
{					/* and linenumbers		     */
   int printnode();

   intrav(&tree,printnode);
}


printnode(nodep)			/* Print word of this treenode and   */
TNODE **nodep;				/* collected linenumbers	     */
{
   int printline();

   printf("%-15s : ",(*nodep)->word);
   listtrav(&((*nodep)->front),printline);

   putchar('\n');
}


printline(nodep)			/* Print linenumber of this listnode */
LNODE **nodep;
{
   printf("%4d ",(*nodep)->line);
}


/*------------------------------------------------------ space functions ------
**
**
**
*/

initspace()				/* Reset spaceavail pointer	     */
{
   savail=&space[0];
}


char *getspace(size)			/* Allocate size bytes in space arr  */
int  size;
{
   char *p;

   p=savail;
   savail+=size;
   if (savail > &space[SPACE]) return NULL;
   else			       return p;
}


/*------------------------------------------------------- list functions ------
**
**
**
*/

initlist()				/* Link listnodes & initialize lavail*/
{
   int i;

   lavail=&lnode[0];
   for (i=0; i<LNODES; i++) lnode[i].next=&lnode[i+1];
   lnode[LNODES].next=NULL;
}


LNODE *getlnode()			/* Return free listnodepointer	     */
{
   LNODE *np;

   if (lavail==NULL)
      error("getnode: list overflow.","");
   else
   {
      np=lavail;
      lavail=lavail->next;
      return np;
   }
}


freelnode(np)				/* Free listnodepointer np	     */
LNODE *np;
{
   np->next=lavail;
   lavail=np;
}


LNODE *linstall(lin)			/* Install "lin" in list	     */
int lin;
{
   LNODE *p;

   p=getlnode();
   p->line=lin;

   p->next=NULL;
   return p;
}


/*------------------------------------------------------- tree functions ------
**
**
**
*/

inittree()				/* Link treenodes & initialize tavail*/
{
   int i;

   tree=NULL;
   tavail=&tnode[0];
   for (i=0; i<TNODES; i++) tnode[i].right=&tnode[i+1];
   tnode[TNODES].right=NULL;
}


TNODE *gettnode()			/* Return free treenode		     */
{
   TNODE *tp;

   if (tavail==NULL)
      error("getnode: tree overflow.","");	/* character 0 */
   else
   {
      tp=tavail;
      tavail=tavail->right;
      return tp;
   }
}


freetnode(np)				/* Free treenode np		     */
TNODE *np;
{
   np->right=tavail;
   tavail=np;
}


freetree(tp)				/* Free tree with root tp	     */
{
   int freetnode();
   posttrav(&tree,freetnode);
}


/*-------------------------------------------------------- miscellaneous ------
**
**
**
*/


reset()					/* Initialize global variables &     */
{   					/*   link listnodes and treenodes    */
   lin =0;
   page=1;

   initspace();
   initlist();
   inittree();
}


FILE *efopen(name,mode)			/* fopen() with error check	     */
char *name,*mode;
{
   FILE *fp;

   if ((fp=fopen(name,mode)) != ERROR) return fp;
   error("unable to open file %s.",name);
}


error(s,t)				/* Display errormessage and exit     */
char *s,*t;
{
   fprintf(stderr,"%s: ",PROGNAME);
   fprintf(stderr,s,t);
   fprintf(stderr,"\n");

   exit(-1);
}


strncpy(s1,s2,n)			/* Copy string s2 to s1 with maximum */
char *s1,*s2;				/*   length n			     */
int  n;
{
   while (n-- && (*s1++=*s2++))
   ;
   if (n==0) *s1='\0';
}


char *strupr(string)			/* Convert string to uppercase       */
char *string;
{
   char *p;
   p=string;

   for (; *string; *string=toupper(*string), string++)
   ;

   return p;
}


char *strlowr(string)			/* Convert string to lowercase       */
char *string;
{
   char *p;
   p=string;

   for (; *string; *string=tolower(*string), string++)
   ;

   return p;
}


/*** End Of File ***/