Correct error in wrapped array-span-iteration
[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         unsigned int i;
138         for (i = 0; i < arr_len; i++, arr_step += arr_stride) {
139                 if (memcmp(arr_step, p, arr_stride) == 0) {
140                         return (int)i;
141                 }
142         }
143         return -1;
144 }
145
146 void _bli_array_binary_and(
147         void *arr, const void *arr_a, const void *arr_b,
148         unsigned int arr_len, size_t arr_stride)
149 {
150         char *dst   = arr;
151         const char *src_a = arr_a;
152         const char *src_b = arr_b;
153
154         size_t i = arr_stride * arr_len;
155         while (i--) {
156                 *(dst++) = *(src_a++) & *(src_b++);
157         }
158 }
159
160 void _bli_array_binary_or(
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 /**
175  * Utility function to iterate over contiguous items in an array.
176  *
177  * \param use_wrap: Detect contiguous ranges across the first/last points.
178  * In this case the second index of \a span_step may be lower than the first,
179  * which indicates the values are wrapped.
180  * \param use_delimit_bounds: When false, ranges that defined by the start/end indices are excluded.
181  * This option has no effect when \a use_wrap is enabled.
182  * \param test_fn: Function to test if the item should be included in the range.
183  * \param user_data: User data for \a test_fn.
184  * \param span_step: Indices to iterate over,
185  * initialize both values to the array length to initialize iteration.
186  * \param: r_span_len: The length of the span, useful when \a use_wrap is enabled,
187  * where calculating the length isnt a simple subtraction.
188  */
189 bool _bli_array_iter_span(
190         const void *arr,
191         unsigned int arr_len, size_t arr_stride,
192         bool use_wrap, bool use_delimit_bounds,
193         bool (*test_fn)(const void *arr_item, void *user_data), void *user_data,
194         unsigned int span_step[2], unsigned int *r_span_len)
195 {
196         if (arr_len == 0) {
197                 return false;
198         }
199         else if (use_wrap && (span_step[0] != arr_len) && (span_step[0] > span_step[1])) {
200                 return false;
201         }
202
203         const unsigned int arr_stride_uint = (unsigned int)arr_stride;
204         const void *item_prev;
205         bool test_prev;
206
207         unsigned int i_curr;
208
209         if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) {
210                 if (use_wrap) {
211                         item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint);
212                         i_curr = 0;
213                         test_prev = test_fn(item_prev, user_data);
214                 }
215                 else if (use_delimit_bounds == false) {
216                         item_prev = arr;
217                         i_curr = 1;
218                         test_prev = test_fn(item_prev, user_data);
219                 }
220                 else {
221                         item_prev = NULL;
222                         i_curr = 0;
223                         test_prev = false;
224                 }
225         }
226         else if ((i_curr = span_step[1] + 2) < arr_len) {
227                 item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint);
228                 test_prev = test_fn(item_prev, user_data);
229         }
230         else {
231                 return false;
232         }
233         BLI_assert(i_curr < arr_len);
234
235         const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint);
236
237         while (i_curr < arr_len) {
238                 bool test_curr = test_fn(item_curr, user_data);
239                 if ((test_prev == false) &&
240                     (test_curr == true))
241                 {
242                         unsigned int span_len;
243                         unsigned int i_step_prev = i_curr;
244
245                         if (use_wrap) {
246                                 unsigned int i_step = i_curr + 1;
247                                 if (UNLIKELY(i_step == arr_len)) {
248                                         i_step = 0;
249                                 }
250                                 while (test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) {
251                                         i_step_prev = i_step;
252                                         i_step++;
253                                         if (UNLIKELY(i_step == arr_len)) {
254                                                 i_step = 0;
255                                         }
256                                 }
257
258                                 if (i_step_prev < i_curr) {
259                                         span_len = (i_step_prev + (arr_len - i_curr)) + 1;
260                                 }
261                                 else {
262                                         span_len = (i_step_prev - i_curr) + 1;
263                                 }
264                         }
265                         else {
266                                 unsigned int i_step = i_curr + 1;
267                                 while ((i_step != arr_len) &&
268                                        test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data))
269                                 {
270                                         i_step_prev = i_step;
271                                         i_step++;
272                                 }
273
274                                 span_len = (i_step_prev - i_curr) + 1;
275
276                                 if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) {
277                                         return false;
278                                 }
279                         }
280
281                         span_step[0] = i_curr;
282                         span_step[1] = i_step_prev;
283                         *r_span_len  = span_len;
284
285                         return true;
286                 }
287
288                 test_prev = test_curr;
289
290                 item_prev = item_curr;
291                 item_curr = POINTER_OFFSET(item_curr, arr_stride_uint);
292                 i_curr++;
293         }
294
295         return false;
296 }