/* list.c
   routines to manage the data structures for gopher items and
   gopher directories. */


     /*---------------------------------------------------------------*/
     /* Xgopher        version 1.1     20 April 1991                  */
     /*                version 1.0     04 March 1991                  */
     /* X window system client for the University of Minnesota        */
     /*                                Internet Gopher System.        */
     /* Allan Tuchman, University of Illinois at Urbana-Champaign     */
     /*                Computing Services Office                      */
     /* Copyright 1992 by                                             */
     /*           the Board of Trustees of the University of Illinois */
     /* Permission is granted to freely copy and redistribute this    */
     /* software with the copyright notice intact.                    */
     /*---------------------------------------------------------------*/


#include <stdio.h>

#include "gopher.h"
#include "listP.h"
#include "list.h"

static	gopherItemList	unusedItems = {NULL, NULL};

static	gopherDirP      currentDir = NULL;	/* current directory pointer */

static	int	firstItemAlloc = TRUE;


/* List management routines:
	newItem()			return ptr to a gopherItem structure
	copyItem(gopherItemP)		return a copy of given item
	initItemList(gopherItemListP)	set list pointers to indicate empty
	freeItem(gopherItemP)		return item to the free list
	freeItems(gopherItemP)		return items to the free list (internal)
	freeItemList(gopherItemP)	return list of items to the free list
	emptyItemList(gopherItemListP)	return T/F to indicate if list is empty
	itemListLength(gopherItemListP)	return the length of an item list
	appendItem(gopherItemListP, gopherItemP) add item to the end of a list
	removeItemN(gopherItemListP, n) delete Nth item from a list
	getCurrentItemN(n)		 return ptr to Nth item in current dir
	pushItem(gopherItemListP, gopherItemP) add item to beginning of a list
	popItem(gopherItemListP)	delete the first item of a list
	allocGopherItem(n)		allocate N new items (internally used)
	freeListLength()		return number of unused items

   since C does not support generic types, these routines are duplicated
   for directories.  Each "item" routine above has a corresponding
   "dir" routine.
*/


/* newItem 
	Allocate a gopher item from the free list */

gopherItemP
newItem()
{
	gopherItemP	gi;

	if (unusedItems.first == NULL) {

		/* out of gopher items.  First reclaim those that
		   are out of date, then allocate more if necessary */

		gopherDirP	d=currentDir;
			/* find root of tree */
		if (d != NULL) while (d->parent != NULL) d = d->parent;
		checkTree(d);
		if (unusedItems.first == NULL  ||
					freeListLength() < itemIncrement) {
			allocGopherItem(firstItemAlloc ?
					itemStart : itemIncrement);
			firstItemAlloc = FALSE;
		}
	}
	gi = unusedItems.first;
	unusedItems.first = gi->next;
	if (unusedItems.first == NULL) unusedItems.last = NULL;

	gi->next = NULL;

	return gi;
}


/* copyItem 
	return a copy of a gopher item */

gopherItemP
copyItem(old_gi)
gopherItemP	old_gi;
{
	gopherItemP	gi;

	gi = newItem();
	gi->type = old_gi->type;
	strncpy(USER_STRING(gi), USER_STRING(old_gi), USER_STRING_LEN);
	vStringSet(&(gi->selector), vStringValue(&(old_gi->selector)));
	strncpy(gi->host, old_gi->host, HOST_STRING_LEN);
	gi->port = old_gi->port;
	gi->next = NULL;

	return gi;
}


/* initItemList 
	Set the list pointers to indicate that the list is empty */

void
initItemList(list)
gopherItemListP	list;
{
	list->first = list->last = NULL;

	return;
}


/* freeItem 
	Return a gopher item to the free list */

void
freeItem(gi)
gopherItemP	gi;
{
	if (gi != NULL)
		pushItem(&unusedItems, gi);

	return;
}


/* freeItems
	Return a linked list of gopher items to the free list */

static void
freeItems(gi)
gopherItemP	gi;
{
	gopherItemP	p;

	if (gi == NULL) return;

	/* set p to point to the end of the items */

	for (p=gi; p->next != NULL; p=p->next) ;

	if (unusedItems.last == NULL) unusedItems.last = p;
	p->next = unusedItems.first;
	unusedItems.first = gi;

	return;
}


