1 /* nbdkit 2 * Copyright (C) 2020 Red Hat Inc. 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 #define DEFINE_VECTOR_TYPE(name, type) \ 48 struct name { \ 49 type *ptr; /* Pointer to array of items. */ \ 50 size_t size; /* Number of valid items in the array. */ \ 51 size_t alloc; /* Number of items allocated. */ \ 52 }; \ 53 typedef struct name name; \ 54 static inline int \ 55 name##_reserve (name *v, size_t n) \ 56 { \ 57 return generic_vector_reserve ((struct generic_vector *)v, n, \ 58 sizeof (type)); \ 59 } \ 60 /* Insert at i'th element. i=0 => beginning i=size => append */ \ 61 static inline int \ 62 name##_insert (name *v, type elem, size_t i) \ 63 { \ 64 if (v->size >= v->alloc) { \ 65 if (name##_reserve (v, 1) == -1) return -1; \ 66 } \ 67 memmove (&v->ptr[i+1], &v->ptr[i], (v->size-i) * sizeof (elem)); \ 68 v->ptr[i] = elem; \ 69 v->size++; \ 70 return 0; \ 71 } \ 72 static inline int \ 73 name##_append (name *v, type elem) \ 74 { \ 75 return name##_insert (v, elem, v->size); \ 76 } \ 77 static inline void \ 78 name##_iter (name *v, void (*f) (type elem)) \ 79 { \ 80 size_t i; \ 81 for (i = 0; i < v->size; ++i) \ 82 f (v->ptr[i]); \ 83 } 84 85 #define empty_vector { .ptr = NULL, .size = 0, .alloc = 0 } 86 87 struct generic_vector { 88 void *ptr; 89 size_t size; 90 size_t alloc; 91 }; 92 93 extern int generic_vector_reserve (struct generic_vector *v, 94 size_t n, size_t itemsize); 95 96 #endif /* NBDKIT_VECTOR_H */ 97