/*
**  OSSP al -- Assembly Line
**  Copyright (c) 2002-2005 The OSSP Project <http://www.ossp.org/>
**  Copyright (c) 2002-2005 Cable & Wireless <http://www.cw.com/>
**  Copyright (c) 2002-2005 Ralf S. Engelschall <rse@engelschall.com>
**  Copyright (c) 2002-2005 Michael van Elst <mlelstv@serpens.de>
**
**  This file is part of OSSP al, an abstract datatype of a data buffer
**  that can assemble, move and truncate data but avoids actual copying
**  and which can be found at http://www.ossp.org/pkg/lib/al/.
**
**  Permission to use, copy, modify, and distribute this software for
**  any purpose with or without fee is hereby granted, provided that
**  the above copyright notice and this permission notice appear in all
**  copies.
**
**  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
**  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
**  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
**  IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
**  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
**  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
**  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
**  USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
**  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
**  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
**  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
**  SUCH DAMAGE.
**
**  al.c: assembly line library implementation
*/

/* include optional Autoconf header */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#ifdef TEST
#include <stdio.h>
#endif

#include "list.h"

#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 */

struct al_buffer_st;
typedef struct al_buffer_st al_buffer_t;

typedef struct {
    void           *(*malloc)(size_t); /* malloc(3) style function (for al_chunk_t) */
    void            (*free)(void *);   /* free(3)   style function (for al_chunk_t) */
    void           *(*balloc)(size_t); /* malloc(3) style function (for al_buffer_t) */
    void            (*bfree)(void *);  /* free(3)   style function (for al_buffer_t) */
    size_t            new_buffersize;  /* default size for memory underlying al_buffer_t */
    int               max_freechunks;  /* maximum number of cached al_chunk_t objects */
} al_memops_t;

struct al_st {
    LIST(al_chunk_t)  chunks;          /* list header for al_chunk_t objects */
    size_t            bytes;           /* total cached number of bytes in chunk */
    al_memops_t       m;               /* assembly line memory operations (see above) */
};

struct al_chunk_st {
    NODE(al_chunk_t)  chunks;          /* list node for al_chunk_t object chaining */
    al_buffer_t      *buf;             /* (non-exlusively) referenced buffer object */
    size_t            begin;           /* offset into buf->mem where data starts */
    size_t            end;             /* offset into buf->mem where data ends */
    al_label_t        label;           /* tag data with a label, chunks with distinct labels are not coalesced */
};

struct al_buffer_st {
    char             *mem;             /* reference to underlying chunk of data */
    size_t            size;            /* size of underlying chunk of data */
    int               usecount;        /* reference count (from al_chunk_t) */
    void            (*freemem)(char *p, size_t n, void *u); /* callback function to reclaim memory when it is no longer referenced */
    void             *userdata;          /* arbitrary pointer to pass context data to the callback function */
};

struct al_tx_st {
    al_td_t           dir;             /* traversal direction */
    al_chunk_t       *cur;             /* current chunk during traveral steps */
    size_t            skip;            /* number of bytes to skip for traversal */
    size_t            togo;            /* number of bytes left for traversal */
    al_label_t        label;           /* label filter or NULL */
    al_chunk_t        view;            /* synthetic chunk for returning during traversal steps */
};

/* 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_CHUNK_LEN(alc) - (off)) ? \
    (AL_CHUNK_LEN(alc) - (off)) : (n))

/* return chunk label */
#define AL_CHUNK_LABEL(alc) \
    ((alc)->label)

/* check wether labels match */
#define AL_SAME_LABEL(alc,label) \
    ((label) == NULL || AL_CHUNK_LABEL(alc) == (label))

/*
 * number of bytes a chunk can be grown to the end
 * we must not grow a chunk in a shared buffer since
 * we do not track other chunks sharing the buffer
 */
