/************************************************************************** * * Copyright 2010 Luca Barbieri * Copyright 2023 Hannes Winkler * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice (including the * next paragraph) shall be included in all copies or substantial * portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * **************************************************************************/ #ifndef U_DYNARRAY_H #define U_DYNARRAY_H #include #include #include #include "macros.h" #ifdef __cplusplus extern "C" { #endif static unsigned util_dynarray_is_data_stack_allocated; /* A zero-initialized version of this is guaranteed to represent an * empty array. * * Also, size <= capacity and data != 0 if and only if capacity != 0 * capacity will always be the allocation size of data */ struct util_dynarray { void *mem_ctx; void *data; unsigned size; unsigned capacity; }; static inline void util_dynarray_init(struct util_dynarray *buf) { memset(buf, 0, sizeof(*buf)); buf->mem_ctx = NULL; } static inline void util_dynarray_init_with_memctx(struct util_dynarray *buf, void *mem_ctx) { memset(buf, 0, sizeof(*buf)); buf->mem_ctx = mem_ctx; } static inline void util_dynarray_init_from_stack(struct util_dynarray *buf, void *data, unsigned capacity) { memset(buf, 0, sizeof(*buf)); buf->mem_ctx = &util_dynarray_is_data_stack_allocated; buf->data = data; buf->capacity = capacity; } static inline void util_dynarray_fini(struct util_dynarray *buf) { if (buf->data) { if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated) { } else if (buf->mem_ctx) { free(buf->data); } else { free(buf->data); } util_dynarray_init(buf); } } static inline void util_dynarray_clear(struct util_dynarray *buf) { buf->size = 0; } #define DYN_ARRAY_INITIAL_SIZE 64 MUST_CHECK static inline void *util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap) { if (newcap > buf->capacity) { unsigned capacity = MAX3(DYN_ARRAY_INITIAL_SIZE, buf->capacity * 2, newcap); void *data; if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated) { data = malloc(capacity); if (data) { memcpy(data, buf->data, buf->size); buf->mem_ctx = NULL; } } else { data = realloc(buf->data, capacity); } if (!data) return NULL; buf->data = data; buf->capacity = capacity; } return (void *) ((char *) buf->data + buf->size); } /* use util_dynarray_trim to reduce the allocated storage */ MUST_CHECK static inline void *util_dynarray_resize_bytes(struct util_dynarray *buf, unsigned nelts, size_t eltsize) { if (UNLIKELY(nelts > UINT_MAX / eltsize)) return NULL; unsigned newsize = nelts * eltsize; void *p = util_dynarray_ensure_cap(buf, newsize); if (!p) return NULL; buf->size = newsize; return p; } static inline void util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx, struct util_dynarray *from_buf) { util_dynarray_init_with_memctx(buf, mem_ctx); if (util_dynarray_resize_bytes(buf, from_buf->size, 1)) { memcpy(buf->data, from_buf->data, from_buf->size); } } MUST_CHECK static inline void *util_dynarray_grow_bytes(struct util_dynarray *buf, unsigned ngrow, size_t eltsize) { unsigned growbytes = ngrow * eltsize; if (UNLIKELY(ngrow > (UINT_MAX / eltsize) || growbytes > UINT_MAX - buf->size)) return NULL; unsigned newsize = buf->size + growbytes; void *p = util_dynarray_ensure_cap(buf, newsize); if (!p) return NULL; buf->size = newsize; return p; } static inline void util_dynarray_trim(struct util_dynarray *buf) { if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated) return; if (buf->size != buf->capacity) { if (buf->size) { buf->data = realloc(buf->data, buf->size); buf->capacity = buf->size; } else { free(buf->data); buf->data = NULL; buf->capacity = 0; } } } static inline void util_dynarray_append_dynarray(struct util_dynarray *buf, const struct util_dynarray *other) { if (other->size > 0) { void *p = util_dynarray_grow_bytes(buf, 1, other->size); memcpy(p, other->data, other->size); } } #define util_dynarray_append(buf, type, v) \ do { \ type __v = (v); \ memcpy(util_dynarray_grow_bytes((buf), 1, sizeof(type)), &__v, sizeof(type)); \ } while (0) /* Returns a pointer to the space of the first new element (in case of growth) or NULL on failure. */ #define util_dynarray_resize(buf, type, nelts) util_dynarray_resize_bytes(buf, (nelts), sizeof(type)) #define util_dynarray_grow(buf, type, ngrow) util_dynarray_grow_bytes(buf, (ngrow), sizeof(type)) #define util_dynarray_top_ptr(buf, type) (type *) ((char *) (buf)->data + (buf)->size - sizeof(type)) #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type) #define util_dynarray_pop_ptr(buf, type) (type *) ((char *) (buf)->data + ((buf)->size -= sizeof(type))) #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type) #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type)) #define util_dynarray_element(buf, type, idx) ((type *) (buf)->data + (idx)) #define util_dynarray_begin(buf) ((buf)->data) #define util_dynarray_end(buf) ((void *) util_dynarray_element((buf), char, (buf)->size)) #define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type)) #define util_dynarray_foreach(buf, type, elem) \ for (type *elem = (type *) (buf)->data; elem < (type *) ((char *) (buf)->data + (buf)->size); elem++) #define util_dynarray_foreach_reverse(buf, type, elem) \ if ((buf)->size > 0) \ for (type *elem = util_dynarray_top_ptr(buf, type); elem; elem = elem > (type *) (buf)->data ? elem - 1 : NULL) #define util_dynarray_delete_unordered(buf, type, v) \ do { \ unsigned num_elements = (buf)->size / sizeof(type); \ unsigned i; \ for (i = 0; i < num_elements; i++) { \ type __v = *util_dynarray_element((buf), type, (i)); \ if (v == __v) { \ memcpy(util_dynarray_element((buf), type, (i)), util_dynarray_pop_ptr((buf), type), sizeof(type)); \ break; \ } \ } \ } while (0) #define util_dynarray_delete_unordered_ext(buf, type, v, equals_fn) \ do { \ unsigned num_elements = (buf)->size / sizeof(type); \ unsigned i; \ for (i = 0; i < num_elements; i++) { \ type __v = *util_dynarray_element((buf), type, (i)); \ if (equals_fn((v), __v)) { \ memcpy(util_dynarray_element((buf), type, (i)), util_dynarray_pop_ptr((buf), type), sizeof(type)); \ break; \ } \ } \ } while (0) #define util_dynarray_delete_where_unordered(buf, type, where_fn, userdata) \ do { \ unsigned num_elements = (buf)->size / sizeof(type); \ unsigned i; \ for (i = 0; i < num_elements; i++) { \ type __v = *util_dynarray_element((buf), type, (i)); \ if (where_fn((__v), userdata)) { \ memcpy(util_dynarray_element((buf), type, (i)), util_dynarray_pop_ptr((buf), type), sizeof(type)); \ } \ } \ } while (0) #define util_dynarray_delete_single_where_unordered(buf, type, where_fn, userdata) \ do { \ unsigned num_elements = (buf)->size / sizeof(type); \ unsigned i; \ for (i = 0; i < num_elements; i++) { \ type __v = *util_dynarray_element((buf), type, (i)); \ if (where_fn((__v), userdata)) { \ memcpy(util_dynarray_element((buf), type, (i)), util_dynarray_pop_ptr((buf), type), sizeof(type)); \ break; \ } \ } \ } while (0) #ifdef __cplusplus } #endif #endif /* U_DYNARRAY_H */