[Libguestfs] [PATCH nbdkit 1/9] common: Add a generic implementation of vectors.

[Richard W.M. Jones]

On Wed, Apr 15, 2020 at 02:41:07PM -0500, Eric Blake wrote:
> On 4/15/20 11:16 AM, Richard W.M. Jones wrote:
> >Can be used for building up lists of things, especially
> >lists of strings.
> >---
> >  common/include/Makefile.am   |  6 +++
> >  common/include/test-vector.c | 90 +++++++++++++++++++++++++++++++++
> >  common/include/vector.h      | 96 ++++++++++++++++++++++++++++++++++++
> >  .gitignore                   |  1 +
> >  4 files changed, 193 insertions(+)
> >
> 
> >+++ b/common/include/vector.h
> 
> >+/* Simple implementation of appendable vector.  There are two main
> >+ * use-cases we consider: lists of strings (either with a defined
> >+ * length, or NULL-terminated), and lists of numbers.  It is generic
> >+ * so could be used for lists of anything (eg. structs) where being
> >+ * able to append easily is important.
> >+ */
> >+
> >+#ifndef NBDKIT_VECTOR_H
> >+#define NBDKIT_VECTOR_H
> >+
> >+#include <assert.h>
> >+
> >+#define DEFINE_VECTOR_TYPE(name, type)                                  \
> >+  struct name {                                                         \
> >+    type *ptr;                 /* Pointer to array of items. */         \
> >+    size_t size;               /* Number of valid items in the array. */ \
> >+    size_t alloc;              /* Number of items allocated. */         \
> >+  };                                                                    \
> >+  typedef struct name name;                                             \
> >+  static inline int                                                     \
> >+  name##_extend (name *v, size_t n)                                     \
> >+  {                                                                     \
> >+    return generic_vector_extend ((struct generic_vector *)v, n,        \
> >+                                  sizeof (type));                       \
> >+  }                                                                     \
> >+  static inline int                                                     \
> >+  name##_append (name *v, type elem)                                    \
> >+  {                                                                     \
> >+    if (v->size >= v->alloc) {                                          \
> >+      if (name##_extend (v, 1) == -1) return -1;                        \
> >+    }                                                                   \
> >+    v->ptr[v->size++] = elem;                                           \
> >+    return 0;                                                           \
> >+  }                                                                     \
> >+  static inline void                                                    \
> >+  name##_iter (name *v, void (*f) (type elem))                          \
> 
> Do we want an iterator that can take a void* opaque argument, as in:
> 
> name##_iter_arg (name *v, void (*f) (type elem, void *o), void *o)

I had something like this at some point in development, but dropped it
because it wasn't used in the final version.  We can always add these
things later if they are useful.

Actually one reason I dropped it was because a useful version of the
iterator would not only have a void* parameter, but would also pass
type* to the function (pointing to &ptr[i]).  This allows you to
iterate over the array if it contains large structs that you wouldn't
necessarily want to copy into the function parameter.

> Of course, since you want to pass 'free' to string_vector, you'll
> still want the form without an opaque argument as well.
>
> >+  {                                                                     \
> >+    size_t i;                                                           \
> >+    for (i = 0; i < v->size; ++i)                                       \
> >+      f (v->ptr[i]);                                                    \
> >+  }
> 
> Should we allow the callback to return a value, where returning 0
> can abort the iteration early?

This could be another variation :-) Again, I didn't have this because
it's not compatible with the only use (free).

> >+
> >+#define empty_vector { .ptr = NULL, .size = 0, .alloc = 0 }
> 
> Nice that this initializer is type-agnostic.
> 
> >+
> >+struct generic_vector {
> >+  void *ptr;
> >+  size_t size;
> >+  size_t alloc;
> >+};
> >+
> >+static int
> >+generic_vector_extend (struct generic_vector *v, size_t n, size_t itemsize)
> >+{
> >+  void *newptr;
> >+
> >+  newptr = realloc (v->ptr, (n + v->alloc) * itemsize);
> >+  if (newptr == NULL)
> >+    return -1;
> >+  v->ptr = newptr;
> >+  v->alloc += n;
> >+  return 0;
> >+}
> 
> Do we really want this implemented in the header?

No, it should be in a .c file.  I can update this in my copy.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
Fedora Windows cross-compiler. Compile Windows programs, test, and
build Windows installers. Over 100 libraries supported.
http://fedoraproject.org/wiki/MinGW