Curve Fitting: Add alternate 'refit' method
[blender-staging.git] / extern / curve_fit_nd / intern / generic_alloc_impl.h
1 /*
2  * Copyright (c) 2016, Blender Foundation.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *     * Redistributions of source code must retain the above copyright
7  *       notice, this list of conditions and the following disclaimer.
8  *     * Redistributions in binary form must reproduce the above copyright
9  *       notice, this list of conditions and the following disclaimer in the
10  *       documentation and/or other materials provided with the distribution.
11  *     * Neither the name of the <organization> nor the
12  *       names of its contributors may be used to endorse or promote products
13  *       derived from this software without specific prior written permission.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18  * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
19  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 /**
28  * \file generic_alloc_impl.c
29  *  \ingroup curve_fit
30  *
31  * Simple Memory Chunking Allocator
32  * ================================
33  *
34  * Defines need to be set:
35  * - #TPOOL_IMPL_PREFIX: Prefix to use for the API.
36  * - #TPOOL_ALLOC_TYPE: Struct type this pool handles.
37  * - #TPOOL_STRUCT: Name for pool struct name.
38  * - #TPOOL_CHUNK_SIZE: Chunk size (optional), use 64kb when not defined.
39  *
40  * \note #TPOOL_ALLOC_TYPE must be at least ``sizeof(void *)``.
41  *
42  * Defines the API, uses #TPOOL_IMPL_PREFIX to prefix each function.
43  *
44  * - *_pool_create()
45  * - *_pool_destroy()
46  * - *_pool_clear()
47  *
48  * - *_pool_elem_alloc()
49  * - *_pool_elem_calloc()
50  * - *_pool_elem_free()
51  */
52
53 /* check we're not building directly */
54 #if !defined(TPOOL_IMPL_PREFIX) || \
55     !defined(TPOOL_ALLOC_TYPE) || \
56     !defined(TPOOL_STRUCT)
57 #  error "This file can't be compiled directly, include in another source file"
58 #endif
59
60 #define _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2) MACRO_ARG1 ## MACRO_ARG2
61 #define _CONCAT(MACRO_ARG1, MACRO_ARG2) _CONCAT_AUX(MACRO_ARG1, MACRO_ARG2)
62 #define _TPOOL_PREFIX(id) _CONCAT(TPOOL_IMPL_PREFIX, _##id)
63
64 /* local identifiers */
65 #define pool_create             _TPOOL_PREFIX(pool_create)
66 #define pool_destroy    _TPOOL_PREFIX(pool_destroy)
67 #define pool_clear              _TPOOL_PREFIX(pool_clear)
68
69 #define pool_elem_alloc         _TPOOL_PREFIX(pool_elem_alloc)
70 #define pool_elem_calloc        _TPOOL_PREFIX(pool_elem_calloc)
71 #define pool_elem_free          _TPOOL_PREFIX(pool_elem_free)
72
73 /* private identifiers (only for this file, undefine after) */
74 #define pool_alloc_chunk        _TPOOL_PREFIX(pool_alloc_chunk)
75 #define TPoolChunk                      _TPOOL_PREFIX(TPoolChunk)
76 #define TPoolChunkElemFree      _TPOOL_PREFIX(TPoolChunkElemFree)
77
78 #ifndef TPOOL_CHUNK_SIZE
79 #define  TPOOL_CHUNK_SIZE (1 << 16)  /* 64kb */
80 #define _TPOOL_CHUNK_SIZE_UNDEF
81 #endif
82
83 #ifndef UNLIKELY
84 #  ifdef __GNUC__
85 #    define UNLIKELY(x)     __builtin_expect(!!(x), 0)
86 #  else
87 #    define UNLIKELY(x)     (x)
88 #  endif
89 #endif
90
91 #ifdef __GNUC__
92 #  define MAYBE_UNUSED __attribute__((unused))
93 #else
94 #  define MAYBE_UNUSED
95 #endif
96
97
98 struct TPoolChunk {
99         struct TPoolChunk *prev;
100         unsigned int    size;
101         unsigned int    bufsize;
102         TPOOL_ALLOC_TYPE buf[0];
103 };
104
105 struct TPoolChunkElemFree {
106         struct TPoolChunkElemFree *next;
107 };
108
109 struct TPOOL_STRUCT {
110         /* Always keep at least one chunk (never NULL) */
111         struct TPoolChunk *chunk;
112         /* when NULL, allocate a new chunk */
113         struct TPoolChunkElemFree *free;
114 };
115
116 /**
117  * Number of elems to include per #TPoolChunk when no reserved size is passed,
118  * or we allocate past the reserved number.
119  *
120  * \note Optimize number for 64kb allocs.
121  */
122 #define _TPOOL_CHUNK_DEFAULT_NUM \
123         (((1 << 16) - sizeof(struct TPoolChunk)) / sizeof(TPOOL_ALLOC_TYPE))
124
125
126 /** \name Internal Memory Management
127  * \{ */
128
129 static struct TPoolChunk *pool_alloc_chunk(
130         unsigned int tot_elems, struct TPoolChunk *chunk_prev)
131 {
132         struct TPoolChunk *chunk = malloc(
133                 sizeof(struct TPoolChunk) + (sizeof(TPOOL_ALLOC_TYPE) * tot_elems));
134         chunk->prev = chunk_prev;
135         chunk->bufsize = tot_elems;
136         chunk->size = 0;
137         return chunk;
138 }
139
140 static TPOOL_ALLOC_TYPE *pool_elem_alloc(struct TPOOL_STRUCT *pool)
141 {
142         TPOOL_ALLOC_TYPE *elem;
143
144         if (pool->free) {
145                 elem = (TPOOL_ALLOC_TYPE *)pool->free;
146                 pool->free = pool->free->next;
147         }
148         else {
149                 struct TPoolChunk *chunk = pool->chunk;
150                 if (UNLIKELY(chunk->size == chunk->bufsize)) {
151                         chunk = pool->chunk = pool_alloc_chunk(_TPOOL_CHUNK_DEFAULT_NUM, chunk);
152                 }
153                 elem = &chunk->buf[chunk->size++];
154         }
155
156         return elem;
157 }
158
159 MAYBE_UNUSED
160 static TPOOL_ALLOC_TYPE *pool_elem_calloc(struct TPOOL_STRUCT *pool)
161 {
162         TPOOL_ALLOC_TYPE *elem = pool_elem_alloc(pool);
163         memset(elem, 0, sizeof(*elem));
164         return elem;
165 }
166
167 static void pool_elem_free(struct TPOOL_STRUCT *pool, TPOOL_ALLOC_TYPE *elem)
168 {
169         struct TPoolChunkElemFree *elem_free = (struct TPoolChunkElemFree *)elem;
170         elem_free->next = pool->free;
171         pool->free = elem_free;
172 }
173
174 static void pool_create(struct TPOOL_STRUCT *pool, unsigned int tot_reserve)
175 {
176         pool->chunk = pool_alloc_chunk((tot_reserve > 1) ? tot_reserve : _TPOOL_CHUNK_DEFAULT_NUM, NULL);
177         pool->free = NULL;
178 }
179
180 MAYBE_UNUSED
181 static void pool_clear(struct TPOOL_STRUCT *pool)
182 {
183         /* Remove all except the last chunk */
184         while (pool->chunk->prev) {
185                 struct TPoolChunk *chunk_prev = pool->chunk->prev;
186                 free(pool->chunk);
187                 pool->chunk = chunk_prev;
188         }
189         pool->chunk->size = 0;
190         pool->free = NULL;
191 }
192
193 static void pool_destroy(struct TPOOL_STRUCT *pool)
194 {
195         struct TPoolChunk *chunk = pool->chunk;
196         do {
197                 struct TPoolChunk *chunk_prev;
198                 chunk_prev = chunk->prev;
199                 free(chunk);
200                 chunk = chunk_prev;
201         } while (chunk);
202
203         pool->chunk = NULL;
204         pool->free = NULL;
205 }
206
207 /** \} */
208
209 #undef _TPOOL_CHUNK_DEFAULT_NUM
210 #undef _CONCAT_AUX
211 #undef _CONCAT
212 #undef _TPOOL_PREFIX
213
214 #undef TPoolChunk
215 #undef TPoolChunkElemFree
216
217 #ifdef _TPOOL_CHUNK_SIZE_UNDEF
218 #  undef  TPOOL_CHUNK_SIZE
219 #  undef _TPOOL_CHUNK_SIZE_UNDEF
220 #endif