| /************************************************************************** | |
| * | |
| * Copyright 2010 Luca Barbieri | |
| * | |
| * 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 <stdlib.h> | |
| #include <string.h> | |
| #include <limits.h> | |
| #include "ralloc.h" | |
| #ifdef __cplusplus | |
| extern "C" { | |
| #endif | |
| extern unsigned util_dynarray_is_data_stack_allocated; | |
| /* 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; | |
| }; | |
| /* A zero-initialized util_dynarray represents an empty array. */ | |
| #ifdef __cplusplus | |
| #define UTIL_DYNARRAY_INIT { 0 } | |
| #else | |
| #define UTIL_DYNARRAY_INIT (struct util_dynarray){ .capacity = 0 } | |
| #endif | |
| static inline void | |
| util_dynarray_init(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) { | |
| ralloc_free(buf->data); | |
| } else { | |
| free(buf->data); | |
| } | |
| util_dynarray_init(buf, buf->mem_ctx); | |
| } | |
| } | |
| 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 if (buf->mem_ctx) { | |
| data = reralloc_size(buf->mem_ctx, buf->data, capacity); | |
| } 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 * (unsigned)eltsize; | |
| void *p = util_dynarray_ensure_cap(buf, newsize); | |
| if (!p) | |
| return NULL; | |
| buf->size = newsize; | |
| return p; | |
| } | |
| MUST_CHECK static inline void * | |
| util_dynarray_resize_bytes_zero(struct util_dynarray *buf, unsigned nelts, size_t eltsize) | |
| { | |
| size_t size = buf->capacity; | |
| void *ret = util_dynarray_resize_bytes(buf, nelts, eltsize); | |
| if (ret) { | |
| uint8_t *data = (uint8_t*)buf->data; | |
| memset(data + size, 0, buf->capacity - size); | |
| } | |
| return ret; | |
| } | |
| static inline void | |
| util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx, | |
| struct util_dynarray *from_buf) | |
| { | |
| util_dynarray_init(buf, mem_ctx); | |
| if (util_dynarray_resize_bytes(buf, from_buf->size, 1)) | |
| memcpy(buf->data, from_buf->data, from_buf->size); | |
| } | |
| /* growbytes has already been checked for overflow by the inline wrapper. */ | |
| MUST_CHECK ATTRIBUTE_NOINLINE void * | |
| util_dynarray_grow_bytes_slow(struct util_dynarray *buf, unsigned growbytes); | |
| MUST_CHECK static inline void * | |
| util_dynarray_grow_bytes(struct util_dynarray *buf, unsigned ngrow, size_t eltsize) | |
| { | |
| unsigned growbytes = ngrow * (unsigned)eltsize; | |
| if (unlikely(ngrow > (UINT_MAX / eltsize) || | |
| growbytes > UINT_MAX - buf->size)) | |
| return NULL; | |
| if (likely(growbytes <= buf->capacity - buf->size)) { | |
| void *p = (char *)buf->data + buf->size; | |
| buf->size += growbytes; | |
| return p; | |
| } | |
| return util_dynarray_grow_bytes_slow(buf, growbytes); | |
| } | |
| 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) { | |
| if (buf->mem_ctx) { | |
| buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size); | |
| } else { | |
| buf->data = realloc(buf->data, buf->size); | |
| } | |
| buf->capacity = buf->size; | |
| } else { | |
| if (buf->mem_ctx) { | |
| ralloc_free(buf->data); | |
| } 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_typed(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow_bytes((buf), 1, sizeof(type)), &__v, sizeof(type));} while(0) | |
| #define util_dynarray_append_array(buf, type, v, count) do {memcpy(util_dynarray_grow_bytes((buf), count, sizeof(type)), v, sizeof(type) * count);} 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_resize_zero(buf, type, nelts) util_dynarray_resize_bytes_zero(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_last_ptr(buf, type) ((type*)((char*)(buf)->data + ((buf)->size - sizeof(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)) | |
| /* typeof is standard in C23 but not in C++, and MSVC lacks support when | |
| * compiling as C++. Conversely, decltype is standard in C++11 but missing in C. | |
| * For our purposes, they are equivalent - just use the right one depending | |
| * whether we compile as C or C++ so the macro works everywhere with MSVC. | |
| */ | |
| #ifdef __cplusplus | |
| #define util_dynarray_append(buf, v) util_dynarray_append_typed(buf, decltype(v), v) | |
| #else | |
| #define util_dynarray_append(buf, v) util_dynarray_append_typed(buf, __typeof__(v), v) | |
| #endif | |
| #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_ptr(buf, type, ptr) \ | |
| do { \ | |
| type *__v2 = util_dynarray_pop_ptr((buf), type); \ | |
| if (ptr != __v2) \ | |
| memcpy(ptr, __v2, sizeof(type)); \ | |
| } while (0) | |
| #define util_dynarray_delete_unordered_element(buf, type, elem) \ | |
| util_dynarray_delete_unordered_ptr((buf), type, \ | |
| util_dynarray_element((buf), type, (elem))); | |
| #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) { \ | |
| util_dynarray_delete_unordered_element((buf), type, (i)); \ | |
| break; \ | |
| } \ | |
| } \ | |
| } while (0) | |
| #ifdef __cplusplus | |
| } | |
| #endif | |
| #endif /* U_DYNARRAY_H */ |