/*****************************************************************************
 * File:	search.c
 *
 * Author:	Rhett "Jonzy" Jones
 *		jonzy@cc.utah.edu
 *
 * Date:	March 6, 1993
 *
 * Modified:	March 15, 1993, by Rhett "Jonzy" Jones.
 *		Added the ability to handle the -HUP interrupt.
 *
 *		March 16, 1993, by Rhett "Jonzy" Jones.
 *		PrintPositions() will only return the collected items if
 *		the number of these items is less 1024.  Modified
 *		PostPositions() to watch for the case where A and B and C
 *		yeilds (A and B) = NIL, thus this result anded with C will
 *		no longer print the entire list C.  Oversight in my part.
 *
 * Description:	Either builds an index into a datafile, where the datafile
 *		contains lines of gopher menu items (via jughead), or performs
 *		boolean searches on words from the display string in the
 *		datafile as read from the resultant index file.
 *
 *		When building the index we read from the datafile and for
 *		each line we acquire the current line position in the file via
 *		ftell(), and extract the display string excluding the first
 *		character which is the item type, and break the display string
 *		into words.  We then dump the word followed by a tab and the
 *		position to a temporary file.  We then read from the temporary
 *		file and build a binary tree containing words and a list of
 *		postions, which is the line the word came from.  No word is
 *		duplicated in the tree.  And finaly dump the binary tree to
 *		a file with the following format:
 *		dataFileNameIndexWasBuiltFrom	numberOfnodes
 *		lenWord0	word0	0	1	3
 *		lenWord1	word1	2	5
 *		...
 *		lenThisWord	word_numberOfnodes-1	m	n
 *
 *		where: dataFileNameIndexWasBuiltFrom is the name of the data
 *		file this index was built from, numberOfnodes is the number of
 *		nodes in the tree, lenWordX is the number of characters in wordX
 *		including the terminating null, wordX is the word followed by the
 *		position in the data file the word came from.
 *
 *		When reading from the index file and doing boolean operations,
 *		we read the index into memory, and acquire the string the user
 *		wants to do a search on.  This string is then broken into words,
 *		using the same mechanisim as breaking the display string into
 *		words.  If a single word is found we print all lines from the
 *		datafile in which the word exists in the display string.  If two
 *		words are found it is taken to be word1 AND word2.  The boolean
 *		operations currently supported are AND, NOT, OR.  All boolean
 *		operations are evaluated left to right.
 *
 * Routines:		void	 LogMessage(int sockfd,char *message);
 *			char	 *GetDisplayString(FILE *fp,long *pos);
 *			int	 CreateWordsTree(char *fileName);
 *			short	 ReservedWord(char *word);
 *			short	 ParseSearchString(char *string);
 *		static	void	 PrintPositions(ListType *node);
 *			ListType *DoOperation(short op,ListType *l1,ListType *l2);
 *			void	 LogRequest(int sockfd);
 *			void	 PostPositions(char *what2find);
 *			short	 CreateElements(char *fileName);
 *			void	 CleanUp(void);
 *			int	 HangUpSignal(void);
 *
 * 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.
 *
 ****************************************************************************/

#include <setjmp.h>
#include <signal.h>
#include <stdio.h>
#ifdef NEXT
#	include <libc.h>
#else
#	include <stdlib.h>
#endif
#include <string.h>
#include <fcntl.h>
#include <netinet/in.h>

#include "tree.h"
#include "utils.h"

#define PORT2USE		3000

#define AND		 1	/* The AND operation. */
#define OR		 2	/* The OR  operation. */
#define NOT		 3	/* The NOT operation. */
#define MAXWRDSNCMNDS	20	/* The allowable words and commands. */

/* These are the characters the denote a separator for words. */
#define DELIMETERS	" \t\n\f\r !\"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~"

Element		*items = NIL;			/* Array of words and file postions. */
long		numElements;			/* Number of elements in 'items'. */
char		dataFileName[512],		/* The name of the data file. */
		*logFile = NIL,			/* Name of the file to log to. */
		*wrdsNcmds[MAXWRDSNCMNDS + 1];	/* Array of words and commands. */
short		numCommands;			/* The number of words and commands. */
jmp_buf		hupbuf;				/* The place to go if -HUP encountered. */

extern int	debug;				/* Are we debugging? */

/*****************************************************************************
 * LogMessage logs the message 'message' to the end of the log file 'logFile'.
 * The logging is the same as that found in gopherd.c from the University of
 * Minnesota.
 ****************************************************************************/
