Blender  V3.3
BLI_stack_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 #include <cstring>
5 
6 #include "BLI_array.h"
7 #include "BLI_stack.h"
8 #include "BLI_utildefines.h"
9 
10 #define SIZE 1024
11 
12 /* number of items per chunk. use a small value to expose bugs */
13 #define STACK_CHUNK_SIZE 8
14 
15 /* Ensure block size is set to #STACK_NEW_EX_ARGS */
16 #define BLI_stack_new(esize, descr) BLI_stack_new_ex(esize, descr, esize *STACK_CHUNK_SIZE)
17 
18 TEST(stack, Empty)
19 {
20  BLI_Stack *stack;
21 
22  stack = BLI_stack_new(sizeof(int), __func__);
23  EXPECT_TRUE(BLI_stack_is_empty(stack));
24  EXPECT_EQ(BLI_stack_count(stack), 0);
25  BLI_stack_free(stack);
26 }
27 
28 TEST(stack, One)
29 {
30  BLI_Stack *stack;
31  unsigned int in = -1, out = 1;
32 
33  stack = BLI_stack_new(sizeof(in), __func__);
34 
35  BLI_stack_push(stack, (void *)&in);
36  EXPECT_FALSE(BLI_stack_is_empty(stack));
37  EXPECT_EQ(BLI_stack_count(stack), 1);
38  BLI_stack_pop(stack, (void *)&out);
39  EXPECT_EQ(out, in);
40  EXPECT_TRUE(BLI_stack_is_empty(stack));
41  EXPECT_EQ(BLI_stack_count(stack), 0);
42  BLI_stack_free(stack);
43 }
44 
45 TEST(stack, Range)
46 {
47  const int tot = SIZE;
48  BLI_Stack *stack;
49  int in, out;
50 
51  stack = BLI_stack_new(sizeof(in), __func__);
52 
53  for (in = 0; in < tot; in++) {
54  BLI_stack_push(stack, (void *)&in);
55  }
56 
57  for (in = tot - 1; in >= 0; in--) {
58  EXPECT_FALSE(BLI_stack_is_empty(stack));
59  BLI_stack_pop(stack, (void *)&out);
60  EXPECT_EQ(out, in);
61  }
62  EXPECT_TRUE(BLI_stack_is_empty(stack));
63 
64  BLI_stack_free(stack);
65 }
66 
67 TEST(stack, String)
68 {
69  const int tot = SIZE;
70  int i;
71 
72  BLI_Stack *stack;
73  char in[] = "hello world!";
74  char out[sizeof(in)];
75 
76  stack = BLI_stack_new(sizeof(in), __func__);
77 
78  for (i = 0; i < tot; i++) {
79  *((int *)in) = i;
80  BLI_stack_push(stack, (void *)in);
81  }
82 
83  for (i = tot - 1; i >= 0; i--) {
84  EXPECT_FALSE(BLI_stack_is_empty(stack));
85  *((int *)in) = i;
86  BLI_stack_pop(stack, (void *)&out);
87  EXPECT_STREQ(in, out);
88  }
89  EXPECT_TRUE(BLI_stack_is_empty(stack));
90 
91  BLI_stack_free(stack);
92 }
93 
94 TEST(stack, Peek)
95 {
96  const int tot = SIZE;
97  int i;
98 
99  BLI_Stack *stack;
100  const short in[] = {1, 10, 100, 1000};
101 
102  stack = BLI_stack_new(sizeof(*in), __func__);
103 
104  for (i = 0; i < tot; i++) {
105  BLI_stack_push(stack, &in[i % ARRAY_SIZE(in)]);
106  }
107 
108  for (i = tot - 1; i >= 0; i--, BLI_stack_discard(stack)) {
109  short *ret = (short *)BLI_stack_peek(stack);
110  EXPECT_EQ(*ret, in[i % ARRAY_SIZE(in)]);
111  }
112 
113  EXPECT_TRUE(BLI_stack_is_empty(stack));
114 
115  BLI_stack_free(stack);
116 }
117 
118 /* Check that clearing the stack leaves in it a correct state. */
119 TEST(stack, Clear)
120 {
121  const int tot_rerun = 4;
122  int rerun;
123 
124  /* based on range test */
125  int tot = SIZE;
126  BLI_Stack *stack;
127  int in, out;
128 
129  /* use a small chunk size to ensure we test */
130  stack = BLI_stack_new(sizeof(in), __func__);
131 
132  for (rerun = 0; rerun < tot_rerun; rerun++) {
133  for (in = 0; in < tot; in++) {
134  BLI_stack_push(stack, (void *)&in);
135  }
136 
137  BLI_stack_clear(stack);
138  EXPECT_TRUE(BLI_stack_is_empty(stack));
139 
140  /* and again, this time check it is valid */
141  for (in = 0; in < tot; in++) {
142  BLI_stack_push(stack, (void *)&in);
143  }
144 
145  for (in = tot - 1; in >= 0; in--) {
146  EXPECT_FALSE(BLI_stack_is_empty(stack));
147  BLI_stack_pop(stack, (void *)&out);
148  EXPECT_EQ(out, in);
149  }
150 
151  EXPECT_TRUE(BLI_stack_is_empty(stack));
152 
153  /* without this, we won't test case when mixed free/used */
154  tot /= 2;
155  }
156 
157  BLI_stack_free(stack);
158 }
159 
160 TEST(stack, Reuse)
161 {
162  const int sizes[] = {3, 11, 81, 400, 999, 12, 1, 9721, 7, 99, 5, 0};
163  int sizes_test[ARRAY_SIZE(sizes)];
164  const int *s;
165  int out, i;
166  int sum, sum_test;
167 
168  BLI_Stack *stack;
169 
170  stack = BLI_stack_new(sizeof(i), __func__);
171 
172  /* add a bunch of numbers, ensure we get same sum out */
173  sum = 0;
174  for (s = sizes; *s; s++) {
175  for (i = *s; i != 0; i--) {
176  BLI_stack_push(stack, (void *)&i);
177  sum += i;
178  }
179  }
180  sum_test = 0;
181  while (!BLI_stack_is_empty(stack)) {
182  BLI_stack_pop(stack, (void *)&out);
183  sum_test += out;
184  }
185  EXPECT_EQ(sum, sum_test);
186 
187  /* add and remove all except last */
188  for (s = sizes; *s; s++) {
189  for (i = *s; i >= 0; i--) {
190  BLI_stack_push(stack, (void *)&i);
191  }
192  for (i = *s; i > 0; i--) {
193  BLI_stack_pop(stack, (void *)&out);
194  }
195  }
196 
197  i = ARRAY_SIZE(sizes) - 1;
198  while (!BLI_stack_is_empty(stack)) {
199  i--;
200  BLI_stack_pop(stack, (void *)&sizes_test[i]);
201  EXPECT_EQ(sizes_test[i], sizes[i]);
202  EXPECT_GT(i, -1);
203  }
204  EXPECT_EQ(0, i);
205  EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
206 
207  /* finally test BLI_stack_pop_n */
208  for (i = ARRAY_SIZE(sizes); i--;) {
209  BLI_stack_push(stack, (void *)&sizes[i]);
210  }
211  EXPECT_EQ(BLI_stack_count(stack), ARRAY_SIZE(sizes));
212  BLI_stack_pop_n(stack, (void *)sizes_test, ARRAY_SIZE(sizes));
213  EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
214 
215  BLI_stack_free(stack);
216 }
A (mainly) macro array library.
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition: stack.c:135
void * BLI_stack_peek(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:166
void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition: stack.c:144
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:225
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition: stack.c:129
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: stack.c:247
void BLI_stack_clear(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:193
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:94
void BLI_stack_discard(BLI_Stack *stack) ATTR_NONNULL()
Definition: stack.c:173
#define BLI_stack_new(esize, descr)
TEST(stack, Empty)
#define SIZE
#define ARRAY_SIZE(arr)
static T sum(const btAlignedObjectArray< T > &items)
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
return ret