#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#define LIST(elem) \
    struct { elem *head, *tail; }
#define NODE(elem) \
    struct { elem *next, *prev; }

#define HEAD(q,l)       ((q)->l.head)
#define TAIL(q,l)       ((q)->l.tail)
#define NEXT(n,l)       ((n)->l.next)
#define PREV(n,l)       ((n)->l.prev)

#define LISTINIT(q,l) \
do { \
    HEAD(q,l) = NULL; \
    TAIL(q,l) = NULL;  \
} while(0)

#define NODEINIT(n,l) \
do { \
    NEXT(n,l) = NULL; \
    PREV(n,l) = NULL; \
} while(0)

#define ADDTAIL(q,l,n) \
do { \
    if (TAIL(q,l)) { \
        NEXT(TAIL(q,l),l) = (n); \
        PREV(n,l) = TAIL(q,l); \
    } else { \
        PREV(n,l) = NULL; \
        HEAD(q,l) = (n); \
    } \
    TAIL(q,l) = (n); \
    NEXT(n,l) = NULL; \
} while (0)

#define ADDHEAD(q,l,n) \
do { \
    if (HEAD(q,l)) { \
        PREV(HEAD(q,l),l) = (n); \
        NEXT(n,l) = HEAD(q,l); \
    } else { \
        NEXT(n,l) = NULL; \
        TAIL(q,l) = (n); \
    } \
    HEAD(q,l) = (n); \
    PREV(n,l) = NULL; \
} while (0)

#define REMHEAD(q,l,n) \
do { \
    (n) = HEAD(q,l); \
    if (n) { \
        HEAD(q,l) = NEXT(n,l); \
        if (HEAD(q,l)) \
            PREV(HEAD(q,l),l) = NULL; \
        else \
            TAIL(q,l) = NULL; \
    } \
} while(0)

#define REMTAIL(q,l,n) \
do { \
    (n) = TAIL(q,l); \
    if (n) { \
        TAIL(q,l) = PREV(n,l); \
        if (TAIL(q,l)) \
            NEXT(TAIL(q,l),l) = NULL; \
        else \
            HEAD(q,l) = NULL; \
    } \
} while(0)

#define REMOVE(q,l,n) \
do { \
    if (PREV(n,l)) \
        NEXT(PREV(n,l),l) = NEXT(n,l); \
    if (NEXT(n,l)) \
        PREV(NEXT(n,l),l) = PREV(n,l); \
} while (0)

#define ISEMPTY(q,l)      (HEAD(q,l) == NULL)
#define FOREACH(q,l,n)    for (n = HEAD(q,l); n; n = NEXT(n,l))
#define FOREACHR(q,l,n)   for (n = TAIL(q,l); n; n = PREV(n,l))
#define FOREACHD(q,l,n,r) for (n = TAIL(q,l); n && (r = PREV(n,l), 1); n = r)

#include "al.h"

/* unique library identifier */
const char al_id[] = "OSSP al";

/* support for OSSP ex based exception throwing */
#ifdef WITH_EX
#include "ex.h"
#define AL_RC(rv) \
    (  (rv) != AL_OK && (ex_catching && !ex_shielding) \
     ? (ex_throw(al_id, NULL, (rv)), (rv)) : (rv) )
#else
#define AL_RC(rv) (rv)
#endif /* WITH_EX */

typedef struct {
    void   *(*malloc)(size_t);
    void   (*free)(void *);
    void   *(*balloc)(size_t);
    void   (*bfree)(void *);
    size_t new_buffersize;
    int    max_freechunks;
} al_memops_t;

struct al_st {
    LIST(al_chunk_t) chunks;
    size_t           bytes;
    al_memops_t      m;
};

struct al_chunk_st {
    NODE(al_chunk_t) chunks;
    al_buffer_t      *buf;
    size_t           begin, end;
};

struct al_buffer_st {
    unsigned char  *mem;
    size_t         size;
    int            usecount;
    int            freemem;
};