/* freeItemList
	Return a list of gopher items to the free list and clear the
	list header */

void
freeItemList(list)
gopherItemListP	list;
{
	gopherItemP	p;

	if (list != NULL) {
		freeItems(list->first);
		list->first = list->last = NULL;
	}

	return;
}


/* emptyItemList
	tell whether an item list is empty, True or False */

BOOLEAN
emptyItemList(list)
gopherItemListP	list;
{
	if (list->first == NULL) return TRUE;
			    else return FALSE;
}


/* itemListLength
	return the number of items in an item list */

int
itemListLength(list)
gopherItemListP	list;
{
	int	n;
	gopherItemP	p;

	if (list == NULL) return 0;

	for (n=0, p=list->first; p != NULL; n++, p=p->next) ;

	return n;
}


/* appendItem 
	append an item to the end of an item list */

void
appendItem(list, gi)
gopherItemListP	list;
gopherItemP	gi;
{
	if (list->last == NULL) {
		list->first = list->last = gi;
	} else {
		gi->next = NULL;
		list->last->next = gi;
		list->last = gi;
	}

	return;
}


/* removeItemN 
	delete the Nth item from a list.  The first item is numbered 0 */

void
removeItemN(list, n)
gopherItemListP	list;
int		n;
{
	gopherItemP	p, prev;

	if (list == NULL) return;
	if ((p = list->first) == NULL) return;

	if (n == 0) {
		list->first = p->next;
		if (list->last == p) list->last = NULL;
		pushItem(&unusedItems, p);
	} else {
		for (prev=p, p=p->next; p!= NULL; prev=p, p=p->next) {
			if (--n == 0) {
				prev->next = p->next;
				if (p == list->last) list->last = prev;
				pushItem(&unusedItems, p);
				break;
			}
		}
	}

	return;
}


/* getCurrentItemN 
	return a pointer to the Nth item of the current directory
	starting with number 0 */

gopherItemP
getCurrentItemN(n)
int		n;
{
	gopherItemP	p, prev;

	if (n < 0) return NULL;  

	for (p = currentDir->contents.first; p != NULL; p=p->next) {
		if (n-- == 0) break;
	}

	return p;
}


/* pushItem 
	push an item onto the front of a list */

void
pushItem(list, gi)
gopherItemListP	list;
gopherItemP	gi;
{
	gi->next = list->first;
	list->first = gi;
	if (list->last == NULL) list->last = gi;

	return;
}


/* popItem 
	delete the first item of a list */

void
popItem(list)
gopherItemListP	list;
{
	gopherItemP	p;

	p = list->first;
	if (list->first != NULL) {
		list->first = list->first->next;
		freeItem(p);
	}
	if (list->first == NULL)
		list->last = NULL;

	return;
}


/* allocGopherItem
	Allocate n new gopher items, adding them to the free list */

static void
allocGopherItem(n)
int	n;
{
	gopherItemP	gil, p;
	int		i;

	if (n <= 0) return;

	if ((gil = (gopherItemP) malloc(n * sizeof(gopherItem))) == NULL) {
		/* out of memory */
		fprintf (stderr, "There is not enough memory to continue.\n");
		exit(3);
	}

	for (i=0, p=gil; i<n-1; i++, p++) {
		p->selector.len = 0;
		p->selector.data = NULL;
		p->next = p+1;
	}
	p->selector.len = 0;
	p->selector.data = NULL;
	p->next = NULL;
	freeItems(gil);

	return;
}


/* freeItemListLength
	Find length of the free item list */

static int
freeListLength()
{
	gopherItemP	p;
	int		n;

	for (n=0, p=unusedItems.first; p != NULL; n++, p=p->next)  ;

	return n;
}


#ifdef DEBUG


/* printItemList
   Print a list of gopher items for checking the list contents */

void
printItemList(list, label)
gopherItemListP list;
char            *label;
{
        gopherItemP     gi;

        if (list == NULL) fprintf(stdout, "NULL list %s\n", label);
        else {
                gi = list->first;
                fprintf (stdout, "list %s:\n", label);
                while (gi != NULL) {
                        fprintf (stdout, "\t(%s)\n", USER_STRING(gi));
                        gi = gi->next;
                }
                fprintf (stdout, "    end of list\n");
        }
}
#endif

