Blender V5.3
array_utils_c.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
13#include <algorithm>
14#include <cstdlib>
15#include <cstring>
16
17#include "MEM_guardedalloc.h"
18
19#include "BLI_alloca.hh"
20#include "BLI_math_base_c.hh"
21#include "BLI_sys_types.hh"
22#include "BLI_utildefines.hh"
23
24#include "BLI_array_utils_c.hh"
25
26#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
27
28namespace blender {
29
30void _bli_array_reverse(void *arr_v, uint arr_len, size_t arr_stride)
31{
32 const uint arr_stride_uint = uint(arr_stride);
33 const uint arr_half_stride = (arr_len / 2) * arr_stride_uint;
34 uint i, i_end;
35 char *arr = static_cast<char *>(arr_v);
36 char *buf = BLI_array_alloca(buf, arr_stride);
37
38 for (i = 0, i_end = (arr_len - 1) * arr_stride_uint; i < arr_half_stride;
39 i += arr_stride_uint, i_end -= arr_stride_uint)
40 {
41 memcpy(buf, &arr[i], arr_stride);
42 memcpy(&arr[i], &arr[i_end], arr_stride);
43 memcpy(&arr[i_end], buf, arr_stride);
44 }
45}
46
47void _bli_array_wrap(void *arr_v, uint arr_len, size_t arr_stride, int dir)
48{
49 char *arr = static_cast<char *>(arr_v);
50 char *buf = BLI_array_alloca(buf, arr_stride);
51
52 if (dir == -1) {
53 memcpy(buf, arr, arr_stride);
54 memmove(arr, arr + arr_stride, arr_stride * (arr_len - 1));
55 memcpy(arr + (arr_stride * (arr_len - 1)), buf, arr_stride);
56 }
57 else if (dir == 1) {
58 memcpy(buf, arr + (arr_stride * (arr_len - 1)), arr_stride);
59 memmove(arr + arr_stride, arr, arr_stride * (arr_len - 1));
60 memcpy(arr, buf, arr_stride);
61 }
62 else {
64 }
65}
66
68 void *arr, const uint arr_len, const size_t arr_stride, const uint *order, void *arr_temp)
69{
70 const size_t len = arr_len * arr_stride;
71 const uint arr_stride_uint = uint(arr_stride);
72 void *arr_orig;
73 uint i;
74
75 if (arr_temp == nullptr) {
76 arr_orig = MEM_new_uninitialized(len, __func__);
77 }
78 else {
79 arr_orig = arr_temp;
80 }
81
82 memcpy(arr_orig, arr, len);
83
84 for (i = 0; i < arr_len; i++) {
85 BLI_assert(order[i] < arr_len);
86 memcpy(POINTER_OFFSET(arr, arr_stride_uint * i),
87 POINTER_OFFSET(arr_orig, arr_stride_uint * order[i]),
88 arr_stride);
89 }
90
91 if (arr_temp == nullptr) {
92 MEM_delete_void(arr_orig);
93 }
94}
95
96uint _bli_array_deduplicate_ordered(void *arr, uint arr_len, size_t arr_stride)
97{
98 if (arr_len <= 1) [[unlikely]] {
99 return arr_len;
100 }
101
102 const uint arr_stride_uint = uint(arr_stride);
103 uint j = 0;
104 for (uint i = 0; i < arr_len; i++) {
105 if ((i == j) || (memcmp(POINTER_OFFSET(arr, arr_stride_uint * i),
106 POINTER_OFFSET(arr, arr_stride_uint * j),
107 arr_stride) == 0))
108 {
109 continue;
110 }
111 j += 1;
112 memcpy(POINTER_OFFSET(arr, arr_stride_uint * j),
113 POINTER_OFFSET(arr, arr_stride_uint * i),
114 arr_stride);
115 }
116 return j + 1;
117}
118
119int _bli_array_findindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
120{
121 const char *arr_step = static_cast<const char *>(arr);
122 for (uint i = 0; i < arr_len; i++, arr_step += arr_stride) {
123 if (memcmp(arr_step, p, arr_stride) == 0) {
124 return int(i);
125 }
126 }
127 return -1;
128}
129
130int _bli_array_rfindindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
131{
132 const char *arr_step = static_cast<const char *>(arr) + (arr_stride * arr_len);
133 for (uint i = arr_len; i-- != 0;) {
134 arr_step -= arr_stride;
135 if (memcmp(arr_step, p, arr_stride) == 0) {
136 return int(i);
137 }
138 }
139 return -1;
140}
141
143 void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
144{
145 char *dst = static_cast<char *>(arr);
146 const char *src_a = static_cast<const char *>(arr_a);
147 const char *src_b = static_cast<const char *>(arr_b);
148
149 size_t i = arr_stride * arr_len;
150 while (i--) {
151 *(dst++) = *(src_a++) & *(src_b++);
152 }
153}
154
156 void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
157{
158 char *dst = static_cast<char *>(arr);
159 const char *src_a = static_cast<const char *>(arr_a);
160 const char *src_b = static_cast<const char *>(arr_b);
161
162 size_t i = arr_stride * arr_len;
163 while (i--) {
164 *(dst++) = *(src_a++) | *(src_b++);
165 }
166}
167
168bool _bli_array_iter_span(const void *arr,
169 uint arr_len,
170 size_t arr_stride,
171 bool use_wrap,
172 bool use_delimit_bounds,
173 bool (*test_fn)(const void *arr_item, void *user_data),
174 void *user_data,
175 uint span_step[2],
176 uint *r_span_len)
177{
178 if (arr_len == 0) {
179 return false;
180 }
181 if (use_wrap && (span_step[0] != arr_len) && (span_step[0] > span_step[1])) {
182 return false;
183 }
184
185 const uint arr_stride_uint = uint(arr_stride);
186 const void *item_prev;
187 bool test_prev;
188
189 uint i_curr;
190
191 if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) {
192 if (use_wrap) {
193 item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint);
194 i_curr = 0;
195 test_prev = test_fn(item_prev, user_data);
196 }
197 else if (use_delimit_bounds == false) {
198 item_prev = arr;
199 i_curr = 1;
200 test_prev = test_fn(item_prev, user_data);
201 }
202 else {
203 item_prev = nullptr;
204 i_curr = 0;
205 test_prev = false;
206 }
207 }
208 else if ((i_curr = span_step[1] + 2) < arr_len) {
209 item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint);
210 test_prev = test_fn(item_prev, user_data);
211 }
212 else {
213 return false;
214 }
215 BLI_assert(i_curr < arr_len);
216
217 const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint);
218
219 while (i_curr < arr_len) {
220 bool test_curr = test_fn(item_curr, user_data);
221 if ((test_prev == false) && (test_curr == true)) {
222 uint span_len;
223 uint i_step_prev = i_curr;
224
225 if (use_wrap) {
226 uint i_step = i_curr + 1;
227 if (i_step == arr_len) [[unlikely]] {
228 i_step = 0;
229 }
230 while (test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) {
231 i_step_prev = i_step;
232 i_step++;
233 if (i_step == arr_len) [[unlikely]] {
234 i_step = 0;
235 }
236 }
237
238 if (i_step_prev < i_curr) {
239 span_len = (i_step_prev + (arr_len - i_curr)) + 1;
240 }
241 else {
242 span_len = (i_step_prev - i_curr) + 1;
243 }
244 }
245 else {
246 uint i_step = i_curr + 1;
247 while ((i_step != arr_len) &&
248 test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data))
249 {
250 i_step_prev = i_step;
251 i_step++;
252 }
253
254 span_len = (i_step_prev - i_curr) + 1;
255
256 if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) {
257 return false;
258 }
259 }
260
261 span_step[0] = i_curr;
262 span_step[1] = i_step_prev;
263 *r_span_len = span_len;
264
265 return true;
266 }
267
268 test_prev = test_curr;
269
270 item_prev = item_curr;
271 item_curr = POINTER_OFFSET(item_curr, arr_stride_uint);
272 i_curr++;
273 }
274
275 return false;
276}
277
278bool _bli_array_is_zeroed(const void *arr_v, uint arr_len, size_t arr_stride)
279{
280 const char *arr_step = static_cast<const char *>(arr_v);
281 size_t i = arr_stride * arr_len;
282 while (i--) {
283 if (*(arr_step++)) {
284 return false;
285 }
286 }
287 return true;
288}
289
290bool _bli_array_iter_spiral_square(const void *arr_v,
291 const int arr_shape[2],
292 size_t elem_size,
293 const int center[2],
294 bool (*test_fn)(const void *arr_item, void *user_data),
295 void *user_data)
296{
297 BLI_assert(center[0] >= 0 && center[1] >= 0 && center[0] < arr_shape[0] &&
298 center[1] < arr_shape[1]);
299
300 const char *arr = static_cast<const char *>(arr_v);
301 const int stride[2] = {arr_shape[0] * int(elem_size), int(elem_size)};
302
303 /* Test center first. */
304 int ofs[2] = {center[0] * stride[1], center[1] * stride[0]};
305 if (test_fn(arr + ofs[0] + ofs[1], user_data)) {
306 return true;
307 }
308
309 /* #steps_in and #steps_out are the "diameters" of the inscribed and circumscribed squares in the
310 * rectangle. Each step smaller than #steps_in does not need to check bounds. */
311 int steps_in, steps_out;
312 {
313 int x_minus = center[0];
314 int x_plus = arr_shape[0] - center[0] - 1;
315 int y_minus = center[1];
316 int y_plus = arr_shape[1] - center[1] - 1;
317
318 steps_in = 2 * std::min({x_minus, x_plus, y_minus, y_plus});
319 steps_out = 2 * std::max({x_minus, x_plus, y_minus, y_plus});
320 }
321
322 /* For check_bounds. */
323 const int limits[2] = {(arr_shape[0] - 1) * stride[0], stride[0] - stride[1]};
324
325 int steps = 0;
326 while (steps < steps_out) {
327 steps += 2;
328
329 /* Move one step to the diagonal of the negative quadrant. */
330 ofs[0] -= stride[0];
331 ofs[1] -= stride[1];
332
333 bool check_bounds = steps > steps_in;
334
335 /* Sign: 0=negative 1=positive. */
336 for (int sign = 2; sign--;) {
337 /* Axis: 0=x; 1=y. */
338 for (int axis = 2; axis--;) {
339 int ofs_step = stride[axis];
340 if (!sign) {
341 ofs_step *= -1;
342 }
343
344 int ofs_iter = ofs[axis] + ofs_step;
345 int ofs_dest = ofs[axis] + steps * ofs_step;
346 int ofs_other = ofs[!axis];
347
348 ofs[axis] = ofs_dest;
349 if (check_bounds) {
350 if (ofs_other < 0 || ofs_other > limits[!axis]) {
351 /* Out of bounds. */
352 continue;
353 }
354
355 CLAMP(ofs_iter, 0, limits[axis]);
356 CLAMP(ofs_dest, 0, limits[axis]);
357 }
358
359 while (true) {
360 if (test_fn(arr + ofs_other + ofs_iter, user_data)) {
361 return true;
362 }
363 if (ofs_iter == ofs_dest) {
364 break;
365 }
366 ofs_iter += ofs_step;
367 }
368 }
369 }
370 }
371 return false;
372}
373
374} // namespace blender
#define BLI_array_alloca(arr, realsize)
Definition BLI_alloca.hh:18
Generic array manipulation API.
Read Blender memory allocation and freeing.
#define CLAMP(a, b, c)
#define BLI_assert_unreachable()
#define POINTER_OFFSET(v, ofs)
constexpr T sign(T) RET
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned int uint
Definition BKE_text.h:55
uint _bli_array_deduplicate_ordered(void *arr, uint arr_len, size_t arr_stride)
bool _bli_array_is_zeroed(const void *arr_v, uint arr_len, size_t arr_stride)
void _bli_array_wrap(void *arr_v, uint arr_len, size_t arr_stride, int dir)
void MEM_delete_void(void *vmemh)
void _bli_array_binary_and(void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
void _bli_array_permute(void *arr, uint arr_len, size_t arr_stride, const uint *order, void *arr_temp)
bool _bli_array_iter_spiral_square(const void *arr_v, const int arr_shape[2], size_t elem_size, const int center[2], bool(*test_fn)(const void *arr_item, void *user_data), void *user_data)
void _bli_array_reverse(void *arr_v, uint arr_len, size_t arr_stride)
void _bli_array_binary_or(void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
int _bli_array_findindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
int _bli_array_rfindindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
bool _bli_array_iter_span(const void *arr, uint arr_len, size_t arr_stride, bool use_wrap, bool use_delimit_bounds, bool(*test_fn)(const void *arr_item, void *user_data), void *user_data, uint span_step[2], uint *r_span_len)