void LogMessage(sockfd,message)
	int		sockfd;		/* The socket file descriptor. */
	char		*message;	/* The message to log. */
{	static char	hostName[256],	/* Name of the host we are talking to. */
			ip[256];	/* The hosts IP number. */
	struct flock	lock;		/* Info to lock the log file. */
	time_t		theTime;	/* The current time. */
	char		*cTime,		/* The calendar time. */
			*lineFeed,	/* Location of the line feed. */
			logEntry[1024];	/* The entry to place in the log. */
	int		theLog = -1;	/* The file to log to. */

	if (logFile)	/* Open the sucker. */
		theLog = open(logFile,O_WRONLY | O_APPEND | O_CREAT,0644);

	hostName[0] = '\0';

	if (sockfd > -1)
		IP2Hostname(sockfd,hostName,ip);
	time(&theTime);
	cTime = ctime(&theTime);
	if (lineFeed = strchr(cTime,'\n'))	/* Get rid of the line feed. */
		*lineFeed = '\0';
	sprintf(logEntry,"%s %d %s : %s\n",cTime,getpid(),hostName,message);

	if (theLog != -1)
		{
		lock.l_type = F_WRLCK;
		lock.l_whence = SEEK_SET;
		lock.l_start = lock.l_len = 0L;
		fcntl(theLog,F_SETLKW,&lock);		/* Lock the file so no one can write to it. */
		lseek(theLog,0L,SEEK_END);		/* Make sure we are at the end of file. */
		write(theLog,logEntry,strlen(logEntry));
		lock.l_type = F_UNLCK;
		fcntl(theLog,F_SETLKW,&lock);		/* Unlock the file. */
		}

	if (logFile)	/* I guess we can close it now. */
		close(theLog);

	if (debug)
		fprintf(stderr,"%s\n",logEntry);

}	/* LogMessage */

/*****************************************************************************
 * GetDisplayString returns the display string portion of the gopher line
 * contained in 'str'.  I should mention the item type, which is the first
 * character in the display string, is skipped.
 ****************************************************************************/
char *GetDisplayString(fp,pos)
	FILE		*fp;		/* The file we are reading. */
	long		*pos;		/* Position in the file of the line. */
{	static char	buf[2048];	/* Buffer for the display string. */
	size_t		len;		/* Number of characters to the tab. */
	static long	line = 0;	/* The line number in the file for error reporting. */
	char		*s;		/* Pointer to the line we acquire from the file. */
	short		error = 0;	/* Did we encounter an error? */

	*pos = ftell(fp);
	line++;

	if (fgets(buf,2048,fp))
		if (s = strchr(buf,'\t'))
			if ((len = (size_t)(s - buf)) > 0)
				{
				buf[len] = '\0';
				return(buf + 1);
				}
			else
				error = 1;
		else
			error = 1;

	if (error)
		{
		fprintf(stderr,"warning:GetDisplayString found bad line = %ld, culprit = %s\n",line,buf);
		pos = 0;
		return("");
		}

	return(NIL);

}	/* GetDisplayString */

/*****************************************************************************
 * CreateWordsTree creates a tree where each node of the tree contains a
 * word and a list of file positions, representing the line the word is
 * contained in.  It should be mentioned that the words are parsed from
 * the display string according to the 
 ****************************************************************************/
int CreateWordsTree(fileName)
	char	*fileName;	/* Name of the data file. */
{	long	position;	/* Position in the file of the current line. */
	FILE	*fpIn;		/* The data file we area reading from .*/
	char	*dStr,		/* The display string with no leading item type. */		
		*word;		/* A word from dStr. */
	int	error = 0;	/* Did we get an error? */

	if (fpIn = fopen(fileName,"r"))
		{
		while (dStr = GetDisplayString(fpIn,&position))
			if (*dStr)
				for (word = strtok(dStr,DELIMETERS); word; word = strtok(NIL,DELIMETERS))
					BuildTree(&root,StrToLower(word),position);
		fclose(fpIn);
		}
	else
		error = fprintf(stderr,"error: CreateWordsTree could not open %s\n",fileName);

	return(!error);

}	/* CreateWordsTree */
	
/*****************************************************************************
 * ReservedWord returns true if 'word' is "AND", "OR", or "NOT", otherwise
 * it returns false.  If 'word' is "AND" this routine returns 1, if 'word' is
 * "OR" we return 2, if 'word' is "NOT" 3 gets returned.
 ****************************************************************************/
