diff options
Diffstat (limited to 'extern/curve_fit_nd/intern/generic_alloc_impl.h')
-rw-r--r-- | extern/curve_fit_nd/intern/generic_alloc_impl.h | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/extern/curve_fit_nd/intern/generic_alloc_impl.h b/extern/curve_fit_nd/intern/generic_alloc_impl.h new file mode 100644 index 00000000000..687c154f14a --- /dev/null +++ b/extern/curve_fit_nd/intern/generic_alloc_impl.h @@ -0,0 +1,220 @@ +/* + * Copyright (c) 2016, Blender Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the <organization> nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file generic_alloc_impl.c + * \ingroup curve_fit + * + * Simple Memory Chunking Allocator + * ================================ + * + * Defines need to be set: + * - #TPOOL_IMPL_PREFIX: Prefix to use for the API. + * - #TPOOL_ALLOC_TYPE: Struct type this pool handles. + * - #TPOOL_STRUCT: Name for pool struct name. + * - #TPOOL_CHUNK_SIZE: Chunk size (optional), use 64kb when not defined. + * + * \note #TPOOL_ALLOC_TYPE must be at least ``sizeof(void *)``. + * + * Defines the API, uses #TPOOL_IMPL_PREFIX to prefix each function. + * + * - *_pool_create() + * - *_pool_destroy() + * - *_pool_clear() + * + * - *_pool_elem_alloc() + * - *_pool_elem_calloc() + * - *_pool_elem_free() + */ + +/* check we're not building directly */ +#if !defined(TPOOL_IMPL_PREFIX) || \ + !defined(TPOOL_ALLOC_TYPE) || \ + !defined(TPOOL_STRUCT) +# error "This file can't be compiled directly, include in another source file" +#endif + +#define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2 +#define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) +#define _TPOOL_PREFIX(id) _CONCAT(TPOOL_IMPL_PREFIX, _##id) + +/* local identifiers */ +#define pool_create _TPOOL_PREFIX(pool_create) +#define pool_destroy _TPOOL_PREFIX(pool_destroy) +#define pool_clear _TPOOL_PREFIX(pool_clear) + +#define pool_elem_alloc _TPOOL_PREFIX(pool_elem_alloc) +#define pool_elem_calloc _TPOOL_PREFIX(pool_elem_calloc) +#define pool_elem_free _TPOOL_PREFIX(pool_elem_free) + +/* private identifiers (only for this file, undefine after) */ +#define pool_alloc_chunk _TPOOL_PREFIX(pool_alloc_chunk) +#define TPoolChunk _TPOOL_PREFIX(TPoolChunk) +#define TPoolChunkElemFree _TPOOL_PREFIX(TPoolChunkElemFree) + +#ifndef TPOOL_CHUNK_SIZE +#define TPOOL_CHUNK_SIZE (1 << 16) /* 64kb */ +#define _TPOOL_CHUNK_SIZE_UNDEF +#endif + +#ifndef UNLIKELY +# ifdef __GNUC__ +# define UNLIKELY(x) __builtin_expect(!!(x), 0) +# else +# define UNLIKELY(x) (x) +# endif +#endif + +#ifdef __GNUC__ +# define MAYBE_UNUSED __attribute__((unused)) +#else +# define MAYBE_UNUSED +#endif + + +struct TPoolChunk { + struct TPoolChunk *prev; + unsigned int size; + unsigned int bufsize; + TPOOL_ALLOC_TYPE buf[0]; +}; + +struct TPoolChunkElemFree { + struct TPoolChunkElemFree *next; +}; + +struct TPOOL_STRUCT { + /* Always keep at least one chunk (never NULL) */ + struct TPoolChunk *chunk; + /* when NULL, allocate a new chunk */ + struct TPoolChunkElemFree *free; +}; + +/** + * Number of elems to include per #TPoolChunk when no reserved size is passed, + * or we allocate past the reserved number. + * + * \note Optimize number for 64kb allocs. + */ +#define _TPOOL_CHUNK_DEFAULT_NUM \ + (((1 << 16) - sizeof(struct TPoolChunk)) / sizeof(TPOOL_ALLOC_TYPE)) + + +/** \name Internal Memory Management + * \{ */ + +static struct TPoolChunk *pool_alloc_chunk( + unsigned int tot_elems, struct TPoolChunk *chunk_prev) +{ + struct TPoolChunk *chunk = malloc( + sizeof(struct TPoolChunk) + (sizeof(TPOOL_ALLOC_TYPE) * tot_elems)); + chunk->prev = chunk_prev; + chunk->bufsize = tot_elems; + chunk->size = 0; + return chunk; +} + +static TPOOL_ALLOC_TYPE *pool_elem_alloc(struct TPOOL_STRUCT *pool) +{ + TPOOL_ALLOC_TYPE *elem; + + if (pool->free) { + elem = (TPOOL_ALLOC_TYPE *)pool->free; + pool->free = pool->free->next; + } + else { + struct TPoolChunk *chunk = pool->chunk; + if (UNLIKELY(chunk->size == chunk->bufsize)) { + chunk = pool->chunk = pool_alloc_chunk(_TPOOL_CHUNK_DEFAULT_NUM, chunk); + } + elem = &chunk->buf[chunk->size++]; + } + + return elem; +} + +MAYBE_UNUSED +static TPOOL_ALLOC_TYPE *pool_elem_calloc(struct TPOOL_STRUCT *pool) +{ + TPOOL_ALLOC_TYPE *elem = pool_elem_alloc(pool); + memset(elem, 0, sizeof(*elem)); + return elem; +} + +static void pool_elem_free(struct TPOOL_STRUCT *pool, TPOOL_ALLOC_TYPE *elem) +{ + struct TPoolChunkElemFree *elem_free = (struct TPoolChunkElemFree *)elem; + elem_free->next = pool->free; + pool->free = elem_free; +} + +static void pool_create(struct TPOOL_STRUCT *pool, unsigned int tot_reserve) +{ + pool->chunk = pool_alloc_chunk((tot_reserve > 1) ? tot_reserve : _TPOOL_CHUNK_DEFAULT_NUM, NULL); + pool->free = NULL; +} + +MAYBE_UNUSED +static void pool_clear(struct TPOOL_STRUCT *pool) +{ + /* Remove all except the last chunk */ + while (pool->chunk->prev) { + struct TPoolChunk *chunk_prev = pool->chunk->prev; + free(pool->chunk); + pool->chunk = chunk_prev; + } + pool->chunk->size = 0; + pool->free = NULL; +} + +static void pool_destroy(struct TPOOL_STRUCT *pool) +{ + struct TPoolChunk *chunk = pool->chunk; + do { + struct TPoolChunk *chunk_prev; + chunk_prev = chunk->prev; + free(chunk); + chunk = chunk_prev; + } while (chunk); + + pool->chunk = NULL; + pool->free = NULL; +} + +/** \} */ + +#undef _TPOOL_CHUNK_DEFAULT_NUM +#undef _CONCAT_AUX +#undef _CONCAT +#undef _TPOOL_PREFIX + +#undef TPoolChunk +#undef TPoolChunkElemFree + +#ifdef _TPOOL_CHUNK_SIZE_UNDEF +# undef TPOOL_CHUNK_SIZE +# undef _TPOOL_CHUNK_SIZE_UNDEF +#endif |