/* ----------------------------------------------------------------------*/

#include "globals.h"

static	gopherDirList	unusedDirs = {NULL, NULL};
static	gopherDirList	bookmarks = {NULL, NULL};
static	int		firstDirAlloc  = TRUE;


/* Directory tree management routines:
	* newDir()			return ptr to a gopherDir structure
	* freeDir(gopherDirP)		return dir to the free list
	* markDir()			set bookmark at current dir and parents
	* getMarkN()			get pointer to directory of bookmark N
	* getCurrentDirectory()		return pointer to the current directry
	* getCurrentDirIndex()		return index search string of cur dir
	* getParentDirectory()		return pointer to parent of current dir
	* unmarkDir(gopherDirP)		remove bookmark at dir
	* unmarkDirN(gopherDirP)	remove bookmark at Nth directory
	* unmarkAllDirs()		remove every bookmark
	* markListLength()		return the number of bookmarks 
	* pushDir(gopherDirP)		add child dir to current position
	* popDir()			delete current, switch to parent
	* goToDir(gopherDirP)		warp to directory
	* anyMarks()			bookean to determine if mark list empty

	-- internal routines --

	freeDirPath(gopherDirP)		ensure childList empty; free up lists;
					freeDir(dir); freeDirPath(parent);
	* setActiveDirPath(gopherDirP)	sets active flag for path to this dir
	* clearActiveDirPath(gopherDirP) clear active flag for path to this dir
	* appendDir(gopherDirListP, gopherDirP) append directory to a list
	* removeDir(gopherDirListP, gopherDirP) remove directory from a list
	* removeDirN(gopherDirListP, n) remove directory N from a list
	* dirInList(gopherDirListP, gopherDirP) see if directory is in a list
	* freeDirs(gopherDirP)		return  list of dirs to free
	* freeDirContents(gopherDirP)	free up the gopher items of a directory
	* allocGopherDir(n)		allocate N new dirs
*/


/* newDir 
	Allocate a gopher item from the free list */

gopherDirP
newDir()
{
	gopherDirP	dir;

	if (unusedDirs.first == NULL) {
		/* out of gopher directories, so allocate more */
		allocGopherDir(firstDirAlloc ? dirStart : dirIncrement);
		firstDirAlloc = FALSE;
	}
	dir = unusedDirs.first;
	unusedDirs.first = dir->next;
	if (unusedDirs.first == NULL) unusedDirs.last = NULL;

	dir->child = dir->sibling = dir->parent = dir->next = NULL;
	dir->selectorItem = NULL;
	dir->indexSearchString = NULL;
	dir->markCount = 0;
	dir->created = NOT_LOADED;
	initItemList(&(dir->contents));

	return dir;
}


/* freeDir 
	Return a gopher directory to the free list */

void
freeDir(dir)
gopherDirP	dir;
{
	freeDirContents(dir);

	dir->next = unusedDirs.first;
	unusedDirs.first = dir;
	if (unusedDirs.last == NULL) unusedDirs.last = dir;

	return;
}


/* anyMarks
	Report if the bookmark list is empty as T/F */

BOOLEAN
anyMarks()
{
	if (bookmarks.first == NULL) return FALSE;
				else return TRUE;
}


/* firstMark
	Return a pointer to the head of the bookmark list */

gopherDirP
firstMark()
{
	return bookmarks.first;
}


/* markDir
	Set a bookmark at a directory, marking its parents also */

void
markDir()
{
	gopherDirP	dir=currentDir;

	if (dir == NULL) return;
	if (dirInList(&bookmarks, dir)) return;

	appendDir(&bookmarks, dir);

	do {
		dir->markCount++;
		dir = dir->parent;
	} while (dir != NULL);
}


/* getMarkN 
	return a pointer to the Nth directory of the bookmark list
	starting with number 0 */