short ReservedWord(word)
	char	*word;			/* The word we are checking if reserved. */
{	int	len = strlen(word);	/* The length of 'word'. */

	switch (len)
		{
		case 2:
			if ((word[0] == 'O' || word[0] == 'o') &&
			    (word[1] == 'R' || word[1] == 'r'))
	    			{
			    	word[0] = 'O'; word[1] = 'R';
				return(OR);
				}
			break;
		case 3:
			if ((word[0] == 'A' || word[0] == 'a') &&
			    (word[1] == 'N' || word[1] == 'n') &&
			    (word[2] == 'D' || word[2] == 'd'))
		    		{
		    		word[0] = 'A'; word[1] = 'N'; word[2] = 'D';
				return(AND);
				}
			else if ((word[0] == 'N' || word[0] == 'n') &&
				 (word[1] == 'O' || word[1] == 'o') &&
				 (word[2] == 'T' || word[2] == 't'))
		    		{
		    		word[0] = 'N'; word[1] = 'O'; word[2] = 'T';
				return(NOT);
				}
			break;
		default:
			break;
		}

	return(0);

}	/* ReservedWord */

/*****************************************************************************
 * ParseSearchString parses 'string' into words and or commands which we do
 * searches and boolean searches on.  All words and commands get placed into
 * the array 'commands'.  If any word is "and", "or", or "not" it is taken to
 * be the command AND, OR, or NOT respectivly.  If any 2 words are not
 * seperated with a command, the command AND is implied to be the seperating
 * command.
 ****************************************************************************/
short ParseSearchString(string)
	char		*string;	/* The string we are parsing. */
{	char		*word;		/* The word extracted from 'string'. */
	short		lastOneReserved,/* Was the last word reserved? */
			thisOneReserved,/* Is the current word reserved? */
			i;		/* A loop counter if we are logging. */
	FILE		*fp;		/* Pointer to the logfile if we are logging. */

	for (numCommands = 0, lastOneReserved = 1, word = strtok(string,DELIMETERS);
	     numCommands < MAXWRDSNCMNDS && word;
	     word = strtok(NIL,DELIMETERS))
		{
		thisOneReserved = ReservedWord(word);
		if (!lastOneReserved && !thisOneReserved)
			{
			wrdsNcmds[numCommands++] = "AND";
			wrdsNcmds[numCommands++] = StrToLower(word);
			}
		else if (thisOneReserved)
			wrdsNcmds[numCommands++] = word;
		else
			wrdsNcmds[numCommands++] = StrToLower(word);
		lastOneReserved = thisOneReserved;
		}

	return(numCommands);

}	/* ParseSearchString */

/*****************************************************************************
 * PrintPositions sends the line of text from the data file, the index table
 * was built from, whose postion in the file is specified by 'node->where'
 * to stdout.
 ****************************************************************************/
static void PrintPositions(sockfd,node)
	int		sockfd;
	ListType	*node;		/* The list we are printing. */
{	FILE		*fp;		/* Pointer to the file with the actual data. */
	char		buf[2048];	/* Buffer for the line of text. */

	long	n;
	if ((n = NumberOfListNodes(node)) > 1024)
		{
		char	s[1024];
		sprintf(s,"0%ld items found.  Please consolidate your request.\t\terror.host\t-1\r\n",n);
		SendString(s);
		sprintf(s,"TOO MANY ITEMS: %ld items found",n);
		LogMessage(sockfd,s);
		return;
		}

	if (fp = fopen(dataFileName,"r"))
		{
		while (node)
			{
			if (!fseek(fp,node->where,SEEK_SET))
				SendString(fgets(buf,2048,fp));
			node = node->next;
			}
		fclose(fp);
		}
	else
		fprintf(stderr,"error: PrintPositions could not open data file %s\n",dataFileName);

}	/* PrintPositions */

/*****************************************************************************
 * DoOperation returns a list which is the result of "l1 op l2" where 'l1' and
 * 'l2' are lists, and 'op' is the operation to perform which is either the
 * AND, OR, or NOT operation.
 ****************************************************************************/
