1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// Copyright 2015 The Chromium 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 "net/base/lookup_string_in_fixed_set.h"
#include <string.h>
#include <ostream>
#include "testing/gtest/include/gtest/gtest.h"
namespace net {
namespace {
namespace test1 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest1-inc.cc"
}
namespace test3 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest3-inc.cc"
}
namespace test4 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest4-inc.cc"
}
namespace test5 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest5-inc.cc"
}
namespace test6 {
#include "net/base/registry_controlled_domains/effective_tld_names_unittest6-inc.cc"
}
struct Expectation {
const char* const key;
int value;
};
void PrintTo(const Expectation& expectation, std::ostream* os) {
*os << "{\"" << expectation.key << "\", " << expectation.value << "}";
}
class LookupStringInFixedSetTest : public testing::TestWithParam<Expectation> {
protected:
template <size_t N>
int LookupInGraph(const unsigned char(&graph)[N], const char* key) {
return LookupStringInFixedSet(graph, N, key, strlen(key));
}
};
class Dafsa1Test : public LookupStringInFixedSetTest {};
TEST_P(Dafsa1Test, BasicTest) {
const Expectation& param = GetParam();
EXPECT_EQ(param.value, LookupInGraph(test1::kDafsa, param.key));
}
const Expectation kBasicTestCases[] = {
{"", -1}, {"j", -1}, {"jp", 0}, {"jjp", -1}, {"jpp", -1},
{"bar.jp", 2}, {"pref.bar.jp", 1}, {"c", 2}, {"b.c", 1}, {"priv.no", 4},
};
INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
Dafsa1Test,
::testing::ValuesIn(kBasicTestCases));
class Dafsa3Test : public LookupStringInFixedSetTest {};
// This DAFSA is constructed so that labels begin and end with unique
// characters, which makes it impossible to merge labels. Each inner node
// is about 100 bytes and a one byte offset can at most add 64 bytes to
// previous offset. Thus the paths must go over two byte offsets.
TEST_P(Dafsa3Test, TestDafsaTwoByteOffsets) {
const Expectation& param = GetParam();
EXPECT_EQ(param.value, LookupInGraph(test3::kDafsa, param.key));
}
const Expectation kTwoByteOffsetTestCases[] = {
{"0________________________________________________________________________"
"____________________________0",
0},
{"7________________________________________________________________________"
"____________________________7",
4},
{"a________________________________________________________________________"
"____________________________8",
-1},
};
INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
Dafsa3Test,
::testing::ValuesIn(kTwoByteOffsetTestCases));
class Dafsa4Test : public LookupStringInFixedSetTest {};
// This DAFSA is constructed so that labels begin and end with unique
// characters, which makes it impossible to merge labels. The byte array
// has a size of ~54k. A two byte offset can add at most add 8k to the
// previous offset. Since we can skip only forward in memory, the nodes
// representing the return values must be located near the end of the byte
// array. The probability that we can reach from an arbitrary inner node to
// a return value without using a three byte offset is small (but not zero).
// The test is repeated with some different keys and with a reasonable
// probability at least one of the tested paths has go over a three byte
// offset.
TEST_P(Dafsa4Test, TestDafsaThreeByteOffsets) {
const Expectation& param = GetParam();
EXPECT_EQ(param.value, LookupInGraph(test4::kDafsa, param.key));
}
const Expectation kThreeByteOffsetTestCases[] = {
{"Z6_______________________________________________________________________"
"_____________________________Z6",
0},
{"Z7_______________________________________________________________________"
"_____________________________Z7",
4},
{"Za_______________________________________________________________________"
"_____________________________Z8",
-1},
};
INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
Dafsa4Test,
::testing::ValuesIn(kThreeByteOffsetTestCases));
class Dafsa5Test : public LookupStringInFixedSetTest {};
// This DAFSA is constructed from words with similar prefixes but distinct
// suffixes. The DAFSA will then form a trie with the implicit source node
// as root.
TEST_P(Dafsa5Test, TestDafsaJoinedPrefixes) {
const Expectation& param = GetParam();
EXPECT_EQ(param.value, LookupInGraph(test5::kDafsa, param.key));
}
const Expectation kJoinedPrefixesTestCases[] = {
{"ai", 0}, {"bj", 4}, {"aak", 0}, {"bbl", 4},
{"aaa", -1}, {"bbb", -1}, {"aaaam", 0}, {"bbbbn", 0},
};
INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
Dafsa5Test,
::testing::ValuesIn(kJoinedPrefixesTestCases));
class Dafsa6Test : public LookupStringInFixedSetTest {};
// This DAFSA is constructed from words with similar suffixes but distinct
// prefixes. The DAFSA will then form a trie with the implicit sink node as
// root.
TEST_P(Dafsa6Test, TestDafsaJoinedSuffixes) {
const Expectation& param = GetParam();
EXPECT_EQ(param.value, LookupInGraph(test6::kDafsa, param.key));
}
const Expectation kJoinedSuffixesTestCases[] = {
{"ia", 0}, {"jb", 4}, {"kaa", 0}, {"lbb", 4},
{"aaa", -1}, {"bbb", -1}, {"maaaa", 0}, {"nbbbb", 0},
};
INSTANTIATE_TEST_CASE_P(LookupStringInFixedSetTest,
Dafsa6Test,
::testing::ValuesIn(kJoinedSuffixesTestCases));
} // namespace
} // namespace net
|
