BLI_math_rotation: properly name the quaternion power function.
[blender.git] / source / blender / blenlib / intern / array_utils.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenlib/intern/array_utils.c
22  *  \ingroup bli
23  *  \brief Generic array manipulation API.
24  *
25  * \warning Some array operations here are inherently inefficient,
26  * and only included for the cases where the performance is acceptable.
27  * Use with care.
28  */
29 #include <string.h>
30 #include <stdlib.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_array_utils.h"
35
36 #include "BLI_sys_types.h"
37 #include "BLI_utildefines.h"
38 #include "BLI_alloca.h"
39
40 #include "BLI_strict_flags.h"
41
42 /**
43  *In-place array reverse.
44  *
45  * Access via #BLI_array_reverse
46  */
47 void _bli_array_reverse(void *arr_v, unsigned int arr_len, size_t arr_stride)
48 {
49         const unsigned int arr_stride_uint = (unsigned int)arr_stride;
50         const unsigned int arr_half_stride = (arr_len / 2) * arr_stride_uint;
51         unsigned int i, i_end;
52         char *arr = arr_v;
53         char *buf = BLI_array_alloca(buf, arr_stride);
54
55         for (i = 0, i_end = (arr_len - 1) * arr_stride_uint;
56              i < arr_half_stride;
57              i += arr_stride_uint, i_end -= arr_stride_uint)
58         {
59                 memcpy(buf, &arr[i], arr_stride);
60                 memcpy(&arr[i], &arr[i_end], arr_stride);
61                 memcpy(&arr[i_end], buf, arr_stride);
62         }
63 }
64
65 /**
66  * In-place array wrap.
67  * (rotate the array one step forward or backwards).
68  *
69  * Access via #BLI_array_wrap
70  */
71 void _bli_array_wrap(void *arr_v, unsigned int arr_len, size_t arr_stride, int dir)
72 {
73         char *arr = arr_v;
74         char *buf = BLI_array_alloca(buf, arr_stride);
75
76         if (dir == -1) {
77                 memcpy(buf, arr, arr_stride);
78                 memmove(arr, arr + arr_stride, arr_stride * (arr_len - 1));
79                 memcpy(arr + (arr_stride * (arr_len - 1)), buf, arr_stride);
80         }
81         else if (dir == 1) {
82                 memcpy(buf, arr + (arr_stride * (arr_len - 1)), arr_stride);
83                 memmove(arr + arr_stride, arr, arr_stride * (arr_len - 1));
84                 memcpy(arr, buf, arr_stride);
85         }
86         else {
87                 BLI_assert(0);
88         }
89 }
90
91 /**
92  *In-place array permute.
93  * (re-arrange elements based on an array of indices).
94  *
95  * Access via #BLI_array_wrap
96  */
97 void _bli_array_permute(
98         void *arr_v, const unsigned int arr_len, const size_t arr_stride,
99         const unsigned int *order, void *arr_temp)
100 {
101         const size_t len = arr_len * arr_stride;
102         const unsigned int arr_stride_uint = (unsigned int)arr_stride;
103         void *arr_orig;
104         unsigned int i;
105
106         if (arr_temp == NULL) {
107                 arr_orig = MEM_mallocN(len, __func__);
108         }
109         else {
110                 arr_orig = arr_temp;
111         }
112
113         memcpy(arr_orig, arr_v, len);
114
115         for (i = 0; i < arr_len; i++) {
116                 BLI_assert(order[i] < arr_len);
117                 memcpy(POINTER_OFFSET(arr_v,    arr_stride_uint * i),
118                        POINTER_OFFSET(arr_orig, arr_stride_uint * order[i]),
119                        arr_stride);
120         }
121
122         if (arr_temp == NULL) {
123                 MEM_freeN(arr_orig);
124         }
125 }
126
127 /**
128  * Find the first index of an item in an array.
129  *
130  * Access via #BLI_array_findindex
131  *
132  * \note Not efficient, use for error checks/asserts.
133  */
134 int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p)
135 {
136         const char *arr_step = (const char *)arr;
137         for (unsigned int i = 0; i < arr_len; i++, arr_step += arr_stride) {
138                 if (memcmp(arr_step, p, arr_stride) == 0) {
139                         return (int)i;
140                 }
141         }
142         return -1;
143 }
144
145 /**
146  * A version of #BLI_array_findindex that searches from the end of the list.
147  */
148 int _bli_array_rfindindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p)
149 {
150         const char *arr_step = (const char *)arr + (arr_stride * arr_len);
151         for (unsigned int i = arr_len; i-- != 0; ) {
152                 arr_step -= arr_stride;
153                 if (memcmp(arr_step, p, arr_stride) == 0) {
154                         return (int)i;
155                 }
156         }
157         return -1;
158 }
159
160 void _bli_array_binary_and(
161         void *arr, const void *arr_a, const void *arr_b,
162         unsigned int arr_len, size_t arr_stride)
163 {
164         char *dst   = arr;
165         const char *src_a = arr_a;
166         const char *src_b = arr_b;
167
168         size_t i = arr_stride * arr_len;
169         while (i--) {
170                 *(dst++) = *(src_a++) & *(src_b++);
171         }
172 }
173
174 void _bli_array_binary_or(
175         void *arr, const void *arr_a, const void *arr_b,
176         unsigned int arr_len, size_t arr_stride)
177 {
178         char *dst   = arr;
179         const char *src_a = arr_a;
180         const char *src_b = arr_b;
181
182         size_t i = arr_stride * arr_len;
183         while (i--) {
184                 *(dst++) = *(src_a++) | *(src_b++);
185         }
186 }
187
188 /**
189  * Utility function to iterate over contiguous items in an array.
190  *
191  * \param use_wrap: Detect contiguous ranges across the first/last points.
192  * In this case the second index of \a span_step may be lower than the first,
193  * which indicates the values are wrapped.
194  * \param use_delimit_bounds: When false, ranges that defined by the start/end indices are excluded.
195  * This option has no effect when \a use_wrap is enabled.
196  * \param test_fn: Function to test if the item should be included in the range.
197  * \param user_data: User data for \a test_fn.
198  * \param span_step: Indices to iterate over,
199  * initialize both values to the array length to initialize iteration.
200  * \param r_span_len: The length of the span, useful when \a use_wrap is enabled,
201  * where calculating the length isnt a simple subtraction.
202  */
203 bool _bli_array_iter_span(
204         const void *arr,
205         unsigned int arr_len, size_t arr_stride,
206         bool use_wrap, bool use_delimit_bounds,
207         bool (*test_fn)(const void *arr_item, void *user_data), void *user_data,
208         unsigned int span_step[2], unsigned int *r_span_len)
209 {
210         if (arr_len == 0) {
211                 return false;
212         }
213         else if (use_wrap && (span_step[0] != arr_len) && (span_step[0] > span_step[1])) {
214                 return false;
215         }
216
217         const unsigned int arr_stride_uint = (unsigned int)arr_stride;
218         const void *item_prev;
219         bool test_prev;
220
221         unsigned int i_curr;
222
223         if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) {
224                 if (use_wrap) {
225                         item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint);
226                         i_curr = 0;
227                         test_prev = test_fn(item_prev, user_data);
228                 }
229                 else if (use_delimit_bounds == false) {
230                         item_prev = arr;
231                         i_curr = 1;
232                         test_prev = test_fn(item_prev, user_data);
233                 }
234                 else {
235                         item_prev = NULL;
236                         i_curr = 0;
237                         test_prev = false;
238                 }
239         }
240         else if ((i_curr = span_step[1] + 2) < arr_len) {
241                 item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint);
242                 test_prev = test_fn(item_prev, user_data);
243         }
244         else {
245                 return false;
246         }
247         BLI_assert(i_curr < arr_len);
248
249         const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint);
250
251         while (i_curr < arr_len) {
252                 bool test_curr = test_fn(item_curr, user_data);
253                 if ((test_prev == false) &&
254                     (test_curr == true))
255                 {
256                         unsigned int span_len;
257                         unsigned int i_step_prev = i_curr;
258
259                         if (use_wrap) {
260                                 unsigned int i_step = i_curr + 1;
261                                 if (UNLIKELY(i_step == arr_len)) {
262                                         i_step = 0;
263                                 }
264                                 while (test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) {
265                                         i_step_prev = i_step;
266                                         i_step++;
267                                         if (UNLIKELY(i_step == arr_len)) {
268                                                 i_step = 0;
269                                         }
270                                 }
271
272                                 if (i_step_prev < i_curr) {
273                                         span_len = (i_step_prev + (arr_len - i_curr)) + 1;
274                                 }
275                                 else {
276                                         span_len = (i_step_prev - i_curr) + 1;
277                                 }
278                         }
279                         else {
280                                 unsigned int i_step = i_curr + 1;
281                                 while ((i_step != arr_len) &&
282                                        test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data))
283                                 {
284                                         i_step_prev = i_step;
285                                         i_step++;
286                                 }
287
288                                 span_len = (i_step_prev - i_curr) + 1;
289
290                                 if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) {
291                                         return false;
292                                 }
293                         }
294
295                         span_step[0] = i_curr;
296                         span_step[1] = i_step_prev;
297                         *r_span_len  = span_len;
298
299                         return true;
300                 }
301
302                 test_prev = test_curr;
303
304                 item_prev = item_curr;
305                 item_curr = POINTER_OFFSET(item_curr, arr_stride_uint);
306                 i_curr++;
307         }
308
309         return false;
310 }
311
312 /**
313  * Simple utility to check memory is zeroed.
314  */
315 bool _bli_array_is_zeroed(
316         const void *arr_v,
317         unsigned int arr_len, size_t arr_stride)
318 {
319         const char *arr_step = (const char *)arr_v;
320         size_t i = arr_stride * arr_len;
321         while (i--) {
322                 if (*(arr_step++)) {
323                         return false;
324                 }
325         }
326         return true;
327 }