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

    MODULE
	DLL.c

    DESCRIPTION
	Type DLL - Double Linked List

	This module is used to simplify work with some Exec
	structures like Tasks, Processes, Lists ...

	DList/DNode are equivalent to Exec:MinList/MinNode
	I chose using new names to keep bindings stricter;
	(btw. there seems to be 0 Exec function accepting Min*
	according to Protos)

    HISTORY
	14-11-94 b_noll created
	$Log: DLL.c $

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

/**************************************
	      Includes
**************************************/

#ifndef   DLL_H
#include <DLL.h>
#endif /* DLL_H */

/**************************************
      Internal Defines & Structures
**************************************/

#undef	Prototype
#define Prototype extern
#undef DLL_GetHead
#undef DLL_GetTail
#undef DLL_GetSucc
#undef DLL_GetPred



Prototype void DLL_Init (struct DList *l);
void DLL_Init (struct DList *l)
{
    l->Head	= (struct DNode *)&l->Tail;
    l->Tail	= NULL;
    l->TailPred = (struct DNode *)l;
} /* DLL_Init */

/* ---- Movement */

Prototype struct DNode *DLL_GetHead (struct DList *l);
struct DNode *DLL_GetHead (struct DList *l)
{
    return l->Head->Succ ? l->Head : NULL;
} /* DLL_GetHead */
#define DLL_GetHead(l)   (l->Head->Succ?    l->Head:    NULL)

Prototype struct DNode *DLL_GetTail (struct DList *l);
struct DNode *DLL_GetTail (struct DList *l)
{
    return l->TailPred->Succ ? l->TailPred : NULL;
} /* DLL_GetTail */
#define DLL_GetTail(l)   (l->TailPred->Pred?l->TailPred:NULL)

Prototype struct DNode *DLL_GetSucc (struct DList *l, struct DNode *n);
struct DNode *DLL_GetSucc (struct DList *l, struct DNode *n)
{
    return n->Succ->Succ ? n->Succ : NULL;
} /* DLL_GetSucc */
#define DLL_GetSucc(l,n) (n->Succ->Succ?    n->Succ:    NULL)

Prototype struct DNode *DLL_GetPred (struct DList *l, struct DNode *n);
struct DNode *DLL_GetPred (struct DList *l, struct DNode *n)
{
    return n->Pred->Pred ? n->Pred : NULL;
} /* DLL_GetPred */
#define DLL_GetPred(l,n) (n->Pred->Pred?    n->Pred:    NULL)

/* ---- Destruction */

Prototype void DLL_Remove (struct DList *l, struct DNode *n);
void DLL_Remove (struct DList *l, struct DNode *n)
{
    n->Pred->Succ = n->Succ;
    n->Succ->Pred = n->Pred;
} /* DLL_Remove */
#define DLL_Remove(l,n) do{ n->Pred->Succ = n->Succ; n->Succ->Pred = n->Pred; }while(0)

Prototype struct DNode * DLL_RemTail (struct DList *l);
struct DNode * DLL_RemTail (struct DList *l)
{
    struct DNode *n;
    if ((n = DLL_GetTail(l))) {
	DLL_Remove (l,n);
    } /* if */
    return n;
} /* DLL_RemTail */

Prototype struct DNode * DLL_RemHead (struct DList *l);
struct DNode * DLL_RemHead (struct DList *l)
{
    struct DNode *n;
    if ((n = DLL_GetHead(l))) {
	DLL_Remove (l,n);
    } /* if */
    return n;
} /* DLL_RemHead */

/* ---- Construction */

Prototype void DLL_AddBehind (struct DList *l, struct DNode *n, struct DNode *pos);
void DLL_AddBehind (struct DList *l, struct DNode *n, struct DNode *pos)
{
    n->Succ	    = pos->Succ;
    n->Pred	    = pos;
    pos->Succ->Pred = n;
    pos->Succ	    = n;
} /* DLL_AddBehind */

Prototype void DLL_AddInfront (struct DList *l, struct DNode *n, struct DNode *pos);
void DLL_AddInfront (struct DList *l, struct DNode *n, struct DNode *pos)
{
    DLL_AddBehind (l, n, pos->Pred);
} /* DLL_AddInfront */

Prototype void DLL_AddHead (struct DList *l, struct DNode *n);
void DLL_AddHead (struct DList *l, struct DNode *n)
{
    DLL_AddBehind (l, n, (struct DNode *)l);
} /* DLL_AddHead */

Prototype void DLL_AddTail (struct DList *l, struct DNode *n);
void DLL_AddTail (struct DList *l, struct DNode *n)
{
    DLL_AddBehind (l, n, l->TailPred);
} /* DLL_AddTail */

/* ---- Movement 2 */

