ossp-pkg/sio/al.c
1.2
#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);
}