1 /* Apache License, Version 2.0 */
2
3 #include "testing/testing.h"
4 #include <string.h>
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
TEST(stack,Empty)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
TEST(stack,One)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
TEST(stack,Range)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
TEST(stack,String)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
TEST(stack,Peek)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. */
TEST(stack,Clear)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 its 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 wont test case when mixed free/used */
154 tot /= 2;
155 }
156
157 BLI_stack_free(stack);
158 }
159
TEST(stack,Reuse)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 }
217