/* dlist.c - linked list routines by Harry Sintonen <sintonen@iki.fi>

   faster swapnodes() by Jamie van den Berge <entity@vapor.com>
   mergesortlist() by Fabio Alemagna <falemagn@aros.org>

   dlist.c and dlist.h are public domain as long name of all contributers
   still appear in both files.
*/

/* HISTORY

   2107A1 - cleaned up the source & the header file. placed in public
            domain. - Harry

   1012A1 - added qsortlist() routine. - Harry

   2204A3 - added faster swapnodes() by Jamie van den Berge
            <entity@vapor.com>. - Harry

   1512A3 - fixed LISTEMPTY macro. - Harry

   1703A4 - added mergesortlist by Fabio Alemagna
            <falemagn@aros.org>. - Harry

   0610A6 - fixed LISTEMPTY macro to avoid type-punned ptr warning.
            thx Rennex. - Harry


   NOTES:

   API design was very stronly influenced by AmigaOS exec list routines,
   since I am very familiar with them. No documentation is included, the
   use is too obvious (at least for me, oh well... ;-) - Harry
*/

#include <stddef.h>
#include "dlist.h"


#ifdef __cplusplus
extern "C" {
#endif


void newlist(
	struct dlist *l)
{
	l->l_head	= (struct dnode *) &l->l_tail;
	l->l_tail	= NULL;
	l->l_tailpred	= (struct dnode *) &l->l_head;
}


void addhead(
	struct dlist *l,
	struct dnode *n)
{
	n->n_succ		= l->l_head;
	n->n_pred		= (struct dnode *) &l->l_head;
	l->l_head->n_pred	= n;
	l->l_head		= n;
}


void addtail(
	struct dlist *l,
	struct dnode *n)
{
	n->n_succ		= (struct dnode *) &l->l_tail;
	n->n_pred		= l->l_tailpred;
	l->l_tailpred->n_succ	= n;
	l->l_tailpred		= n;
}


void insert(
	struct dlist *l,
	struct dnode *n,
	struct dnode *afterof)
{
	if (afterof == NULL)
	{
		addhead(l, n);
		return;
	}

	n->n_pred		= afterof;
	n->n_succ		= afterof->n_succ;
	afterof->n_succ		= n;
	n->n_succ->n_pred	= n;
}


struct dnode *remhead(
	struct dlist *l)
{
	struct dnode *n = NULL;

	/* anything to remove?
	*/
	if (!LISTEMPTY(l))
	{
		n = l->l_head;
		n->n_succ->n_pred = n->n_pred;
		n->n_pred->n_succ = n->n_succ;
	}

	return n;
}


struct dnode *remtail(
	struct dlist *l)
{
	struct dnode *n = NULL;

	/* anything to remove?
	*/
	if (!LISTEMPTY(l))
	{
		n = l->l_tailpred;
		n->n_succ->n_pred = n->n_pred;
		n->n_pred->n_succ = n->n_succ;
	}

	return n;
}


void remnode(
	struct dnode *n)
{
	n->n_succ->n_pred = n->n_pred;
	n->n_pred->n_succ = n->n_succ;
}


struct dnode *findnode(
	struct dlist *l,
	struct dnode *n)
{
	struct dnode *worknode;

	worknode = (struct dnode *) &l->l_head;

	while ((worknode = worknode->n_succ))
	{
		if (worknode == n)
		{
			return n;
		}
	}

	return NULL;
}


struct dnode *callfornode(
	struct dlist *l,
	LISTFUNCPTR func,
	void *userdata,
	unsigned long int flags)
{
	struct dnode *worknode, *nextnode;

	if (flags & CFNF_BACKWARDS)
	{
		worknode = l->l_tailpred;

		while ((nextnode = worknode->n_pred))
		{
			if (func(worknode, userdata))
			{
				return worknode;
			}
			worknode = nextnode;
		}
	}
	else
	{
		worknode = l->l_head;

		while ((nextnode = worknode->n_succ))
		{
			if (func(worknode, userdata))
			{
				return worknode;
			}
			worknode = nextnode;
		}
	}

	return NULL;
}


#if 1

static
void swapnodes(
	struct dnode *b,
	struct dnode *y)
{
	/*
	// Fast linked list node swap - by Jamie van den Berge <entity@vapor.com>
	// 
	// Using just 10 assignments, 14 ptr dereferences and 2 pointers on stack.
	// Public domain so long as my name remains in this function.
	*/

	struct dnode *x, *z;

	/* give the nodes before/after y a name... */
	x = y->n_pred;
	z = y->n_succ;

	/* now let x and z believe they got b inbetween */
	x->n_succ = b;
	z->n_pred = b;

	/* let y think it has the nodes before/after b (named a and c) around it */
	y->n_succ = b->n_succ;
	y->n_pred = b->n_pred;

	/* now let b believe it's between x and y */
	b->n_succ = z;
	b->n_pred = x;

	/* which leaves us to make a and c believe they got y inbetween, however:
	   we didnt store the pointers to a and c! luckily we can reference
	   them from node y though.. */
	y->n_pred->n_succ = y;
	y->n_succ->n_pred = y;
}

#else

static
void swapnodes(
	struct dnode *a,
	struct dnode *b)
{
	struct dnode t;

	t.n_succ  = (a->n_succ == b) ? a : a->n_succ;
	t.n_pred  = (a->n_pred == b) ? a : a->n_pred;
	a->n_succ->n_pred = b;
	a->n_succ = (b->n_succ == a) ? b : b->n_succ;
	a->n_pred->n_succ = b;
	a->n_pred = (b->n_pred == a) ? b : b->n_pred;

	b->n_succ->n_pred = a;
	b->n_succ = t.n_succ;
	b->n_pred->n_succ = a;
	b->n_pred = t.n_pred;
}

#endif


void qsortlist(
	struct dlist *l,
	struct dnode *basenode,
	unsigned long int nmemb,
	COMPARFUNCPTR compar)
{
	struct dnode *worknode;
	struct dnode *leftnode, *rightnode, *middlenode = NULL;
	unsigned long int cnt, left, right;

	/* NULL basenode mean list head
	*/
	if (basenode == NULL)
	{
		basenode = l->l_head;
	}

#ifdef USE_QSL_ALL

	/* calculate number of nodes from base position to tail of the list
	*/
	for (cnt = 0, worknode = basenode; worknode = worknode->n_succ;) { cnt++; }

	/* adjust nmemb, if necessary
	*/
	if (nmemb == QSL_ALL || nmemb > cnt)
	{
		nmemb = cnt;
	}

#endif

	while (nmemb > 1)
	{
		left = 0; leftnode = basenode;		/* left node */
		right = nmemb - 1;

		for (cnt = 0, worknode = basenode; ; cnt++, worknode = worknode->n_succ)
		{
			if (cnt == right / 2)		/* middle node ((left + right) / 2) */
			{
				middlenode = worknode;
			}
			else if (cnt == right)		/* right node */
			{
				rightnode = worknode;
				break;
			}
		}

		for (;;)
		{
			while ((*compar)(middlenode, leftnode) > 0)
			{
				/* look for one >= middle
				*/
				left++; leftnode = leftnode->n_succ;
			}
			while ((*compar)(middlenode, rightnode) < 0)
			{
				/* look for one <= middle
				*/
				right--; rightnode = rightnode->n_pred;
			}
			if (left >= right)
			{
				/* we found no pair
				*/
				break;
			}

			/* Swap leftnode & rightnode in the list
			*/
			swapnodes(leftnode, rightnode);

			/* Swap leftnode & rightnode pointers
			*/
			worknode = leftnode;
			leftnode = rightnode;
			rightnode = worknode;

			if (basenode == leftnode || basenode == rightnode)
			{
				/* Recalculate basenode address! (IMPORTANT!)
				*/
				basenode = (basenode == leftnode) ? rightnode : leftnode;
			}

			/* Note: automagically keep track of middle node
			*/

			/* These two are already sorted
			*/
			left++; leftnode   = leftnode->n_succ;
			right--; rightnode = rightnode->n_pred;
		}

		/* left points to first element of right interval now (right to last of left)
		*/
		right++;

		for (cnt = right, worknode = basenode; cnt--; worknode = worknode->n_succ) {}

		/* do recursion on smaller interval and iteration on larger one,
		   avoids recursion to save stack storage & avoid recursion overhead
		*/
		if (right < nmemb - right)
		{
			qsortlist(l, basenode, right, compar);
			basenode = worknode;
			nmemb -= right;
		}
		else
		{
			qsortlist(l, worknode, nmemb - right, compar);
			nmemb = right;
		}
	}
}


static inline
struct dnode *mslmerge(
	struct dnode *l,
	COMPARFUNCPTR compar)
{
	struct dnode *l1, *last_l1, *l2, *last_l2, *next_l;
	struct dnode *first = NULL, **first_ptr, **last_ptr = &first;

	l1 = l;

	/* l1 points to the 1st sublist, l2 points to the 2nd.

	   Should there be no l2, we don't need to do anything special, as
	   l1 will already be linked with the rest of the list AND it won't 
	   obviously need to be merged with another list.
	*/
	while (l1 && (l2 = (last_l1 = l1->n_pred)->n_succ))
	{
		last_l2 = l2->n_pred;

		next_l  = last_l2->n_succ;

		/* This will make the below loop slightly faster, since there will only
		   be tests against the constant NULL.
		*/
		last_l1->n_succ = NULL;
		last_l2->n_succ = NULL;

		/* Pointer to the beginning of the merged sublist
		*/
		first_ptr = last_ptr;
		do
		{
			if ((*compar)(l1, l2) < 0)
			{
				l1->n_pred = (struct dnode *)((char *)last_ptr - 
				             offsetof(struct dnode, n_succ));
				*last_ptr  = l1;
				l1         = l1->n_succ;
			}
			else
			{
				l2->n_pred = (struct dnode *)((char *)last_ptr - 
				             offsetof(struct dnode, n_succ));
				*last_ptr  = l2;
				l2         = l2->n_succ;
			}

			last_ptr = &(*last_ptr)->n_succ;

		} while (l1 && l2);

		if (l1)
		{
			l1->n_pred = (struct dnode *)((char *)last_ptr - 
			             offsetof(struct dnode, n_succ));

			*last_ptr            = l1;
			(*first_ptr)->n_pred = last_l1;
			last_ptr             = &last_l1->n_succ;
		}
		else if (l2)
		{
			l2->n_pred = (struct dnode *)((char *)last_ptr - 
			             offsetof(struct dnode, n_succ));

			*last_ptr            = l2;
			(*first_ptr)->n_pred = last_l2;
			last_ptr             = &last_l2->n_succ;
		}
		else
		{
			(*first_ptr)->n_pred = (struct dnode *)((char *)last_ptr - 
			                       offsetof(struct dnode, n_succ));
		}

		l1 = *last_ptr = next_l;
	}

	return first;
}

void mergesortlist(
	struct dlist *l,
	COMPARFUNCPTR compar)
{
	struct dnode *head, *tail;

	struct dnode *l1, *l2, *first, **last_ptr;

	if (!l)
		return;

	head = l->l_head;
	tail = l->l_tailpred;

	if (tail == (struct dnode *) l || head == tail)
		return;
	
	tail->n_succ = NULL;
	last_ptr = &first;

	/* The mslmerge() function requires a list of sublists, each of which
	   has to be a circular list. Since the given list doesn't have these 
	   properties, we need to divide the sorting algorithm in 2 parts:

	       1) we first go trough the list once, making every node's Pred pointer
	          point to the node itself, so that the given list of n nodes is
	          transformed in a list of n circular sublists. Here we do the merging
	          "manually", without the help of the mslmerge() function, as we have
	          to deal with just couples of nodes, thus we can do some extra
	          optimization.

	       2) We then feed the resulting list to the mslmerge() function, as many
	          times as it takes to the mslmerge() function to give back just one
	          circular list, rather than a list of circular sublists: that will be
	          our sorted list.
	*/

	/* This is the first part.
	*/
	l1 = head;
	l2 = l1->n_succ;
	do
	{
		/* It can happen that the 2 nodes are already in the right,
		   order and thus we only need to make a circular list out
		   of them, or their order needs to be reversed, but
		   in either case, the below line is necessary, because:

		       1) In the first case, it serves to build the 
		          circular list.

		       2) In the 2nd case, it does hald the job of
		          reversing the order of the nodes (the 
		          other half is done inside the if block).
		*/
		l1->n_pred = l2;

		if ((*compar)(l1, l2) >= 0)
		{
			/* l2 comes before l1, so rearrange them and
			   make a circular list out of them.
			*/
			l1->n_succ = l2->n_succ;
			l2->n_succ = l1;
			l2->n_pred = l1;

			l1 = l2;
		}
	
		*last_ptr = l1;
		last_ptr  = &l1->n_pred->n_succ;
		l1        = *last_ptr;

	} while (l1 && (l2 = l1->n_succ));

	/* An orphan node? Add it at the end of the list of sublists and 
	   make a circular list out of it.
	*/
	if (l1)
	{
		l1->n_pred = l1;
		*last_ptr  = l1;
	}

	/* And this is the 2nd part.
	*/
	while (first->n_pred->n_succ)
		first = mslmerge(first, compar);

	/* Now we fix up the list header.
	*/
	l->l_head     = first;
	l->l_tailpred = first->n_pred;
	first->n_pred->n_succ = (struct dnode *)&l->l_tail;
	first->n_pred = (struct dnode *)&l->l_head;
}

#ifdef __cplusplus
} // extern "C"
#endif