Home | History | Annotate | Download | only in bsdiff 
      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:
     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
     79