/*****************************************************************************
 * File:	dirTree.c
 *
 * Author:	Rhett "Jonzy" Jones
 *		jonzy@cc.utah.edu
 *
 * Date:	March 26, 1993
 *
 * Modified:	March 27, 1993, by Rhett "Jonzy" Jones.
 *		Made the local variable 'strs' global to this file to reduce
 *		the amount of stack space used when calling recursive routines.
 *		Swapped the values of SSTR and PSTR so the tree will now be
 *		built with the port as the initial tree and the selector string
 *		as the last tree.  This was done to reduce the amount of memory
 *		used by the tree itself.
 *
 *		March 30, 1993, by Rhett "Jonzy" Jones.
 *		Added PrintDirTree().
 *		Fixed that damn bug in BuildDirTree() that built the tree wrong.
 *		'dTree' is NOT the same as 'node'...  dah!
 *
 *		April 1, 1993, by Rhett "Jonzy' Jones.
 *		Modified PrintDirTree() and added the routine NumberOfDirs() to
 *		support the -a and -A options.
 *
 * Description:	Contains tree routines for use with keeping track of directory
 *		items encountered.  The tree structure is such that each node
 *		contains the line number the directory was printed on if the
 *		node contains the selector string, otherwise the value is -1, a
 *		string representing the port, host, or selector string.  The purpose
 *		of this code is to prevent retraversing a pretraveresed gopher
 *		directory item.  No sense in traversing a directory more than once.
 *		Fred Barrie says "some gopher administrators don't like to have
 *		their server treed".  Thus the reason for keeping the traversing
 *		to a mimimum.
 *
 *		To summarize: we build 3 level tree with level, the base,
 *		sorted on the port, the second level of the tree is sorted
 *		on host, and the last level is sorted on selector string.
 *		The tree is built in this fashion to mimimize the impact on
 *		memory.  With less ports being used in gopher space than hosts,
 *		and less hosts than documents or directories being served, I
 *		opted to to sort on port first.  Thus if all gopher space uses
 *		port 70 tree, the base tree or level one only has one node.
 *
 * Routines:	static	long	    NumberOfDirs(DirTreeType *node);
 *			void	    PrintDirTree(DirTreeType *dTree,short whichStr);
 *			long	    InDirTree(DirTreeType *dTree,short whichStr);
 *			DirTreeType *WhatDirBranch(DirTreeType *dTree,short whichStr);
 *		static	DirTreeType *CreateDirBranch(long lineNum,short whichStr);
 *		static	DirTreeType *CreateDirNode(long lineNum,short whichStr);
 *			DirTreeType *BuildDirTree(DirTreeType *dTree);
 *			void	    WaterTree(char *sStr,char *hStr,char *pStr);
 *
 * Bugs:	No known bugs.
 *
 * Copyright:	Copyright 1993, University of Utah Computer Center.
 *		This source may be freely distributed as long as this copyright
 * 		notice remains intact, and is in no way used for any monetary
 * 		gain, by any institution, business, person, or persons.
 *
 * TODO:	Consolidate these routines into tree.c.  Many of the
 *		routines in this file are very similar to those in tree.c.
 *
 ****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dirTree.h"
#include "utils.h"

#define NIL		(void *)0L

/* These are also defined in "tree.h". */
#define GOLEFT	-1
#define THISONE	0
#define GORITE	1

/* This is also defined in "jughead.c". */
#define EMPTYSTRING	""			/* The empty C string. */

	DirTreeType	*dirRoot = NIL;
	long		lineNumber = 0;
	char		*strs[STRS];
static	DirTreeType	*lastDirNode = NIL;
static	short		lastStrType,
			limb;

/* The following is defined in "jughead.c". */
extern int	debug,				/* Are we debugging? */
		printDTreeDirs;			/* Do we print the directories? */

#if(1)
/* Also defined in "tree.c". */
/*****************************************************************************
 * WhatDirection returns GOLEFT if 's1' is less than 's2', returns GORITE if
 * if 's1' is greater than 's2', or returns THISONE if 's1' is the same as
 * 's2'.
 ****************************************************************************/
