From: Rusty Russell Date: Mon, 17 Sep 2018 01:17:42 +0000 (+0930) Subject: membuf: new module for linear memory buffers. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=86d30436820cacfc872de2ba518dd0b54b544647;hp=a8722345053b7cd860499aa31fd6bb414c120cc8 membuf: new module for linear memory buffers. Signed-off-by: Rusty Russell --- diff --git a/ccan/membuf/LICENSE b/ccan/membuf/LICENSE new file mode 120000 index 00000000..2354d129 --- /dev/null +++ b/ccan/membuf/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/membuf/_info b/ccan/membuf/_info new file mode 100644 index 00000000..bdcbce2b --- /dev/null +++ b/ccan/membuf/_info @@ -0,0 +1,51 @@ +#include "config.h" +#include +#include + +/** + * membuf - simple linear memory buffer routines. + * + * It's common to want a linear memory buffer, where you can get memory on + * the end, and consume memory from the start. The details of actually + * when to enlarge or move the buffer are slightly nontrivial, so they're + * encapsulated here. + * + * License: BSD-MIT + * Author: Rusty Russell + * + * Example: + * #include + * #include + * #include + * + * // Given "hello world" outputs helloworld + * // Given "hello there world" outputs hellothereworld + * int main(int argc, char *argv[]) + * { + * MEMBUF(char) charbuf; + * + * membuf_init(&charbuf, malloc(10), 10, membuf_realloc); + * + * for (int i = 1; i < argc; i++) + * strcpy(membuf_add(&charbuf, strlen(argv[i])), argv[i]); + * + * // This is dumb, we could do all at once, but shows technique. + * while (membuf_num_elems(&charbuf) > 0) + * printf("%c", *(char *)membuf_consume(&charbuf, 1)); + * printf("\n"); + * return 0; + * } + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/tcon\n"); + return 0; + } + + return 1; +} diff --git a/ccan/membuf/membuf.c b/ccan/membuf/membuf.c new file mode 100644 index 00000000..b3b2f08d --- /dev/null +++ b/ccan/membuf/membuf.c @@ -0,0 +1,60 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#include +#include +#include +#include + +void membuf_init_(struct membuf *mb, + void *elems, size_t num_elems, size_t elemsize, + void *(*expandfn)(struct membuf *, void *, size_t)) +{ + + mb->start = mb->end = 0; + mb->max_elems = num_elems; + mb->elems = elems; + mb->expandfn = expandfn; +} + +size_t membuf_prepare_space_(struct membuf *mb, + size_t num_extra, size_t elemsize) +{ + char *oldstart = membuf_elems_(mb, elemsize); + + /* Always reset in the trivial empty case. */ + if (mb->start == mb->end) + mb->start = mb->end = 0; + + if (membuf_num_space_(mb) >= num_extra) + return 0; + + /* There are two ways to make space: enlarge buffer, and memmove + * down. We use a simple heuristic: if we are using less than half + * the buffer, and memmove would get us sufficient space, do that. */ + if (membuf_num_elems_(mb) <= mb->max_elems / 2 + && membuf_num_elems_(mb) + num_extra <= mb->max_elems) { + memmove(mb->elems, oldstart, (mb->end - mb->start) * elemsize); + mb->end -= mb->start; + mb->start = 0; + } else { + void *expand; + + /* Since we're going to expand, at least double. */ + if (num_extra < mb->max_elems) + num_extra = mb->max_elems; + + expand = mb->expandfn(mb, mb->elems, + (mb->max_elems + num_extra) * elemsize); + if (!expand) { + errno = ENOMEM; + } else { + mb->max_elems += num_extra; + mb->elems = expand; + } + } + return (char *)membuf_elems_(mb, elemsize) - oldstart; +} + +void *membuf_realloc(struct membuf *mb, void *rawelems, size_t newsize) +{ + return realloc(rawelems, newsize); +} diff --git a/ccan/membuf/membuf.h b/ccan/membuf/membuf.h new file mode 100644 index 00000000..dcb48752 --- /dev/null +++ b/ccan/membuf/membuf.h @@ -0,0 +1,209 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#ifndef CCAN_MEMBUF_H +#define CCAN_MEMBUF_H +#include "config.h" +#include +#include + +/** + * struct membuf - representation of a memory buffer. + * + * It's exposed here to allow you to embed it and so we can inline the + * trivial functions. + */ +struct membuf { + /* These are the cursors into buf elements */ + size_t start; + size_t end; + + /* Number of elements in buf */ + size_t max_elems; + /* The buffer; at this low-level, untyped. */ + char *elems; + + void *(*expandfn)(struct membuf *, void *elems, size_t max_elems); +}; + +/** + * MEMBUF - declare a type-specific membuf + * @membertype: type for this buffer's values. + * + * You use this to create your own typed membuf. + * + * Example: + * MEMBUF(int *) intp_membuf; + * printf("Address of our int * membuf = %p\n", &intp_membuf); + */ +#define MEMBUF(membertype) \ + TCON_WRAP(struct membuf, membertype canary) + +/** + * membuf_init - initialize a type-specfic membuf. + * @mb: the MEMBUF() declared membuf. + * @elems: the initial buffer, if any. + * @max_elems: the initial space @elems, in number of elements. + * @expandfn: the function to enlarge buf (eg. membuf_realloc). + * + * Example: + * membuf_init(&intp_membuf, NULL, 0, membuf_realloc); + */ +#define membuf_init(mb, elems, num, expandfn) \ + membuf_init_(tcon_unwrap(tcon_check_ptr((mb), canary, (elems))), \ + (elems), (num), tcon_sizeof((mb), canary), (expandfn)) + +void membuf_init_(struct membuf *mb, + void *elems, size_t max_elems, size_t elemsize, + void *(*expandfn)(struct membuf *, void *, size_t)); + +/** + * membuf_realloc - simple membuf helper to do realloc(). + * + * Assumes initial buffer was NULL, or malloc(). + */ +void *membuf_realloc(struct membuf *mb, void *rawelems, size_t newsize); + +/** + * membuf_num_elems - number of populated elements in the membuf. + * @mb: the MEMBUF() declared membuf. + */ +#define membuf_num_elems(mb) membuf_num_elems_(tcon_unwrap(mb)) + +static inline size_t membuf_num_elems_(const struct membuf *mb) +{ + return mb->end - mb->start; +} + +/** + * membuf_elems - pointer to the populated elements in the membuf. + * @mb: the MEMBUF() declared membuf. + */ +#define membuf_elems(mb) \ + tcon_cast_ptr(mb, canary, \ + membuf_elems_(tcon_unwrap(mb), tcon_sizeof((mb), canary))) + +static inline void *membuf_elems_(const struct membuf *mb, size_t elemsize) +{ + return mb->elems + mb->start * elemsize; +} + +/** + * membuf_consume - we've used up this many membuf_elems. + * @mb: the MEMBUF() declared membuf. + * @num: the number of elems. + * + * Returns a pointer to the old start of membuf, so you can mark consumed + * and actually process in a single call. + */ +#define membuf_consume(mb, num) \ + tcon_cast_ptr(mb, canary, \ + membuf_consume_(tcon_unwrap(mb), (num), \ + tcon_sizeof((mb), canary))) + +static inline void *membuf_consume_(struct membuf *mb, + size_t num, size_t elemsize) +{ + void *old_start = membuf_elems_(mb, elemsize); + assert(num <= membuf_num_elems_(mb)); + mb->start += num; + + return old_start; +} + +/** + * membuf_num_space - number of unpopulated elements at end of the membuf. + * @mb: the MEMBUF() declared membuf. + */ +#define membuf_num_space(mb) membuf_num_space_(tcon_unwrap(mb)) + +static inline size_t membuf_num_space_(const struct membuf *mb) +{ + return mb->max_elems - mb->end; +} + +/** + * membuf_space - pointer to the unpopulated elements at end of membuf. + * @mb: the MEMBUF() declared membuf. + */ +#define membuf_space(mb) \ + tcon_cast_ptr(mb, canary, \ + membuf_space_(tcon_unwrap(mb), tcon_sizeof((mb), canary))) + +static inline void *membuf_space_(struct membuf *mb, size_t elemsize) +{ + return mb->elems + mb->end * elemsize; +} + +/** + * membuf_prepare_space - internal routine to make sure we've got space. + * @mb: the MEMBUF() declared membuf. + * @num_extra: the minimum number of elements of space we need + * + * Usually you wouldn't call this yourself; see membuf_add() below. But + * you might use this if you need to know about moves within mb->elements + * so you can adjust your own pointers/offsets. + * + * It returns the offset *in bytes* between the old locations and the new. + * This is because it may not be a whole number of elements, in the case + * of realloc! + * + * If you want to check for expandfn failure (which sets errno to + * ENOMEM), you can check if membuf_num_space() is < num_extra which will + * never otherwise happen. + */ +#define membuf_prepare_space(mb, num_extra) \ + membuf_prepare_space_(tcon_unwrap(mb), \ + (num_extra), \ + tcon_sizeof((mb), canary)) + +size_t membuf_prepare_space_(struct membuf *mb, + size_t num_extra, size_t elemsize); + +/** + * membuf_add - add to the end of the membuf. + * @mb: the MEMBUF() declared membuf. + * @num: the number of elements (must be that much space available!). + * + * Returns the pointer to the space just added, in case you want to + * populate it afterwards. + * + * Note that this may invalidate existing buf pointers! If you want to + * avoid that, call membuf_prepare_space(mb, num) first. + */ +#define membuf_add(mb, num) \ + tcon_cast_ptr(mb, canary, \ + membuf_add_(tcon_unwrap(mb), (num), \ + tcon_sizeof((mb), canary))) + +static inline void *membuf_add_(struct membuf *mb, size_t num, size_t elemsize) +{ + void *oldend; + membuf_prepare_space_(mb, num, elemsize); + + oldend = membuf_space_(mb, elemsize); + /* We assume expandfn succeeded. */ + assert(num <= membuf_num_space_(mb)); + mb->end += num; + + return oldend; +} + +/** + * membuf_cleanup - reset membuf, return elems array for freeing. + * @mb: the MEMBUF() declared membuf. + * + * The mb will be empty after this, and crash if you try to expand it. + * You can membuf_init() it again, however. + * + * Example: + * free(membuf_cleanup(&intp_membuf)); + */ +#define membuf_cleanup(mb) membuf_cleanup_(tcon_unwrap(mb)) + +static inline void *membuf_cleanup_(struct membuf *mb) +{ + mb->start = mb->end = mb->max_elems = 0; + mb->expandfn = NULL; + + return mb->elems; +} +#endif /* CCAN_MEMBUF_H */ diff --git a/ccan/membuf/test/run.c b/ccan/membuf/test/run.c new file mode 100644 index 00000000..08836e2a --- /dev/null +++ b/ccan/membuf/test/run.c @@ -0,0 +1,103 @@ +#include +#include +#include + +static int num_realloc, num_memmove; + +void *memmove_test(void *dest, const void *src, size_t n); +void *realloc_test(void *ptr, size_t size); + +void *memmove_test(void *dest, const void *src, size_t n) +{ + num_memmove++; + return memmove(dest, src, n); +} + +void *realloc_test(void *ptr, size_t size) +{ + num_realloc++; + return realloc(ptr, size); +} + +#undef memmove +#define memmove memmove_test + +#undef realloc +#define realloc realloc_test + +/* Include the C files directly. */ +#include +#include + +int main(void) +{ + int prev_reallocs; + MEMBUF(int) intbuf; + + /* This is how many tests you plan to run */ + plan_tests(13 + 100 * 4 + 999); + + membuf_init(&intbuf, malloc(10 * sizeof(int)), 10, membuf_realloc); + ok1(membuf_num_elems(&intbuf) == 0); + ok1(membuf_num_space(&intbuf) == 10); + ok1(membuf_space(&intbuf) != NULL); + + /* Add 100 ints. */ + for (int i = 0; i < 100; i++) { + memcpy(membuf_add(&intbuf, 1), &i, sizeof(i)); + ok1(membuf_num_elems(&intbuf) == i+1); + + /* Make sure membuf_elems works */ + if (i == 0) + ok1(memcmp(membuf_elems(&intbuf), &i, sizeof(i)) == 0); + } + + + /* Pull 100 ints. */ + for (int i = 0; i < 100; i++) { + ok1(memcmp(membuf_consume(&intbuf, 1), &i, sizeof(i)) == 0); + ok1(membuf_num_elems(&intbuf) == 100 - i - 1); + } + + /* Should not have continuously realloced or memmoved */ + ok1(num_realloc < 10); + ok1(num_memmove == 0); + + /* Doing it again should give 0 reallocs. */ + prev_reallocs = num_realloc; + for (int i = 0; i < 100; i++) { + memcpy(membuf_add(&intbuf, 1), &i, sizeof(i)); + ok1(membuf_num_elems(&intbuf) == i+1); + } + ok1(num_realloc == prev_reallocs); + ok1(num_memmove == 0); + + membuf_consume(&intbuf, 100); + + /* Keep a single element in the queue, make sure we don't realloc! */ + for (int i = 0; i < 1000; i++) { + memcpy(membuf_add(&intbuf, 1), &i, sizeof(i)); + if (i > 0) { + int prev = i - 1; + ok1(memcmp(membuf_consume(&intbuf, 1), + &prev, sizeof(prev)) == 0); + } + } + + ok1(num_realloc == prev_reallocs); + /* Should have moved occasionally. */ + ok1(num_memmove < 20); + + ok1(membuf_consume(&intbuf, 1)); + ok1(membuf_num_elems(&intbuf) == 0); + + /* Force it to more-than-double; make sure that works! */ + memset(membuf_add(&intbuf, 300), 0, 300*sizeof(int)); + ok1(membuf_num_elems(&intbuf) == 300); + + /* Free buffer so valgrind is happy. */ + free(membuf_cleanup(&intbuf)); + + /* This exits depending on whether all tests passed */ + return exit_status(); +}