struct al_tx_st {
    al_td_t       dir;
    al_chunk_t    *cur;
    size_t        skip;
    size_t        togo;
    al_chunk_t    view;
};

/* number of bytes described by a chunk */
#define AL_CHUNK_LEN(alc) \
    ((alc)->end - (alc)->begin)

/* memory pointer into a chunk, offset must be less than length */
#define AL_CHUNK_PTR(alc, off) \
    ((alc)->buf->mem + (alc)->begin + (off))

/* number of bytes of a span that are stored in a chunk */
#define AL_CHUNK_SPAN(alc, off, n) \
    ((n) == AL_BYTES_ALL || (n) > AL_CHUNK_LEN(alc) - (off) ? \
    AL_CHUNK_LEN(alc) - (off) : (n))

/* number of bytes a chunk can be grown to the end */
#define AL_CHUNK_RESERVE(alc) \
    ((alc) \
    ? (alc)->buf->usecount > 1 ? 0 : (alc)->buf->size - (alc)->end \
    : 0)

/* grow chunk to the end */
#define AL_RESIZE(al, alc, n) \
    do { (alc)->end += n; (al)->bytes += (n); } while (0)

/* number of bytes a chunk can be grown to the beginning */
#define AL_CHUNK_PRESERVE(alc) \
    ((alc) \
    ? (alc)->buf->usecount > 1 ? 0 : (alc)->begin \
    : 0)

/* grow chunk to the beginning */
#define AL_PRESIZE(al, alc, n) \
    do { (alc)->begin -= n; (al)->bytes += (n); } while (0)

/*
 * allocate backing store and its control structure from heap
 * can be freed when usecount drops to zero
 */
static
al_rc_t new_buffer(al_t *al, al_buffer_t **bufp)
{
    size_t n = al->m.new_buffersize;
    al_buffer_t *buf;

    if ((buf = (al_buffer_t *)(al->m.malloc)(sizeof(al_buffer_t))) == NULL)
        return AL_ERR_MEM;

    if ((buf->mem = (al->m.balloc)(n)) == NULL) {
        (al->m.free)(buf);
        return AL_ERR_MEM;
    }

    buf->freemem  = 1;
    buf->size     = n;
    buf->usecount = 0;

    *bufp = buf;
    return AL_OK;
}

static
al_rc_t dispose_buffer(al_t *al, al_buffer_t *buf)
{
    /* must not happen */
    if (buf->usecount != 0)
        return AL_ERR_INT;

    if (buf->freemem)
        (al->m.bfree)(buf->mem);

    (al->m.free)(buf);
    return AL_OK;
}

/*
 * allocate only control structure for backing store from heap
 * and attach to existing memory
 * only the control structure will be freed later
 */
static
al_rc_t make_buffer(al_t *al, char *p, size_t n, al_buffer_t **bufp)
{
    al_buffer_t *buf;

    if ((buf = (al_buffer_t *)(al->m.malloc)(sizeof(al_buffer_t))) == NULL)
        return AL_ERR_MEM;

    buf->mem      = p;

    buf->freemem  = 0;
    buf->size     = n;
    buf->usecount = 0;

    *bufp = buf;
    return AL_OK;
}

/*
 * allocate chunks from heap and attach to backing store
 * keep some freed chunks in a freelist to avoid expensive malloc()
 * and excessive fragmentation
 * maintain usage count of backing store
 * free backing store when no longer in use, this also includes
 * the case where new_chunk fails and the buffer has no other
 * users
 */
static
struct {
    LIST(al_chunk_t) chunks;
} alc_freelist;
static
int alc_freecount = 0;

