Index: ossp-pkg/sio/al.c RCS File: /v/ossp/cvs/ossp-pkg/sio/Attic/al.c,v co -q -kk -p'1.1' '/v/ossp/cvs/ossp-pkg/sio/Attic/al.c,v' | diff -u /dev/null - -L'ossp-pkg/sio/al.c' 2>/dev/null --- ossp-pkg/sio/al.c +++ - 2024-05-19 08:58:24.006467274 +0200 @@ -0,0 +1,675 @@ +#include +#include +#include + +#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 */ + +struct al_st { + LIST(al_chunk_t) chunks; + size_t bytes; +}; + +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) + +#define AL_NEW_BUFFERSIZE 100 +#define AL_MAX_FREECHUNKS 500 + +/* + * allocate backing store and its control structure from heap + * can be freed when usecount drops to zero + */ +static +al_rc_t new_buffer(al_buffer_t **bufp) +{ + size_t n = AL_NEW_BUFFERSIZE; + al_buffer_t *buf; + + if ((buf = (al_buffer_t *)malloc(sizeof(al_buffer_t))) == NULL) + return AL_ERR_MEM; + + if ((buf->mem = malloc(n)) == NULL) { + 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_buffer_t *buf) +{ + /* must not happen */ + if (buf->usecount != 0) + return AL_ERR_INT; + + if (buf->freemem) + free(buf->mem); + + 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(char *p, size_t n, al_buffer_t **bufp) +{ + al_buffer_t *buf; + + if ((buf = (al_buffer_t *)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_buffer_t *buf, al_chunk_t **alcp) +{ + al_chunk_t *alc; + + if (ISEMPTY(&alc_freelist, chunks)) { + if ((alc = (al_chunk_t *)malloc(sizeof(al_chunk_t))) == NULL) { + if (buf->usecount == 0) + dispose_buffer(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_chunk_t *alc) +{ + --alc->buf->usecount; + if (alc->buf->usecount == 0) + dispose_buffer(alc->buf); + alc->buf = NULL; + + /* stop freelist from growing infinitely */ + if (alc_freecount >= AL_MAX_FREECHUNKS) { + 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 +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 */ + if ((al = (al_t *)malloc(sizeof(al_t))) == NULL) + return AL_RC(AL_ERR_MEM); + + LISTINIT(al,chunks); + al->bytes = 0; + + /* 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(cur); + } + + /* free object itself */ + 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(&buf); + /* XXX handle error */ + rc = new_chunk(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(&buf); + if (rc != AL_OK) return rc; + rc = new_chunk(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(p, n, &buf); + if (rc != AL_OK) return rc; + rc = new_chunk(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(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); +} + Index: ossp-pkg/sio/al.h RCS File: /v/ossp/cvs/ossp-pkg/sio/Attic/al.h,v co -q -kk -p'1.1' '/v/ossp/cvs/ossp-pkg/sio/Attic/al.h,v' | diff -u /dev/null - -L'ossp-pkg/sio/al.h' 2>/dev/null --- ossp-pkg/sio/al.h +++ - 2024-05-19 08:58:24.009776865 +0200 @@ -0,0 +1,45 @@ +typedef enum { + AL_OK, + AL_ERR_ARG, + AL_ERR_MEM, + AL_ERR_EOF, + AL_ERR_INT +} al_rc_t; + +struct al_st; +typedef struct al_st al_t; + +struct al_chunk_st; +typedef struct al_chunk_st al_chunk_t; + +struct al_buffer_st; +typedef struct al_buffer_st al_buffer_t; + +typedef enum { + AL_FORWARD, + AL_BACKWARD +} al_td_t; + +#define AL_BYTES_ALL (-1) + +struct al_tx_st; +typedef struct al_tx_st al_tx_t; + +al_rc_t al_create(al_t **alp); +al_rc_t al_destroy(al_t *al); +al_rc_t al_append_bytes(al_t *al, const char *src, size_t n); +al_rc_t al_prepend_bytes(al_t *al, const char *src, size_t n); +al_rc_t al_attach_buffer(al_t *al, char *p, size_t n); +al_rc_t al_splice(al_t *al, size_t off, size_t n, al_t *tal); +al_rc_t al_truncate(al_t *al, size_t off, size_t n); +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 al_traverse_next(al_t *al, al_tx_t *txp, al_chunk_t **alcp); +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 al_flatten(al_t *al, size_t off, size_t n, char *dst); + +size_t al_bytes(const al_t *al); +size_t al_chunk_len(al_chunk_t *alc); +size_t al_chunk_span(al_chunk_t *alc, size_t off, size_t n); +char *al_chunk_ptr(al_chunk_t *alc, size_t off); + Index: ossp-pkg/sio/al_test.c RCS File: /v/ossp/cvs/ossp-pkg/sio/Attic/al_test.c,v co -q -kk -p'1.1' '/v/ossp/cvs/ossp-pkg/sio/Attic/al_test.c,v' | diff -u /dev/null - -L'ossp-pkg/sio/al_test.c' 2>/dev/null --- ossp-pkg/sio/al_test.c +++ - 2024-05-19 08:58:24.012476065 +0200 @@ -0,0 +1,76 @@ +#include +#include +#include + +#include "al.h" + +#define S(s) s, strlen(s) + +al_rc_t printchunk(al_chunk_t *alc, void *u) +{ + printf("C: %8p = %8p + %d\n", + alc, + al_chunk_ptr(alc, 0), + al_chunk_len(alc)); + + return AL_OK; +} + +#define DUMP(tag,al) do {\ +printf("+DUMP(%s)\n",tag);\ +al_traverse_cb(al, 0, al_bytes(al), AL_FORWARD, printchunk, NULL);\ +printf("-DUMP(%s)\n\n",tag);\ +} while (0) + +int main() +{ + al_t *al, *al2; + char buf[10000]; + size_t n; + char baf[] = "Mittendrin\n"; + int i; + + al_create(&al); + al_create(&al2); + + al_append_bytes(al, S("Hello world\n")); + al_attach_buffer(al, S(baf)); + + for (i=0; i<500; ++i) + al_append_bytes(al, S("Huhu world\n")); + + al_append_bytes(al, S("Hello world\n")); + + + DUMP("ALL",al); +#if 1 + al_splice(al, 102, 200, al2); +#else + al_splice(al, 102, 200, NULL); +#endif + DUMP("SPLICED",al); + DUMP("BUFFER",al2); + + printf("RESULT\n"); + n = al_bytes(al); + if (n > 10000) n = 10000; + al_flatten(al, 0, n, buf); + fwrite(">>", 2, 1, stdout); + fwrite(buf, n, 1, stdout); + fwrite("<<", 2, 1, stdout); + + printf("BUFFER\n"); + n = al_bytes(al2); + if (n > 10000) n = 10000; + al_flatten(al2, 0, n, buf); + fwrite(">>", 2, 1, stdout); + fwrite(buf, n, 1, stdout); + fwrite("<<", 2, 1, stdout); + + + al_destroy(al2); + al_destroy(al); + + + return 0; +}