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 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 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 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 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 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 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 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 177 int main(int argc, char** argv) { 178 return leveldb::test::RunAllTests(); 179 } 180