static
al_rc_t new_chunk(al_t *al, al_buffer_t *buf, al_chunk_t **alcp)
{
    al_chunk_t *alc;

    if (ISEMPTY(&alc_freelist, chunks)) {
        if ((alc = (al_chunk_t *)(al->m.malloc)(sizeof(al_chunk_t))) == NULL) {
            if (buf->usecount == 0)
                dispose_buffer(al,buf);
            return AL_ERR_MEM;
        }
    } else {
        REMHEAD(&alc_freelist, chunks, alc);
        --alc_freecount;
    }

    NODEINIT(alc, chunks);
    alc->buf   = buf;
    alc->begin = 0;
    alc->end   = 0;

    ++buf->usecount;

    *alcp = alc;
    return AL_OK;
}

static
void dispose_chunk(al_t *al, al_chunk_t *alc)
{
        --alc->buf->usecount;
        if (alc->buf->usecount == 0)
            dispose_buffer(al,alc->buf);
        alc->buf = NULL;

        /* stop freelist from growing infinitely */
        if (alc_freecount >= al->m.max_freechunks) {
            (al->m.free)(alc);
        } else {
            ADDTAIL(&alc_freelist, chunks, alc);
            ++alc_freecount;
        }
}

/*
 *  find chunk that represents a particular offset
 *  if off is negative, treat it as relative offset from the end
 *  a reference to the chunk is stored in *alcp
 *  the relative offset into the chunk is stored in *skipp
 *  return AL_ERR_EOF when no such chunk can be found
 */
static
al_rc_t al_seek(al_t *al, size_t off, al_chunk_t **alcp, size_t *skipp)
{
    al_chunk_t *cur;
    size_t pos;
    size_t chunksize;

    if (off >= 0) {
        pos = 0;
        FOREACH(al,chunks,cur) {
            chunksize = AL_CHUNK_LEN(cur);
            if (pos <= off && off < pos+chunksize) {
                *alcp  = cur;
                *skipp = off - pos;
                return AL_OK;
            }
            if (pos+chunksize >= off)
                return AL_ERR_EOF;
            pos += chunksize;
        }
    } else {
        off += al->bytes;
        pos  = al->bytes;
        FOREACHR(al,chunks,cur) {
            chunksize = AL_CHUNK_LEN(cur);
            pos -= chunksize;
            if (pos <= off && off < pos+chunksize) {
                *alcp  = cur;
                *skipp = off - pos;
                return AL_OK;
            }
            if (pos+chunksize < off)
                return AL_ERR_EOF;
        }
    }

    return AL_ERR_EOF;
}

#if 0
#include <stdio.h>
static
void dump(al_t *al)
{
    al_chunk_t *cur;

    printf("AL: %x\n", al);
    FOREACH(al,chunks,cur) {
        printf(" C: %x (%d @ %x + %d < %d)\n",
            cur,
            cur->buf->size,cur->buf->mem,
            cur->begin,cur->end);
    }
    printf("--\n\n");
}
#endif

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

/*
 * allocate an empty assembly line
 * dispose all chunks and all allocated backing store
 */
al_rc_t al_create(al_t **alp)
{
    al_t *al;

    /* argument sanity check(s) */
    if (alp == NULL)
            return AL_RC(AL_ERR_ARG);

    /* allocate and initialize new assembly line object */
    /* XXX - what malloc ? */
    if ((al = (al_t *)malloc(sizeof(al_t))) == NULL)
            return AL_RC(AL_ERR_MEM);

    LISTINIT(al,chunks);
    al->bytes = 0;

    /* memory policy */
    al->m.malloc = malloc;    /* structure allocation */
    al->m.free   = free;
    al->m.balloc = malloc;    /* buffer allocation */
    al->m.bfree  = free;
    al->m.new_buffersize = 4096;
    al->m.max_freechunks = 500;

    /* pass object to caller */
    *alp = al;

    return AL_OK;
}

al_rc_t al_destroy(al_t *al)
{
    al_chunk_t *cur, *pred;

    /* argument sanity check(s) */
    if (al == NULL)
            return AL_RC(AL_ERR_ARG);

    /* free chunks and backing store */
    FOREACHD(al,chunks,cur,pred) {
        dispose_chunk(al,cur);
    }

    /* free object itself */
    /* XXX - which free() ? */
    free(al);

    return AL_OK;
}

