#ifndef LINKLIST_H_INCLUDED
#define LINKLIST_H_INCLUDED

#include "inline.h"

struct list_head {
/*----------------------------------------------------------------------------
  This is a header for an element of a doubly linked list, or an anchor
  for such a list.

  itemP == NULL means it's an anchor; otherwise it's a header.

  Initialize a list header with list_init_header().  You don't have to
  do anything to terminate a list header.

  Initialize an anchor with list_make_emtpy().  You don't have to do anything
  to terminate a list header.
-----------------------------------------------------------------------------*/
    struct list_head * nextP;
        /* For a header, this is the address of the list header for
           the next element in the list.  If there is no next element,
           it points to the anchor.  If the header is not in a list at
           all, it is NULL.

           For an anchor, it is the address of the list header of the
           first element.  If the list is empty, it points to the
           anchor itself.  
        */
    struct list_head * prevP;
        /* For a header, this is the address of the list header for
           the previous element in the list.  If there is no previous element,
           it points to the anchor.  If the header is not in a list at
           all, it is NULL.

           For an anchor, it is the address of the list header of the
           last element.  If the list is empty, it points to the
           anchor itself.  
        */
    void * itemP;
        /* For a header, this is the address of the list element to which it
           belongs.  For an anchor, this is NULL.
        */
};

static __inline__ void
list_init_header(struct list_head * const headerP,
                 void *             const itemP) {

    headerP->prevP = NULL;
    headerP->nextP = NULL;
    headerP->itemP = itemP;
}


static __inline__ int
list_is_linked(struct list_head * headerP) {
    return headerP->prevP != NULL;
}


static __inline__ int
list_is_empty(struct list_head * const anchorP)  {
    return anchorP->nextP == anchorP;
}


static __inline__ unsigned int
list_count(struct list_head * const anchorP) {
    unsigned int count;

    struct list_head * p;

    for (p = anchorP->nextP, count = 0;
         p != anchorP;
         p = p->nextP, ++count);

    return count;
}


static __inline__ void
list_make_empty(struct list_head * const anchorP) {
    anchorP->prevP = anchorP;
    anchorP->nextP = anchorP;
    anchorP->itemP = NULL;
}

static __inline__ void
list_insert_after(struct list_head * const beforeHeaderP,
                  struct list_head * const newHeaderP) {
    newHeaderP->prevP = beforeHeaderP;
    newHeaderP->nextP = beforeHeaderP->nextP;

    beforeHeaderP->nextP = newHeaderP;
    newHeaderP->nextP->prevP = newHeaderP;
}


static __inline__ void
list_add_tail(struct list_head * const anchorP,
              struct list_head * const headerP) {
    list_insert_after(anchorP->prevP, headerP);
}


static __inline__ void
list_add_head(struct list_head * const anchorP,
              struct list_head * const headerP) {
    list_insert_after(anchorP, headerP);
}


static __inline__ void
list_remove(struct list_head * const headerP) {
    headerP->prevP->nextP = headerP->nextP;
    headerP->nextP->prevP = headerP->prevP;
    headerP->prevP = NULL;
    headerP->nextP = NULL;
}


static __inline__ struct list_head *
list_remove_head(struct list_head * const anchorP) {
    struct list_head * retval;

    if (list_is_empty(anchorP))
        retval = NULL;
    else {
        retval = anchorP->nextP;
        list_remove(retval);
    }            
    return retval;
}


static __inline__ struct list_head *
list_remove_tail(struct list_head * const anchorP) {
    struct list_head * retval;

    if (list_is_empty(anchorP))
        retval = NULL;
    else {
        retval = anchorP->prevP;
        list_remove(retval);
    }            
    return retval;
}


static __inline__ void *
list_foreach(struct list_head * const anchorP,
             void * functionP(struct list_head * const, void * const),
             void *             const context) {

    struct list_head * p;
    struct list_head * nextP;
    void * result;

    for (p = anchorP->nextP, nextP = p->nextP, result=NULL;
         p != anchorP && result == NULL; 
         p = nextP, nextP = p->nextP) 
        result = (*functionP)(p, context);

    return result;
}


static __inline__ void
list_append(struct list_head * const newAnchorP,
            struct list_head * const baseAnchorP) {

    if (!list_is_empty(newAnchorP)) {
        baseAnchorP->prevP->nextP = newAnchorP->nextP;
        newAnchorP->nextP->prevP = baseAnchorP->prevP;
        newAnchorP->prevP->nextP = baseAnchorP;
        baseAnchorP->prevP = newAnchorP->prevP;
    }
}

#endif