#ifndef	__DLIST_H__
#define	__DLIST_H__

/* dlist.h - 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.
*/

#include <stdio.h>

struct dnode
{
	struct dnode *n_succ;
	struct dnode *n_pred;
};

struct dlist
{
	struct dnode *l_head;
	struct dnode *l_tail;
	struct dnode *l_tailpred;
};

/* callback function type for callfornode()
*/
typedef int (*LISTFUNCPTR) (struct dnode *, void *);

/* return value for LISTFUNCPTR:
*/
#define LFR_CONTINUE    0   /* continue list travelsal */
#define LFR_BREAK       1   /* stop list travelsal and return current node */

/* flags for callfornode()
*/
#define	CFNF_BACKWARDS	(1 << 0)

/* callback function type for qsortlist()
*/
typedef int (*COMPARFUNCPTR) (struct dnode*, struct dnode *);


#ifdef USE_QSL_ALL

/* use this as qsortlist() nmemb to sort all nodes from base
*/
#define	QSL_ALL		0xffffffff

#endif


#define	LISTEMPTY(l) \
((void *) (l)->l_tailpred == (void *) (l))

#define	CNEWLIST(l) \
{(struct dnode *) &(l)->l_tail, NULL, (struct dnode *) &(l)->l_head}


#ifdef __cplusplus
extern "C" {
#endif


void newlist(
	struct dlist *l);

void addhead(
	struct dlist *l,
	struct dnode *n);

void addtail(
	struct dlist *l,
	struct dnode *n);

void insert(
	struct dlist *l,
	struct dnode *n,
	struct dnode *afterof);

struct dnode *remhead(
	struct dlist *l);

struct dnode *remtail(
	struct dlist *l);

void remnode(
	struct dnode *n);

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

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

void qsortlist(
	struct dlist *l,
	struct dnode *base,
	unsigned long int nmemb,
	COMPARFUNCPTR compar);

void mergesortlist(
	struct dlist *l,
	COMPARFUNCPTR compar);

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

#endif /* __DLIST_H__ */