/* include files */

#include <stdio.h>
#include <ctype.h>

/* definitions */

#define BLANK ' '	/* ascii blank character */
#define BOOLE int
#define DEFINED 1	/* resulte of find next function */
#define DEFINING 0	/* result of find next function */
#define EOFCHAR 26	/* end of file character */
#define EOL '\n'	/* ascii end of line character */
#define EOS '\0'	/* end of string marker */
#define FAULCE 0
#define HASHTABLEFULLFLAG - 1	/* indicates hash table overflow */
#define HTSIZE 1009	/* must be a prime number */
#define MAXDEPTH 25	/* maximum recursive calling depth */
#define MAXFILENAME 100	/* maximum length of a filename */
#define MAXSINLENGTH 20	/* maximum significant characters in a symbol */
#define PAPERWIDTH 132	/* default output page width */
#define TABSIZE 8	/* default output indentation size */
#define TRUE 1
#define USAGE "CALLS file [function ... ]"

void Scan(), NewOccurrence(), OutPut(), BackUp(), Error();

/* code macros */

#define Assert(expr) if (!(expr)) \
{ fprintf(stderr, "Assertion %s failed\n", "expr"); exit(0); }
#define GenericMalloc(t) ((t *) malloc(sizeof(t)))
#define GenerateNewIndex(x, y) (((x + y * y ) % HTSIZE) + 1)
#define GenericNULL(t) ((t *) 0)
#define StrEq(a, b) (strcmp((a), (b)) == 0)

/* typedefs */

/* NameDefinition is the name type for this instance.
NextCally is the next instance called */

typedef struct iType {
	struct nType *NameDefinition;
	struct iType *NextCally;
}
InstanceType, *InstPtrType;

/* FunctionName is the unique function name.  CallCount is the number of
times the function is called.  FirstLineNumber is the line when first
printed.  FirstCally is a pointer to an instance type describing the
first all for this function.  NextNamePtr is the next function name type
in the list */

typedef struct nType {
	char FunctionName[MAXSINLENGTH];
	int CallCount;
	int FirstLineNumber;
	InstPtrType FirstCally;
	struct nType *NextNamePtr;
}
NameType, *NamePtrType;

/* external functions */

extern NamePtrType FindNameEntry();
extern NamePtrType LookFor();
extern char *malloc();
extern NamePtrType AllocNameEntry();
extern InstPtrType AllocInstanceEntry();

/* globle variables */

NamePtrType ActiveList[MAXDEPTH];
/* used by OutPut to avoid infinite recursion */

int BracketCount = 0;
/* keeps track of the nesting of brackets.  A function found when
BracketCount is 0, must be it's defining occurrence.  Since function
invocations must always appear with in some block of code */

FILE *FilePtr;	/* input file pointer */
char *HashTable[HTSIZE];
int LineCount = 0;

int MaxActiveIndex = 0;
/* indexes ActiveList from 0 to MAXDEPTH */

NamePtrType NameListHead = GenericNULL(NameType);

FILE *OutFile;

int TabsPerPage = (PAPERWIDTH - MAXSINLENGTH) / TABSIZE;
/* default number of tabs per page */

BOOLE Turs = TRUE;

