OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "courgette/third_party/bsdiff/qsufsort.h" | 5 #include "courgette/third_party/bsdiff/qsufsort.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 | 8 |
9 #include <algorithm> | 9 #include <algorithm> |
10 #include <cstring> | 10 #include <cstring> |
11 #include <string> | 11 #include <string> |
12 #include <vector> | 12 #include <vector> |
13 | 13 |
14 #include "base/macros.h" | 14 #include "base/macros.h" |
| 15 #include "courgette/third_party/bsdiff/bsdiff_search.h" |
15 #include "testing/gtest/include/gtest/gtest.h" | 16 #include "testing/gtest/include/gtest/gtest.h" |
16 | 17 |
17 TEST(QSufSortTest, Sort) { | 18 TEST(QSufSortTest, Sort) { |
18 const char* test_cases[] = { | 19 const char* test_cases[] = { |
19 "", | 20 "", |
20 "a", | 21 "a", |
21 "za", | 22 "za", |
22 "CACAO", | 23 "CACAO", |
23 "banana", | 24 "banana", |
24 "tobeornottobe", | 25 "tobeornottobe", |
25 "The quick brown fox jumps over the lazy dog.", | 26 "The quick brown fox jumps over the lazy dog.", |
26 "elephantelephantelephantelephantelephant", | 27 "elephantelephantelephantelephantelephant", |
27 "-------------------------", | 28 "-------------------------", |
28 "011010011001011010010110011010010", | 29 "011010011001011010010110011010010", |
29 "3141592653589793238462643383279502884197169399375105", | 30 "3141592653589793238462643383279502884197169399375105", |
30 "\xFF\xFE\xFF\xFE\xFD\x80\x30\x31\x32\x80\x30\xFF\x01\xAB\xCD", | 31 "\xFF\xFE\xFF\xFE\xFD\x80\x30\x31\x32\x80\x30\xFF\x01\xAB\xCD", |
31 }; | 32 }; |
32 | 33 |
33 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 34 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
34 int len = static_cast<int>(::strlen(test_cases[idx])); | 35 int len = static_cast<int>(::strlen(test_cases[idx])); |
35 const unsigned char* s = | 36 const unsigned char* s = |
36 reinterpret_cast<const unsigned char*>(test_cases[idx]); | 37 reinterpret_cast<const unsigned char*>(test_cases[idx]); |
37 | 38 |
38 // Generate the suffix array as I. | 39 // Generate the suffix array as I. |
39 std::vector<int> I(len + 1); | 40 std::vector<int> I(len + 1); |
40 std::vector<int> V(len + 1); | 41 std::vector<int> V(len + 1); |
41 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], s, len); | 42 qsuf::qsufsort<int*>(&I[0], &V[0], s, len); |
42 | 43 |
43 // Expect that I[] is a permutation of [0, len]. | 44 // Expect that I[] is a permutation of [0, len]. |
44 std::vector<int> I_sorted(I); | 45 std::vector<int> I_sorted(I); |
45 std::sort(I_sorted.begin(), I_sorted.end()); | 46 std::sort(I_sorted.begin(), I_sorted.end()); |
46 for (int i = 0; i < len + 1; ++i) { | 47 for (int i = 0; i < len + 1; ++i) { |
47 EXPECT_EQ(i, I_sorted[i]) << "test_case[" << idx << "]"; | 48 EXPECT_EQ(i, I_sorted[i]) << "test_case[" << idx << "]"; |
48 } | 49 } |
49 | 50 |
50 // First string must be empty string. | 51 // First string must be empty string. |
51 EXPECT_EQ(len, I[0]) << "test_case[" << idx << "]"; | 52 EXPECT_EQ(len, I[0]) << "test_case[" << idx << "]"; |
(...skipping 12 matching lines...) Expand all Loading... |
64 TEST(QSufSortTest, Search) { | 65 TEST(QSufSortTest, Search) { |
65 // Initialize main string and the suffix array. | 66 // Initialize main string and the suffix array. |
66 // Positions: 00000000001111111111122222222233333333334444 | 67 // Positions: 00000000001111111111122222222233333333334444 |
67 // 01234567890123456789012345678901234567890123 | 68 // 01234567890123456789012345678901234567890123 |
68 const char* old_str = "the quick brown fox jumps over the lazy dog."; | 69 const char* old_str = "the quick brown fox jumps over the lazy dog."; |
69 int old_size = static_cast<int>(::strlen(old_str)); | 70 int old_size = static_cast<int>(::strlen(old_str)); |
70 const unsigned char* old_buf = | 71 const unsigned char* old_buf = |
71 reinterpret_cast<const unsigned char*>(old_str); | 72 reinterpret_cast<const unsigned char*>(old_str); |
72 std::vector<int> I(old_size + 1); | 73 std::vector<int> I(old_size + 1); |
73 std::vector<int> V(old_size + 1); | 74 std::vector<int> V(old_size + 1); |
74 courgette::qsuf::qsufsort<int*>(&I[0], &V[0], old_buf, old_size); | 75 qsuf::qsufsort<int*>(&I[0], &V[0], old_buf, old_size); |
75 | 76 |
76 // Test queries. | 77 // Test queries. |
77 const struct { | 78 const struct { |
78 int exp_pos; // -1 means "don't care". | 79 int exp_pos; // -1 means "don't care". |
79 int exp_match_len; | 80 int exp_match_len; |
80 const char* query_str; | 81 const char* query_str; |
81 } test_cases[] = { | 82 } test_cases[] = { |
82 // Entire string. | 83 // Entire string. |
83 {0, 44, "the quick brown fox jumps over the lazy dog."}, | 84 {0, 44, "the quick brown fox jumps over the lazy dog."}, |
84 // Empty string. | 85 // Empty string. |
(...skipping 25 matching lines...) Expand all Loading... |
110 }; | 111 }; |
111 | 112 |
112 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 113 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
113 const auto& test_case = test_cases[idx]; | 114 const auto& test_case = test_cases[idx]; |
114 int new_size = static_cast<int>(::strlen(test_case.query_str)); | 115 int new_size = static_cast<int>(::strlen(test_case.query_str)); |
115 const unsigned char* new_buf = | 116 const unsigned char* new_buf = |
116 reinterpret_cast<const unsigned char*>(test_case.query_str); | 117 reinterpret_cast<const unsigned char*>(test_case.query_str); |
117 | 118 |
118 // Perform the search. | 119 // Perform the search. |
119 int pos = 0; | 120 int pos = 0; |
120 int match_len = courgette::qsuf::search(&I[0], old_buf, old_size, new_buf, | 121 int match_len = bsdiff::search(&I[0], old_buf, old_size, new_buf, new_size, |
121 new_size, &pos); | 122 &pos); |
122 | 123 |
123 // Check basic properties and match with expected values. | 124 // Check basic properties and match with expected values. |
124 EXPECT_GE(match_len, 0) << "test_case[" << idx << "]"; | 125 EXPECT_GE(match_len, 0) << "test_case[" << idx << "]"; |
125 EXPECT_LE(match_len, new_size) << "test_case[" << idx << "]"; | 126 EXPECT_LE(match_len, new_size) << "test_case[" << idx << "]"; |
126 if (match_len > 0) { | 127 if (match_len > 0) { |
127 EXPECT_GE(pos, 0) << "test_case[" << idx << "]"; | 128 EXPECT_GE(pos, 0) << "test_case[" << idx << "]"; |
128 EXPECT_LE(pos, old_size - match_len) << "test_case[" << idx << "]"; | 129 EXPECT_LE(pos, old_size - match_len) << "test_case[" << idx << "]"; |
129 EXPECT_EQ(0, ::memcmp(old_buf + pos, new_buf, match_len)) << "test_case[" | 130 EXPECT_EQ(0, ::memcmp(old_buf + pos, new_buf, match_len)) << "test_case[" |
130 << idx << "]"; | 131 << idx << "]"; |
131 } | 132 } |
132 if (test_case.exp_pos >= 0) { | 133 if (test_case.exp_pos >= 0) { |
133 EXPECT_EQ(test_case.exp_pos, pos) << "test_case[" << idx << "]"; | 134 EXPECT_EQ(test_case.exp_pos, pos) << "test_case[" << idx << "]"; |
134 } | 135 } |
135 EXPECT_EQ(test_case.exp_match_len, match_len) << "test_case[" << idx << "]"; | 136 EXPECT_EQ(test_case.exp_match_len, match_len) << "test_case[" << idx << "]"; |
136 } | 137 } |
137 } | 138 } |
OLD | NEW |