Blender  V3.3
array_utils.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
11 #include <stdlib.h>
12 #include <string.h>
13 
14 #include "MEM_guardedalloc.h"
15 
16 #include "BLI_alloca.h"
17 #include "BLI_math_base.h"
18 #include "BLI_strict_flags.h"
19 #include "BLI_sys_types.h"
20 #include "BLI_utildefines.h"
21 
22 #include "BLI_array_utils.h"
23 
24 void _bli_array_reverse(void *arr_v, uint arr_len, size_t arr_stride)
25 {
26  const uint arr_stride_uint = (uint)arr_stride;
27  const uint arr_half_stride = (arr_len / 2) * arr_stride_uint;
28  uint i, i_end;
29  char *arr = arr_v;
30  char *buf = BLI_array_alloca(buf, arr_stride);
31 
32  for (i = 0, i_end = (arr_len - 1) * arr_stride_uint; i < arr_half_stride;
33  i += arr_stride_uint, i_end -= arr_stride_uint) {
34  memcpy(buf, &arr[i], arr_stride);
35  memcpy(&arr[i], &arr[i_end], arr_stride);
36  memcpy(&arr[i_end], buf, arr_stride);
37  }
38 }
39 
40 void _bli_array_wrap(void *arr_v, uint arr_len, size_t arr_stride, int dir)
41 {
42  char *arr = arr_v;
43  char *buf = BLI_array_alloca(buf, arr_stride);
44 
45  if (dir == -1) {
46  memcpy(buf, arr, arr_stride);
47  memmove(arr, arr + arr_stride, arr_stride * (arr_len - 1));
48  memcpy(arr + (arr_stride * (arr_len - 1)), buf, arr_stride);
49  }
50  else if (dir == 1) {
51  memcpy(buf, arr + (arr_stride * (arr_len - 1)), arr_stride);
52  memmove(arr + arr_stride, arr, arr_stride * (arr_len - 1));
53  memcpy(arr, buf, arr_stride);
54  }
55  else {
57  }
58 }
59 
61  void *arr, const uint arr_len, const size_t arr_stride, const uint *order, void *arr_temp)
62 {
63  const size_t len = arr_len * arr_stride;
64  const uint arr_stride_uint = (uint)arr_stride;
65  void *arr_orig;
66  uint i;
67 
68  if (arr_temp == NULL) {
69  arr_orig = MEM_mallocN(len, __func__);
70  }
71  else {
72  arr_orig = arr_temp;
73  }
74 
75  memcpy(arr_orig, arr, len);
76 
77  for (i = 0; i < arr_len; i++) {
78  BLI_assert(order[i] < arr_len);
79  memcpy(POINTER_OFFSET(arr, arr_stride_uint * i),
80  POINTER_OFFSET(arr_orig, arr_stride_uint * order[i]),
81  arr_stride);
82  }
83 
84  if (arr_temp == NULL) {
85  MEM_freeN(arr_orig);
86  }
87 }
88 
89 uint _bli_array_deduplicate_ordered(void *arr, uint arr_len, size_t arr_stride)
90 {
91  if (UNLIKELY(arr_len <= 1)) {
92  return arr_len;
93  }
94 
95  const uint arr_stride_uint = (uint)arr_stride;
96  uint j = 0;
97  for (uint i = 0; i < arr_len; i++) {
98  if ((i == j) || (memcmp(POINTER_OFFSET(arr, arr_stride_uint * i),
99  POINTER_OFFSET(arr, arr_stride_uint * j),
100  arr_stride) == 0)) {
101  continue;
102  }
103  j += 1;
104  memcpy(POINTER_OFFSET(arr, arr_stride_uint * j),
105  POINTER_OFFSET(arr, arr_stride_uint * i),
106  arr_stride);
107  }
108  return j + 1;
109 }
110 
111 int _bli_array_findindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
112 {
113  const char *arr_step = (const char *)arr;
114  for (uint i = 0; i < arr_len; i++, arr_step += arr_stride) {
115  if (memcmp(arr_step, p, arr_stride) == 0) {
116  return (int)i;
117  }
118  }
119  return -1;
120 }
121 
122 int _bli_array_rfindindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
123 {
124  const char *arr_step = (const char *)arr + (arr_stride * arr_len);
125  for (uint i = arr_len; i-- != 0;) {
126  arr_step -= arr_stride;
127  if (memcmp(arr_step, p, arr_stride) == 0) {
128  return (int)i;
129  }
130  }
131  return -1;
132 }
133 
135  void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
136 {
137  char *dst = arr;
138  const char *src_a = arr_a;
139  const char *src_b = arr_b;
140 
141  size_t i = arr_stride * arr_len;
142  while (i--) {
143  *(dst++) = *(src_a++) & *(src_b++);
144  }
145 }
146 
148  void *arr, const void *arr_a, const void *arr_b, uint 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 bool _bli_array_iter_span(const void *arr,
161  uint arr_len,
162  size_t arr_stride,
163  bool use_wrap,
164  bool use_delimit_bounds,
165  bool (*test_fn)(const void *arr_item, void *user_data),
166  void *user_data,
167  uint span_step[2],
168  uint *r_span_len)
169 {
170  if (arr_len == 0) {
171  return false;
172  }
173  if (use_wrap && (span_step[0] != arr_len) && (span_step[0] > span_step[1])) {
174  return false;
175  }
176 
177  const uint arr_stride_uint = (uint)arr_stride;
178  const void *item_prev;
179  bool test_prev;
180 
181  uint i_curr;
182 
183  if ((span_step[0] == arr_len) && (span_step[1] == arr_len)) {
184  if (use_wrap) {
185  item_prev = POINTER_OFFSET(arr, (arr_len - 1) * arr_stride_uint);
186  i_curr = 0;
187  test_prev = test_fn(item_prev, user_data);
188  }
189  else if (use_delimit_bounds == false) {
190  item_prev = arr;
191  i_curr = 1;
192  test_prev = test_fn(item_prev, user_data);
193  }
194  else {
195  item_prev = NULL;
196  i_curr = 0;
197  test_prev = false;
198  }
199  }
200  else if ((i_curr = span_step[1] + 2) < arr_len) {
201  item_prev = POINTER_OFFSET(arr, (span_step[1] + 1) * arr_stride_uint);
202  test_prev = test_fn(item_prev, user_data);
203  }
204  else {
205  return false;
206  }
207  BLI_assert(i_curr < arr_len);
208 
209  const void *item_curr = POINTER_OFFSET(arr, i_curr * arr_stride_uint);
210 
211  while (i_curr < arr_len) {
212  bool test_curr = test_fn(item_curr, user_data);
213  if ((test_prev == false) && (test_curr == true)) {
214  uint span_len;
215  uint i_step_prev = i_curr;
216 
217  if (use_wrap) {
218  uint i_step = i_curr + 1;
219  if (UNLIKELY(i_step == arr_len)) {
220  i_step = 0;
221  }
222  while (test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) {
223  i_step_prev = i_step;
224  i_step++;
225  if (UNLIKELY(i_step == arr_len)) {
226  i_step = 0;
227  }
228  }
229 
230  if (i_step_prev < i_curr) {
231  span_len = (i_step_prev + (arr_len - i_curr)) + 1;
232  }
233  else {
234  span_len = (i_step_prev - i_curr) + 1;
235  }
236  }
237  else {
238  uint i_step = i_curr + 1;
239  while ((i_step != arr_len) &&
240  test_fn(POINTER_OFFSET(arr, i_step * arr_stride_uint), user_data)) {
241  i_step_prev = i_step;
242  i_step++;
243  }
244 
245  span_len = (i_step_prev - i_curr) + 1;
246 
247  if ((use_delimit_bounds == false) && (i_step_prev == arr_len - 1)) {
248  return false;
249  }
250  }
251 
252  span_step[0] = i_curr;
253  span_step[1] = i_step_prev;
254  *r_span_len = span_len;
255 
256  return true;
257  }
258 
259  test_prev = test_curr;
260 
261  item_prev = item_curr;
262  item_curr = POINTER_OFFSET(item_curr, arr_stride_uint);
263  i_curr++;
264  }
265 
266  return false;
267 }
268 
269 bool _bli_array_is_zeroed(const void *arr_v, uint arr_len, size_t arr_stride)
270 {
271  const char *arr_step = (const char *)arr_v;
272  size_t i = arr_stride * arr_len;
273  while (i--) {
274  if (*(arr_step++)) {
275  return false;
276  }
277  }
278  return true;
279 }
280 
281 bool _bli_array_iter_spiral_square(const void *arr_v,
282  const int arr_shape[2],
283  size_t elem_size,
284  const int center[2],
285  bool (*test_fn)(const void *arr_item, void *user_data),
286  void *user_data)
287 {
288  BLI_assert(center[0] >= 0 && center[1] >= 0 && center[0] < arr_shape[0] &&
289  center[1] < arr_shape[1]);
290 
291  const char *arr = arr_v;
292  const int stride[2] = {arr_shape[0] * (int)elem_size, (int)elem_size};
293 
294  /* Test center first. */
295  int ofs[2] = {center[0] * stride[1], center[1] * stride[0]};
296  if (test_fn(arr + ofs[0] + ofs[1], user_data)) {
297  return true;
298  }
299 
300  /* #steps_in and #steps_out are the "diameters" of the inscribed and circumscribed squares in the
301  * rectangle. Each step smaller than #steps_in does not need to check bounds. */
302  int steps_in, steps_out;
303  {
304  int x_minus = center[0];
305  int x_plus = arr_shape[0] - center[0] - 1;
306  int y_minus = center[1];
307  int y_plus = arr_shape[1] - center[1] - 1;
308 
309  steps_in = 2 * min_iiii(x_minus, x_plus, y_minus, y_plus);
310  steps_out = 2 * max_iiii(x_minus, x_plus, y_minus, y_plus);
311  }
312 
313  /* For check_bounds. */
314  int limits[2] = {(arr_shape[0] - 1) * stride[0], stride[0] - stride[1]};
315 
316  int steps = 0;
317  while (steps < steps_out) {
318  steps += 2;
319 
320  /* Move one step to the diagonal of the negative quadrant. */
321  ofs[0] -= stride[0];
322  ofs[1] -= stride[1];
323 
324  bool check_bounds = steps > steps_in;
325 
326  /* sign: 0 neg; 1 pos; */
327  for (int sign = 2; sign--;) {
328  /* axis: 0 x; 1 y; */
329  for (int axis = 2; axis--;) {
330  int ofs_step = stride[axis];
331  if (!sign) {
332  ofs_step *= -1;
333  }
334 
335  int ofs_iter = ofs[axis] + ofs_step;
336  int ofs_dest = ofs[axis] + steps * ofs_step;
337  int ofs_other = ofs[!axis];
338 
339  ofs[axis] = ofs_dest;
340  if (check_bounds) {
341  if (ofs_other < 0 || ofs_other > limits[!axis]) {
342  /* Out of bounds. */
343  continue;
344  }
345 
346  CLAMP(ofs_iter, 0, limits[axis]);
347  CLAMP(ofs_dest, 0, limits[axis]);
348  }
349 
350  while (true) {
351  if (test_fn(arr + ofs_other + ofs_iter, user_data)) {
352  return true;
353  }
354  if (ofs_iter == ofs_dest) {
355  break;
356  }
357  ofs_iter += ofs_step;
358  }
359  }
360  }
361  }
362  return false;
363 }
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
Generic array manipulation API.
#define BLI_assert_unreachable()
Definition: BLI_assert.h:93
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE int max_iiii(int a, int b, int c, int d)
MINLINE int min_iiii(int a, int b, int c, int d)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNLIKELY(x)
#define POINTER_OFFSET(v, ofs)
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei stride
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint order
Read Guarded memory(de)allocation.
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to used to fine tune the interpolation of the input Camera Retrieve information about the camera and how it relates to the current shading point s position CLAMP
void _bli_array_binary_or(void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
Definition: array_utils.c:147
int _bli_array_rfindindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
Definition: array_utils.c:122
uint _bli_array_deduplicate_ordered(void *arr, uint arr_len, size_t arr_stride)
Definition: array_utils.c:89
bool _bli_array_is_zeroed(const void *arr_v, uint arr_len, size_t arr_stride)
Definition: array_utils.c:269
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)
Definition: array_utils.c:281
int _bli_array_findindex(const void *arr, uint arr_len, size_t arr_stride, const void *p)
Definition: array_utils.c:111
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)
Definition: array_utils.c:160
void _bli_array_wrap(void *arr_v, uint arr_len, size_t arr_stride, int dir)
Definition: array_utils.c:40
void _bli_array_permute(void *arr, const uint arr_len, const size_t arr_stride, const uint *order, void *arr_temp)
Definition: array_utils.c:60
void _bli_array_reverse(void *arr_v, uint arr_len, size_t arr_stride)
Definition: array_utils.c:24
void _bli_array_binary_and(void *arr, const void *arr_a, const void *arr_b, uint arr_len, size_t arr_stride)
Definition: array_utils.c:134
void * user_data
int len
Definition: draw_manager.c:108
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
double sign(double arg)
Definition: utility.h:250
static const int steps
Definition: sky_nishita.cpp:19