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 32 static void TEST_INT_free(TEST_INT *x) { OPENSSL_free(x); } 33 34 BSSL_NAMESPACE_BEGIN 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 { 51 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 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 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 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 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 225 static int compare_reverse(const TEST_INT **a, const TEST_INT **b) { 226 return -compare(a, b); 227 } 228 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. 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. 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