static short WhatDirection(s1,s2)
	char	*s1,			/* String contained in the leaf. */
		*s2;			/* String we are looking for. */
{	short	direction;		/* What direction do we look? */

	if ((direction = strcmp(s1,s2)) < 0)
		return(GOLEFT);
	else if (direction > 0)
		return(GORITE);
	else
		return(THISONE);

}	/* WhatDirection */
#endif

/*****************************************************************************
 * NumberOfDirs returns the nuber of the leaves contained in the tree 'node'.
 ****************************************************************************/
static long NumberOfDirs(node)
	DirTreeType	*node;		/* The node to have summed. */
{
	if (!node)
		return(0);
	else
		return(1 + NumberOfDirs(node->left) + NumberOfDirs(node->right));

}	/* NumberOfDirs */

/*****************************************************************************
 * PrintDirTree prints the contents of the tree in a format depending on the
 * 'debug' and 'printDTreeDirs' variables.  Basicly the format is:
 * port1
 *	host1
 *		selectorString1
 *		...
 *		selectorStringN
 *	...
 *	hostN
 * ...
 * portN
 ****************************************************************************/
void PrintDirTree(dTree,whichStr)
	DirTreeType	*dTree;
	short		whichStr;
{	short		i;

	if (dTree)
		{
		PrintDirTree(dTree->left,whichStr);

		/* Give some indention. */
		for (i = PSTR; i < whichStr; i++)
			fprintf(stdout,"\t");
		if (whichStr < SSTR)
			{
			if (printDTreeDirs)
				if (debug)
					fprintf(stdout,"<see line %8ld>\t%s",dTree->lineNum,dTree->str);
				else
					fprintf(stdout,"\t%s",dTree->str);
			else
				fprintf(stdout,"%ld %s accesed via: %s",NumberOfDirs(dTree),
						(whichStr == PSTR) ? "port(s)" : "host(s)",
						dTree->str);
			if (whichStr == HSTR && !printDTreeDirs)
				fprintf(stdout," serving %ld directories\n",NumberOfDirs(dTree->tree));
			else
				{
				fprintf(stdout,"\n");
				PrintDirTree(dTree->tree,whichStr + 1);
				}
		}
		else if (printDTreeDirs)
			fprintf(stdout,"<see line %8ld>\t[%s]\n",dTree->lineNum,dTree->str);

		PrintDirTree(dTree->right,whichStr);
		}

}	/* PrintDirTree */

/*****************************************************************************
 * InDirTree returns the line number the data was previously encountered if
 * the data has been seen before and false otherwise.
 ****************************************************************************/
long InDirTree(dTree,whichStr)
	DirTreeType	*dTree;		/* The tree we are looking at. */
	short		whichStr;	/* Index into array 'strs'. */
{	int		result;		/* Result of calling strcmp(). */

	if (!dTree || whichStr > SSTR)
		return(0);
	else if (!(result = strcmp(strs[whichStr],dTree->str)))
		if (whichStr == SSTR)
			return(dTree->lineNum);
		else
			return(InDirTree(dTree->tree,whichStr + 1));
	else if (result < 0)
		return(InDirTree(dTree->left,whichStr));
	else
		return(InDirTree(dTree->right,whichStr));

}	/* InDirTree */

/*****************************************************************************
 * WhatDirBranch returns the limb of the tree containing string indexed by
 * 'whichStr.  This routine also assigns to 'limb' the direction we are
 * looking in the tree and assigns to 'lastDirNode' the last node encountered.
 * These assignments are done to speed the time required when building the tree.
 ****************************************************************************/
DirTreeType *WhatDirBranch(dTree,whichStr)
	DirTreeType	*dTree;		/* The tree we are looking at. */
	short		whichStr;	/* Index into the array 'strs'. */
{
	if (!dTree)		/* Insert at last position. */
		return(dTree);
	else switch (WhatDirection(strs[whichStr],dTree->str))
		{
		case GOLEFT:
			limb = GOLEFT;
			lastDirNode = dTree;
			return(WhatDirBranch(dTree->left,whichStr));
		case GORITE:
			limb = GORITE;
			lastDirNode = dTree;
			return(WhatDirBranch(dTree->right,whichStr));
		case THISONE:
			return(dTree);
		}

}	/* WhatDirBranch */

