/*
Name   : FLISTS.C
Date   : 19 March, 1990
Author : Kim Moser
System : Microsoft C 5.1 or Turbo C 2.0
Descrip: Generic linked list utilities (for linked lists stored in a file)
*/

#include <stdio.h>  /* size_t */
#include <stdlib.h>
#include <string.h>  /* memcpy() */

#include "flists.h"
#include "etlog.h"

#define LISTSIGNATURE ((unsigned int)0xAACC)
/* $10101010 $11001100 is a fairly unique signature to
   represent an initialized list */

#define ELMTSIGNATURE ((unsigned char)153)
/* $10011001 is a fairly unique signature to
   represent an initialized element */

#define index long

typedef struct elmt {
	index data;		/* Offset of data */
	int width;		/* Size of data */
	char dispose;		/* Whether we allocated it dynamically
				   and must dispose of it when
				   deallocating list */
	index next;		/* Pointer to next element in list */
	index prev;		/* Pointer to previous element in list */
	unsigned char signature;/* Whether this element has been
				   properly initialized */
};

typedef struct header {
	index first;		/* Pointer to first element */
	index last;		/* Pointer to last element */
	struct elmt recent;	/* Copy of most recently accessed element */
	int mostrecent;		/* Index (offset from 0) of most recently
				   accessed element */
	int len;		/* Number of elements in list */
	unsigned int signature;	/* SIGNATURE (hopefully) */
}

typedef struct alist {
	FILE *fp;		/* The associated file */
	struct header h;	/* Info that gets written to the file */
};

typedef struct alist *alistptr;
  /* Pointers to 'list' are cast into alistptrs (pointers to 'alist') */

static int thelen(struct list *p);
static int thelen(struct list *p)
{
	return ((alistptr)p)->len;
}

static int listinitialized(struct list *p);
static int listinitialized(struct list *p)
{
	return (((alistptr)p)->signature == LISTSIGNATURE);
}

static int elmtinitialized(struct elmt *q);
static int elmtinitialized(struct elmt *q)
{
	return (q->signature == ELMTSIGNATURE);
}

static struct elmt *readnext(alistptr p);
static struct elmt *readnext(alistptr p)
/* Reads the next elmt into p->recent */
{
	if (fseek(p->fp, p->h.next, SEEK_SET)) {
		writewarn("readnext(): fseek failed for position %ld\n", p->h.next);
		return NULL;
	}
	if ((fread( (void*) p->recent, sizeof(struct elmt), 1, p->fp )) != 1) {
		writewarn("readnext(): fread() failed.\n");
		return NULL;
	}
	p->mostrecent++;
	return (p->recent);
}

static struct elmt *readprev(alistptr p);
static struct elmt *readprev(alistptr p)
/* Reads the previous elmt into p->recent */
{
	if (fseek(p->fp, p->h.prev, SEEK_SET)) {
		writewarn("readprev(): fseek failed for position %ld\n", p->h.prev);
		return NULL;
	}
	if ((fread( (void*) p->recent, sizeof(struct elmt), 1, p->fp )) != 1) {
		writewarn("readprev(): fread() failed.\n");
		return NULL;
	}
	p->mostrecent--;
	return (p->recent);
}