Prototype int DLL_Length (struct DList *l);
int DLL_Length (struct DList *l) {
    struct DNode *n;
    int 	  num = 0;

    for (n = DLL_GetHead (l); n; n = DLL_GetSucc(l,n))
	num ++;

    return num;
} /* DLL_Length */

Prototype struct DNode *DLL_NumToNode (struct DList *l, int num);
struct DNode *DLL_NumToNode (struct DList *l, int num) {
    struct DNode *n;
    if (num >= 0) {
	for (n = DLL_GetHead (l); (num > 0) && (n != NULL); n = DLL_GetSucc (l,n), num --);
    } else {
	for (n = DLL_GetTail (l); (num < 0) && (n != NULL); n = DLL_GetPred (l,n), num ++);
    } /* if */

    return n;
} /* DLL_NumToNode */

Prototype int DLL_NodeToNum (struct DList *l, struct DNode *n);
int DLL_NodeToNum (struct DList *l, struct DNode *n) {
    int num = 0;

    if (n != NULL) {
	while (n = DLL_GetPred (l,n)) {
	    num ++;
	} /* while */

	return num;
    } /* if */
    return -1;
} /* DLL_NodeToNum */

/* ---- Movement 3 */

Prototype struct DNode *DLL_Find (struct DList *l, int (*find)(struct DNode *, void *, int), void *ud);
struct DNode *DLL_Find (struct DList *l, int (*find)(struct DNode *, void *, int), void *ud) {
    struct DNode *n;
    int 	  i = 0;
    for (n = DLL_GetHead(l); n; n = DLL_GetSucc(l,n)) {
	if (!(*find)(n, ud, i++))
	    return n;
    } /* for */
    return NULL;
} /* DLL_Find */

Prototype void DLL_Scan (struct DList *l, void (*scan)(struct DNode *, void *, int), void *ud);
void DLL_Scan (struct DList *l, void (*scan)(struct DNode *, void *, int), void *ud) {
    struct DNode *n, *nn;
    int i = 0;
    for (n = DLL_GetHead(l); n; n = nn) {
	nn = DLL_GetSucc(l,n);
	(*scan)(n, ud, i++);
    } /* for */
} /* DLL_Scan */






#if 0
/* ---- Complex functions */


Prototype void DLL_Sort (struct DList *l, int (*comp)(struct DNode *, struct DNode *));
void DLL_Sort (struct DList *l, int (*comp)(struct DNode *, struct DNode *)) {
    struct DNode *n, *c;
    struct DList inter;
    int diff;

    NewList (&inter);

    while (n = DLL_GetHead(l)) {
	for (c = DLL_GetSucc(l,n); c; c = DLL_GetSucc(c)) {
	    diff = (*comp)(c, n);
	    if (diff < 0)
		n = c;
	} /* for */
	DLL_Remove (l, n);
	DLL_AddHead(&inter, n);
    } /* while */

    while (n = DLL_RemHead(&inter)) {
	AddHead(l, n);
    } /* while */
} /* DLL_Sort */


Prototype void DLL_Filter (struct DList *l, struct DList *dest, int (*check)(struct DNode *, void *), void *ud);
void DLL_Filter (struct DList *l, struct DList *dest, int (*check)(struct DNode *, void *), void *ud) {
    struct DNode *n, *nn;
    int chck;

    for (n = DLL_GetHead(l); n; n = nn) {
	nn = DLL_GetSucc(l,n);

	chck = (*check)(n, ud);
	if (chck) {
	    DLL_Remove(l, n);
	    DLL_AddTail(dest, n);
	} /* if */
    } /* for */
} /* DLL_Filter */





Prototype void DLL_Join (struct DList *dest, struct DList *add);
void DLL_Join (struct DList *dest, struct DList *add) {
#if 1
    struct DNode *inter;

    while (inter = DLL_RemHead (add)) {
	AddTail (dest, inter);
    } /* while */
#else
    struct DNode *last	 = dest->TailPred;
    struct DNode *afirst = DLL_GetHead (add);

    if (afirst) {
	last->Succ   = afirst;
	afirst->Pred = last;
	last = DLL_GetTail (add);

	last->Succ     = &dest->Tail;
	dest->TailPred = last;

	NewList (add);
    } /* if */
#endif /* NOT_DEF */
} /* DLL_Join */


Prototype void DLL_AddSorted (struct DList *l, struct DNode *n, int (*comp)(struct DNode *, struct DNode *, void *), void *ud);
void DLL_AddSorted (struct DList *l, struct DNode *n, int (*comp)(struct DNode *, struct DNode *, void *), void *ud) {
    struct DNode *m;
    for (m = DLL_GetHead(l); m && ((*comp)(m, n, ud) < 0); m = DLL_GetSucc (l,m));
    if (!m) {
	DLL_AddTail(l,n);
    } else {
	Insert(l, n, m->Pred);
    }
} /* DLL_AddSorted */

#endif


/******************************************************************************
*****  END DLL.c
******************************************************************************/