From a68ee34ebfbbc6e6bc653aadc284264e10694930 Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Mon, 14 May 2007 17:07:21 +0000 Subject: add bufferq structure git-svn-id: file:///home/lennart/svn/public/libsydney/trunk@17 9ba3c220-e4d3-45a2-8aa3-73fcc9aff6ce --- Makefile | 5 ++ TODO | 5 ++ bufferq.c | 235 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bufferq.h | 35 +++++++++ llist.h | 70 +++++++++++++++++ macro.h | 6 ++ test-bufferq.c | 39 ++++++++++ test-llist.c | 34 +++++++++ 8 files changed, 429 insertions(+) create mode 100644 bufferq.c create mode 100644 bufferq.h create mode 100644 llist.h create mode 100644 test-bufferq.c create mode 100644 test-llist.c diff --git a/Makefile b/Makefile index 4338843..c9a3eda 100644 --- a/Makefile +++ b/Makefile @@ -4,6 +4,11 @@ LIBS=-lm `pkg-config --libs liboil-0.3` SOURCES=common.c malloc.c test-sine.c oss.c bbuffer.c format.c volscale.c byteswap.c continued-fraction.c zero.c add.c speex/resample.c resample.c interleave.c converter.c g711.c OBJS=$(SOURCES:.c=.o) +test-bufferq: test-bufferq.o bufferq.o + $(CC) $(CFLAGS) -o $@ $^ + +test-llist: test-llist.o + $(CC) $(CFLAGS) -o $@ $^ test-sine: $(OBJS) $(CC) $(CFLAGS) -o $@ $^ $(LIBS) diff --git a/TODO b/TODO index a6ef411..982b82c 100644 --- a/TODO +++ b/TODO @@ -14,3 +14,8 @@ * pulse * windows + + +* s/sa_/syd_/g + +* vbr diff --git a/bufferq.c b/bufferq.c new file mode 100644 index 0000000..df22ec3 --- /dev/null +++ b/bufferq.c @@ -0,0 +1,235 @@ +#include + +#include "malloc.h" +#include "macro.h" +#include "bufferq.h" + +int bufferq_init(bufferq_t *q, unsigned nchannels, size_t sample_size) { + sa_assert(q); + sa_assert(sample_size > 0); + sa_assert(nchannels > 0); + + memset(q, 0, sizeof(*q)); + q->sample_size = sample_size; + q->nchannels = nchannels; + + if (!(q->items = sa_new0(bufferq_item_t*, nchannels))) + return SA_ERROR_OOM; + + if (!(q->last = sa_new0(bufferq_item_t*, nchannels))) { + sa_free(q->items); + q->items = NULL; + return SA_ERROR_OOM; + } + + return SA_SUCCESS; +} + +void bufferq_done(bufferq_t *q) { + unsigned u; + sa_assert(q); + + for (u = 0; u < q->nchannels; u++) { + bufferq_item_t *i; + + while ((i = q->items[u])) { + SA_LLIST_REMOVE(bufferq_item_t, bufferq, q->items[u], i); + sa_free(i); + } + } + + sa_free(q->items); + sa_free(q->last); +} + +static bufferq_item_t* bufferq_item_new(size_t size) { + bufferq_item_t *i; + sa_assert(size > 0); + + if (!(i = sa_malloc(ALIGN(sizeof(bufferq_item_t)) + size))) + return i; + + SA_LLIST_ITEM_INIT(bufferq_item_t, bufferq, i); + + return i; +} + +int bufferq_push(bufferq_t *q, unsigned channel, const void *data, size_t nbytes, int64_t offset, sa_seek_t whence) { + int64_t idx; + bufferq_item_t *i, *j; + + sa_assert(q); + + switch (whence) { + case SA_SEEK_RELATIVE: + idx = q->write_index + offset; + break; + case SA_SEEK_ABSOLUTE: + idx = offset; + break; + case SA_SEEK_RELATIVE_END: + idx = q->end_index + offset; + break; + case _SA_SEEK_MAX: + sa_assert_not_reached(); + } + + if (q->read_index > idx) { + int64_t l = q->read_index - idx; + + if (l > nbytes) + l = nbytes; + + idx += l; + data += l; + nbytes -= l; + + } + + i = q->items[channel]; + + while (i && nbytes > 0) { + + if (idx >= i->idx + i->size) { + /* The new data belongs behind the current node */ + + i = i->bufferq_next; + + } else if (idx < i->idx) { + size_t l; + /* The new data belongs before the current node (at least partially) */ + + l = nbytes; + + if (l > i->idx - idx) + l = i->idx - idx; + + if (!(j = bufferq_item_new(l))) + return SA_ERROR_OOM; + + memcpy(BUFFERQ_ITEM_DATA(j), data, l); + j->idx = idx; + j->size = l; + + SA_LLIST_INSERT_BEFORE(bufferq_item_t, bufferq, q->items[channel], i, j); + + idx += l; + data += l; + nbytes -= l; + + } else { + size_t l; + + /* The data belongs right in the current node somewhere */ + + l = nbytes; + + if (l > i->idx + i->size - idx) + l = i->idx + i->size - idx; + + memcpy((uint8_t*) BUFFERQ_ITEM_DATA(i) + (idx - i->idx), data, l); + + idx += l; + data += l; + nbytes -= l; + } + } + + if (nbytes > 0) { + sa_assert(!i); + + if (!(j = bufferq_item_new(nbytes))) + return SA_ERROR_OOM; + + memcpy(BUFFERQ_ITEM_DATA(j), data, nbytes); + j->idx = idx; + j->size = nbytes; + + if (q->last[channel]) + SA_LLIST_INSERT_AFTER(bufferq_item_t, bufferq, q->items[channel], q->last[channel], j); + else + SA_LLIST_PREPEND(bufferq_item_t, bufferq, q->items[channel], j); + + q->last[channel] = j; + } + + q->write_index = idx + nbytes; + + if (q->write_index > q->end_index) + q->end_index = q->write_index; + + return SA_SUCCESS; +} + +int bufferq_get(bufferq_t *q, void *i[], size_t *bytes) { + int first = 1; + unsigned u; + sa_assert(q); + + *bytes = 0; + + for (u = 0; u < q->nchannels; u++) { + + if (q->items[u]) { + + if (q->items[u]->idx > q->read_index) { + int64_t l; + i[u] = NULL; + + l = q->items[u]->idx - q->read_index; + + if (first) { + *bytes = l; + first = 0; + } else + *bytes = l < *bytes ? l : *bytes; + } else { + int64_t l; + + i[u] = (uint8_t*) BUFFERQ_ITEM_DATA(q->items[u]) + q->read_index - q->items[u]->idx; + + l = q->items[u]->size - (q->read_index - q->items[u]->idx); + + if (first) { + *bytes = l; + first = 0; + } else + *bytes = l < *bytes ? l : *bytes; + } + + } else + i[u] = NULL; + } + + return SA_SUCCESS; +} + + +int bufferq_drop(bufferq_t *q, int64_t bytes) { + unsigned u; + + sa_assert(q); + + q->read_index += bytes; + + for (u = 0; u < q->nchannels; u++) { + + bufferq_item_t *i; + + i = q->items[u]; + + while (i && q->read_index >= i->idx + i->size) { + bufferq_item_t *n = i->bufferq_next; + + SA_LLIST_REMOVE(bufferq_item_t, bufferq, q->items[u], i); + + sa_free(i); + i = n; + } + + if (!i) + q->last[u] = NULL; + } + + return SA_SUCCESS; +} diff --git a/bufferq.h b/bufferq.h new file mode 100644 index 0000000..da4eac3 --- /dev/null +++ b/bufferq.h @@ -0,0 +1,35 @@ +#ifndef foosydneybufferqhfoo +#define foosydneybufferqhfoo + +#include + +#include "macro.h" +#include "llist.h" +#include "sydney.h" + +typedef struct bufferq_item { + int64_t idx; + size_t size; + SA_LLIST_ITEM(struct bufferq_item, bufferq); +} bufferq_item_t; + +#define BUFFERQ_ITEM_DATA(x) ((void*) (uint8_t*) (x) + ALIGN(sizeof(bufferq_item_t))) + +typedef struct bufferq { + SA_LLIST_HEAD(bufferq_item_t, *items); + bufferq_item_t **last; + int64_t read_index, write_index, end_index; + size_t sample_size; + unsigned nchannels; +} bufferq_t; + +int bufferq_init(bufferq_t *q, unsigned nchannels, size_t sample_size); + +void bufferq_done(bufferq_t *q); + +int bufferq_push(bufferq_t *q, unsigned channel, const void *data, size_t nbytes, int64_t offset, sa_seek_t whence); + +int bufferq_get(bufferq_t *q, void *i[], size_t *bytes); +int bufferq_drop(bufferq_t *q, int64_t bytes); + +#endif diff --git a/llist.h b/llist.h new file mode 100644 index 0000000..3d42218 --- /dev/null +++ b/llist.h @@ -0,0 +1,70 @@ +#ifndef foosydneyllistfoo +#define foosydneyllistfoo + + +#include "macro.h" + +#define SA_LLIST_HEAD(t,head) t* head + +#define SA_LLIST_ITEM(t,name) t* name##_prev, *name##_next + +#define SA_LLIST_HEAD_INIT(t,head) (head) = (t*) NULL + +#define SA_LLIST_ITEM_INIT(t,name,item) do { \ + t *_item = (item); \ + sa_assert(_item); \ + _item->name##_prev = _item->name##_next = NULL; \ + } while(0) + +#define SA_LLIST_PREPEND(t,name,head,item) do { \ + t **_head = &(head), *_item = (item); \ + sa_assert(_item); \ + if ((_item->name##_next = *_head)) \ + _item->name##_next->name##_prev = _item; \ + _item->name##_prev = NULL; \ + *_head = _item; \ + } while (0) + +#define SA_LLIST_INSERT_BEFORE(t,name,head,at,item) do { \ + t **_head = &(head), *_item = (item), *_at = (at); \ + sa_assert(_item); \ + sa_assert(_at); \ + if ((_item->name##_prev = _at->name##_prev)) { \ + sa_assert(_item->name##_prev->name##_next == _at); \ + _item->name##_prev->name##_next = _item; \ + } else {\ + sa_assert(*_head == _at); \ + *_head = _item; \ + } \ + _item->name##_next = _at; \ + _at->name##_prev = _item; \ + } while (0) + +#define SA_LLIST_INSERT_AFTER(t,name,head,at,item) do { \ + t *_item = (item), *_at = (at); \ + sa_assert(_item); \ + sa_assert(_at); \ + if ((_item->name##_next = _at->name##_next)) { \ + sa_assert(_item->name##_next->name##_prev == _at); \ + _item->name##_next->name##_prev = _item; \ + } \ + _item->name##_prev = _at; \ + _at->name##_next = _item; \ + } while (0) + +#define SA_LLIST_REMOVE(t,name,head,item) do { \ + t **_head = &(head), *_item = (item); \ + sa_assert(_item); \ + if (_item->name##_next) \ + _item->name##_next->name##_prev = _item->name##_prev; \ + if (_item->name##_prev) \ + _item->name##_prev->name##_next = _item->name##_next; \ + else {\ + sa_assert(*_head == _item); \ + *_head = _item->name##_next; \ + } \ + _item->name##_next = _item->name##_prev = NULL; \ + } while(0) + + +#endif diff --git a/macro.h b/macro.h index 368555d..847bf97 100644 --- a/macro.h +++ b/macro.h @@ -39,4 +39,10 @@ #define MIN(a, b) ((a) < (b) ? (a) : (b)) #endif +static inline size_t align(size_t l) { + return (((l + sizeof(void*) - 1) / sizeof(void*)) * sizeof(void*)); +} + +#define ALIGN(x) (align(x)) + #endif diff --git a/test-bufferq.c b/test-bufferq.c new file mode 100644 index 0000000..d4585e2 --- /dev/null +++ b/test-bufferq.c @@ -0,0 +1,39 @@ +#include "bufferq.h" + +int main(int argc, char *argv[]) { + + bufferq_t q; + + bufferq_init(&q, 1, 1); + + bufferq_push(&q, 0, "{AAAAAAAA}", 10, 0, SA_SEEK_RELATIVE); + bufferq_push(&q, 0, "", 10, 5, SA_SEEK_RELATIVE); + bufferq_push(&q, 0, "[CCCC]", 6, -18, SA_SEEK_RELATIVE); + bufferq_push(&q, 0, "(DDDD)", 6, -3, SA_SEEK_ABSOLUTE); + bufferq_push(&q, 0, "XXX", 3, 10, SA_SEEK_RELATIVE_END); + bufferq_push(&q, 0, "YYYYY", 5, -4, SA_SEEK_RELATIVE); + + for (;;) { + void *b[1]; + size_t size; + + bufferq_get(&q, b, &size); + + if (size == 0) + break; + + printf("Got %u bytes: ", size); + if (b[0]) + fwrite(b[0], size, 1, stdout); + else + printf("empty"); + + printf("\n"); + + bufferq_drop(&q, size); + } + + bufferq_done(&q); + + return 0; +} diff --git a/test-llist.c b/test-llist.c new file mode 100644 index 0000000..2059ef8 --- /dev/null +++ b/test-llist.c @@ -0,0 +1,34 @@ +#include "llist.h" + +struct foobar { + SA_LLIST_ITEM(struct foobar, list); +}; + + +static SA_LLIST_HEAD(struct foobar, list); + +int main(int argc, char *argv[]) { + struct foobar a, b, c; + + SA_LLIST_HEAD_INIT(struct foobar, list); + + SA_LLIST_ITEM_INIT(struct foobar, list, &a); + SA_LLIST_ITEM_INIT(struct foobar, list, &b); + SA_LLIST_ITEM_INIT(struct foobar, list, &c); + + SA_LLIST_PREPEND(struct foobar, list, list, &a); + SA_LLIST_INSERT_BEFORE(struct foobar, list, list, &a, &b); + SA_LLIST_INSERT_AFTER(struct foobar, list, list, &a, &c); + + sa_assert(list == &b); + sa_assert(list->list_next == &a); + sa_assert(list->list_next->list_next == &c); + + SA_LLIST_REMOVE(struct foobar, list, list, &a); + SA_LLIST_REMOVE(struct foobar, list, list, &b); + SA_LLIST_REMOVE(struct foobar, list, list, &c); + + sa_assert(!list); + + return 0; +} -- cgit