/*
Name   : LISTS.CPP
Date   : 19 March, 1990 (C version); 5 April, 1992 (C++ version)
Author : Kim Moser
System : Borland C++ 3.0
Descrip: Generic linked list utilities
*/

//#define NDEBUG

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

#include "lists.h"
#include "etlog.h"

#ifndef NDEBUG
DEF_MODULE_NAME(__FILE__);
#endif

static dupefunc_t mem_dup;
static void* mem_dupe(void* data, int datalen)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* mem_dupe(void* data, int datalen)");
#endif
	void* r;

	if ((r = new[datalen]) == NULL) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"new[" << datalen << "] failed.\n";
#endif
	} else {
		memcpy(r, data, datalen);
	}

	return (r);
}

static deletefunc_t mem_delete;
#pragma argsused	// Suppress "argument 'datalen' is never used..."
static int mem_delete(void* data, int datalen)
{
	delete data;
	return (1);
}

int elmt::init_elmt(int size)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("int elmt::init_elmt(int size)");
#endif
	int r = 1;  /* Assume */

	signature = ELMTSIGNATURE;
	esize = size;
	if (size) {
		if (!(data = new[size])) {
#ifndef NDEBUG
			warn_module_function_macro <<
			"new[" << size << "] failed.\n";
#endif
			signature = 0;
			r = 0;
		}
	} else {
		data = NULL;
	}

	return (r);
}

#pragma argsused	// Suppress "argument 'size' never used..."

void* elmt::operator new(size_t size, size_t elmtsize)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* elmt::operator new(size_t size, size_t elmtsize)");
#endif

	elmt* q;

	if (!(q = (elmt*) ::operator new(sizeof(elmt)))) {
#ifndef NDEBUG
		warn_module_function_macro <<
		" ::operator new(sizeof(elmt)) failed.\n";
#endif
		return (NULL);
	} else if (q->init_elmt(elmtsize)) {
		return ((void*) q);
	} else {
#ifndef NDEBUG
		warn_module_function_macro <<
		"q->init_elmt[" << elmtsize << "] failed.\n";
#endif
		return (NULL);
	}
}

void elmt::operator delete(void* e)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void elmt::operator delete(void* e)");
#endif

	if (((elmt*)e)->elmtinitialized()) {
		((elmt*)e)->signature = 0;
		delete[] ((elmt*)e)->data;	// Delete vector
		delete e;			// Delete this elmt
	} else {
#ifndef NDEBUG
		warn_module_function_macro <<
		"elmt not initialized.\n";
#endif
	}
}

int elmt::elmtinitialized(void)
{
	return (signature == ELMTSIGNATURE);
}

int elmt::elmtsize(void)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("int elmt::elmtsize(void)");
#endif

	if (elmtinitialized()) {
		return (esize);
	} else {
#ifndef NDEBUG
		warn_module_function_macro <<
		"elmt not initialized.\n";
#endif
		return (0);
	}
}

/*************************************************************************/

elmt* list::eptr(int n)
/* Returns a pointer to the n'th elmt (offset from 0) in list 'p';
   assumes 'p' contains at least n+1 elements. */
{
#ifndef NDEBUG
	DEF_FUNC_NAME("elmt* list::eptr(int n)");
#endif

	int i=0;
	elmt *q;
	int tmp;
	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=((fast_listlen()-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 = 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 = 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 = 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 = last;  /* Start at last elmt */
			for (i=fast_listlen()-1; (i>n) && (q != NULL); i--) q = q->prev;
			break;
		default:
#ifndef NDEBUG
			warn_module_function_macro <<
			"invalid list seek path (" << path << ") for " << n << "'th elmt.\n";
#endif
			return (NULL);
	}

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

	return (q);
}

void list::list(void)
{
	first = last = recent = NULL;
	mostrecent = -1;
	len = 0;
	signature = LISTSIGNATURE;
}

int list::listlen(void)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("int list::listlen(void)");
#endif

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"list is uninitialized.\n";
#endif
		return (0);
	}

	return (fast_listlen());
}

void list::insert(elmt& q, int spot)
/* Adds element 'q' to spot 'spot' (offset from 0)
   (or to end of list if list contains fewer than spot+1 elments) */
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void list::insert(elmt& q, int spot)");
#endif

	elmt *e;

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

		if (fast_listlen()) {
			q.next->prev = &q;
		} else {
			last = &q;
		}
		first = recent = &q;
		mostrecent = 0;
	} else {
		/* list has at least 1 elmt already, and spot > 0: */
		if (spot >= fast_listlen()) {
			/* Add to end of list */
			if ((e = eptr(fast_listlen()-1)) == NULL) {
#ifndef NDEBUG
				warn_module_function_macro <<
				"eptr() returned NULL (spot=" << spot << ", listlen=" << fast_listlen() << ").\n";
#endif
				return;
			}
			e->next = &q;
			q.prev = e;
			q.next = NULL;
			last = recent = &q;
			mostrecent = fast_listlen();
		} else {
			if ((e = eptr(spot)) == NULL) {
				/* This should never happen */
#ifndef NDEBUG
				warn_module_function_macro <<
				"eptr() returned NULL (spot=" << spot << ", listlen=" << fast_listlen() << ").\n";
#endif
				return;  /* To avoid further corruption */
			}
			q.next = e;
			q.prev = e->prev;
			e->prev->next = &q;
			e->prev = &q;

			recent = &q;
			mostrecent = spot;
		}
	}
	len++;
}