static struct elmt *eptr(struct list *p, int n);
static struct elmt *eptr(struct list *p, int n)
/* Returns a pointer to the n'th elmt (offset from 0) in list 'p';
   assumes 'p' contains at least n+1 elements. */
{
	int i=0;
	struct elmt *q;
	int tmp;
	int mostrecent = ((alistptr)p)->mostrecent;
	int distance=n;
	int path=0;  /* Which "shortest path" we'll take to get to n'th elmt */
	/* 0: start from beginning and seek forward
	   1: start from most recent and seek backward
	   2: start from most recent and seek forward
	   3: start from end and seek backward */

	/* Find "shortest path" to n'th element, i.e. do we start from
	   beginning and traverse forward, start from end and traverse
	   backward, or start from most recently accessed element and
	   traverse forward or backward? */

	if (n <= mostrecent) {  /* Can we even consider path 1? */
		if ((tmp=(mostrecent-n)) < distance) {
			path = 1;
			distance = tmp;
		}
	} else {  /* Consider path 2 and 3 */
		if ((tmp=(n-mostrecent)) < distance) {
			path = 2;
			distance = tmp;
		}
		if ((tmp=(thelen(p)-1 - n)) < distance) {
			path = 3;
			distance = tmp;
		}
	}

	/* Now we know the shortest path to the n'th elmt, so let's do it: */

	switch (path) {
		case 0:  /* Start at first elmt and seek forward */
			q = ((alistptr)p)->first;  /* Start at first elmt */
			for (i=0; (i<n) && (q != NULL); i++) q = readnext((alistptr)p);
			break;
		case 1:  /* Start at most recent elmt and seek backward */
			q = ((alistptr)p)->recent;  /* Start at most recent elmt */
			for (i=mostrecent; (i>n) && (q != NULL); i--) q = readprev((alistptr)p);
			break;
		case 2:  /* Start at most recent elmt and seek forward */
			q = ((alistptr)p)->recent;  /* Start at most recent elmt */
			for (i=mostrecent; (i<n) && (q != NULL); i++) q = readnext((alistptr)p);
			break;
		case 3:  /* Start at end and seek backward */
			q = ((alistptr)p)->last;  /* Start at last elmt */
			for (i=thelen(p)-1; (i>n) && (q != NULL); i--) q = readprev((alistptr)p);
			break;
		default:
			/* This should never happen: */
			writewarn("lists.eptr(): invalid list seek path (%d) for %d'th elmt.\n", path, n);
			return NULL;
	}

	if (q == NULL) {
		writewarn("lists.eptr(): NULL found before %d'th elmt found (path=%d).\n", n, path);
		return NULL;
	}
	if (!elmtinitialized(q)) {
		writewarn("lists.eptr(): %d'th elmt is corrupt: signature (%u) != ELMTSIGNATURE (%u).\n",
			  n, (unsigned int) (q->signature), (unsigned int) ELMTSIGNATURE);
		return NULL;
	}
#if 0
	/* NOT NECESSARY BECAUSE readprev() AND readnext() DO THIS FOR US: */
	/* Memorize most recently accessed elmt (i.e. the one we just got): */
	((alistptr)p)->recent = q;
	((alistptr)p)->mostrecent = n;
#endif
	return q;
}

static int readheader(alistptr p);
static int readheader(alistptr p)
{
	if (fseek(p->fp, 0, SEEK_SET)) {
		readwarn("readheader(): fseek() failed for pos 0.\n");
		return 0;
	}
	if (fread((void*) p, sizeof(*p), p->fp) != 1) {
		readwarn("readheader(): fread() failed.\n");
		return 0;
	}
	return 1;
}

static int writeheader(alistptr p);
static int writeheader(alistptr p)
{
	if (fseek(p->fp, 0, SEEK_SET)) {
		writewarn("writeheader(): fseek() failed for pos 0.\n");
		return 0;
	}
	if (fwrite((void*) p, sizeof(*p), p->fp) != 1) {
		writewarn("writeheader(): fwrite() failed.\n");
		return 0;
	}
	return 1;
}

struct list *listnew(char *fname)
{
	alistptr p;
	int exists;

	if ((p=(alistptr) malloc(sizeof(struct alist))) == NULL) {
		writewarn("lists.listnew(): malloc(%u) returned NULL.\n", sizeof(struct alist));
	} else {
		p->first = p->last = (index) 0;
		p->mostrecent = 0;
		p->len = 0;
		p->signature = LISTSIGNATURE;
		exists = !access(fname, 0);
		if ((p->fp = fopen(fname, "r+b")) == NULL) {
			writewarn("listnew(): fopen() failed for file '%s'.\n", fname);
			return NULL;
		}
		if (exists) {
			readheader(p);  /* Read existing header */
		} else {
			writeheader(p);  /* Create the header */
		}
	}
	return (p);
}

int listclose(struct list *p)
{
	writeheader((alistptr)p);

	if (fclose(p->fp)) {
		writewarn("listclose(): fclose() failed.\n");
		return 0;
	}
	return 1;
}

struct list *listwipe(struct list **p, char *fname)
{
	if (*p != NULL) while (listlen(*p)) listdel(*p, 0);
	return (*p = listnew(fname));
}

