| 120 | } |
| 121 | |
| 122 | bool SomeFileOverlapsRange(const InternalKeyComparator& icmp, |
| 123 | bool disjoint_sorted_files, |
| 124 | const std::vector<FileMetaData*>& files, |
| 125 | const Slice* smallest_user_key, |
| 126 | const Slice* largest_user_key) { |
| 127 | const Comparator* ucmp = icmp.user_comparator(); |
| 128 | if (!disjoint_sorted_files) { |
| 129 | // Need to check against all files |
| 130 | for (size_t i = 0; i < files.size(); i++) { |
| 131 | const FileMetaData* f = files[i]; |
| 132 | if (AfterFile(ucmp, smallest_user_key, f) || |
| 133 | BeforeFile(ucmp, largest_user_key, f)) { |
| 134 | // No overlap |
| 135 | } else { |
| 136 | return true; // Overlap |
| 137 | } |
| 138 | } |
| 139 | return false; |
| 140 | } |
| 141 | |
| 142 | // Binary search over file list |
| 143 | uint32_t index = 0; |
| 144 | if (smallest_user_key != nullptr) { |
| 145 | // Find the earliest possible internal key for smallest_user_key |
| 146 | InternalKey small_key(*smallest_user_key, kMaxSequenceNumber, |
| 147 | kValueTypeForSeek); |
| 148 | index = FindFile(icmp, files, small_key.Encode()); |
| 149 | } |
| 150 | |
| 151 | if (index >= files.size()) { |
| 152 | // beginning of range is after all files, so no overlap. |
| 153 | return false; |
| 154 | } |
| 155 | |
| 156 | return !BeforeFile(ucmp, largest_user_key, files[index]); |
| 157 | } |
| 158 | |
| 159 | // An internal iterator. For a given version/level pair, yields |
| 160 | // information about the files in the level. For a given entry, key() |