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
10namespace leveldb {
11
12class FindFileTest {
13 public:
14  std::vector<FileMetaData*> files_;
15  bool disjoint_sorted_files_;
16
17  FindFileTest() : disjoint_sorted_files_(true) { }
18
19  ~FindFileTest() {
20    for (int i = 0; i < files_.size(); i++) {
21      delete files_[i];
22    }
23  }
24
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
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
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
51TEST(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
59TEST(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
90TEST(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
128TEST(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
148TEST(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
157TEST(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
177int main(int argc, char** argv) {
178  return leveldb::test::RunAllTests();
179}
180