/* clist.c     v0.1  (C) 1999 adolfo@di-mare.com */

#include "clist.h"


void cl_link_after(clist *L_, cl_link *p_, cl_link* px_) {
/*=================================================*\
| Links after position "p" the object that contains |
| link field "*px".                                 |
| - To link as first set p == NULL                  |
\*=================================================*/

    clist_rep *L  = (clist_rep*) L_;
    link_rep  *p  = (link_rep*)  p_;
    link_rep  *px = (link_rep*)  px_;

    #ifndef NDEBUG
    if (NULL != px->next) {
        abort();            /* check unlinked */
    }
    #endif
    if (NULL == L->last) {  /* empty list:   */
        px->next = px;      /* link as first */
        L->last  = px;
    }
    else if (NULL == p) {   /* link as first */
        p             = L->last->next;
        L->last->next = px;
        px->next      = p;
    }
    else if (p == L->last) { /* link as last */
        px->next      = L->last->next;
        L->last->next = px;
        L->last       = px;
    }
    else {             /* link in the middle */
        px->next = p->next;
        p->next  = px;
    }
}

cl_link* cl_unlink_after(clist *L_, cl_link* p_) {
/*===================================================*\
| Detaches from the list the object that comes after  |
| position "p" in the list.                           |
| - Returns a pointer to the link field just detached |
| - To unlink the first, set p == NULL                |
\*===================================================*/

    clist_rep *L  = (clist_rep*) L_;
    link_rep  *p  = (link_rep*)  p_;
    link_rep  *px;

    #ifndef NDEBUG
    if (NULL == p->next) {
        abort();            /* check unlinked */
    }
    #endif
    if (p == NULL) {
        px = L->last->next;
        if (L->last == L->last->next) {
            L->last = NULL; /* just 1 element */
        }
        else {            /* detach the first */
            p = L->last->next;
            L->last->next = p->next;
        };
    }
    else {                      /* p != NULL */
        px = p->next;
        if (L->last == L->last->next) {
            abort(); /* only 1 element ==> p must be NULL */
        }
        else { /* detach from the middle */
            link_rep *tmp;
            tmp = p->next;
            p->next = tmp->next;
            if (tmp == L->last) {
                L->last = p;
            }
        }
    }

    #ifndef NDEBUG
        px->next = NULL; /* clean up link field */
    #endif
    return (cl_link*) px;
}


cl_link* cl_nth(const clist *L_, cl_link *q_, size_t n) {
/*==========================================*\
| Returns the position of the "n-th" element |
| counting from "q"                          |
| - For n==0 returns "q"                     |
\*==========================================*/

    size_t    i;
    link_rep *p;

    if (0 == n) {
        return q_;
    }
    else if (NULL == q_) {
        p = ((clist_rep*) L_)->last;
    }
    else {
        p  = (link_rep*) q_;
    }

    for (i=0; i!= n; i++, p = p->next) {}
    return (cl_link*) p;
}


size_t cl_count(const clist *L_) {
/*==========================================*\
| Returns the number of elements in the list |
\*==========================================*/
    clist_rep *L = (clist_rep*) L_;
    link_rep  *p = L->last;

    size_t n = 0;

    if (L->last != NULL) {
        p = L->last;
        do {
            p = p->next;
            n++;
        } while (p != L->last);
    }
    return n;
}

        /*============================*\
        ||                            ||
        || All these require a binder ||
        ||                            ||
        \*============================*/


void cl_swap_binder (clist *LLL, clist *SRC, const binder *B) {
/*===========================================*\
| Swaps the contents of "L" and "src".        |
| - No copying in done: only pointer swapping |
| - Takes O(1) time and space                 |
\*===========================================*/
    link_rep *    TMP          = ((clist_rep*)(LLL))->last;
    ((clist_rep*)(LLL))->last  = ((clist_rep*)(SRC))->last;
    ((clist_rep*)(SRC))->last  =  TMP;
     #pragma argsused
}

void cl_copy_binder (clist *L_, clist * src_, const binder *B) {
/*===========================================*\
| Copies list "src" over "L_"                 |
| - B->copy() is used to copy each element    |
| - List "src" remains unchanged              |
| - Takes O(n) time and space                 |
\*===========================================*/

    clist_rep *L   = (clist_rep*) L_;
    clist_rep *src = (clist_rep*) src_;
    link_rep  *DELETED;

    if (L==src) {
        return;    /* avoid auto-copy */
    }

    DELETED = L->last;
    if (NULL != DELETED) {
        DELETED       = L->last->next;   /* cl_first() */
        L->last->next = NULL;
        L->last       = NULL;
    }

    /* copy element by element, from src */
    if (NULL != src->last) { /* src isn't empty */
        const ofs  = B->offset;
        const size = B->size;
        const void (* INIT ) (void *) = B->init;
        const void (* COPY ) (void *, void *) = B->copy;
        /* INIT: pointer to a function that returns void,
                 and takes a (void *) as argument.       */

        link_rep * pSrc;

        pSrc = src->last;
        do {
            void     * pNew;
            link_rep * pLink;   /* == pNew->Link */

            pSrc = pSrc->next;

            /* "bend backwards" to avoid malloc()-ing */
            if (NULL != DELETED) { /* reuse nodes from L */
                pLink = DELETED;
                pNew  = SUB_OFFSET(pLink, ofs);

                DELETED = pLink->next;
            }
            else {
                INIT(pNew = malloc(size));
                pLink = (link_rep *) ADD_OFFSET(pNew, ofs);
            }

            COPY(pNew, SUB_OFFSET(pSrc, ofs));
            cl_append(L_, (cl_link*) pLink);

        } while (pSrc != src->last);
    }

    if (NULL != DELETED) {   /* delete rest */
        const         ofs            = B->offset;
        const void (* DONE) (void *) = B->done;

        while (DELETED != NULL) {
            void     *del = SUB_OFFSET(DELETED, ofs);
            link_rep *p   = DELETED->next;

            DONE(del);
            free(del);
            DELETED = p;
        }
    }
}