void main(argc, argv)
int argc;
char *argv[];
{	/* main */
	int ActListIndex;
	int ArgIndex = 1;
	char Identifier[MAXSINLENGTH];
	NamePtrType CallerPtr;
	char FileName[MAXFILENAME];
	int FunctionUse;
	int HTIndex;
	NamePtrType NamePtr;

	/* initialize the hash table */

	for (HTIndex = 0; (HTIndex < HTSIZE); HTIndex++)
		HashTable[HTIndex] = GenericNULL(char);

	/* the following are keywords that look like function calls in C */

	InsertWord("for");
	InsertWord("if");
	InsertWord("return");
	InsertWord("sizeof");
	InsertWord("switch");
	InsertWord("while");

	/* initialize the active list */

	for (ActListIndex = 0; (ActListIndex < MAXDEPTH);)
		ActiveList[ActListIndex++] = GenericNULL(NameType);

	/* there must be at least one command line option */

	if (argc < 2) {
		printf("USAGE: %s\n", USAGE);
		exit(0);
	}

	/* determan the input file and open it */

	if (ArgIndex < argc) {

		/* extract the filename from the command line */

		strcpy(FileName, argv[ArgIndex++]);

		if ((FilePtr = fopen(FileName, "r")) == NULL)
			Error("Specified file can not be opened", TRUE);
	}

	/* pause the streem and build the appropriate tables */

	CallerPtr = GenericNULL(NameType);
	while ((FunctionUse =
					FindNextFunction(Identifier, CallerPtr)) != EOF)
		if (FunctionUse == DEFINING)
			CallerPtr = FindNameEntry(Identifier);
		else
			NewOccurrence(Identifier, CallerPtr);

	/* If there are any command line arguments, they are the names of the
	functions from which to begin the call charts */

	if (ArgIndex < argc) {
		do {
			if ((NamePtr = LookFor(argv[ArgIndex])) != 0) {
				OutPut(NamePtr, 0);
				printf("\n\n");
			}
			else
				Error(
			"Starting function from command line not found", FAULCE);
		}
		while ((++ArgIndex) < argc);
	}
	else {

		/* print beginning with main if there is one */

		if ((NamePtr = LookFor("main")) != 0) {
			OutPut(NamePtr, 0);
			printf("\n\n");
			NamePtr->CallCount = 1;

			/* don't print main again later */

		}

		/* now print all functions not called by anyone else*/

		for (NamePtr = NameListHead; NamePtr;
						NamePtr = NamePtr->NextNamePtr)
			if (NamePtr->CallCount == 0) {
				OutPut(NamePtr, 0);
				printf("\n\n");
			}

		/* finely print any mutually recursive functions*/

		for (NamePtr = NameListHead; NamePtr;
						NamePtr = NamePtr->NextNamePtr)
			if (NamePtr->FirstLineNumber == 0) {
				OutPut(NamePtr, 0);
				printf("\n\n");
			}
	}
}	/* main */

int FindNextFunction(Identifier, CurFunction)
char *Identifier;
NamePtrType CurFunction;

/* sets it's arguments to the name of the next function found in the input
streem.  It returns as it's value DEFINING if this is the defining occurrence
of the function, DEFINED if it is simply an invocation of the function
and EOF if the input streem is exhausted */

{	/* FindNextFunction */
	int CurChar;

	while (TRUE) {
		CurChar = getc(FilePtr);
		if (IsStartingLetter(CurChar)) {
			ungetc(CurChar, FilePtr);
			Scan(Identifier);
		}
		else {
			switch(CurChar) {
			case '\t' :
			case BLANK :

				/* skip over white space */

				break;

			case EOL :

				/* skip over preprocesser lines */

				if ((CurChar = getc(FilePtr)) == '#')
					while ((CurChar = getc(FilePtr)) != EOL)
						if (CurChar == '\\')
							getc(FilePtr); /* continuation */
				ungetc(CurChar, FilePtr);
				break;

			case '\'' :
				/* this dosn't work if the literal
				contains a quoted apostraphy ( \') */

				Identifier[0] = EOS;

				/* skip over character literals */

				while ((CurChar = getc(FilePtr)) != '\'')
					if (CurChar == '\\')
						getc(FilePtr); /* continuation */
				break;

			case '\"' :

				/* this dosn't work if the literal  contains a
				quoted quotation mark (\") */
				/* skip over string literals */

				while ((CurChar = getc(FilePtr)) != '\"')
					if (CurChar == '\\')
						getc(FilePtr); /* continuation */
				break;
			case '\\' :
				Identifier[0] = EOS;
				getc(FilePtr);
				break;

			case '{' :
				BracketCount++;
				Identifier[0] = EOS;
				break;

			case '}' :
				BracketCount--;
				if (BracketCount < 0)
					Error("Brackets are not properly nessted", FAULCE);
				Identifier[0] = EOS;
				break;

			case '(' :
				if (Identifier[0] == EOS)
					break; /* no function name was found */

				/* ignore any words occurring in the hash table */

				if (!FindWord(Identifier)) {

					/* not with in the body of a function */

					if (BracketCount == 0)
						return(DEFINING);
					else if (!Seen(Identifier, CurFunction))
						return(DEFINED);

					/* ignore multiple occurrences with in a function */

				}
				Identifier[0] = EOS;
				break;

			case EOF :
				return(EOF);

			case '/' :
				if ((CurChar = getc(FilePtr)) == '*') {

					/* skip over comments */

					while (TRUE) {
						while (getc(FilePtr) != '*');
						if ((CurChar = getc(FilePtr)) == '/')
							break;
						ungetc(CurChar, FilePtr);
					}
				}
				else ungetc(CurChar, FilePtr);
				break;

				/* all over characters must delimit identifiers */

			default:
				Identifier[0] = EOS;
				break;
			}	/* switch */
		}	/* else */
	}	/* while */
}	/* FindNextFunction */