/*****************************************************************************
 * CreateDirBranch returns a node for the dTree containing 'str', and
 * 'lineNum', with all other pointers set to nil.
 ****************************************************************************/
static DirTreeType *CreateDirBranch(lineNum,whichStr)
	long		lineNum;	/* The line 'str' is from. */
	short		whichStr;	/* Index into the array 'strs'. */
{	DirTreeType	*node;		/* The node we are creating. */

	if (node = (DirTreeType *)malloc(sizeof(DirTreeType)))
		if (node->str = (char *)malloc(strlen(strs[whichStr]) + 1))
			{
			if (whichStr == SSTR)
				node->lineNum = lineNum;
			else
				node->lineNum = -1;
			strcpy(node->str,strs[whichStr]);
			node->left = node->right = node->tree = NIL;
			}
		else
			{
			free(node);
			node = NIL;
			fprintf(stderr,"error: CreateDirBranch could not get memory for the string [%s].\n",strs[whichStr]);
			}
	else
		fprintf(stderr,"error: CreateDirBranch could not get memory for the node.\n");

	return(node);

}	/* CreateDirBranch */

/*****************************************************************************
 * CreateDirNode returns a node for use in the 3 tiered tree.  This node
 * may or may not contain all 3 trees.  This is dependent on the value of
 * 'whichStr', which indexes into the array 'strs' telling us what string
 * item we are processing.
 ****************************************************************************/
static DirTreeType *CreateDirNode(lineNum,whichStr)
	long		lineNum;	/* The line 'strs' are from. */
	short		whichStr;	/* Index into the array 'strs'. */
{	DirTreeType	*node;		/* The node we are creating. */

	if (node = CreateDirBranch(lineNum,whichStr++))
		if (whichStr < STRS)
			if (node->tree = CreateDirBranch(lineNum,whichStr++))
				if (whichStr < STRS)
					if (node->tree->tree = CreateDirBranch(lineNum,whichStr++))
						return(node);
					else
						fprintf(stderr,"error: CreateDirNode failed.\n");
				else
					return(node);
			else
				fprintf(stderr,"error: CreateDirNode failed.\n");
		else
			return(node);
	else
		fprintf(stderr,"error: CreateDirNode failed.\n");
	return(NIL);

}	/* CreateDirNode */

/*****************************************************************************
 * BuildDirTree returns the root of the 3 tiered tree, and adds the strings
 * indexed by 'whichStr' to the proper branch of the tree.
 ****************************************************************************/
DirTreeType *BuildDirTree(dTree)
	DirTreeType	*dTree;		/* The tree we are processing. */
{	DirTreeType	*node;		/* The node we are adding. */
	short		whichStr;	/* Index into the array 'strs'. */

	if (!dTree)
		return(CreateDirNode(lineNumber,PSTR));

	if (node = WhatDirBranch(dTree,whichStr = PSTR))
		if (node = WhatDirBranch(node->tree,whichStr = HSTR))
			if (node = WhatDirBranch(node->tree,whichStr = SSTR))
				return(dTree);	/* Allready in the tree. */

	node = CreateDirNode(lineNumber,whichStr);
	switch (limb)
		{
		case GOLEFT:
			lastDirNode->left = node;
			break;
		case GORITE:
			lastDirNode->right = node;
			break;
		}

	return(dTree);

}	/* BuildDirTree */

/*****************************************************************************
 * WaterTree prepares BuildDirTree() and InDirTree() to either search on
 * build on 'sStr', 'hStr', or 'pStr, by initializing the array 'strs',
 * 'limb', and 'lastDirNode'.
 ****************************************************************************/
void WaterTree(sStr,hStr,pStr)
	char	*sStr,		/* The selector string. */
		*hStr,		/* The host string. */
		*pStr;		/* The port string. */
{

	strs[DSTR] = EMPTYSTRING;
	strs[SSTR] = sStr;
	strs[HSTR] = hStr;
	strs[PSTR] = pStr;

	/* These don't realy need to be initializes because WhatDirBranch()	*
	 * assigns these variable to the proper value.  Better safe then sorry.	*/
	limb = 0;
	lastDirNode = NIL;

}	/* WaterTree */
