common/utils/vector.h

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /* Simple implementation of a vector.  It can be cheaply appended, and
  34  * more expensively inserted.  There are two main use-cases we
  35  * consider: lists of strings (either with a defined length, or
  36  * NULL-terminated), and lists of numbers.  It is generic so could be
  37  * used for lists of anything (eg. structs) where being able to append
  38  * easily is important.
  39  */
  40
  41 #ifndef NBDKIT_VECTOR_H
  42 #define NBDKIT_VECTOR_H
  43
  44 #include <assert.h>
  45 #include <string.h>
  46
  47 #include "compiler-macros.h"
  48 #include "static-assert.h"
  49
  50 #ifdef __clang__
  51 #pragma clang diagnostic ignored "-Wunused-function"
  52 #pragma clang diagnostic ignored "-Wduplicate-decl-specifier"
  53 #endif
  54
  55 /* Use of this macro defines a new type called ‘name’ containing an
  56  * extensible vector of ‘type’ elements.  For example:
  57  *
  58  *   DEFINE_VECTOR_TYPE (string_vector, char *);
  59  *
  60  * defines a new type called ‘string_vector’ as a vector of ‘char *’.
  61  * You can create variables of this type:
  62  *
  63  *   string_vector names = empty_vector;
  64  *
  65  * where ‘names.ptr[]’ will be an array of strings and ‘names.len’
  66  * will be the number of strings.  There are no get/set accessors.  To
  67  * iterate over the strings you can use the ‘.ptr’ field directly:
  68  *
  69  *   for (size_t i = 0; i < names.len; ++i)
  70  *     printf ("%s\n", names.ptr[i]);
  71  *
  72  * Initializing with ‘empty_vector’ sets ‘.ptr = NULL’ and ‘.len = 0’.
  73  *
  74  * DEFINE_VECTOR_TYPE also defines utility functions.  For the full
  75  * list see the definition below, but useful functions include:
  76  *
  77  * ‘name’_append  (eg. ‘string_vector_append’)
  78  *   - Append a new element at the end.  This operation is cheap.
  79  *
  80  * ‘name’_insert  (eg. ‘string_vector_insert’)
  81  *   - Insert a new element at the beginning, middle or end.  This
  82  *     operation is more expensive because existing elements may need
  83  *     to be copied around.
  84  *
  85  * Both functions extend the vector if required, and so both may fail
  86  * (returning -1) which you must check for.
  87  */
  88 #define DEFINE_VECTOR_TYPE(name, type)                                  \
  89   struct name {                                                         \
  90     type *ptr;              /* Pointer to array of items. */            \
  91     size_t len;             /* Number of valid items in the array. */   \
  92     size_t cap;             /* Maximum number of items. */              \
  93   };                                                                    \
  94   typedef struct name name;                                             \
  95                                                                         \
  96   /* Reserve n elements at the end of the vector.  Note space is        \
  97    * allocated and capacity is increased, but the vector length is      \
  98    * not increased and the new elements are not initialized.            \
  99    */                                                                   \
 100   static inline int __attribute__ ((__unused__))                        \
 101   name##_reserve (name *v, size_t n)                                    \
 102   {                                                                     \
 103     return generic_vector_reserve ((struct generic_vector *)v, n,       \
 104                                    sizeof (type));                      \
 105   }                                                                     \
 106                                                                         \
 107   /* Same as _reserve, but the allocation will be page aligned.  Note   \
 108    * that the machine page size must be divisible by sizeof (type).     \
 109    */                                                                   \
 110   static inline int __attribute__ ((__unused__))                        \
 111   name##_reserve_page_aligned (name *v, size_t n)                       \
 112   {                                                                     \
 113     return generic_vector_reserve_page_aligned ((struct generic_vector *)v, \
 114                                                 n, sizeof (type));      \
 115   }                                                                     \
 116                                                                         \
 117   /* Insert at i'th element.  i=0 => beginning  i=len => append */      \
 118   static inline int __attribute__ ((__unused__))                        \
 119   name##_insert (name *v, type elem, size_t i)                          \
 120   {                                                                     \
 121     assert (i <= v->len);                                               \
 122     if (v->len >= v->cap) {                                             \
 123       if (name##_reserve (v, 1) == -1) return -1;                       \
 124     }                                                                   \
 125     memmove (&v->ptr[i+1], &v->ptr[i], (v->len-i) * sizeof (elem));     \
 126     v->ptr[i] = elem;                                                   \
 127     v->len++;                                                           \
 128     return 0;                                                           \
 129   }                                                                     \
 130                                                                         \
 131   /* Append a new element to the end of the vector. */                  \
 132   static inline int __attribute__ ((__unused__))                        \
 133   name##_append (name *v, type elem)                                    \
 134   {                                                                     \
 135     return name##_insert (v, elem, v->len);                             \
 136   }                                                                     \
 137                                                                         \
 138   /* Remove i'th element.  i=0 => beginning  i=len-1 => end */          \
 139   static inline void __attribute__ ((__unused__))                       \
 140   name##_remove (name *v, size_t i)                                     \
 141   {                                                                     \
 142     assert (i < v->len);                                                \
 143     memmove (&v->ptr[i], &v->ptr[i+1], (v->len-i-1) * sizeof (type));   \
 144     v->len--;                                                           \
 145   }                                                                     \
 146                                                                         \
 147   /* Remove all elements and deallocate the vector. */                  \
 148   static inline void __attribute__ ((__unused__))                       \
 149   name##_reset (name *v)                                                \
 150   {                                                                     \
 151     free (v->ptr);                                                      \
 152     v->ptr = NULL;                                                      \
 153     v->len = v->cap = 0;                                                \
 154   }                                                                     \
 155                                                                         \
 156   /* Iterate over the vector, calling f() on each element. */           \
 157   static inline void __attribute__ ((__unused__))                       \
 158   name##_iter (name *v, void (*f) (type elem))                          \
 159   {                                                                     \
 160     size_t i;                                                           \
 161     for (i = 0; i < v->len; ++i)                                        \
 162       f (v->ptr[i]);                                                    \
 163   }                                                                     \
 164                                                                         \
 165   /* Sort the elements of the vector. */                                \
 166   static inline void __attribute__ ((__unused__))                       \
 167   name##_sort (name *v,                                                 \
 168                int (*compare) (const type *p1, const type *p2))         \
 169   {                                                                     \
 170     qsort (v->ptr, v->len, sizeof (type), (void *) compare);            \
 171   }                                                                     \
 172                                                                         \
 173   /* Search for an exactly matching element in the vector using a       \
 174    * binary search.  Returns a pointer to the element or NULL.          \
 175    */                                                                   \
 176   static inline type * __attribute__ ((__unused__))                     \
 177   name##_search (const name *v, const void *key,                        \
 178                  int (*compare) (const void *key, const type *v))       \
 179   {                                                                     \
 180     return bsearch (key, v->ptr, v->len, sizeof (type),                 \
 181                     (void *) compare);                                  \
 182   }                                                                     \
 183                                                                         \
 184   /* Make a new vector with the same elements. */                       \
 185   static inline int __attribute__ ((__unused__))                        \
 186   name##_duplicate (name *v, name *copy)                                \
 187   {                                                                     \
 188     /* Note it's allowed for v and copy to be the same pointer. */      \
 189     type *vptr = v->ptr;                                                \
 190     type *newptr;                                                       \
 191     size_t len = v->len * sizeof (type);                                \
 192                                                                         \
 193     newptr = malloc (len);                                              \
 194     if (newptr == NULL) return -1;                                      \
 195     memcpy (newptr, vptr, len);                                         \
 196     copy->ptr = newptr;                                                 \
 197     copy->len = copy->cap = v->len;                                     \
 198     return 0;                                                           \
 199   }                                                                     \
 200                                                                         \
 201   /* End with duplicate declaration, so callers must supply ';'. */     \
 202   struct name
 203
 204 #define empty_vector { .ptr = NULL, .len = 0, .cap = 0 }
 205
 206 /* This macro should only be used if:
 207  * - the vector contains pointers, and
 208  * - the pointed-to objects are:
 209  *   - neither const- nor volatile-qualified, and
 210  *   - allocated with malloc() or equivalent.
 211  */
 212 #define ADD_VECTOR_EMPTY_METHOD(name)                                  \
 213   /* Call free() on each element of the vector, then reset the vector. \
 214    */                                                                  \
 215   static inline void __attribute__ ((__unused__))                      \
 216   name##_empty (name *v)                                               \
 217   {                                                                    \
 218     size_t i;                                                          \
 219     for (i = 0; i < v->len; ++i) {                                     \
 220       STATIC_ASSERT (TYPE_IS_POINTER (v->ptr[i]),                      \
 221                      _vector_contains_pointers);                       \
 222       free (v->ptr[i]);                                                \
 223     }                                                                  \
 224     name##_reset (v);                                                  \
 225   }                                                                    \
 226                                                                        \
 227   /* Force callers to supply ';'. */                                   \
 228   struct name
 229
 230 /* Convenience macro tying together DEFINE_VECTOR_TYPE() and
 231  * ADD_VECTOR_EMPTY_METHOD(). Inherit and forward the requirement for a
 232  * trailing semicolon from ADD_VECTOR_EMPTY_METHOD() to the caller.
 233  */
 234 #define DEFINE_POINTER_VECTOR_TYPE(name, type) \
 235   DEFINE_VECTOR_TYPE (name, type);             \
 236   ADD_VECTOR_EMPTY_METHOD (name)
 237
 238 struct generic_vector {
 239   void *ptr;
 240   size_t len;
 241   size_t cap;
 242 };
 243
 244 extern int generic_vector_reserve (struct generic_vector *v,
 245                                    size_t n, size_t itemsize);
 246
 247 extern int generic_vector_reserve_page_aligned (struct generic_vector *v,
 248                                                 size_t n, size_t itemsize);
 249
 250 #endif /* NBDKIT_VECTOR_H */