void* list::listinsert(void* data, int elmtsize, int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* list::listinsert(void* data, int elmtsize, int spot)");
#endif

	elmt *q;

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to insert element into uninitialized list.\n";
#endif
		return (NULL);
	}

	if (spot < 0) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to insert element into spot (" << spot << ") that is < 0.\n";
#endif
		return (NULL);
	}

	if (!(q = (elmt*) new(elmtsize) elmt)) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"new(elmtsize) failed.\n";
#endif
		return (NULL);
	}

	q->dispose = 1;
	memcpy(q->data, data, (size_t)elmtsize);
	insert(*q, spot);

	return (q->data);
}

void* list::listins(void* data, int elmtsize, dupefunc_t dupefunc, int do_dupe, deletefunc_t deletefunc, int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* list::listins(void* data, int elmtsize, dupefunc_t dupefunc, int do_dupe, deletefunc_t deletefunc, int spot)");
#endif

	elmt *q;

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to insert element into uninitialized list.\n";
#endif
		return (NULL);
	}

	if (spot < 0) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to insert element into spot (" << spot << ") that is < 0.\n";
#endif
		return (NULL);
	}

	if (!(q = (elmt*) new(elmtsize) elmt)) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"new(elmtsize==" << elmtsize << ") failed.\n";
#endif
		return (NULL);
	}

	q->dispose = 1;
	q->dupefunc = dupefunc;
	q->deletefunc = deletefunc;
	if (do_dupe) {
		if (dupefunc == NULL) {
#ifndef NDEBUG
			warn_module_function_macro <<
			"do_dupe is true, but dupefunc is NULL.\n";
#endif
		} else {
			if ((q->data = dupefunc(data, elmtsize)) == NULL) {
#ifndef NDEBUG
				warn_module_function_macro <<
				"dupefunc() returned NULL.\n";
#endif
			}
		}
	} else {
		q->data = data;
	}

	insert(*q, spot);

	return (q->data);
}

void* list::listabsorb(void* data, int elmtsize, int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* list::listabsorb(void* data, int elmtsize, int spot)");
#endif
	void* r;

	if ((r = listins(data, elmtsize, mem_dup, 0, mem_delete, spot)) == NULL) {
		warn_module_function_macro << "listins() failed.\n";
	}

	return (r);
}

void* list::listelmt(int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void* list::listelmt(int spot)");
#endif

	elmt *q;

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get " << spot << "'th element of uninitialized list.\n";
#endif
		return (NULL);
	}

	if (spot < 0) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get element from spot (" << spot << ") that is < 0.\n";
#endif
		return (NULL);
	}

	if (spot >= fast_listlen()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get " << spot << "'th element from list with only " << fast_listlen() << " elements.\n";
#endif
		return (NULL);
	}

	q = eptr(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 list::elmtsize(int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("int list::elmtsize(int spot)");
#endif

	elmt *q;

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get " << spot << "'th element of uninitialized list.\n";
#endif
		return 0;
	}

	if (spot < 0) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get element from spot (" << spot << ") that is < 0.\n";
#endif
		return 0;
	}

	if (spot >= fast_listlen()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to get " << spot << "'th element from list with only " << fast_listlen() << " elements.\n";
#endif
		return 0;
	}

	q = eptr(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->esize);
}

void list::listdel(int spot)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("void list::listdel(int spot)");
#endif

	elmt *q;

	if (!listinitialized()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to delete " << spot << "'th element of uninitialized list.\n";
#endif
		return;
	}

	if (spot < 0) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to delete element from spot (" << spot << ") that is < 0.\n";
#endif
		return;
	}

	if (spot >= fast_listlen()) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to delete " << spot << "'th element from list with only " << fast_listlen() << " elements.\n";
#endif
		return;
	}

	if ((q = eptr(spot)) == NULL) {
#ifndef NDEBUG
		warn_module_function_macro <<
		"eptr(" << spot << ") returned NULL.\n";
#endif
		return;
	}
	if (fast_listlen() == 1) {  /* List len == 1 */
		/* We must be removing the 0'th elmt: */
		first = last = recent = NULL;
		mostrecent = -1;
	} else {  /* List len >= 2 */
		if (!spot) {
			/* We're removing the 0'th elmt */
			first = recent = q->next;
			q->next->prev = NULL;
		} else {
			if (spot == fast_listlen()-1) {  /* Last elmt */
				last = recent = q->prev;
				mostrecent--;
				q->prev->next = NULL;
			} else {
				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 */
		delete (q->data);
	}
	q->signature = 0;
	delete (q);
	len--;
}

list::~list(void)
{
#ifndef NDEBUG
	DEF_FUNC_NAME("list::~list(void)");
#endif

	if (listinitialized()) {
		while (fast_listlen()) listdel(0);
	} else {
#ifndef NDEBUG
		warn_module_function_macro <<
		"attempt to destroy uninitialized list.\n";
#endif
		return;
	}

	if (first == NULL) {
		signature = 0;
	} else {
#ifndef NDEBUG
		warn_module_function_macro <<
		"listlen()==0 but first != NULL.\n";
#endif
	}
}