al_rc_t al_append_bytes(al_t *al, const char *src, size_t n)
{
    al_rc_t rc;
    al_chunk_t *cur;
    al_buffer_t *buf;
    size_t res, step;
    char *dst;

    cur = TAIL(al,chunks);
    res = AL_CHUNK_RESERVE(cur);

    while (n > 0) {
        if (res == 0) {
            rc = new_buffer(al, &buf);
            /* XXX handle error */
            rc = new_chunk(al,buf,&cur);
            /* XXX handle error */
            res = AL_CHUNK_RESERVE(cur);
            ADDTAIL(al, chunks, cur);
        }
        step = n;
        if (step > res)
            step = res;

        dst = AL_CHUNK_PTR(cur, AL_CHUNK_LEN(cur));
        memcpy(dst, src, step);

        src += step;
        AL_RESIZE(al, cur, step);
        n   -= step;
        res = AL_CHUNK_RESERVE(cur);
    }

    return AL_OK;
}

al_rc_t al_prepend_bytes(al_t *al, const char *src, size_t n)
{
    al_rc_t rc;
    al_chunk_t *cur;
    al_buffer_t *buf;
    size_t res, step;
    char *dst;

    cur = HEAD(al,chunks);
    res = AL_CHUNK_PRESERVE(cur);

    src += n;

    while (n > 0) {
        if (res == 0) {
            rc = new_buffer(al, &buf);
            if (rc != AL_OK) return rc;
            rc = new_chunk(al,buf,&cur);
            if (rc != AL_OK) return rc;
            res = AL_CHUNK_PRESERVE(cur);
            ADDHEAD(al, chunks, cur);
        }
        step = n;
        if (step > res)
            step = res;

        src -= step;
        AL_RESIZE(al, cur, step);
        n   -= step;
        res = AL_CHUNK_RESERVE(cur);

        dst = AL_CHUNK_PTR(cur, 0);
        memcpy(dst, src, step);
    }

    return AL_OK;
}

al_rc_t al_attach_buffer(al_t *al, char *p, size_t n)
{
    al_rc_t rc;
    al_buffer_t *buf;
    al_chunk_t  *cur;

    rc = make_buffer(al, p, n, &buf);
    if (rc != AL_OK) return rc;
    rc = new_chunk(al,buf, &cur);
    if (rc != AL_OK) return rc;
    ADDTAIL(al, chunks, cur);

    /* validate data in buffer */
    AL_RESIZE(al, cur, n);

    return AL_OK;
}

al_rc_t al_splice(al_t *al, size_t off, size_t n, al_t *tal)
{
    al_rc_t rc;
    al_chunk_t *cur, *next;
    size_t skip, len, step;

    if (n == AL_BYTES_ALL) n = al->bytes - off;

    rc = al_seek(al, off, &cur, &skip);
    if (rc != AL_OK) return rc;
printf("initial seek %d -> %p + %d\n",off,cur,skip);
    while (n > 0) {
        /* check if a partial chunk was selected */
        next = NEXT(cur, chunks);
        len  = AL_CHUNK_LEN(cur);
        if (skip > 0 || n < len - skip) {
            /* copy span from src chunk to target */
            step = len - skip;
            if (n < step)
                step = n;
printf("partial copy (%p + %d) + %d bytes\n",cur,skip,step);
            if (tal != NULL)
                al_append_bytes(tal, AL_CHUNK_PTR(cur, skip), step);
            /* cut span from src chunk */
            if (skip == 0) {
printf("shrink at begin\n");
                AL_PRESIZE(al, cur, -step);
            } else {
                /* align trailing bytes */
                if (len > (skip+step)) {
printf("align chunk buffer (%d + %d) <- %d\n",skip,step,len-(skip+step));
                    memmove(
                        AL_CHUNK_PTR(cur, skip),
                        AL_CHUNK_PTR(cur, skip+step),
                        len - (skip+step)
                    );
                }
printf("shrink at end\n");
                AL_RESIZE(al, cur, -step);
            }
        } else {
            step = len;
printf("hand over chunk %d\n",step);
            REMOVE(al, chunks, cur);
            al->bytes -= step;
            if (tal != NULL) {
                ADDTAIL(tal, chunks, cur);
                tal->bytes += step;
            } else {
                dispose_chunk(al,cur);
            }
        }
        n   -= step;
        off += step;
        cur  = next;
        skip = 0;
    }

    return AL_ERR_INT;
}