void Scan(Token)
char *Token;

/* scans the input streem until a token is found that might be the
name of a function.  It returns the item found */

{	/* scan */
	int CurChar;
	int StringIndex;

	for (StringIndex = 0;
			CurChar = getc(FilePtr), IsStartingLetter(CurChar); ) {
		Token[StringIndex++] = CurChar;
		if (StringIndex >= MAXSINLENGTH) {
			StringIndex = MAXSINLENGTH - 1;
			break;
		}
	}
	Assert(StringIndex < MAXSINLENGTH);
	Token[StringIndex] = EOS;
	ungetc(CurChar, FilePtr);
}	/* scan */

BOOLE FindWord(Word)
char *Word;

/* looks up an identifier in the hash table and returns TRUE or faulce to
indecate the presents or absents of the identifier */

{	/* FindWord */
	int HTIndex = Hash(Word);

	if ((HTIndex == HASHTABLEFULLFLAG) ||
			HashTable[HTIndex] == GenericNULL(char))
		return(FAULCE);
	return(TRUE);
}	/* FindWord */

BOOLE Seen(CheckID, CurFunction)
char *CheckID;
NamePtrType CurFunction;

/* determines if the argument string CheckID has already been seen as an
argument function */

{	/* Seen */
	InstPtrType InstPtr;

	Assert(CurFunction != GenericNULL(NameType));

	for (InstPtr = CurFunction->FirstCally;
				(InstPtr != GenericNULL(InstanceType));
				InstPtr = InstPtr->NextCally)
		if (StrEq(CheckID, (InstPtr->NameDefinition)->FunctionName))
			return(TRUE);
	return(FAULCE);
}	/* Seen */

NamePtrType FindNameEntry(Name)
char *Name;

/* returns a pointer to the argument name on the list of name entries.
If the name is not there, a new name entry is created */

{	/*FindNameEntry */
	NamePtrType LastNamePtr = NULL;
	NamePtrType NamePtr;
	NamePtrType NewNamePtr;
	int StrTest;

	/* search for the name in the current list of known defind functions.
	Since the names are inserted in sorted order, stop when we have past
	the	new name in the list */

	for (NamePtr = NameListHead;
				NamePtr != NULL &&
					(StrTest = strcmp(Name, NamePtr->FunctionName)) >= 0;
				LastNamePtr = NamePtr,
					NamePtr = NamePtr->NextNamePtr)
		if (StrTest == 0)
			return(NamePtr);

	/* name was not found, so add it */

	NewNamePtr = AllocNameEntry();
	strcpy(NewNamePtr->FunctionName, Name);

	/* link the new name entry into the appropriate place in the chain */

	NewNamePtr->NextNamePtr = NamePtr;
	if (!LastNamePtr)
		NameListHead = NewNamePtr;
	else
		LastNamePtr->NextNamePtr = NewNamePtr;
	return(NewNamePtr);
}	/* FindNameEntry */

NamePtrType AllocNameEntry()

/* allocate storage for a name entry */

{	/* AllocNameEntry */
	NamePtrType NamePtr;

	if ((NamePtr = GenericMalloc(NameType)) == NULL)
		Error("Ran out of memory", TRUE);

	/* initialize the new entry */

	NamePtr->FunctionName[0] = EOS;
	NamePtr->CallCount = 0;
	NamePtr->FirstLineNumber = 0;
	NamePtr->FirstCally = GenericNULL(InstanceType);
	NamePtr->NextNamePtr = GenericNULL(NameType);
	return(NamePtr);
}	/* AllocNameEntry */

void NewOccurrence(Name, CallerPtr)
char *Name;
NamePtrType CallerPtr;

/* creates an instance entry for a function use */