#define AL_CHUNK_RESERVE(alc,label) \
    (  (alc) != NULL \
     ? (  (alc)->buf->usecount > 1 || !AL_SAME_LABEL(alc,label) \
        ? 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
 * we must not grow a chunk in a shared buffer since
 * we do not track other chunks sharing the buffer
 *
 * empty chunks can be aligned with end
 */
#define AL_CHUNK_PRESERVE(alc,label) \
    ( (alc) != NULL \
     ? (  (alc)->buf->usecount > 1 || !AL_SAME_LABEL(alc,label) \
        ? 0 \
        : (alc)->end <= (alc)->begin ? \
          (alc)->buf->size \
          : (alc)->begin) \
     : 0)

/*
 * grow chunk to the beginning
 *
 * empty chunks can be aligned with end
 */
#define AL_PRESIZE(al, alc, n) \
    do { \
        if ((alc)->end <= (alc)->begin) \
            (alc)->end = (alc)->begin = (alc)->buf->size; \
        (alc)->begin -= n; (al)->bytes += (n); \
    } while (0)

/*
 * callback to release buffer memory allocated by the library
 */
static
void freemem(char *p, size_t n, void *u)
{
    void (*f)(void *) = (void (*)(void *))u;
    f(p);
}

/*
 * 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  = freemem;
    buf->userdata = (void *)al->m.bfree;
    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)
        (buf->freemem)(buf->mem, buf->size, buf->userdata);

    (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, void (*freemem_cb)(char *, size_t, void *), void *u, 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  = freemem_cb;
    buf->userdata = u;
    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_label_t label, 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 {
        /* thl: FIXME i would suggest using REMTAIL() here because dispose_chunk
         *            puts the latest disposed chunks at the end of the list and
         *            those latest data should have a closer approximation to the
         *            CPU in terms of internal cache, external cache, RAM and VM
         */
        REMHEAD(&alc_freelist, chunks, alc);
        --alc_freecount;
    }

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

    buf->usecount++;

    *alcp = alc;
    return AL_OK;
}

static al_rc_t
split_chunk(al_t *al, al_chunk_t *orig, size_t off, al_chunk_t **alcp)
{
    al_rc_t rc;
    al_chunk_t *alc;
    size_t len = AL_CHUNK_LEN(orig);

    if (off > len)
        return AL_ERR_ARG;

    rc = new_chunk(al, orig->buf, orig->label, &alc);
    if (rc != AL_OK)
        return rc;

    alc->begin  = orig->begin;
    alc->end    = orig->begin+off;
    orig->begin = alc->end;

    *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;
    alc->label = 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
 *  a reference to the chunk is stored in *alcp
 *  the relative offset into the chunk is stored in *skipp
 *  return AL_OK and *alcp == NULL if positioned exactly to end of list
 *  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, end;
    size_t chunksize;

    if ((al->bytes / 2) >= off) { /* FIXME poor man's heuristic */
        /* forward search */
        pos = 0;
        FOREACH(al,chunks,cur) {
            chunksize = AL_CHUNK_LEN(cur);
            end = pos+chunksize;
            if (pos <= off && off < end) {
                *alcp  = cur;
                *skipp = off - pos;
                return AL_OK;
            }
            if (end > off)
                break;
            pos = end;
        }
        /* seek to EOF position is ok */
        if (pos == off) {
            *alcp  = NULL;
            *skipp = 0;
            return AL_OK;
        }
    } else {
        /* reverse search */
        pos  = al->bytes;
        /* seek to EOF position is ok */
        if (pos == off) {
            *alcp  = NULL;
            *skipp = 0;
            return AL_OK;
        }
        FOREACHR(al,chunks,cur) {
            chunksize = AL_CHUNK_LEN(cur);
            end  = pos;
            pos -= chunksize;
            if (pos <= off && off < end) {
                *alcp  = cur;
                *skipp = off - pos;
                return AL_OK;
            }
            if (pos < off)
                break;
        }
    }

    return AL_ERR_EOF;
}