int listlen(struct list *p)
{
	if (p == NULL) {
		writewarn("lists.listlen(): list is NULL.\n");
		return 0;
	}
	if (!listinitialized(p)) {
		writewarn("lists.listlen(): list is uninitialized.\n");
		return 0;
	}

	return (thelen(p));
}

static void insert(struct list *p, struct elmt *q, void *data, int spot);
static void insert(struct list *p, struct elmt *q, void *data, int spot)
/* Adds element 'q' to spot 'spot' (offset from 0) in alist 'p'
   (or to end of list if list contains fewer than spot+1 elments) */
{
	struct elmt *e;

	if (!thelen(p) || !spot) {
		/* Empty list, or spot==0, so this becomes the first
		   (0'th) element: */
		q->h.next = ((alistptr)p)->first;  /* Might be 0, but that's fine */
		q->h.prev = 0;  /* There is no previous element: this is the first one! */

		if (thelen(p)) {
			q->h.next->h.prev = q;
		} else {
			((alistptr)p)->h.last = q;
		}
		((alistptr)p)->h.first = ((alistptr)p)->h.recent = q;
		((alistptr)p)->h.mostrecent = 0;
	} else {
		/* list has at least 1 elmt already, and spot > 0: */
		if (spot >= thelen(p)) {
			/* Add to end of list */
			if ((e = eptr(p, thelen(p)-1)) == NULL) {
				writewarn("lists.insert(): eptr() returned NULL (spot=%d, listlen=%d)\n", spot, thelen(p));
				return;
			}
			e->h.next = q;
			q->h.prev = e;
			q->h.next = NULL;
			((alistptr)p)->last = ((alistptr)p)->recent = q;
			((alistptr)p)->mostrecent = thelen(p);
		} else {
			if ((e = eptr(p, spot)) == NULL) {
				/* This should never happen */
				writewarn("lists.insert(): eptr() returned NULL (spot=%d, listlen=%d)\n", spot, thelen(p));
				return;  /* To avoid further corruption */
			}
			q->h.next = e;
			q->h.prev = e->h.prev;
			e->h.prev->h.next = q;
			e->h.prev = q;

			((alistptr)p)->recent = q;
			((alistptr)p)->mostrecent = spot;
		}
	}
	((alistptr)p)->len++;
}

void *listinsert(struct list *p, void *data, int width, int spot)
{
	struct elmt *q;

	if (p == NULL) {
		writewarn("lists.listinsert(): attempt to insert element into NULL list.\n");
		return NULL;
	}

	if (!listinitialized(p)) {
		writewarn("lists.listinsert(): attempt to insert element into uninitialized list.\n");
		return NULL;
	}

	if (spot < 0) {
		writewarn("lists.listinsert(): attempt to insert element into spot (%d) that is < 0.\n", spot);
		return NULL;
	}

	if ((q = newelmt()) == NULL) {
		writewarn("lists.listinsert(): newelmt() returned NULL.\n");
	} else {
		q->dispose = 1;
		q->width = width;
		if ((q->data = malloc(width)) == NULL) {
			writewarn("listinsert(): malloc(%d) returned NULL.\n", width);
		} else {
			memcpy(q->data, data, (size_t)width);
			insert(p, q, spot);
		}
	}

	return (q==NULL ? q : q->data);
}

void *listelmt(struct list *p, int spot, void *dest)
{
	if (p == NULL) {
		writewarn("lists.listelmt(): attempt to get %d'th element of a NULL list.\n", spot);
		return NULL;
	}

	if (!listinitialized(p)) {
		writewarn("lists.listelmt(): attempt to get %d'th element of uninitialized list.\n", spot);
		return NULL;
	}

	if (spot < 0) {
		writewarn("lists.listelmt(): attempt to get element from spot (%d) that is < 0.\n", spot);
		return NULL;
	}

	if (spot >= thelen(p)) {
		writewarn("lists.listelmt(): attempt to get %d'th element from list with only %d elements.\n", spot, thelen(p));
		return NULL;
	}

	if (eptr(p, spot, dest) == NULL);
	  /* Should return NULL only if list is corrupt (or, God forbid,
	     the eptr() function has a bug), but you never know */
		writewarn("listelmt(): eptr() returned NULL.\n");
		return NULL;
	}
	return (dest);
}