{	/* NewOccurrence */
	InstPtrType InstPtr;
	NamePtrType NamePtr;
	InstPtrType NewInstPtr;

	Assert(CallerPtr != GenericNULL(NameType));

	/* create the new instance and link it with the name type
	describing it */

	InstPtr = CallerPtr->FirstCally;
	NamePtr = FindNameEntry(Name);
	NewInstPtr = AllocInstanceEntry();
	NewInstPtr->NameDefinition = NamePtr;
	if (InstPtr != GenericNULL(InstanceType)) {

		/* run down the cally chain until a NULL link is found */

		for (; (InstPtr->NextCally != GenericNULL(InstanceType));
				InstPtr = InstPtr->NextCally)
			; /* no body */

		/* now add the new instance to the Cally chain */

		InstPtr->NextCally = NewInstPtr;
	}
	else
		CallerPtr->FirstCally = NewInstPtr;

	/* increment the cally's CallCount */

	(NamePtr->CallCount)++;
}	/* NewOccurrence */

InstPtrType AllocInstanceEntry()

/* allocate storage for an instance entry */

{	/* AllocateInstanceEntry */
	InstPtrType InstPtr;

	if ((InstPtr = GenericMalloc(InstanceType)) == NULL)
		Error("Ran out of memory", TRUE);
	InstPtr->NameDefinition = GenericNULL(NameType);
	InstPtr->NextCally = GenericNULL(InstanceType);
	return(InstPtr);
}	/* AllocInstanceEntry */

NamePtrType LookFor(Name)
char *Name;

/* looks for it's argument name on the list of name entries.  If found it
returns a pointer to the entry, otherwise it returns NULL */

{	/* LookFor */
	NamePtrType NamePtr;

	for (NamePtr = NameListHead;
				(NamePtr != GenericNULL(NameType));
				NamePtr = NamePtr->NextNamePtr)
		if (StrEq(Name, NamePtr->FunctionName))
			return(NamePtr);
	return(GenericNULL(NameType));
}	/* LookFor */

void OutPut(NamePtr, CurTab)
NamePtrType NamePtr;
int CurTab;

/* a recursive routine that prints one tab for level of nesting.  then
of the function called, followed by the next function called at the same
level.  In doing this it invokes it self to output the names of the functions
called by the current function.  It maintains an active list of functions
currently being output by the deferent levels of recursion.  And if it finds
it self asked to output one which is already active it terminates, marking
that call with an astarisc */

{	/* OutPut */
	InstPtrType InstPtr;
	int LoopCount;
	int NumOfTabs = CurTab;
	BOOLE PageOverflow;
	int TabCount;

	LineCount++;

	printf("\n%4d", LineCount);
	if (!(MakeActive(NamePtr)))
		printf("*");	/* calls nested to deep */
	else {
		for (TabCount = 0; (NumOfTabs > TabsPerPage); TabCount++)
			NumOfTabs -= TabsPerPage;
		for (LoopCount = 0; (LoopCount < TabCount); LoopCount++)
			printf("<");
		printf(" ");
		for (LoopCount = 0; (LoopCount < NumOfTabs); LoopCount++)
			printf("\t");

		if (IsActive(NamePtr))	/* recursive call */
			printf("%s [Recursive]", NamePtr->FunctionName);
		else {
			InstPtr = NamePtr->FirstCally;
			if (InstPtr != GenericNULL(InstanceType)) {
				printf("%s", NamePtr->FunctionName);
				if (!Turs || ((NamePtr->FirstLineNumber == 0))) {
					CurTab++;
					if (NamePtr->FirstLineNumber == 0)
						NamePtr->FirstLineNumber = LineCount;
					if ((CurTab > TabsPerPage) &&
								(CurTab % TabsPerPage == 1) &&
								(InstPtr->NextCally
									!= GenericNULL(InstanceType))) {
						printf(
			"\n- - - - - - - - - - - - - - - - - - - - - - - -");
						printf(" - - - - - - - - - -");
						PageOverflow = TRUE;
			}
			else PageOverflow =FAULCE;

			for (; (InstPtr != GenericNULL(InstanceType));
								InstPtr = InstPtr->NextCally)
						OutPut(InstPtr->NameDefinition, CurTab);
					if (PageOverflow) {
						printf(
			"\n- - - - - - - - - - - - - - - - - - - - - - - -");
						printf(" - - - - - - - - - -");
						PageOverflow = FAULCE;
					}
				}
				else if (InstPtr != GenericNULL(InstanceType))
					printf(" ... [See line %d]", NamePtr->FirstLineNumber);
			}
			else printf("%s", NamePtr->FunctionName);

			/* library external or macro call */

		}
		BackUp();
		if (NamePtr->FirstLineNumber == 0)
			NamePtr->FirstLineNumber = LineCount;
	}
}	/* OutPut */