#ifdef TEST
static void
dump(al_t *al)
{
    al_chunk_t *cur;
    size_t total;

    printf("AL: %p\n", al);
    total = 0;
    FOREACH(al,chunks,cur) {
        printf(" C: %p [%p] (%d @ %p + %d < %d (use=%d))\n",
            cur,
            cur->label,
            cur->buf->size,cur->buf->mem,
            cur->begin,cur->end,
            cur->buf->usecount);
        total += AL_CHUNK_LEN(cur);
    }
    printf("size = %d == %d\n",al->bytes,total);
    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;
#ifdef TEST
    al->m.new_buffersize = 42;
#else
    al->m.new_buffersize = 4096;
#endif
    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) {
        REMOVE(al,chunks,cur);
        dispose_chunk(al,cur);
    }

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

    return AL_OK;
}

/*
 * copy bytes into buffer, FIFO
 *
 * stops copy operation when a new buffer cannot be created
 * but leaves data structure consistent
 */
al_rc_t
al_append_bytes(al_t *al, const char *src, size_t n, al_label_t label)
{
    al_rc_t rc;
    al_chunk_t *cur;
    al_buffer_t *buf;
    size_t res, step;
    char *dst;

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

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

    while (n > 0) {
        if (res == 0) {
            rc = new_buffer(al, &buf);
            if (rc != AL_OK)
                return AL_RC(rc);
            rc = new_chunk(al,buf,label,&cur);
            if (rc != AL_OK)
                return AL_RC(rc);
            res = AL_CHUNK_RESERVE(cur,label);
            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,label);
    }

    return AL_OK;
}

/*
 * copy bytes into buffer, LIFO
 *
 * stops copy operation when a new buffer cannot be created
 * but leaves data structure consistent
 */
al_rc_t
al_prepend_bytes(al_t *al, const char *src, size_t n, al_label_t label)
{
    al_rc_t rc;
    al_chunk_t *cur;
    al_buffer_t *buf;
    size_t res, step;
    char *dst;

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

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

    src += n;

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

        src -= step;
        AL_PRESIZE(al, cur, step);
        n   -= step;
        res = AL_CHUNK_PRESERVE(cur,label);

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

    return AL_OK;
}

/*
 * append a caller supplied buffer
 *
 * buffer must exist until list is destroyed
 * XXX - buffer can have multiple refs caused by splice operations
 * XXX - some list operations modify the buffer
 *
 */
al_rc_t al_attach_buffer(al_t *al, char *p, size_t n, al_label_t label,
                         void (*freemem_cb)(char *, size_t, void *), void *u)
{
    al_rc_t rc;
    al_buffer_t *buf;
    al_chunk_t  *cur;

    /* argument sanity check(s) */
    if (al == NULL || p == NULL || n <= 0)
        return AL_RC(AL_ERR_ARG);

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

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

    return AL_OK;
}

/*
 * this is the central function to manipulate assembly line
 *
 * cut arbitrary spans from list into a destination buffer (or drop it)
 * insert (destructive move) content from another list into the cut
 *
 * this is analog to perls splice function, except that
 * -> the output is not stored in the target buffer but is appended
 * -> the replacement data is moved and not copied.
 *
 */