ListType *DoOperation(op,l1,l2)
	short		op;		/* The operation [AND,OR,NOT]. */
	ListType	*l1,		/* A list we operate on. */
			*l2;		/* The other list we operate on. */
{	ListType	*result = NIL,	/* The result of "l1 op l2". */
			*t = NIL;	/* A pointer into 'l1' or 'l2'. */

	switch (op)
		{
		case AND:
			while (l1 && l2)
				if (l1->where == l2->where)
					{
					result = BuildList(result,l1->where);
					l1 = l1->next;
					l2 = l2->next;
					}
				else if (l1->where < l2->where)
					l1 = l1->next;
				else if (l1->where > l2->where)
					l2 = l2->next;
			break;
		case OR:
			while (l1 && l2)
				if (l1->where == l2->where)
					{
					result = BuildList(result,l1->where);
					l1 = l1->next;
					l2 = l2->next;
					}
				else if (l1->where < l2->where)
					{
					result = BuildList(result,l1->where);
					l1 = l1->next;
					}
				else if (l1->where > l2->where)
					{
					result = BuildList(result,l2->where);
					l2 = l2->next;
					}
			if (l1)
				t = l1;
			else if (l2)
				t = l2;
			while (t)
				{
				result = BuildList(result,t->where);
				t = t->next;
				}
			break;
		case NOT:
			while (l1 && l2)
				if (l1->where == l2->where)
					{
					l1 = l1->next;
					l2 = l2->next;
					}
				else if (l1->where < l2->where)
					{
					result = BuildList(result,l1->where);
					l1 = l1->next;
					}
				else if (l1->where > l2->where)
					l2 = l2->next;
			while (l1)
				{
				result = BuildList(result,l1->where);
				l1 = l1->next;
				}
			break;
		default:
			result = NIL;
			break;
		}

	return(result);

}	/* DoOperation */

/*****************************************************************************
 * LogRequest
 ****************************************************************************/
void LogRequest(sockfd)
	int		sockfd;		/* The socket to write to. */
{	char		buf[1024];
	short		i;

	buf[0] = '\0';
	strcpy(buf,"jughead-Search -> ");
	for (i = 0; i < numCommands; i++)
		{
		strcat(buf," ");
		strcat(buf,wrdsNcmds[i]);
		}
	LogMessage(sockfd,buf);

}	/* LogRequest */

/*****************************************************************************
 * PostPositions posts the result of doing the boolean operations on 'what2find'
 * and checking for membership in 'array'.
 ****************************************************************************/
void PostPositions(sockfd,what2find)
	int		sockfd;		/* The socket to write to. */
	char		*what2find;	/* String with words and operations. */
{	short		i,		/* A loop counter. */
			operation = 0,	/* Either [AND,OR,NOT] or none. */
			reserved,	/* Is the current word reserved? */
			thrashOld = 0;	/* Do we need to free up 'oldRslt'? */
	long		index;		/* Index into the items array. */
	TreeType	*node;		/* The node in 'array' with the word. */
	ListType	*positions,	/* List with the positions. */
			*list1  = NIL,	/* List of positions to operate against list2. */
			*list2  = NIL,	/* List of positions to operate against list1. */
			*oldRslt = NIL,	/* The old result of "list1 operation list2". */
			*result = NIL;	/* The result of "list1 operation list2'. */

	if (ParseSearchString(what2find))
		{
		LogRequest(sockfd);
		for (i = 0; i < numCommands; i++)
			if (reserved = ReservedWord(wrdsNcmds[i]))
				operation = reserved;
			else if ((index = BinarySearch(StrToLower(wrdsNcmds[i]),items,numElements)) >= 0)
				{
				if (!list1)
					list1 = items[index].positions;
				else if (!list2)
					{
					list2 = items[index].positions;
					if (oldRslt && oldRslt == result)
						thrashOld = 1;

					result = DoOperation(operation,list1,list2);

					if (thrashOld)
						{
						DestroyList(oldRslt);
						thrashOld = 0;
						}
					list1 = oldRslt = result;
					list2 = NIL;
					operation = 0;
					}
				}
			else
				{
				char	message[256];
				sprintf(message,"COULD NOT FIND [%s]",wrdsNcmds[i]);
				if (debug)
					fprintf(stdout,"%s\n",message);
				if (logFile)
					LogMessage(sockfd,message);
				}

		if (list1 && !list2 && !result)
			if (!operation || operation == OR)
				PrintPositions(sockfd,list1);
		if (result)
			{
			PrintPositions(sockfd,result);
			DestroyList(result);
			}
		}

}	/* PostPositions */

/*****************************************************************************
 * CreateElements returns true if we could create the dynamic array 'items'
 * and false othewise.
 ****************************************************************************/