BOOLE MakeActive(CurNameEntry)
NamePtrType CurNameEntry;

/* puts a pointer to the argument name entry into the active list.  FAULCE is
returned if the function failes, because the function nesting is to deep.
Otherwise TRUE is returned */

{	/* MakeActive */
	if (MaxActiveIndex < MAXDEPTH) {
		ActiveList[MaxActiveIndex++] = CurNameEntry;
		return(TRUE);
	}
	else return(FAULCE);
}	/* MakeActive */

BOOLE IsActive(CurNameEntry)
NamePtrType CurNameEntry;

/* checks if it's argument is already on the active list */

{	/* IsActive */
	int ActListIndex;

	for (ActListIndex = 0; (ActListIndex < MaxActiveIndex - 1);
				ActListIndex++)
		if (CurNameEntry == ActiveList[ActListIndex])
			return(TRUE);
	return(FAULCE);
}	/* IsActive */

void BackUp()

/* pops an item from the active list */

{	/* BackUp */
	Assert(MaxActiveIndex > 0);
	ActiveList[MaxActiveIndex--] = NULL;
}	/* BackUp */

char *Copy(OldString)
char *OldString;

/* Copy makes a copy of OldString and returns the address of the copy */

{	/* Copy */
	char *NewString;
	char *ReturnPtr;

	/* Allocate a string able to hold the length of the string plus 1
	for the terminator */

	ReturnPtr = NewString = malloc(strlen(OldString) + 1);

	/* Copy the string and return a pointer to it */

	while (( *NewString++= *OldString ++) != NULL);
	return(ReturnPtr);
}	/* Copy */

void Error(Message, AbortFlag)
char *Message;
BOOLE AbortFlag;

/* reports any errors detectid */

{	/* Error */
	fprintf(stderr, "\n*** Calls: %s. ***\n", Message);
	if (AbortFlag)
		exit(0);
}	/* Error */

int Hash(Word)
char *Word;

/* generates a unique hash table index for the argument identifier.  The
value of HASHTABLEFULLFLAG is returned if the hash table overflowes */

{	/* Hash */
	int HTIndex;
	int InitHTIndex;
     int ProbeCounter = 0;

	HTIndex = InitHTIndex = TransformId(Word);
	Assert(strlen(Word) > 0);

	if (HashTable[HTIndex] == GenericNULL(char))
		; /* NULL, we'v got it */
	else	/* have we found the corect index? */
	if (StrEq(Word, HashTable[HTIndex]))
		; /* done, a direct hit */
	else	/* Collision.  Generate indexes */

		for (; (ProbeCounter < (HTSIZE / 2)); ProbeCounter++) {
			HTIndex = GenerateNewIndex(InitHTIndex, ProbeCounter);
			if ((HashTable[HTIndex] == GenericNULL(char)) ||
					StrEq(Word, HashTable[HTIndex]))
				break; /* We'v got it */
		}

	if (ProbeCounter >= (HTSIZE / 2))
		return(HASHTABLEFULLFLAG);
	return(HTIndex);
}	/* Hash */

BOOLE InsertWord(Word)
char *Word;

/* inserts an identifier into the hash table and returns TRUE.  If the hash
table overflows, FAULCE is returned */

{	/* InsertWord */
	int HTIndex;

	if ((HTIndex = Hash(Word)) == HASHTABLEFULLFLAG)
		return(FAULCE);

	/* add word to the hash table if it is not already present */

	if (HashTable[HTIndex] == GenericNULL(char))
		HashTable[HTIndex] = Copy(Word);
	return(TRUE);
}	/* InsertWord */

BOOLE IsStartingLetter(Ch)
char Ch;

/* IsStartingLetter returns TRUE if Ch is a valid character to begin
a C token */

{	/* IsStartingLetter */
	return((isalpha(Ch) || Ch == '_') ? TRUE : FAULCE);
}	/* IsStartingLetter */

int TransformId(Word)
char Word[];

/* converts the identifier into an integer with in the index
range of HashTable.  A polonomial is generated in reduced modula HTSIZE
to produce this number */

{	/* TransFormId */
	int Term = 0;
	int WordIndex;

	for (WordIndex = strlen(Word) - 1; (WordIndex >= 0); WordIndex--)
		Term = (257 * Term) + Word[WordIndex];
	Term = abs(Term);
	return(Term % HTSIZE);
}	/* TransFormId */
