Alex Deymo | 48ad5ab | 2017-09-13 22:17:57 +0200 | [diff] [blame] | 1 | // Copyright 2017 The Chromium OS Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #include "bsdiff/suffix_array_index.h" |
| 6 | |
| 7 | #include <stdlib.h> |
| 8 | |
| 9 | #include <algorithm> |
| 10 | #include <string> |
| 11 | #include <utility> |
| 12 | #include <vector> |
| 13 | |
Alex Deymo | 48ad5ab | 2017-09-13 22:17:57 +0200 | [diff] [blame] | 14 | #include <gtest/gtest.h> |
| 15 | |
| 16 | namespace bsdiff { |
| 17 | |
| 18 | class SuffixArrayIndexTest : public ::testing::Test { |
| 19 | protected: |
| 20 | void InitSA(const std::string& text) { |
| 21 | text_.resize(text.size()); |
| 22 | std::copy(text.begin(), text.end(), text_.data()); |
| 23 | sai_ = CreateSuffixArrayIndex(text_.data(), text_.size()); |
| 24 | } |
| 25 | |
| 26 | void SearchPrefix(const std::string& pattern, |
| 27 | size_t* out_length, |
| 28 | uint64_t* out_pos) { |
| 29 | sai_->SearchPrefix(reinterpret_cast<const uint8_t*>(pattern.data()), |
| 30 | pattern.size(), out_length, out_pos); |
| 31 | // Check that the returned values are indeed a valid prefix. |
| 32 | EXPECT_LE(*out_length, pattern.size()); |
| 33 | ASSERT_LT(*out_pos, text_.size()); |
| 34 | ASSERT_LE(*out_pos + *out_length, text_.size()); |
| 35 | EXPECT_EQ(0, memcmp(text_.data() + *out_pos, pattern.data(), *out_length)); |
| 36 | } |
| 37 | |
| 38 | std::vector<uint8_t> text_; |
| 39 | std::unique_ptr<SuffixArrayIndexInterface> sai_; |
| 40 | }; |
| 41 | |
| 42 | // Test that the suffix array index can be initialized with an example text. |
| 43 | TEST_F(SuffixArrayIndexTest, MississippiTest) { |
| 44 | InitSA("mississippi"); |
| 45 | } |
| 46 | |
| 47 | TEST_F(SuffixArrayIndexTest, EmptySuffixArrayTest) { |
| 48 | InitSA(""); |
| 49 | } |
| 50 | |
| 51 | // Test various corner cases while searching for prefixes. |
| 52 | TEST_F(SuffixArrayIndexTest, SearchPrefixTest) { |
| 53 | InitSA("abc1_abc2_abc3_ab_abcd"); |
| 54 | |
| 55 | uint64_t pos; |
| 56 | size_t length; |
| 57 | // The string is not found at all. |
| 58 | SearchPrefix("zzz", &length, &pos); // lexicographically highest. |
| 59 | EXPECT_EQ(0U, length); |
| 60 | |
| 61 | SearchPrefix(" ", &length, &pos); // lexicographically lowest. |
| 62 | EXPECT_EQ(0U, length); |
| 63 | |
| 64 | // The exact pattern is found multiple times. |
| 65 | SearchPrefix("abc", &length, &pos); |
| 66 | EXPECT_EQ(3U, length); |
| 67 | |
| 68 | // The exact pattern is found only one time, at the end of the string. |
| 69 | SearchPrefix("abcd", &length, &pos); |
| 70 | EXPECT_EQ(4U, length); |
| 71 | EXPECT_EQ(18U, pos); |
| 72 | |
| 73 | // The string is not found, but a prefix is found. |
| 74 | SearchPrefix("abcW", &length, &pos); |
| 75 | EXPECT_EQ(3U, length); |
| 76 | } |
| 77 | |
| 78 | } // namespace bsdiff |