membuf: new module for linear memory buffers.
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 17 Sep 2018 01:17:42 +0000 (10:47 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 17 Sep 2018 01:17:42 +0000 (10:47 +0930)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/membuf/LICENSE [new symlink]
ccan/membuf/_info [new file with mode: 0644]
ccan/membuf/membuf.c [new file with mode: 0644]
ccan/membuf/membuf.h [new file with mode: 0644]
ccan/membuf/test/run.c [new file with mode: 0644]

diff --git a/ccan/membuf/LICENSE b/ccan/membuf/LICENSE
new file mode 120000 (symlink)
index 0000000..2354d12
--- /dev/null
@@ -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 (file)
index 0000000..bdcbce2
--- /dev/null
@@ -0,0 +1,51 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <rusty@rustcorp.com.au>
+ *
+ * Example:
+ * #include <ccan/membuf/membuf.h>
+ * #include <string.h>
+ * #include <stdio.h>
+ *
+ * // 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 (file)
index 0000000..b3b2f08
--- /dev/null
@@ -0,0 +1,60 @@
+/* MIT (BSD) license - see LICENSE file for details */
+#include <ccan/membuf/membuf.h>
+#include <errno.h>
+#include <string.h>
+#include <stdlib.h>
+
+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 (file)
index 0000000..dcb4875
--- /dev/null
@@ -0,0 +1,209 @@
+/* MIT (BSD) license - see LICENSE file for details */
+#ifndef CCAN_MEMBUF_H
+#define CCAN_MEMBUF_H
+#include "config.h"
+#include <assert.h>
+#include <ccan/tcon/tcon.h>
+
+/**
+ * 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 (file)
index 0000000..08836e2
--- /dev/null
@@ -0,0 +1,103 @@
+#include <ccan/membuf/membuf.h>
+#include <stdlib.h>
+#include <string.h>
+
+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 <ccan/membuf/membuf.c>
+#include <ccan/tap/tap.h>
+
+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();
+}