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