al_rc_t
al_splice(al_t *al, size_t off, size_t n, al_t *nal, al_t *tal)
{
    al_rc_t rc;
    al_chunk_t *cur, *start, *end, *next, *ins, *splitbuf;
    size_t pos, skip, len, step;
    int doinsert;

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

    /* optimization: treat an empty list as no insertion at all */
    doinsert = (nal != NULL) && !ISEMPTY(nal,chunks);

    /*
     * seek to beginning, return EOF when seek position does not exist
     * EOD must be a valid seek position so that we can append data
     */
    rc = al_seek(al, off, &cur, &skip);
    if (rc != AL_OK)
        return AL_RC(rc);

    /*
     * remember insertion point
     *
     * caveat: if the first chunk is removed from input the insertion
     *         point shifts to the next chunk (or EOD -> NULL pointer)
     */
    ins = cur;

    /*
     * the inseration point is either behind the list or
     * within the current chunk
     *
     * if it is behind the list:
     * -> insert operation switches to append mode
     *
     * if the insertion point is at the beginning of the current chunk:
     * -> insertion point moves later if the chunk is removed
     *
     * if the inseration point is in the middle of the current chunk:
     * -> chunk is split into two so that the insertion
     *    point is at the beginning of the second part
     *
     * insertion point cannot be at EOD of the chunk
     *
     * splitting at this point preserves all data in case the
     * allocation of the split buffer fails
     */
    if (doinsert) {
        if (ins != NULL && skip > 0) {
            rc = split_chunk(al, ins, skip, &splitbuf);
            if (rc != AL_OK)
                return AL_RC(rc);
            INSERT(al,chunks,ins,splitbuf);
            skip = 0;
        }
    }

    /*
     * as long as there is data to move
     */
    pos = off;
    while (n > 0 && cur != NULL) {
        next = NEXT(cur, chunks);
        len  = AL_CHUNK_LEN(cur);

        /*
         * check if partial chunk was selected
         * if skip > 0 we have to preserve bytes at the beginning
         * if skip == 0 && n < len-skip we have to preserve bytes at the end
         */
        if (skip > 0 || n < len - skip) {

            /* compute number of bytes to process */
            step = AL_CHUNK_SPAN(cur, skip, n);

            /* copy data to target */
            if (tal != NULL) {
                /*
                 * XXX - this operation can fail
                 */
                size_t before = tal->bytes;

                rc = al_append_bytes(tal, AL_CHUNK_PTR(cur, skip),
                                     step, AL_CHUNK_LABEL(cur));
                if (rc != AL_OK)
                    /* correct step size to actual size */
                    step = tal->bytes - before;

            } else
                rc = AL_OK;

            /*
             * cut span from src chunk
             * if skip == 0, simply shrink the chunk from the beginning
             * if skip > 0, compute number of bytes to preserve,
             *              align buffer and shrink chunk from the end
             */
            if (skip == 0)
                AL_PRESIZE(al, cur, -step);
            else {
                /* align trailing bytes */
                if (len > (skip+step)) {
                    memmove(
                        AL_CHUNK_PTR(cur, skip),
                        AL_CHUNK_PTR(cur, skip+step),
                        len - (skip+step)
                    );
                }
                AL_RESIZE(al, cur, -step);
            }

            /*
             * bail out from failed al_append_bytes operation above
             *
             */
            if (rc != AL_OK)
                return AL_RC(rc);
        }
        else {
            /*
             * the whole chunk has to be moved,
             *
             * scan ahead for more such chunks to unlink
             * and relink a whole chain in a single operation
             *
             * move the chunks to the target chain
             * manual accounting for total size
             */

            /*
             * when the insertion chunk is removed, we have to adjust
             * the insertion point
             *
             * if the insertion chunk was the last chunk we get a NULL
             * next pointer and the insertion method switches to append
             * mode
             */

            step  = len;
            start = cur;
            end   = cur;

            if (cur == ins)
                ins = next;

            while (next && step + (len = AL_CHUNK_LEN(next)) <= n) {
                step += len;
                end  = next;
                next = NEXT(next, chunks);
                if (end == ins)
                    ins = next;
            }
            REMOVE2(al, chunks, start, end);

            al->bytes -= step;
            if (tal == NULL) {
                do {
                    cur = start;
                    start = NEXT(cur, chunks);
                    dispose_chunk(al, cur);
                } while (cur != end);
            } else {
                ADDTAIL2(tal, chunks, start, end);
                tal->bytes += step;
            }
        }
        n   -= step;
        pos += step;
        cur  = next;
        skip = 0;
    }

    /*
     * now splice in replacement chunks
     */
    if (doinsert) {
        if (ins != NULL) {
            /*
             * complex case where list is inserted
             *
             * the original list has already been modified so
             * that we can simply insert between two chunks
             */
            INSERTLIST(al,chunks,ins,nal);
        } else {
            /*
             * simple case where list end is 'replaced'
             */
            APPENDLIST(al,chunks,nal);
        }

        al->bytes += nal->bytes;
        nal->bytes = 0;

    }

    return AL_OK;
}