gopherDirP
getMarkN(n)
int		n;
{
	gopherDirP	d, prev;

	if (bookmarks.first == NULL  ||   n < 0) return NULL;  

	for (d = bookmarks.first; d != NULL; d=d->next) {
		if (n-- == 0) break;
	}

	return d;
}


/* getCurrentDirectory 
	return a pointer to the current directory */

gopherDirP
getCurrentDirectory()
{
	return currentDir;
}


/* getCurrentDirIndex 
	return a pointer to the index search string of the current directory */

char *
getCurrentDirIndex()
{
	return currentDir->indexSearchString;
}


/* getParentDirectory 
	return a pointer to the parent of the current directory */

gopherDirP
getParentDirectory()
{
	if (currentDir == NULL) return NULL;
	return currentDir->parent;
}


/* atRoot 
	return TRUE is current directory is root, FALSE otherwise */

BOOLEAN
atRoot()
{
	return ((currentDir == NULL) || (currentDir->parent == NULL));
}


/* unmarkDir
	Remove a bookmark at a directory, unmarking its parents also.
	free any subtrees that are no longer marked */

void
unmarkDir(dir)
gopherDirP	dir;
{
	gopherDirP	p;

	if (dir == NULL) return;
	if (dir->markCount == 0) return;

	removeDir(&bookmarks, dir);

	p = dir;
	do {
		p->markCount--;
		p = p->parent;
	} while (p != NULL);

	freeDirPath(dir);
}


/* unmarkDirN
	Remove a bookmark at the Nth directory, unmarking its parents also.
	free any subtrees that are no longer marked */

void
unmarkDirN(n)
int	n;
{
	gopherDirP	dir, p;

	if (n < 0) return;

	p = dir = removeDirN(&bookmarks, n);

	if (p != NULL) {
		do {
			p->markCount--;
			p = p->parent;
		} while (p != NULL);

		freeDirPath(dir);
	}
}


/* unmarkAllDirs
	Remove all bookmarks */

void
unmarkAllDirs()
{
	gopherDirP	p;

	while ((p = bookmarks.first) != NULL) {
		unmarkDir(p);
	}
}


/* markListLength
	return the number of items in the bookmark list */

int
markListLength()
{
	int	n;
	gopherDirP	d;

	for (n=0, d=bookmarks.first; d != NULL; n++, d=d->next) ;

	return n;
}


/* pushDir
	Add a new child directory to the current, and make child current */

void
pushDir(dir)
gopherDirP	dir;
{
	/* if no children, set it.  if children, add to list */

	if (currentDir == NULL) {
		dir->sibling = NULL;
		dir->parent = NULL;
	} else if (currentDir->child == NULL) {
		dir->sibling = NULL;
		currentDir->child = dir;
		dir->parent = currentDir;
	} else {
		dir->sibling = currentDir->child;
		currentDir->child = dir;
		dir->parent = currentDir;
	}

	dir->child = NULL;
	dir->markCount = 0;
	dir->active = TRUE;
	currentDir = dir;

	return;
}


/* popDir
	Delete current directory (if unmarked) and change to parent */

void
popDir()
{
	gopherDirP	ancestor;

	if (currentDir == NULL  ||  currentDir->parent == NULL) return;
	ancestor = currentDir->parent;

	/* if unmarked, reclaim contents and directory then return to parent */
	/* if it is marked, just go up to parent */

	currentDir->active = FALSE;
	if (currentDir->markCount == 0) {
		freeDir(currentDir);
	}

	currentDir = ancestor;

	return;
}


/* goToDir
	Warp over to directory dir, cleaning up the current stack */

void
goToDir(dir)
gopherDirP	dir;
{
	gopherDirP	p;

	/* ensure that there is a record of the target directory */

	if (! dirInList(&bookmarks, dir)) return;

	clearActiveDirPath(currentDir);

	/* ***** */
	freeDirPath(currentDir);

	setActiveDirPath(dir);
	currentDir = dir;
}


/* appendDir
	append a directory to a directory list */

void
appendDir(list, dir)
gopherDirListP	list;
gopherDirP	dir;
{
	if (list->last == NULL) {
		list->first = list->last = dir;
	} else {
		dir->next = NULL;
		list->last->next = dir;
		list->last = dir;
	}

	return;
}


