/* ============================== dl.c ============================== */
#include "dl.h"

void *malloc();

char *getnode(size)
{
	DL_NODE *n;

	if (n = (DL_NODE *) malloc(size)) {
		memset(n, '\0', size);
		n->size = size;
	}
	return(n);
}

freenode(n)
DL_NODE *n;
{
	free(n);
}

/*
 * Create an empty list
 */
DLIST dl_create(flags)
int flags;
{
	DLIST l;

	if ((l = (DLIST) malloc(sizeof(struct dl))) == NULL)
		return NULL;

	l->head = l->tail = l->curr = NULL;
	l->size = 0;
	l->flags = flags;
	return(l);
}

/*
 * Free entire list
 */
dl_destroy(l)
DLIST l;
{
	while (dl_shead(l))
		dl_delete(l);
	/*
	 * it is assumed that the list head structure itself was
	 * from dl_create, thus will always be free'd.
	 */
	free(l);
}

/*
 * Delete specific node
 */
dl_delete_node(l, n)
DLIST l;
DL_NODE *n;
{
	if (n) {
		dl_detach_node(l, n);

		if ((l->flags & DL_FREE) == DL_FREE)
			freenode(n);
	}
}

/*
 * Delete node, but leave memory alone
 */
dl_detach_node(l, n)
DLIST l;
DL_NODE *n;
{
	l->size--;

	l->curr = n->next;
	if (n->prev)
		n->prev->next = n->next;
	else
		l->head = n->next;
	if (n->next)
		n->next->prev = n->prev;
	else
		l->tail = n->prev;
}

/*
 * Insert node n before the current location in list l
 */
dl_ins_before_node(l, n_on_list, new_n)
DLIST l;
DL_NODE *n_on_list, *new_n;
{
	l->size++;

	if (l->head == NULL) {
		l->head = l->tail = l->curr = new_n;
		new_n->next = new_n->prev = NULL;
		return;
	}

	dl_set(l, n_on_list);
	if (l->curr == NULL)
		l->curr = l->head;

	new_n->prev = l->curr->prev;
	new_n->next = l->curr;
	if (l->curr->prev)
		l->curr->prev->next = new_n;
	else
		l->head = new_n;		/* else l->curr == l->head */
	l->curr->prev = new_n;

	l->curr = new_n;
}

dl_ins_after_node(l, n_on_list, new_n)
DLIST l;
DL_NODE *n_on_list, *new_n;
{
	l->size++;

	if (l->head == NULL) {
		l->head = l->tail = l->curr = new_n;
		new_n->next = new_n->prev = NULL;
		return;
	}

	dl_set(l, n_on_list);
	if (l->curr == NULL)
		l->curr = l->tail;

	new_n->prev = l->curr;
	new_n->next = l->curr->next;
	if (l->curr->next)
		l->curr->next->prev = new_n;
	else
		l->tail = new_n;		/* else l->curr == l->tail */
	l->curr->next = new_n;

	l->curr = new_n;
}

/*
 * Join l2 to the end of l1; l2 is no longer usable
 */
dl_cat(l1, l2)
DLIST l1, l2;
{
	l1->size += l2->size;
	l1->tail->next = l2->head;
	l2->head->prev = l1->tail;
	l1->tail = l2->tail;

	free(l2);
}

/*
 *  Split list 'l' into two, so that 'n' is the first node of the new list,
 *  return pointer to new list.
 */
/*  Uncomment and do as exercise
DLIST dl_split_at_node(l, n)
DLIST l;
DL_NODE *n;
{
	DLIST newl;

	if ((newl = dl_create(dl_flags(l))) == NULL)
		return(NULL);

	newl->size = count from current pos to end
	l->size = count up to current pos (l->size - newl->size)

	adjust pointers (last of l, first of newl (i.e., n))

	return newl
}
*/

DLIST dl_copy(l)
DLIST l;
{
	DLIST newl;
	DL_NODE *n, *newn;

	if ((newl = dl_create(dl_flags(l))) == NULL)
		return(NULL);

	foreachnode(l, n) {
		newn = getnode(n->size);
		if (newn == NULL) {
			dl_destroy(newl);
			return(NULL);
		}
		memcpy(newn, n, n->size);	/* copies ptrs, but is ok */
		dl_append(newl, newn);
	}

	return(newl);
}

dl_compare(l1, l2, func)
DLIST l1, l2;
int (*func)();
{
	int comp;

	for (dl_shead(l1), dl_shead(l2);
	     dl_curr(l1) && dl_curr(l2);
	     dl_snext(l1), dl_snext(l2))
		if ((comp = (*func)(dl_curr(l1), dl_curr(l2))) != 0)
			return(comp);

	if (dl_curr(l1))
		return(1);	/* l2 ran out first */
	else if (dl_curr(l2))
		return(-1);	/* l1 ran out first */
	else
		return(0);	/* both ran out at same time */
}

dl_apply(l, func, arg)
DLIST l;
int (*func)();
char *arg;
{
	foreach(l)
		(*func)(dl_curr(l), arg);
}

/*
 * Do a linear search on the list, given a start/end point
 */
dl_lsearch(l, begin, end, key, func)
DLIST l;
DL_NODE *begin, *end;
void *key;
int (*func)();
{
	DL_NODE *n;

	for (n = begin; n != end; n = n->next)
		if ((*func)(n, key)) {
			l->curr = n;
			return(TRUE);
		}

	return(FALSE);
}

/*
 * dl_sort - take a list and a 'qsort' type cmp func & sort
 *
 * since we make an array of ptrs, qsort really needs a cmp func
 * that follows a pointer to pointer to user struct; but this is
 * ugly for users, so dl_sort_cmp_fun does one indirection then
 * calls the users cmp func.
 */

static int (*dl_sort_user_cmp_fun)();

dl_sort_cmp_fun(p1, p2)
DL_NODE **p1, **p2;
{
	return((*dl_sort_user_cmp_fun)(*p1, *p2));
}

dl_sort(l, func)
DLIST l;
int (*func)();
{
	DL_NODE **array;
	int i, last;

	if (l->size <= 1)
		return(0);

	if ((array = dl_l2a(l)) == NULL)
		return(-1);

	dl_sort_user_cmp_fun = func;
	qsort(array, l->size, sizeof(DL_NODE *), dl_sort_cmp_fun);

	dl_a2l(l, array);

	free(array);

	return(0);
}

/* from a list, make an array of pointers to the list items */
DL_NODE **
dl_l2a(l)
DLIST l;
{
	DL_NODE *n, **array, **a;

	array = (DL_NODE **) malloc(l->size*sizeof(DL_NODE *));
	if (array == NULL)
		return(NULL);
	
	for (n = l->head, a = array; n != NULL; n = n->next, a++)
		*a = n;

	return(array);
}

/* turn an array of pointers to the list items into a list */
dl_a2l(l, array)
DLIST l;
DL_NODE **array;
{
	int i, last;

	l->head = array[0];
	l->head->prev = NULL;
	l->head->next = array[1];

	last = l->size - 1;
	for (i = 1; i < last; i++) {
		array[i]->next = array[i+1];
		array[i]->prev = array[i-1];
	}

	l->tail = array[last];
	l->tail->next = NULL;
	l->tail->prev = array[last-1];
}