blob: 87c867dba3c6c9245c80eecbe2b3cdc5b14413b4 [file] [log] [blame]
// Copyright 2017 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "bsdiff/suffix_array_index.h"
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <gtest/gtest.h>
namespace bsdiff {
class SuffixArrayIndexTest : public ::testing::Test {
void InitSA(const std::string& text) {
std::copy(text.begin(), text.end(),;
sai_ = CreateSuffixArrayIndex(, text_.size());
void SearchPrefix(const std::string& pattern,
size_t* out_length,
uint64_t* out_pos) {
sai_->SearchPrefix(reinterpret_cast<const uint8_t*>(,
pattern.size(), out_length, out_pos);
// Check that the returned values are indeed a valid prefix.
EXPECT_LE(*out_length, pattern.size());
ASSERT_LT(*out_pos, text_.size());
ASSERT_LE(*out_pos + *out_length, text_.size());
EXPECT_EQ(0, memcmp( + *out_pos,, *out_length));
std::vector<uint8_t> text_;
std::unique_ptr<SuffixArrayIndexInterface> sai_;
// Test that the suffix array index can be initialized with an example text.
TEST_F(SuffixArrayIndexTest, MississippiTest) {
TEST_F(SuffixArrayIndexTest, EmptySuffixArrayTest) {
// Test various corner cases while searching for prefixes.
TEST_F(SuffixArrayIndexTest, SearchPrefixTest) {
uint64_t pos;
size_t length;
// The string is not found at all.
SearchPrefix("zzz", &length, &pos); // lexicographically highest.
EXPECT_EQ(0U, length);
SearchPrefix(" ", &length, &pos); // lexicographically lowest.
EXPECT_EQ(0U, length);
// The exact pattern is found multiple times.
SearchPrefix("abc", &length, &pos);
EXPECT_EQ(3U, length);
// The exact pattern is found only one time, at the end of the string.
SearchPrefix("abcd", &length, &pos);
EXPECT_EQ(4U, length);
EXPECT_EQ(18U, pos);
// The string is not found, but a prefix is found.
SearchPrefix("abcW", &length, &pos);
EXPECT_EQ(3U, length);
} // namespace bsdiff