/* removeDir
	remove a directory from a directory list */

void
removeDir(list, dir)
gopherDirListP	list;
gopherDirP	dir;
{
        gopherDirP     p, prev;

        if (list == NULL) return;
        if ((p = list->first) == NULL) return;

        if (p == dir) {
                list->first = p->next;
                if (list->last == p) list->last = NULL;
		p->next = NULL;
        } else {
                for (prev=p, p=p->next; p!= NULL; prev=p, p=p->next) {
                        if (p == dir) {
                                prev->next = p->next;
                                if (p == list->last) list->last = prev;
				p->next = NULL;
                                break;
                        }
                }
        }

        return;
}


/* removeDirN
	remove the Nth directory from a directory list */

gopherDirP
removeDirN(list, n)
gopherDirListP	list;
int		n;
{
        gopherDirP     p, prev;

        if (list == NULL) return NULL;
        if ((p = list->first) == NULL) return NULL;

        if (n == 0) {
                list->first = p->next;
                if (list->last == p) list->last = NULL;
		p->next = NULL;
        } else {
                for (prev=p, p=p->next; p!= NULL; prev=p, p=p->next) {
                        if (--n == 0) {
                                prev->next = p->next;
                                if (p == list->last) list->last = prev;
				p->next = NULL;
                                break;
                        }
                }
        }

        return p;
}


/* dirInList
	see if directory is in a directory list */

BOOLEAN
dirInList(list, dir)
gopherDirListP	list;
gopherDirP	dir;
{
	gopherDirP	p;

	if (list == NULL  ||  dir == NULL) return FALSE;

	for (p = list->first; (p != dir  &&  p != NULL); p=p->next) ;
	
	return (p != NULL);
}


/* freeDirPath
	Free the current directory and its ancestors up the tree as possible */

void
freeDirPath(dir)
gopherDirP	dir;
{
	gopherDirP	ancestor;

	/* used when warping from an active directory to a bookmark
	   or when a bookmark is deleted. */
	

	while (dir != NULL) {

		/* do not free this directory or it ancestors if it is
		   in the active path or if it is needed for at least
		   one bookmark. */

		if (dir->active) break;
		if (dir->markCount > 0) break;

		/* this should never occur, but just in case... */
		if (dir->child != NULL) break;

		ancestor = dir->parent;
		freeDir(dir);
		dir = ancestor;
	}

	return;
}


/* setActiveDirPath
	set the active flag for the path from a directory back to the root */

static void
setActiveDirPath(dir)
gopherDirP	dir;
{
	if (dir == NULL) return;

	do {
		dir->active = TRUE;
		dir = dir->parent;
	} while (dir != NULL);
}


/* clearActiveDirPath
	clear the active flag for the path from a directory back to the root */

static void
clearActiveDirPath(dir)
gopherDirP	dir;
{
	if (dir == NULL) return;

	do {
		dir->active = FALSE;
		dir = dir->parent;
	} while (dir != NULL);
}


/* freeDirs
	Free a list of directories */

static void
freeDirs(dir)
gopherDirP	dir;
{
	gopherDirP	p;

	for (p=dir; p->next != NULL; p=p->next) ;

	if (unusedDirs.last == NULL) unusedDirs.last = p;
	p->next = unusedDirs.first;
	unusedDirs.first = dir;

	return;
}


/* freeDirContents
	Recover gopher items from a directory that is being freed.
	By now, assume that the children have been freed, the directory
	is not marked, and is really unencumbered. */

static void
freeDirContents(dir)
gopherDirP	dir;
{
	gopherDirP	ancestor, c, prev;

	if (dir == NULL) return;

	/* free selector item and directory contents item list */

	freeItem(dir->selectorItem);
	freeItemList(&(dir->contents));

	if (dir->indexSearchString != NULL) free(dir->indexSearchString);

	/* remove directory from a sibling list */

	if ((ancestor = dir->parent) != NULL) {
		c = ancestor->child;
		if (c == dir) {
			ancestor->child = dir->sibling;
		} else {
			while (c != NULL) {
				prev=c;
				c=c->sibling;
				if (c == dir) {
					prev->sibling = c->sibling;
					break;
				}
			}
		}
	}
	return;
}


