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

[Eric Blake]

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)

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?

> +
> +#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?

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org