/*
Name   : LISTS.C
Date   : 19 March, 1990
Author : Kim Moser
System : Microsoft C 5.1 or Turbo C 2.0
Descrip: Generic linked list utilities
*/

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

#include "lists.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 */

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

typedef struct alist {
	struct elmt *first;	/* Pointer to first element */
	struct elmt *last;	/* Pointer to last element */
	struct elmt *recent;	/* Pointer to 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 *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 *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 = q->next;
			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 = q->prev;
			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 = q->next;
			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 = q->prev;
			break;
		default:
#ifndef NDEBUG
			writewarn("lists.eptr(): invalid list seek path (%d) for %d'th elmt.\n", path, n);
#endif
			return NULL;
	}

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

	return q;
}

static struct elmt *newelmt(void);
static struct elmt *newelmt(void)
/* Returns a pointer to a newly allocated elmt, or NULL if unable
   to allocate memory for it. */
{
	struct elmt *q;

	if ((q=malloc(sizeof(struct elmt))) == NULL) {
#ifndef NDEBUG
		writewarn("lists.newelmt(): malloc(%u) returned NULL.\n", sizeof(struct elmt));
#endif
	} else {
		q->signature = ELMTSIGNATURE;
	}
	return q;
}

struct list *listnew(void)
{
	alistptr p;

	if ((p=malloc(sizeof(struct alist))) == NULL) {
#ifndef NDEBUG
		writewarn("lists.listnew(): malloc(%u) returned NULL.\n", sizeof(struct alist));
#endif
	} else {
		p->first = p->last = p->recent = NULL;
		p->mostrecent = -1;
		p->len = 0;
		p->signature = LISTSIGNATURE;
	}
	return (struct list *)p;
}

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

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

	return (thelen(p));
}

static void insert(struct list *p, struct elmt *q, int spot);
static void insert(struct list *p, struct elmt *q, 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->next = ((alistptr)p)->first;  /* Might be NULL, but that's fine */
		q->prev = NULL;  /* There is no previous element: this is the first one! */

		if (thelen(p)) {
			q->next->prev = q;
		} else {
			((alistptr)p)->last = q;
		}
		((alistptr)p)->first = ((alistptr)p)->recent = q;
		((alistptr)p)->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) {
#ifndef NDEBUG
				writewarn("lists.insert(): eptr() returned NULL (spot=%d, listlen=%d)\n", spot, thelen(p));
#endif
				return;
			}
			e->next = q;
			q->prev = e;
			q->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 */
#ifndef NDEBUG
				writewarn("lists.insert(): eptr() returned NULL (spot=%d, listlen=%d)\n", spot, thelen(p));
#endif
				return;  /* To avoid further corruption */
			}
			q->next = e;
			q->prev = e->prev;
			e->prev->next = q;
			e->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) {
#ifndef NDEBUG
		writewarn("lists.listinsert(): attempt to insert element into NULL list.\n");
#endif
		return NULL;
	}

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

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

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

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

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

	if (p == NULL) {
#ifndef NDEBUG
		writewarn("lists.listabsorb(): attempt to absorb element into NULL list.\n");
#endif
		return NULL;
	}

	if (!listinitialized(p)) {
#ifndef NDEBUG
		writewarn("lists.listabsorb(): attempt to absorb element into uninitialized list.\n");
#endif
		return NULL;
	}

	if (spot < 0) {
#ifndef NDEBUG
		writewarn("lists.listabsorb(): attempt to absorb element into spot (%d) that is < 0.\n", spot);
#endif
		return NULL;
	}

	if ((q = newelmt()) == NULL) {
#ifndef NDEBUG
		writewarn("lists.listabsorb(): newelmt() returned NULL.\n");
#endif
	} else {
		q->dispose = 0;
		q->width = width;
		q->data = data;
		insert(p, q, spot);
	}

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

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

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

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

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

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

	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 ? q : q->data);
}

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

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

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

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

	if (spot >= thelen(p)) {
#ifndef NDEBUG
		writewarn("lists.elmtwidth(): attempt to get %d'th element from list with only %d elements.\n", spot, thelen(p));
#endif
		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) {
#ifndef NDEBUG
		writewarn("lists.listdel(): attempt to delete %d'th element of a NULL list.\n", spot);
#endif
		return;
	}

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

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

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

	if ((q = eptr(p, spot)) == NULL) {
#ifndef NDEBUG
		writewarn("lists.listdel(): eptr() returned NULL.\n");
#endif
		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->next;
			q->next->prev = NULL;
		} else {
			if (spot == thelen(p)-1) {  /* Last elmt */
				((alistptr)p)->last = ((alistptr)p)->recent = q->prev;
				((alistptr)p)->mostrecent--;
				q->prev->next = NULL;
			} else {
				((alistptr)p)->recent = q->next;
				q->prev->next = q->next;
				q->next->prev = q->prev;
			}
		}
	}

	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) {
#ifndef NDEBUG
		writewarn("lists.listdispose(): attempt to dispose NULL list.\n");
#endif
		return NULL;
	}

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

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

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