1 /* Copyright (c) 2018, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 #include <openssl/stack.h>
16
17 #include <limits.h>
18
19 #include <algorithm>
20 #include <memory>
21 #include <utility>
22 #include <vector>
23
24 #include <gtest/gtest.h>
25
26 #include <openssl/mem.h>
27
28
29 // Define a custom stack type for testing.
30 using TEST_INT = int;
31
TEST_INT_free(TEST_INT * x)32 static void TEST_INT_free(TEST_INT *x) { OPENSSL_free(x); }
33
34 BSSL_NAMESPACE_BEGIN
BORINGSSL_MAKE_DELETER(TEST_INT,TEST_INT_free)35 BORINGSSL_MAKE_DELETER(TEST_INT, TEST_INT_free)
36 BSSL_NAMESPACE_END
37
38 static bssl::UniquePtr<TEST_INT> TEST_INT_new(int x) {
39 bssl::UniquePtr<TEST_INT> ret(
40 static_cast<TEST_INT *>(OPENSSL_malloc(sizeof(TEST_INT))));
41 if (!ret) {
42 return nullptr;
43 }
44 *ret = x;
45 return ret;
46 }
47
48 DEFINE_STACK_OF(TEST_INT)
49
50 struct ShallowStackDeleter {
operator ()ShallowStackDeleter51 void operator()(STACK_OF(TEST_INT) *sk) const { sk_TEST_INT_free(sk); }
52 };
53
54 using ShallowStack = std::unique_ptr<STACK_OF(TEST_INT), ShallowStackDeleter>;
55
56 // kNull is treated as a nullptr expectation for purposes of ExpectStackEquals.
57 // The tests in this file will never use it as a test value.
58 static const int kNull = INT_MIN;
59
ExpectStackEquals(const STACK_OF (TEST_INT)* sk,const std::vector<int> & vec)60 static void ExpectStackEquals(const STACK_OF(TEST_INT) *sk,
61 const std::vector<int> &vec) {
62 EXPECT_EQ(vec.size(), sk_TEST_INT_num(sk));
63 for (size_t i = 0; i < vec.size(); i++) {
64 SCOPED_TRACE(i);
65 const TEST_INT *obj = sk_TEST_INT_value(sk, i);
66 if (vec[i] == kNull) {
67 EXPECT_FALSE(obj);
68 } else {
69 EXPECT_TRUE(obj);
70 if (obj) {
71 EXPECT_EQ(vec[i], *obj);
72 }
73 }
74 }
75
76 // Reading out-of-bounds fails.
77 EXPECT_FALSE(sk_TEST_INT_value(sk, vec.size()));
78 EXPECT_FALSE(sk_TEST_INT_value(sk, vec.size() + 1));
79 }
80
TEST(StackTest,Basic)81 TEST(StackTest, Basic) {
82 bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
83 ASSERT_TRUE(sk);
84
85 // The stack starts out empty.
86 ExpectStackEquals(sk.get(), {});
87
88 // Removing elements from an empty stack does nothing.
89 EXPECT_FALSE(sk_TEST_INT_pop(sk.get()));
90 EXPECT_FALSE(sk_TEST_INT_shift(sk.get()));
91 EXPECT_FALSE(sk_TEST_INT_delete(sk.get(), 0));
92
93 // Push some elements.
94 for (int i = 0; i < 6; i++) {
95 auto value = TEST_INT_new(i);
96 ASSERT_TRUE(value);
97 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
98 }
99
100 ExpectStackEquals(sk.get(), {0, 1, 2, 3, 4, 5});
101
102 // Items may be inserted in the middle.
103 auto value = TEST_INT_new(6);
104 ASSERT_TRUE(value);
105 // Hold on to the object for later.
106 TEST_INT *raw = value.get();
107 ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 4));
108 value.release(); // sk_TEST_INT_insert takes ownership on success.
109
110 ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5});
111
112 // Without a comparison function, find searches by pointer.
113 value = TEST_INT_new(6);
114 ASSERT_TRUE(value);
115 size_t index;
116 EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, value.get()));
117 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, raw));
118 EXPECT_EQ(4u, index);
119
120 // sk_TEST_INT_insert can also insert values at the end.
121 value = TEST_INT_new(7);
122 ASSERT_TRUE(value);
123 ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 7));
124 value.release(); // sk_TEST_INT_insert takes ownership on success.
125
126 ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7});
127
128 // Out-of-bounds indices are clamped.
129 value = TEST_INT_new(8);
130 ASSERT_TRUE(value);
131 ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 999));
132 value.release(); // sk_TEST_INT_insert takes ownership on success.
133
134 ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7, 8});
135
136 // Test removing elements from various places.
137 bssl::UniquePtr<TEST_INT> removed(sk_TEST_INT_pop(sk.get()));
138 EXPECT_EQ(8, *removed);
139 ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7});
140
141 removed.reset(sk_TEST_INT_shift(sk.get()));
142 EXPECT_EQ(0, *removed);
143 ExpectStackEquals(sk.get(), {1, 2, 3, 6, 4, 5, 7});
144
145 removed.reset(sk_TEST_INT_delete(sk.get(), 2));
146 EXPECT_EQ(3, *removed);
147 ExpectStackEquals(sk.get(), {1, 2, 6, 4, 5, 7});
148
149 // Objects may also be deleted by pointer.
150 removed.reset(sk_TEST_INT_delete_ptr(sk.get(), raw));
151 EXPECT_EQ(raw, removed.get());
152 ExpectStackEquals(sk.get(), {1, 2, 4, 5, 7});
153
154 // Deleting is a no-op is the object is not found.
155 value = TEST_INT_new(100);
156 ASSERT_TRUE(value);
157 EXPECT_FALSE(sk_TEST_INT_delete_ptr(sk.get(), value.get()));
158
159 // Insert nullptr to test deep copy handling of it.
160 ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), nullptr, 0));
161 ExpectStackEquals(sk.get(), {kNull, 1, 2, 4, 5, 7});
162
163 // Test both deep and shallow copies.
164 bssl::UniquePtr<STACK_OF(TEST_INT)> copy(sk_TEST_INT_deep_copy(
165 sk.get(),
166 [](TEST_INT *x) -> TEST_INT * {
167 return x == nullptr ? nullptr : TEST_INT_new(*x).release();
168 },
169 TEST_INT_free));
170 ASSERT_TRUE(copy);
171 ExpectStackEquals(copy.get(), {kNull, 1, 2, 4, 5, 7});
172
173 ShallowStack shallow(sk_TEST_INT_dup(sk.get()));
174 ASSERT_TRUE(shallow);
175 ASSERT_EQ(sk_TEST_INT_num(sk.get()), sk_TEST_INT_num(shallow.get()));
176 for (size_t i = 0; i < sk_TEST_INT_num(sk.get()); i++) {
177 EXPECT_EQ(sk_TEST_INT_value(sk.get(), i),
178 sk_TEST_INT_value(shallow.get(), i));
179 }
180
181 // Deep copies may fail. This should clean up temporaries.
182 EXPECT_FALSE(sk_TEST_INT_deep_copy(sk.get(),
183 [](TEST_INT *x) -> TEST_INT * {
184 return x == nullptr || *x == 4
185 ? nullptr
186 : TEST_INT_new(*x).release();
187 },
188 TEST_INT_free));
189
190 // sk_TEST_INT_zero clears a stack, but does not free the elements.
191 ShallowStack shallow2(sk_TEST_INT_dup(sk.get()));
192 ASSERT_TRUE(shallow2);
193 sk_TEST_INT_zero(shallow2.get());
194 ExpectStackEquals(shallow2.get(), {});
195 }
196
TEST(StackTest,BigStack)197 TEST(StackTest, BigStack) {
198 bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
199 ASSERT_TRUE(sk);
200
201 std::vector<int> expected;
202 static const int kCount = 100000;
203 for (int i = 0; i < kCount; i++) {
204 auto value = TEST_INT_new(i);
205 ASSERT_TRUE(value);
206 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
207 expected.push_back(i);
208 }
209 ExpectStackEquals(sk.get(), expected);
210 }
211
212 static uint64_t g_compare_count = 0;
213
compare(const TEST_INT ** a,const TEST_INT ** b)214 static int compare(const TEST_INT **a, const TEST_INT **b) {
215 g_compare_count++;
216 if (**a < **b) {
217 return -1;
218 }
219 if (**a > **b) {
220 return 1;
221 }
222 return 0;
223 }
224
compare_reverse(const TEST_INT ** a,const TEST_INT ** b)225 static int compare_reverse(const TEST_INT **a, const TEST_INT **b) {
226 return -compare(a, b);
227 }
228
TEST(StackTest,Sorted)229 TEST(StackTest, Sorted) {
230 std::vector<int> vec_sorted = {0, 1, 2, 3, 4, 5, 6};
231 std::vector<int> vec = vec_sorted;
232 do {
233 bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
234 ASSERT_TRUE(sk);
235 for (int v : vec) {
236 auto value = TEST_INT_new(v);
237 ASSERT_TRUE(value);
238 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
239 }
240
241 // The stack is not (known to be) sorted.
242 EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
243
244 // With a comparison function, find matches by value.
245 auto ten = TEST_INT_new(10);
246 ASSERT_TRUE(ten);
247 size_t index;
248 EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, ten.get()));
249
250 auto three = TEST_INT_new(3);
251 ASSERT_TRUE(three);
252 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
253 EXPECT_EQ(3, *sk_TEST_INT_value(sk.get(), index));
254
255 sk_TEST_INT_sort(sk.get());
256 EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
257 ExpectStackEquals(sk.get(), vec_sorted);
258
259 // Sorting an already-sorted list is a no-op.
260 uint64_t old_compare_count = g_compare_count;
261 sk_TEST_INT_sort(sk.get());
262 EXPECT_EQ(old_compare_count, g_compare_count);
263 EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
264 ExpectStackEquals(sk.get(), vec_sorted);
265
266 // When sorted, find uses binary search.
267 ASSERT_TRUE(ten);
268 EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, ten.get()));
269
270 ASSERT_TRUE(three);
271 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
272 EXPECT_EQ(3u, index);
273
274 // Copies preserve comparison and sorted information.
275 bssl::UniquePtr<STACK_OF(TEST_INT)> copy(sk_TEST_INT_deep_copy(
276 sk.get(),
277 [](TEST_INT *x) -> TEST_INT * { return TEST_INT_new(*x).release(); },
278 TEST_INT_free));
279 ASSERT_TRUE(copy);
280 EXPECT_TRUE(sk_TEST_INT_is_sorted(copy.get()));
281 ASSERT_TRUE(sk_TEST_INT_find(copy.get(), &index, three.get()));
282 EXPECT_EQ(3u, index);
283
284 ShallowStack copy2(sk_TEST_INT_dup(sk.get()));
285 ASSERT_TRUE(copy2);
286 EXPECT_TRUE(sk_TEST_INT_is_sorted(copy2.get()));
287 ASSERT_TRUE(sk_TEST_INT_find(copy2.get(), &index, three.get()));
288 EXPECT_EQ(3u, index);
289
290 // Removing elements does not affect sortedness.
291 TEST_INT_free(sk_TEST_INT_delete(sk.get(), 0));
292 EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
293
294 // Changing the comparison function invalidates sortedness.
295 sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
296 EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
297 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
298 EXPECT_EQ(2u, index);
299
300 sk_TEST_INT_sort(sk.get());
301 ExpectStackEquals(sk.get(), {6, 5, 4, 3, 2, 1});
302 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
303 EXPECT_EQ(3u, index);
304
305 // Inserting a new element invalidates sortedness.
306 auto tmp = TEST_INT_new(10);
307 ASSERT_TRUE(tmp);
308 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(tmp)));
309 EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
310 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, ten.get()));
311 EXPECT_EQ(6u, index);
312 } while (std::next_permutation(vec.begin(), vec.end()));
313 }
314
315 // sk_*_find should return the first matching element in all cases.
TEST(StackTest,FindFirst)316 TEST(StackTest, FindFirst) {
317 bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
318 auto value = TEST_INT_new(1);
319 ASSERT_TRUE(value);
320 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
321 for (int i = 0; i < 10; i++) {
322 value = TEST_INT_new(2);
323 ASSERT_TRUE(value);
324 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
325 }
326
327 const TEST_INT *two = sk_TEST_INT_value(sk.get(), 1);
328 // Pointer-based equality.
329 size_t index;
330 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
331 EXPECT_EQ(1u, index);
332
333 // Comparator-based equality, unsorted.
334 sk_TEST_INT_set_cmp_func(sk.get(), compare);
335 EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
336 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
337 EXPECT_EQ(1u, index);
338
339 // Comparator-based equality, sorted.
340 sk_TEST_INT_sort(sk.get());
341 EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
342 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
343 EXPECT_EQ(1u, index);
344
345 // Comparator-based equality, sorted and at the front.
346 sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
347 sk_TEST_INT_sort(sk.get());
348 EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
349 ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
350 EXPECT_EQ(0u, index);
351 }
352
353 // Exhaustively test the binary search.
TEST(StackTest,BinarySearch)354 TEST(StackTest, BinarySearch) {
355 static const size_t kCount = 100;
356 for (size_t i = 0; i < kCount; i++) {
357 SCOPED_TRACE(i);
358 for (size_t j = i; j <= kCount; j++) {
359 SCOPED_TRACE(j);
360 // Make a stack where [0, i) are below, [i, j) match, and [j, kCount) are
361 // above.
362 bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
363 ASSERT_TRUE(sk);
364 for (size_t k = 0; k < i; k++) {
365 auto value = TEST_INT_new(-1);
366 ASSERT_TRUE(value);
367 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
368 }
369 for (size_t k = i; k < j; k++) {
370 auto value = TEST_INT_new(0);
371 ASSERT_TRUE(value);
372 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
373 }
374 for (size_t k = j; k < kCount; k++) {
375 auto value = TEST_INT_new(1);
376 ASSERT_TRUE(value);
377 ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
378 }
379 sk_TEST_INT_sort(sk.get());
380
381 auto key = TEST_INT_new(0);
382 ASSERT_TRUE(key);
383
384 size_t idx;
385 int found = sk_TEST_INT_find(sk.get(), &idx, key.get());
386 if (i == j) {
387 EXPECT_FALSE(found);
388 } else {
389 ASSERT_TRUE(found);
390 EXPECT_EQ(i, idx);
391 }
392 }
393 }
394 }
395