/*
 *
 */
al_rc_t
al_setlabel(al_t *al, size_t off, size_t n,
            al_label_t oldlabel, al_label_t newlabel)
{
    al_rc_t rc;
    al_chunk_t *cur, *splitbuf;
    size_t skip, len;

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

    /*
     * seek to beginning, return EOF when seek position does not exist
     * EOD must be a valid seek position so that we can append data
     */
    rc = al_seek(al, off, &cur, &skip);
    if (rc != AL_OK)
        return AL_RC(rc);

    /*
     * seek to EOD, nothing to label
     */
    if (cur == NULL)
        return AL_OK;

    /*
     * if first chunk doesn't need relabeling
     * then skip it, adjust seek size
     *
     * else if offset is not at chunk start
     * then split chunk at offset, continue
     * with second half
     */
    if (!AL_SAME_LABEL(cur, oldlabel) ||
        AL_SAME_LABEL(cur, newlabel)) {
        len = AL_CHUNK_LEN(cur) - skip;
        n = n < len ? 0 : n - len;
        cur = NEXT(cur, chunks);
    } else if (skip > 0) {
        rc = split_chunk(al, cur, skip, &splitbuf);
        if (rc != AL_OK)
            return AL_RC(rc);
        INSERT(al,chunks,cur,splitbuf);
    }

    /*
     * for all remaining chunks and bytes
     *
     * if chunk doesn't need relabeling
     * then skip it, adjust size
     *
     * else if chunk isn't covered in total
     * then split chunk at end offset and
     * process first half
     */
    while (n > 0 && cur != NULL) {
        len = AL_CHUNK_LEN(cur);
        if (!AL_SAME_LABEL(cur, oldlabel) ||
            AL_SAME_LABEL(cur, newlabel)) {
            n = n < len ? 0 : n - len;
        } else {
            if (n < len) {
                /*
                 * split last chunk at end offset
                 */
                rc = split_chunk(al, cur, n, &splitbuf);
                if (rc != AL_OK)
                    return AL_RC(rc);
                INSERT(al,chunks,cur,splitbuf);
                cur = splitbuf;
                len = AL_CHUNK_LEN(cur);
            }
            AL_CHUNK_LABEL(cur) = newlabel;
            n   -= len;
        }
        cur  = NEXT(cur, chunks);
    }

    return AL_OK;
}

/*
 * assembly line traversal requires a context. It needs to be
 * malloced to keep its inner structure private
 */
al_rc_t
al_txalloc(al_t *al, al_tx_t **txp)
{
    al_tx_t *tx;

    tx = (al_tx_t*)(al->m.malloc)(sizeof(al_tx_t));
    if (tx == NULL)
        return AL_RC(AL_ERR_MEM);

    *txp = tx;
    return AL_OK;
}

/*
 * free traversal context using proper policy function
 */
al_rc_t
al_txfree(al_t *al, al_tx_t *tx)
{
    (al->m.free)(tx);
    return AL_OK;
}

/*
 * initiate assembly line traversal
 *
 * - do initial seek, fail if position does not exist
 * - save traversal parameters
 */
al_rc_t
al_traverse(al_t *al, size_t off, size_t n, al_td_t dir, al_label_t label, al_tx_t *tx)
{
    al_rc_t rc;

    tx->cur = NULL;

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

    tx->dir   = dir;
    tx->togo  = n;
    tx->label = label;

    return AL_OK;
}

/*
 * assembly line traversal step
 *
 * return EOF if at end of assembly line
 * clip view chunk to traversal bounds
 * advance chunk cursor according to traversal direction
 */
