1 // Copyright (c) 2011 The LevelDB 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. See the AUTHORS file for names of contributors.
4
5 #include "db/version_set.h"
6 #include "util/logging.h"
7 #include "util/testharness.h"
8 #include "util/testutil.h"
9
10 namespace leveldb {
11
12 class FindFileTest {
13 public:
14 std::vector<FileMetaData*> files_;
15 bool disjoint_sorted_files_;
16
FindFileTest()17 FindFileTest() : disjoint_sorted_files_(true) { }
18
~FindFileTest()19 ~FindFileTest() {
20 for (int i = 0; i < files_.size(); i++) {
21 delete files_[i];
22 }
23 }
24
Add(const char * smallest,const char * largest,SequenceNumber smallest_seq=100,SequenceNumber largest_seq=100)25 void Add(const char* smallest, const char* largest,
26 SequenceNumber smallest_seq = 100,
27 SequenceNumber largest_seq = 100) {
28 FileMetaData* f = new FileMetaData;
29 f->number = files_.size() + 1;
30 f->smallest = InternalKey(smallest, smallest_seq, kTypeValue);
31 f->largest = InternalKey(largest, largest_seq, kTypeValue);
32 files_.push_back(f);
33 }
34
Find(const char * key)35 int Find(const char* key) {
36 InternalKey target(key, 100, kTypeValue);
37 InternalKeyComparator cmp(BytewiseComparator());
38 return FindFile(cmp, files_, target.Encode());
39 }
40
Overlaps(const char * smallest,const char * largest)41 bool Overlaps(const char* smallest, const char* largest) {
42 InternalKeyComparator cmp(BytewiseComparator());
43 Slice s(smallest != NULL ? smallest : "");
44 Slice l(largest != NULL ? largest : "");
45 return SomeFileOverlapsRange(cmp, disjoint_sorted_files_, files_,
46 (smallest != NULL ? &s : NULL),
47 (largest != NULL ? &l : NULL));
48 }
49 };
50
TEST(FindFileTest,Empty)51 TEST(FindFileTest, Empty) {
52 ASSERT_EQ(0, Find("foo"));
53 ASSERT_TRUE(! Overlaps("a", "z"));
54 ASSERT_TRUE(! Overlaps(NULL, "z"));
55 ASSERT_TRUE(! Overlaps("a", NULL));
56 ASSERT_TRUE(! Overlaps(NULL, NULL));
57 }
58
TEST(FindFileTest,Single)59 TEST(FindFileTest, Single) {
60 Add("p", "q");
61 ASSERT_EQ(0, Find("a"));
62 ASSERT_EQ(0, Find("p"));
63 ASSERT_EQ(0, Find("p1"));
64 ASSERT_EQ(0, Find("q"));
65 ASSERT_EQ(1, Find("q1"));
66 ASSERT_EQ(1, Find("z"));
67
68 ASSERT_TRUE(! Overlaps("a", "b"));
69 ASSERT_TRUE(! Overlaps("z1", "z2"));
70 ASSERT_TRUE(Overlaps("a", "p"));
71 ASSERT_TRUE(Overlaps("a", "q"));
72 ASSERT_TRUE(Overlaps("a", "z"));
73 ASSERT_TRUE(Overlaps("p", "p1"));
74 ASSERT_TRUE(Overlaps("p", "q"));
75 ASSERT_TRUE(Overlaps("p", "z"));
76 ASSERT_TRUE(Overlaps("p1", "p2"));
77 ASSERT_TRUE(Overlaps("p1", "z"));
78 ASSERT_TRUE(Overlaps("q", "q"));
79 ASSERT_TRUE(Overlaps("q", "q1"));
80
81 ASSERT_TRUE(! Overlaps(NULL, "j"));
82 ASSERT_TRUE(! Overlaps("r", NULL));
83 ASSERT_TRUE(Overlaps(NULL, "p"));
84 ASSERT_TRUE(Overlaps(NULL, "p1"));
85 ASSERT_TRUE(Overlaps("q", NULL));
86 ASSERT_TRUE(Overlaps(NULL, NULL));
87 }
88
89
TEST(FindFileTest,Multiple)90 TEST(FindFileTest, Multiple) {
91 Add("150", "200");
92 Add("200", "250");
93 Add("300", "350");
94 Add("400", "450");
95 ASSERT_EQ(0, Find("100"));
96 ASSERT_EQ(0, Find("150"));
97 ASSERT_EQ(0, Find("151"));
98 ASSERT_EQ(0, Find("199"));
99 ASSERT_EQ(0, Find("200"));
100 ASSERT_EQ(1, Find("201"));
101 ASSERT_EQ(1, Find("249"));
102 ASSERT_EQ(1, Find("250"));
103 ASSERT_EQ(2, Find("251"));
104 ASSERT_EQ(2, Find("299"));
105 ASSERT_EQ(2, Find("300"));
106 ASSERT_EQ(2, Find("349"));
107 ASSERT_EQ(2, Find("350"));
108 ASSERT_EQ(3, Find("351"));
109 ASSERT_EQ(3, Find("400"));
110 ASSERT_EQ(3, Find("450"));
111 ASSERT_EQ(4, Find("451"));
112
113 ASSERT_TRUE(! Overlaps("100", "149"));
114 ASSERT_TRUE(! Overlaps("251", "299"));
115 ASSERT_TRUE(! Overlaps("451", "500"));
116 ASSERT_TRUE(! Overlaps("351", "399"));
117
118 ASSERT_TRUE(Overlaps("100", "150"));
119 ASSERT_TRUE(Overlaps("100", "200"));
120 ASSERT_TRUE(Overlaps("100", "300"));
121 ASSERT_TRUE(Overlaps("100", "400"));
122 ASSERT_TRUE(Overlaps("100", "500"));
123 ASSERT_TRUE(Overlaps("375", "400"));
124 ASSERT_TRUE(Overlaps("450", "450"));
125 ASSERT_TRUE(Overlaps("450", "500"));
126 }
127
TEST(FindFileTest,MultipleNullBoundaries)128 TEST(FindFileTest, MultipleNullBoundaries) {
129 Add("150", "200");
130 Add("200", "250");
131 Add("300", "350");
132 Add("400", "450");
133 ASSERT_TRUE(! Overlaps(NULL, "149"));
134 ASSERT_TRUE(! Overlaps("451", NULL));
135 ASSERT_TRUE(Overlaps(NULL, NULL));
136 ASSERT_TRUE(Overlaps(NULL, "150"));
137 ASSERT_TRUE(Overlaps(NULL, "199"));
138 ASSERT_TRUE(Overlaps(NULL, "200"));
139 ASSERT_TRUE(Overlaps(NULL, "201"));
140 ASSERT_TRUE(Overlaps(NULL, "400"));
141 ASSERT_TRUE(Overlaps(NULL, "800"));
142 ASSERT_TRUE(Overlaps("100", NULL));
143 ASSERT_TRUE(Overlaps("200", NULL));
144 ASSERT_TRUE(Overlaps("449", NULL));
145 ASSERT_TRUE(Overlaps("450", NULL));
146 }
147
TEST(FindFileTest,OverlapSequenceChecks)148 TEST(FindFileTest, OverlapSequenceChecks) {
149 Add("200", "200", 5000, 3000);
150 ASSERT_TRUE(! Overlaps("199", "199"));
151 ASSERT_TRUE(! Overlaps("201", "300"));
152 ASSERT_TRUE(Overlaps("200", "200"));
153 ASSERT_TRUE(Overlaps("190", "200"));
154 ASSERT_TRUE(Overlaps("200", "210"));
155 }
156
TEST(FindFileTest,OverlappingFiles)157 TEST(FindFileTest, OverlappingFiles) {
158 Add("150", "600");
159 Add("400", "500");
160 disjoint_sorted_files_ = false;
161 ASSERT_TRUE(! Overlaps("100", "149"));
162 ASSERT_TRUE(! Overlaps("601", "700"));
163 ASSERT_TRUE(Overlaps("100", "150"));
164 ASSERT_TRUE(Overlaps("100", "200"));
165 ASSERT_TRUE(Overlaps("100", "300"));
166 ASSERT_TRUE(Overlaps("100", "400"));
167 ASSERT_TRUE(Overlaps("100", "500"));
168 ASSERT_TRUE(Overlaps("375", "400"));
169 ASSERT_TRUE(Overlaps("450", "450"));
170 ASSERT_TRUE(Overlaps("450", "500"));
171 ASSERT_TRUE(Overlaps("450", "700"));
172 ASSERT_TRUE(Overlaps("600", "700"));
173 }
174
175 } // namespace leveldb
176
main(int argc,char ** argv)177 int main(int argc, char** argv) {
178 return leveldb::test::RunAllTests();
179 }
180