*** /dev/null Sat Nov 23 02:13:36 2024
--- - Sat Nov 23 02:13:50 2024
***************
*** 0 ****
--- 1,675 ----
+ #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 */
+
+ 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 <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 */
+ 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);
+ }
+
|