al_rc_t al_truncate(al_t *al, size_t off, size_t n)
{
    return al_splice(al, off, n, NULL);
}

al_rc_t al_traverse(al_t *al, size_t off, size_t n, al_td_t dir, al_tx_t *txp)
{
    al_rc_t rc;

    if (n == AL_BYTES_ALL) n = al->bytes - off;

    txp->cur = NULL;

    rc = al_seek(al, off, &txp->cur, &txp->skip);
    if (rc != AL_OK) return AL_OK;

    txp->dir  = dir;
    txp->togo = n;

    return AL_OK;
}

al_rc_t al_traverse_next(al_t *al, al_tx_t *txp, al_chunk_t **alcp)
{
    size_t step;

    if (txp->cur == NULL)
        return AL_ERR_EOF;

    step = AL_CHUNK_LEN(txp->cur);
    if (step > txp->togo)
        step = txp->togo;

    /*
     * synthetic chunk which is NOT maintained in usecount
     * MUST NOT BE USED for modifications to chunk list
     * MUST NOT BE USED for modifications to chunk size
     * ALLOWED is read access to chunk content
     * ALLOWED is modification in place of chunk content
     */
    txp->view        = *(txp->cur);
    txp->view.begin += txp->skip;
    txp->view.end    = txp->view.begin + step;

    switch (txp->dir) {
    case AL_FORWARD:
        txp->cur   = NEXT(txp->cur,chunks);
        txp->togo -= step;
        break;
    case AL_BACKWARD:
        txp->cur   = PREV(txp->cur,chunks);
        txp->togo -= step;
        break;
    }

    *alcp = &txp->view;
    return AL_OK;
}

al_rc_t al_traverse_cb(al_t *al, size_t off, size_t n, al_td_t dir,
                       al_rc_t (*cb)(al_chunk_t *, void *), void *u)
{
    al_rc_t rc;
    al_tx_t tx;
    al_chunk_t *view;

    rc = al_traverse(al, off, n, dir, &tx);
    if (rc != AL_OK) return rc;

    while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK) {
        rc = cb(view, u);
        if (rc != AL_OK)
            break;
    }

    if (rc != AL_ERR_EOF)
        return rc;

    return AL_OK;
}

al_rc_t al_flatten(al_t *al, size_t off, size_t n, char *dst)
{
    al_rc_t rc;
    al_tx_t tx;
    al_chunk_t *view;
    size_t step;

    rc = al_traverse(al, off, n, AL_FORWARD, &tx);
    if (rc != AL_OK) return rc;

    while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK) {
        step = AL_CHUNK_LEN(view);
        memmove(dst, AL_CHUNK_PTR(view,0), step);
        dst += step;
    }

    if (rc != AL_ERR_EOF)
        return rc;

    return AL_OK;
}

size_t al_bytes(const al_t *al)
{
    return al->bytes;
}

size_t al_chunk_len(al_chunk_t *alc)
{
    return AL_CHUNK_LEN(alc);
}

size_t al_chunk_span(al_chunk_t *alc, size_t off, size_t n)
{
    return AL_CHUNK_SPAN(alc, off, n);
}

char *al_chunk_ptr(al_chunk_t *alc, size_t off)
{
    return AL_CHUNK_PTR(alc, off);
}