/* allocGopherDir
	Allocate n new gopher directories, adding them to the free list */

static void
allocGopherDir(n)
int	n;
{
	gopherDirP	dirList, p;
	int		i;

	if (n <= 0) return;

	if ((dirList = (gopherDirP) malloc(n * sizeof(gopherDir))) == NULL) {
		/* out of memory */
		fprintf (stderr, "There is not enough memory to continue.\n");
		exit(3);
	}

	for (i=0, p=dirList; i<n-1; i++, p++) {
		p->next = p+1;
	}
	p->next = NULL;
	freeDirs(dirList);

	return;
}


/* checkTree
	traverse directory tree freeing expired gopher items */

static void
checkTree(d)
gopherDirP	d;
{
	if (d == NULL) return;
	if (d->created != NOT_LOADED) clearDirWhenOld(d);
	if (d->sibling != NULL) checkTree(d->sibling);
	if (d->child != NULL) checkTree(d->child);
	return;
}


#ifdef DEBUG


/* printDirTree
   Print a directory tree rooted at dir */

static level=0;

void
printDirTree(dir, label)
gopherDirP	 dir;
char            *label;
{
	char		string[256];
	int		kidNumber;
	gopherDirP	c;

	if (level==0)fprintf (stdout, "===== print directory tree =====\n");
	level++;
	sprintf (string, "%s - Root", label);
        if (dir == NULL) fprintf(stdout, "NULL directory tree %s\n", label);
        else {
		printDir(dir, string);
		kidNumber=0;
		for (c = dir->child; c != NULL; c = c->sibling) {
			sprintf (string, " Level %d, child %d",
					level, kidNumber);
			printDirTree(c, string);
			kidNumber++;
		}
        }
	level--;
	if (level==0)fprintf (stdout, "===== end of directory tree =====\n");
	return;
}


/* printBookmarks
   Print the bookmark list */

void
printBookmarks()
{
	gopherDirP	 dir;

	dir = bookmarks.first;
	fprintf (stdout, "----- Bookmark List -----\n");
	while(dir!=NULL) {
		printDir(dir, "bookmark");
		dir = dir->next;
	}
	fprintf (stdout, "----- End of Bookmark List -----\n");
}


#define NAMEOF(x) USER_STRING(x->selectorItem)
/* printDir
   Print a single gopher directory for checking the list contents */

void
printDir(dir, label)
gopherDirP	 dir;
char            *label;
{
        gopherItemP     gi;

        if (dir == NULL) fprintf(stdout, "NULL directory %s\n", label);
        else {
		/*
                fprintf (stdout, "directory %s (%#o):\n", label, dir);
		*/
                fprintf (stdout, "directory %s (%s):\n", label, NAMEOF(dir));

		if (dir->parent == NULL) fprintf (stdout, "\tnull parent\n");
		/*
		else fprintf (stdout, "\tparent:%#o\n", dir->parent);
		*/
		else fprintf (stdout, "\tparent:%s\n", NAMEOF(dir->parent));

		if (dir->sibling == NULL) fprintf (stdout, "\tnull sibling\n");
		/*
		else fprintf (stdout, "\tsibling:%#o\n", dir->sibling);
		*/
		else fprintf (stdout, "\tsibling:%s\n", NAMEOF(dir->sibling));

		if (dir->child == NULL) fprintf (stdout, "\tnull child\n");
		/*
		else fprintf (stdout, "\tchild:%#o\n", dir->child);
		*/
		else fprintf (stdout, "\tchild:%s\n", NAMEOF(dir->child));

		fprintf (stdout, "\tbookmarks:%d\n", dir->markCount);
		fprintf (stdout, "\tstatus:%s\n",
					dir->active ? "active" : " not active");
		if (dir->selectorItem == NULL)
			fprintf (stdout, "\tno selector item!\n");
		else fprintf (stdout, "\tselector item:%s\n",
					USER_STRING(dir->selectorItem));
		if (dir->contents.first == NULL)
			fprintf (stdout, "\tno saved contents\n");
		else printItemList(&(dir->contents), "");
        }
}
#endif
