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
14 #include <gtest/gtest.h>
15
16 namespace bsdiff {
17
18 class SuffixArrayIndexTest : public ::testing::Test {
19 protected:
InitSA(const std::string & text)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
SearchPrefix(const std::string & pattern,size_t * out_length,uint64_t * out_pos)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.
TEST_F(SuffixArrayIndexTest,MississippiTest)43 TEST_F(SuffixArrayIndexTest, MississippiTest) {
44 InitSA("mississippi");
45 }
46
TEST_F(SuffixArrayIndexTest,EmptySuffixArrayTest)47 TEST_F(SuffixArrayIndexTest, EmptySuffixArrayTest) {
48 InitSA("");
49 }
50
51 // Test various corner cases while searching for prefixes.
TEST_F(SuffixArrayIndexTest,SearchPrefixTest)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
79