int elmtwidth(struct list *p, int spot)
{
	struct elmt *q;

	if (p == NULL) {
		writewarn("lists.elmtwidth(): attempt to get %d'th element of a NULL list.\n", spot);
		return 0;
	}

	if (!listinitialized(p)) {
		writewarn("lists.elmtwidth(): attempt to get %d'th element of uninitialized list.\n", spot);
		return 0;
	}

	if (spot < 0) {
		writewarn("lists.elmtwidth(): attempt to get element from spot (%d) that is < 0.\n", spot);
		return 0;
	}

	if (spot >= thelen(p)) {
		writewarn("lists.elmtwidth(): attempt to get %d'th element from list with only %d elements.\n", spot, thelen(p));
		return 0;
	}

	q = eptr(p, spot);
	  /* Should return NULL only if list is corrupt (or, God forbid,
	     the eptr() function has a bug), but you never know */
	return (q==NULL ? 0 : q->width);
}

void listdel(struct list *p, int spot)
{
	struct elmt *q;

	if (p == NULL) {
		writewarn("lists.listdel(): attempt to delete %d'th element of a NULL list.\n", spot);
		return;
	}

	if (!listinitialized(p)) {
		writewarn("lists.listdel(): attempt to delete %d'th element of uninitialized list.\n", spot);
		return;
	}

	if (spot < 0) {
		writewarn("lists.listdel(): attemp to delete element from spot (%d) that is < 0.\n", spot);
		return;
	}

	if (spot >= thelen(p)) {
		writewarn("lists.listdel(): attempt to delete %d'th element from list with only %d elements.\n", spot, thelen(p));
		return;
	}

	if ((q = eptr(p, spot)) == NULL) {
		writewarn("lists.listdel(): eptr() returned NULL.\n");
		return;
	}
	if (thelen(p) == 1) {  /* List len == 1 */
		/* We must be removing the 0'th elmt: */
		((alistptr)p)->first = ((alistptr)p)->last = ((alistptr)p)->recent = NULL;
		((alistptr)p)->mostrecent = -1;
	} else {  /* List len >= 2 */
		if (!spot) {
			/* We're removing the 0'th elmt */
			((alistptr)p)->first = ((alistptr)p)->recent = q->h.next;
			q->h.next->h.prev = NULL;
		} else {
			if (spot == thelen(p)-1) {  /* Last elmt */
				((alistptr)p)->last = ((alistptr)p)->recent = q->h.prev;
				((alistptr)p)->mostrecent--;
				q->h.prev->h.next = NULL;
			} else {
				((alistptr)p)->recent = q->h.next;
				q->h.prev->h.next = q->h.next;
				q->h.next->h.prev = q->h.prev;
			}
		}
	}

#ifdef NOT_DEFINED
	if (!spot || thelen(p)==1) {
		/* No choice; must delete 0'th elmt */
		q = ((alistptr)p)->first;
		((alistptr)p)->first = q->h.next;
		/* 'q' gets disposed of after this clause */
	} else {
		/* thelen(p) >= 2, and spot >= 1,
		   so delete 1'th (or greater) elmt: */
		if ((prev=eptr(p, spot-1)) == NULL) {
			/* This should never happen */
			writewarn("lists.listdel(): eptr() returned NULL (spot=%d, listlen=%d)\n", spot, thelen(p));
			return;  /* To avoid further corruption */
		} else {
			q = prev->h.next;  /* q points to the elemt to be deleted */
			prev->h.next = q->h.next;  /* Unlink q's elmt */
			/* 'q' gets disposed of after this clause */
		}
	}
#endif

	if (q->dispose) {
		/* A list function allocated it, so we've got to dispose of it */
		free(q->data);
	}
	q->signature = 0;
	free(q);
	((alistptr)p)->len--;
}

void *listdispose(struct list *p)
{
	if (p == NULL) {
		writewarn("lists.listdispose(): attempt to dispose NULL list.\n");
		return NULL;
	}

	if (!listinitialized(p)) {
		writewarn("lists.listdispose(): attempt to dispose uninitialized list.\n");
		return NULL;
	}

	while (thelen(p)) listdel(p, 0);

	if (((alistptr)p)->first != NULL) {
		writewarn("lists.listdispose(): listlen(p)==0 but p->data != NULL.\n");
		return NULL;
	}
	((alistptr)p)->signature = 0;
	free(p);
	return NULL;
}