short CreateElements(fileName)
	char	*fileName;	/* The name of the file to read. */
{	FILE	*fp;		/* Pointer to the file we are reading. */
	long	l,		/* A loop counter. */
		where;		/* The postions in the "data" file. */
	char	*str;		/* The word to put in the array. */
	short	strLen,		/* The size of the word. */
		i,		/* Another loop counter. */
		numPos;		/* How many positions for this word? */

	if (fp = fopen(fileName,"r"))
		{
		(void)GetStr(fp,dataFileName,512);
		numElements = (short)GetInt(fp);
		if (items = (Element *)malloc(numElements * sizeof(Element)))
			for (l = 0; l < numElements; l++)
				{
				strLen = (short)GetInt(fp);
				if (items[l].word = (char *)malloc(strLen * sizeof(char)))
					{
					(void)GetStr(fp,items[l].word,strLen);
					numPos = (short)GetInt(fp);
					items[l].positions = NIL;
					for (i = 0; i < numPos; i++)
						{
						where = GetLong(fp);
						items[l].positions = BuildList(items[l].positions,where);
						}
					}
				else
					{
					fprintf(stderr,"error: CreateElements could not get memory for string %ld\n",l);
					exit(-1);
					}
				}
		else
			fprintf(stderr,"error: CreateElements could not get memory for the items\n");
		fclose(fp);
		return(1);
		}
	else
		fprintf(stderr,"error: CreateElements could not open %s\n",fileName);
	return(0);

}	/* CreateElements */

/*****************************************************************************
 * CleanUp simply frees up any memory used in the dynamic array 'items'.
 ****************************************************************************/
static void CleanUp()
{	int	i;	/* A loop counter. */

	for (i = 0; i < numElements; i++)
		{
		free(items[i].word);
		DestroyList(items[i].positions);
		}
	free(items);
	numElements = 0;

}	/* CleanUp */

/*****************************************************************************
 * HangUpSignal resets the hangup interrupt, and returns to the saved state.
 ****************************************************************************/
int HangUpSignal()
{
	signal(SIGHUP,HangUpSignal);		/* Set things for next time. */

	if (logFile)
		LogMessage(-1,"SIGHUP signal encountered");

	if (debug)
		{
		fprintf(stderr,"\nSIGHUP signal encountered.\n");
		fprintf(stderr,"Releasing memory ...");
		}
	CleanUp();
	if (debug)
		fprintf(stderr,"\nRebuilding the binary tree.\n");

	longjmp(hupbuf,0);			/* Jump to the saved state. */

}	/* HangUpSignal */

/*****************************************************************************
 * DoSearch is the search server part of jughead.  This routine never
 * returns.
 ****************************************************************************/
void DoSearch(indexTable,logFile)
	char			*indexTable,	/* Name of the index table file. */
				*logFile;	/* The file to log to. */
{	int			childspid,	/* The process ID of the child process. */
				s,		/* The socket file descriptor. */
				newS,		/* The new socket file descriptor. */
				addressLen;	/* Size of the address space. */
	struct sockaddr_in	address;	/* Address of connecting entity. */

	fprintf(stderr,"jughead, Copyright 1993, University of Utah Computer Center\n");
	fprintf(stderr,"Using index table %s\n",indexTable);
	fprintf(stderr,"Using port %d\n",PORT2USE);

	if (logFile)
		{
		char	message[512];
		fprintf(stderr,"Logging to %s\n",logFile);
		strcpy(message,"STARTED UP ON ");
		strcat(message,indexTable);
		LogMessage(-1,message);
		}

	if ((s = ListenerEstablished(PORT2USE)) < 0)
		exit(-1);

	/* Set things up to handle the -HUP signal. */
	if (signal(SIGHUP,SIG_IGN) != SIG_IGN)
		signal(SIGHUP,HangUpSignal);
	setjmp(hupbuf);

	if (debug)
		system("date");

	if (!CreateElements(indexTable))
		{
		fprintf(stderr,"error: DoSearch could not create index tree.\n");
		exit(-1);
		}

	if (debug)
		{
		system("date");
		fprintf(stderr,"Ready for incoming connections.\n");
		}

	while (1)	/* Wait for and handle all connections. */
		{
		addressLen = sizeof(address);
		if ((newS = accept(s,(struct sockaddr *)&address,&addressLen)) < 0)
			{
			fprintf(stderr,"error: DoSearch could not accept\n");
			exit(-1);
			}
		if ((childspid = fork()) < 0)
			{
			fprintf(stderr,"error: DoSearch could not fork\n");
			exit(-1);
			}
		else if (!childspid)	/* Child process so */
			{		/* close original socket */
			close(s);
			ProcessRequest(newS);
			exit(0);
			}

		ChildProcess();		/* Wait for the childs process to die. */
		close(newS);		/* Close the new socket we opened. */
		}

}	/* DoSearch */
