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

General usage:

	Call listnew() to initialize a list.
	
	Thereafter, call listinsert() or listabsorb() to add elements,
	or listdel() to remove them.
	
	Call listwipe to remove all elements from a list.

	Call listdispose() to remove all of the list's elements
	AND dispose of the list's internal data structure.
*/

#include <stdlib.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 void* ((*dupefunc_t)(void* data, int datalen));
typedef int ((*deletefunc_t)(void* data, int datalen));

class elmt {
friend list;
private:
	void* data;		// Pointer to the data
	int esize;		// Size of data
	dupefunc_t dupefunc;	// Points to function that duplicates 'data' type
	deletefunc_t deletefunc;// Points to function that deletes 'data' type
	char dispose;		// Whether we allocated it dynamically
				// and must dispose of it when
				// deallocating list
	elmt* next;		// Pointer to next element in list
	elmt* prev;		// Pointer to previous element in list
	unsigned char signature;// Whether this element has been
				// properly initialized

	inline elmt(void) {};	// Do NOT call this constructor!
	inline elmt(const elmt& e); // Do NOT call this constructor!
	inline ~elmt(void) {};	// Do NOT call this destructor!
	int init_elmt(int elmtsize);
protected:
	void* operator new(size_t size, size_t elmtsize);	// Constructor
	void operator delete(void* e);
	inline int elmtinitialized(void);
	int elmtsize(void);
};

class list {
private:
	elmt *first;		// Pointer to first element
	elmt *last;		// Pointer to last element
	elmt *recent;		// Pointer to most recently accessed elmt
	int mostrecent;		// Index (offset from 0) of most recently
				// accessed elmt
	int len;		// Number of elements in list
	unsigned int signature;	// SIGNATURE (hopefully)

	elmt* eptr(int n);
	inline int listinitialized(void)
	{
		return (signature == LISTSIGNATURE);
	}
	inline int fast_listlen(void)
	{
		return (len);
	}
	void insert(elmt& q, int spot);

public:
	// Constructors:
	list(void);
	list(list& src);

	// Query length:
	int listlen(void);

	// Add elmt:
	void* listinsert(void* data, int elmtsize, int spot);
	void* listins(void* data, int elmtsize, dupefunc_t dupefunc, int do_dupe, deletefunc_t deletefunc, int spot);
	void* listabsorb(void* data, int elmtsize, int spot);

	// Retrieve elmt:
	void* listelmt(int spot);

	// Query elmt size:
	int elmtsize(int spot);

	// Remove elmt:
	void listdel(int spot);

	// Destructor:
	~list(void);
};