int cl_equal_binder(const clist *L_, const clist *src_, const binder * B) {
/*=============================================*\
| Returns "0" when "L_" and "src" are different |
| - B->equal() is used to compare elements      |
| - Takes O(n) time and O(1) space              |
\*=============================================*/

    link_rep *p, *q;
    clist_rep *L   = (clist_rep*) L_;
    clist_rep *src = (clist_rep*) src_;
    const ofs = B->offset;
    const int (* EQUAL ) (void *, void *) = B->equal;

    if (L->last == src->last)  {
        return !0; /* TRUE */
    }

    if ((NULL == L->last) || (NULL == src->last)) {
        /* avoid using a NULL pointer -derreferencing- */
        return 0; /* FALSE, because both can't be NULL */
    }

    /* compare elements one by one */
    p = L->last;
    q = src->last;
    do {
        p = p->next;
        q = q->next;
        if (! EQUAL( SUB_OFFSET(p, ofs), SUB_OFFSET(q, ofs) )) {
            return 0; /* FALSE */
        }
    } while ( (p != L->last) && (q != src->last) );

    return    (p == L->last) && (q == src->last);
}


void cl_print_binder(const clist *L, FILE *F, const binder * B) {
/*=====================================*\
| Prints the whole list with comas and  |
| parenthesis, like this:               |
| - (1, 2, 3, 4, 5) or even ()          |
\*=====================================*/

    const ofs = B->offset;
    const void (* PRINT) (void *, FILE *) = B->print;
    cl_link *last = cl_last(L);

    {
        cl_link * p = cl_first(L);
        fprintf(F, "(");
        while (NULL != p) {
            PRINT( SUB_OFFSET(p, ofs),  F );
            if (p != last) {
                fprintf(F, " ");
            }
            p = cl_next(L, p);
        }
        fprintf(F, ")");
    }
/*
    fprintf(F, "(");
    if (!cl_empty(L)) {
        cl_link * p = cl_first(L);
        do {
            PRINT( SUB_OFFSET(p, ofs),  F );
            p = cl_next(L, p);
            if (p != last) {
                fprintf(F, " ");
            }
        } while (p != last);
    }
    fprintf(F, ")");
*/
}


void cl_delete_all(clist *L_, const binder* B) {
/*===========================================*\
| Destroys the whole list                     |
| - B->done() is used to destroy each element |
\*===========================================*/

    clist_rep *L = (clist_rep*) L_;
    link_rep *p;

    if (L->last != NULL) {
        p       = L->last;      /* begin from the first */
        L->last = L->last->next;
        p->next = NULL;        /* force last to be NULL */

        while (L->last != NULL) {
            void *del = ((char*)L->last) - B->offset;
            p = L->last->next;
            B->done(del);            /* never use last */
            free(del);                 /* after free() */
            L->last = p;
        }
    }
}

void cl_done_binder_(clist *L_, const binder* B) {
    cl_delete_all(L_, B);
}


/* Non-macro versions of inlined code */
#ifdef  COMPILE_NON_INLINE_METHODS

void cl_link_init_(cl_link* link) {
    #pragma argsused
} /* avoid "argument [link] not used" warning */

void cl_link_done_(cl_link* link) {
    #pragma argsused
}

void cl_init_(clist *L) {
/*====================*\
| Initializes the list |
\*====================*/
    ((clist_rep*)(L))->last = NULL;
}

cl_link* cl_first_(const clist *L) {
    return cl_first(L);
}

cl_link* cl_last_(const clist *L) {
    return cl_last(L);
}

cl_link* cl_next_ (const clist *L, cl_link *p) {
/*==========================================*\
| Returns the position that comes after "p"  |
| - After the last position, returns NULL.   |
\*==========================================*/
    return cl_next(L,p);
}

int cl_empty_(const clist * L) {
    return cl_empty(L);
}

void cl_append_(clist *L, cl_link *p) {
/*===================*\
| Appends to the list |
\*===================*/
    cl_append(L, p);
}

#endif

/* EOF:   clist.c */