Merge remote-tracking branch 'origin/master' into blender2.8
[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_TRUE(BLI_stack_is_empty(stack));
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_FALSE(BLI_stack_is_empty(stack));
41         EXPECT_EQ(BLI_stack_count(stack), 1);
42         BLI_stack_pop(stack, (void *)&out);
43         EXPECT_EQ(out, in);
44         EXPECT_TRUE(BLI_stack_is_empty(stack));
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_FALSE(BLI_stack_is_empty(stack));
63                 BLI_stack_pop(stack, (void *)&out);
64                 EXPECT_EQ(out, in);
65
66         }
67         EXPECT_TRUE(BLI_stack_is_empty(stack));
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_FALSE(BLI_stack_is_empty(stack));
90                 *((int *)in) = i;
91                 BLI_stack_pop(stack, (void *)&out);
92                 EXPECT_STREQ(in, out);
93         }
94         EXPECT_TRUE(BLI_stack_is_empty(stack));
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_TRUE(BLI_stack_is_empty(stack));
119
120         BLI_stack_free(stack);
121 }
122
123 /* Check that clearing the stack leaves in it a correct state. */
124 TEST(stack, Clear)
125 {
126         const int tot_rerun = 4;
127         int rerun;
128
129         /* based on range test */
130         int tot = SIZE;
131         BLI_Stack *stack;
132         int in, out;
133
134         /* use a small chunk size to ensure we test */
135         stack = BLI_stack_new(sizeof(in), __func__);
136
137         for (rerun = 0; rerun < tot_rerun; rerun++) {
138                 for (in = 0; in < tot; in++) {
139                         BLI_stack_push(stack, (void *)&in);
140                 }
141
142                 BLI_stack_clear(stack);
143                 EXPECT_TRUE(BLI_stack_is_empty(stack));
144
145                 /* and again, this time check its valid */
146                 for (in = 0; in < tot; in++) {
147                         BLI_stack_push(stack, (void *)&in);
148                 }
149
150                 for (in = tot - 1; in >= 0; in--) {
151                         EXPECT_FALSE(BLI_stack_is_empty(stack));
152                         BLI_stack_pop(stack, (void *)&out);
153                         EXPECT_EQ(out, in);
154                 }
155
156                 EXPECT_TRUE(BLI_stack_is_empty(stack));
157
158                 /* without this, we wont test case when mixed free/used */
159                 tot /= 2;
160         }
161
162         BLI_stack_free(stack);
163 }
164
165
166 TEST(stack, Reuse)
167 {
168         const int sizes[] = {3, 11, 81, 400, 999, 12, 1, 9721, 7, 99, 5, 0};
169         int sizes_test[ARRAY_SIZE(sizes)];
170         const int *s;
171         int out, i;
172         int sum, sum_test;
173
174         BLI_Stack *stack;
175
176         stack = BLI_stack_new(sizeof(i), __func__);
177
178         /* add a bunch of numbers, ensure we get same sum out */
179         sum = 0;
180         for (s = sizes; *s; s++) {
181                 for (i = *s; i != 0; i--) {
182                         BLI_stack_push(stack, (void *)&i);
183                         sum += i;
184                 }
185         }
186         sum_test = 0;
187         while (!BLI_stack_is_empty(stack)) {
188                 BLI_stack_pop(stack, (void *)&out);
189                 sum_test += out;
190         }
191         EXPECT_EQ(sum, sum_test);
192
193         /* add and remove all except last */
194         for (s = sizes; *s; s++) {
195                 for (i = *s; i >= 0; i--) {
196                         BLI_stack_push(stack, (void *)&i);
197                 }
198                 for (i = *s; i > 0; i--) {
199                         BLI_stack_pop(stack, (void *)&out);
200                 }
201         }
202
203         i = ARRAY_SIZE(sizes) - 1;
204         while (!BLI_stack_is_empty(stack)) {
205                 i--;
206                 BLI_stack_pop(stack, (void *)&sizes_test[i]);
207                 EXPECT_EQ(sizes_test[i], sizes[i]);
208                 EXPECT_GT(i, -1);
209         }
210         EXPECT_EQ(0, i);
211         EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
212
213
214         /* finally test BLI_stack_pop_n */
215         for (i = ARRAY_SIZE(sizes); i--; ) {
216                 BLI_stack_push(stack, (void *)&sizes[i]);
217         }
218         EXPECT_EQ(BLI_stack_count(stack), ARRAY_SIZE(sizes));
219         BLI_stack_pop_n(stack, (void *)sizes_test, ARRAY_SIZE(sizes));
220         EXPECT_EQ(memcmp(sizes, sizes_test, sizeof(sizes) - sizeof(int)), 0);
221
222         BLI_stack_free(stack);
223 }