Cleanup: comments (long lines) in blenlib
[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; i < arr_half_stride;
52        i += arr_stride_uint, i_end -= arr_stride_uint) {
53     memcpy(buf, &arr[i], arr_stride);
54     memcpy(&arr[i], &arr[i_end], arr_stride);
55     memcpy(&arr[i_end], buf, arr_stride);
56   }
57 }
58
59 /**
60  * In-place array wrap.
61  * (rotate the array one step forward or backwards).
62  *
63  * Access via #BLI_array_wrap
64  */
65 void _bli_array_wrap(void *arr_v, unsigned int arr_len, size_t arr_stride, int dir)
66 {
67   char *arr = arr_v;
68   char *buf = BLI_array_alloca(buf, arr_stride);
69
70   if (dir == -1) {
71     memcpy(buf, arr, arr_stride);
72     memmove(arr, arr + arr_stride, arr_stride * (arr_len - 1));
73     memcpy(arr + (arr_stride * (arr_len - 1)), buf, arr_stride);
74   }
75   else if (dir == 1) {
76     memcpy(buf, arr + (arr_stride * (arr_len - 1)), arr_stride);
77     memmove(arr + arr_stride, arr, arr_stride * (arr_len - 1));
78     memcpy(arr, buf, arr_stride);
79   }
80   else {
81     BLI_assert(0);
82   }
83 }
84
85 /**
86  *In-place array permute.
87  * (re-arrange elements based on an array of indices).
88  *
89  * Access via #BLI_array_wrap
90  */
91 void _bli_array_permute(void *arr_v,
92                         const unsigned int arr_len,
93                         const size_t arr_stride,
94                         const unsigned int *order,
95                         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, unsigned int arr_len, size_t arr_stride)
158 {
159   char *dst = arr;
160   const char *src_a = arr_a;
161   const char *src_b = arr_b;
162
163   size_t i = arr_stride * arr_len;
164   while (i--) {
165     *(dst++) = *(src_a++) & *(src_b++);
166   }
167 }
168
169 void _bli_array_binary_or(
170     void *arr, const void *arr_a, const void *arr_b, unsigned int arr_len, size_t arr_stride)
171 {
172   char *dst = arr;
173   const char *src_a = arr_a;
174   const char *src_b = arr_b;
175
176   size_t i = arr_stride * arr_len;
177   while (i--) {
178     *(dst++) = *(src_a++) | *(src_b++);
179   }
180 }
181
182 /**
183  * Utility function to iterate over contiguous items in an array.
184  *
185  * \param use_wrap: Detect contiguous ranges across the first/last points.
186  * In this case the second index of \a span_step may be lower than the first,
187  * which indicates the values are wrapped.
188  * \param use_delimit_bounds: When false,
189  * ranges that defined by the start/end indices are excluded.
190  * This option has no effect when \a use_wrap is enabled.
191  * \param test_fn: Function to test if the item should be included in the range.
192  * \param user_data: User data for \a test_fn.
193  * \param span_step: Indices to iterate over,
194  * initialize both values to the array length to initialize iteration.
195  * \param r_span_len: The length of the span, useful when \a use_wrap is enabled,
196  * where calculating the length isnt a simple subtraction.
197  */
198 bool _bli_array_iter_span(const void *arr,
199                           unsigned int arr_len,
200                           size_t arr_stride,
201                           bool use_wrap,
202                           bool use_delimit_bounds,
203                           bool (*test_fn)(const void *arr_item, void *user_data),
204                           void *user_data,
205                           unsigned int span_step[2],
206                           unsigned int *r_span_len)
207 {
208   if (arr_len == 0) {
209     return false;
210   }
211   else if (use_wrap && (span_step[0] != arr_len) && (span_step[0] > span_step[1])) {
212     return false;
213   }
214
215   const unsigned int arr_stride_uint = (unsigned int)arr_stride;
216   const void *item_prev;
217   bool test_prev;
218
219   unsigned int i_curr;
220
221   if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) {
222     if (use_wrap) {
223       item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint);
224       i_curr = 0;
225       test_prev = test_fn(item_prev, user_data);
226     }
227     else if (use_delimit_bounds == false) {
228       item_prev = arr;
229       i_curr = 1;
230       test_prev = test_fn(item_prev, user_data);
231     }
232     else {
233       item_prev = NULL;
234       i_curr = 0;
235       test_prev = false;
236     }
237   }
238   else if ((i_curr = span_step[1] + 2) < arr_len) {
239     item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint);
240     test_prev = test_fn(item_prev, user_data);
241   }
242   else {
243     return false;
244   }
245   BLI_assert(i_curr < arr_len);
246
247   const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint);
248
249   while (i_curr < arr_len) {
250     bool test_curr = test_fn(item_curr, user_data);
251     if ((test_prev == false) && (test_curr == true)) {
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           i_step_prev = i_step;
280           i_step++;
281         }
282
283         span_len = (i_step_prev - i_curr) + 1;
284
285         if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) {
286           return false;
287         }
288       }
289
290       span_step[0] = i_curr;
291       span_step[1] = i_step_prev;
292       *r_span_len = span_len;
293
294       return true;
295     }
296
297     test_prev = test_curr;
298
299     item_prev = item_curr;
300     item_curr = POINTER_OFFSET(item_curr, arr_stride_uint);
301     i_curr++;
302   }
303
304   return false;
305 }
306
307 /**
308  * Simple utility to check memory is zeroed.
309  */
310 bool _bli_array_is_zeroed(const void *arr_v, unsigned int arr_len, size_t arr_stride)
311 {
312   const char *arr_step = (const char *)arr_v;
313   size_t i = arr_stride * arr_len;
314   while (i--) {
315     if (*(arr_step++)) {
316       return false;
317     }
318   }
319   return true;
320 }