al_rc_t
al_traverse_next(al_t *al, al_tx_t *tx, al_chunk_t **alcp)
{
    size_t step;

    do {
        if (tx->togo <= 0)     /* XXX - togo can be negative from bad input */
            return AL_ERR_EOF;

        if (tx->cur == NULL)   /* premature EOF */
            return AL_ERR_EOF;

        /* compute number of bytes to process */
        step = AL_CHUNK_SPAN(tx->cur, tx->skip, tx->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
         */
        tx->view        = *(tx->cur);
        tx->view.begin += tx->skip;
        tx->view.end    = tx->view.begin + step;

        switch (tx->dir) {
        case AL_FORWARD:
        case AL_BACKWARD:
            break;
        case AL_FORWARD_SPAN:
        case AL_BACKWARD_SPAN:
            if (!AL_SAME_LABEL(&tx->view, tx->label)) {
                tx->togo = 0;
                return AL_ERR_EOF;
            }
            break;
        }

        switch (tx->dir) {
            case AL_FORWARD:
            case AL_FORWARD_SPAN:
                tx->cur   = NEXT(tx->cur,chunks);
                tx->togo -= step;
                tx->skip  = 0;
                break;
            case AL_BACKWARD:
            case AL_BACKWARD_SPAN:
                tx->cur   = PREV(tx->cur,chunks);
                tx->togo -= step;
                tx->skip  = 0;
                break;
        }
    } while (!AL_SAME_LABEL(&tx->view, tx->label));

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

/*
 * assembly line traversal end
 *
 * to free resources allocated/locked during traversal
 * currently a NOOP
 */
al_rc_t al_traverse_end(al_t *al, al_tx_t *tx, int final)
{
    return AL_OK;
}

/*
 * full assembly line traversal with callback
 *
 * traversal is aborted when callback return != AL_OK
 * reaching EOF (and also aborting with AL_ERR_EOF) is not an error
 *
 * traversal context is kept on stack (XXX ?)
 */
al_rc_t
al_traverse_cb(al_t *al, size_t off, size_t n, al_td_t dir, al_label_t label,
               al_rc_t (*cb)(al_chunk_t *, void *), void *u)
{
    al_rc_t rc;
    al_tx_t tx;                /* XXX - private tx structure on stack */
    al_chunk_t *view;

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

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

    al_traverse_end(al, &tx, 1);

    if (rc != AL_ERR_EOF)
        return AL_RC(rc);

    return AL_OK;
}

/*
 * full assembly line traversal with data copy to linear buffer
 *
 * returns actual number of bytes copied
 *
 * Do not copy if destination pointer is NULL, but still count.
 * This can be used to precalculate the size of the needed linear
 * buffer with n set to some arbitrary huge value.
 *
 * traversal context is kept on stack (XXX ?)
 */
al_rc_t
al_flatten(al_t *al, size_t off, size_t n, al_td_t dir, al_label_t label,
           char *dst, size_t *lenp)
{
    al_rc_t rc;
    al_tx_t tx;                /* XXX - private tx structure on stack */
    al_chunk_t *view;
    size_t step, total;

    *lenp = 0; /* keep caller on safe side */

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

    switch (dir) {
    case AL_FORWARD:
    case AL_FORWARD_SPAN:
        break;
    case AL_BACKWARD:
    case AL_BACKWARD_SPAN:
        dst += n;
        break;
    }

    total = 0;

    if (dst == NULL) {
        while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK)
            total += AL_CHUNK_LEN(view);
    } else {
        while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK) {
            step = AL_CHUNK_LEN(view);
            switch (dir) {
            case AL_FORWARD:
            case AL_FORWARD_SPAN:
                memmove(dst, AL_CHUNK_PTR(view, 0), step);
                dst   += step;
                break;
            case AL_BACKWARD:
            case AL_BACKWARD_SPAN:
                dst   -= step;
                memmove(dst, AL_CHUNK_PTR(view, 0), step);
                break;
            }
            total += step;
        }
    }
    *lenp = total;

    al_traverse_end(al, &tx, 1);

    if (rc != AL_ERR_EOF)
        return AL_RC(rc);

    return AL_OK;
}

/*
 * full assembly line traversal with data copy to target assembly line
 *
 * traversal context is kept on stack (XXX ?)
 */
