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