al_rc_t
al_copy(al_t *al, size_t off, size_t n, al_label_t label, al_t *tal)
{
    al_rc_t rc;
    al_tx_t tx;                /* XXX - private tx structure on stack */
    al_chunk_t *view;
    size_t step;

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

    while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK) {
        step = AL_CHUNK_LEN(view);
        al_append_bytes(tal, AL_CHUNK_PTR(view, 0), step, AL_CHUNK_LABEL(view));
    }

    al_traverse_end(al, &tx, 1);

    if (rc != AL_ERR_EOF)
        return AL_RC(rc);

    return AL_OK;
}

/*
 * traverse assembly line and retrieve first chunk
 *
 * traversal context is kept on stack (XXX ?)
 */
al_rc_t
al_firstlabel(al_t *al, size_t off, size_t n, al_td_t dir, al_label_t label,
              al_label_t *labelp)
{
    al_rc_t rc;
    al_tx_t tx;                /* XXX - private tx structure on stack */
    al_chunk_t *view;

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

    if ((rc = al_traverse_next(al, &tx, &view)) == AL_OK)
        *labelp = AL_CHUNK_LABEL(view);

    al_traverse_end(al, &tx, 1);

    return rc;
}

/*
 * traverse assembly line forward and search first chunk
 * that matches label and continue search until end of
 * span of same label
 *
 * return offset to first byte in *offp
 * return size of span to last byte in *spanp
 *
 * traversal context is kept on stack (XXX ?)
 */
al_rc_t
al_spanlabel(al_t *al, size_t off, size_t n, al_label_t label,
             size_t *offp, size_t *spanp)
{
    al_rc_t rc;
    al_tx_t tx;                /* XXX - private tx structure on stack */
    al_chunk_t *view;
    size_t len, total, start;
    int have_first;

    /*
     * we need to track absolute traversal position,
     * so we have to see all chunks.. no filtering
     * allowed
     */
    rc = al_traverse(al, off, n, AL_FORWARD, NULL, &tx);
    if (rc != AL_OK)
        return AL_RC(rc);

    have_first = 0;
    start      = 0;
    total      = 0;
    while ((rc = al_traverse_next(al, &tx, &view)) == AL_OK) {
        len = AL_CHUNK_LEN(view);
        if (AL_SAME_LABEL(view, label)) {
            if (!have_first) {
                start      = total;
                have_first = 1;
            }
        } else if (have_first)
            break;
        total += len;
    }

    al_traverse_end(al, &tx, 1);

    if (rc != AL_OK && rc != AL_ERR_EOF)
        return AL_RC(rc);

    if (!have_first)
        return AL_RC(AL_ERR_EOF);

    *offp   = off + start;
    *spanp  = total - start;

    return AL_OK;
}

/*
 * relay macros to caller
 *
 * al_bytes      - total number of bytes in assembly line
 * al_chunk_len  - number of bytes in chunk
 * al_chunk_span - clip interval (off,off+n( against chunk length
 * al_chunk_label- return chunk label
 * al_same_label - check if label matches with chunk label
 * al_chunk_ptr  - return memory pointer to byte within chunk
 *
 * off must be a valid offset within (0,len(
 */

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);
}

al_label_t
al_chunk_label(al_chunk_t *alc)
{
    return AL_CHUNK_LABEL(alc);
}

int
al_same_label(al_chunk_t *alc, al_label_t label)
{
    return AL_SAME_LABEL(alc, label);
}

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

/*
 * convert error code into human readable form
 */
const char *
al_error(al_rc_t rc)
{
    const char *mess;

    switch (rc) {
        case AL_OK:       mess = "Everything Ok"; break;
        case AL_ERR_ARG:  mess = "Invalid Argument"; break;
        case AL_ERR_MEM:  mess = "Not Enough Memory"; break;
        case AL_ERR_EOF:  mess = "End Of Data"; break;
        case AL_ERR_INT:  mess = "Internal Error"; break;
        default:          mess = "Invalid Result Code"; break;
    }

    return mess;
}