Inside Bitcoin

251  kNotFound,
252  kFound,
253  kDeleted,
254  kCorrupt,
255};
256struct Saver {
257  SaverState state;
258  const Comparator* ucmp;
259  Slice user_key;
260  std::string* value;
261};
262}  // namespace
263static void SaveValue(void* arg, const Slice& ikey, const Slice& v) {
264  Saver* s = reinterpret_cast<Saver*>(arg);
265  ParsedInternalKey parsed_key;
266  if (!ParseInternalKey(ikey, &parsed_key)) {
267    s->state = kCorrupt;
268  } else {
269    if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
270      s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted;
271      if (s->state == kFound) {
272        s->value->assign(v.data(), v.size());
273      }
274    }
275  }
276}
277
278static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
279  return a->number > b->number;
280}
281
282void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
283                                 bool (*func)(void*, int, FileMetaData*)) {
284  const Comparator* ucmp = vset_->icmp_.user_comparator();
285
286  // Search level-0 in order from newest to oldest.
287  std::vector<FileMetaData*> tmp;
288  tmp.reserve(files_[0].size());
289  for (uint32_t i = 0; i < files_[0].size(); i++) {
290    FileMetaData* f = files_[0][i];
291    if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
292        ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
293      tmp.push_back(f);
294    }
295  }
296  if (!tmp.empty()) {
297    std::sort(tmp.begin(), tmp.end(), NewestFirst);
298    for (uint32_t i = 0; i < tmp.size(); i++) {
299      if (!(*func)(arg, 0, tmp[i])) {
300        return;
301      }
302    }
303  }
304
305  // Search other levels.
306  for (int level = 1; level < config::kNumLevels; level++) {
307    size_t num_files = files_[level].size();
308    if (num_files == 0) continue;
309
310    // Binary search to find earliest index whose largest key >= internal_key.
311    uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
312    if (index < num_files) {
313      FileMetaData* f = files_[level][index];
314      if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
315        // All of "f" is past any data for user_key
316      } else {
317        if (!(*func)(arg, level, f)) {
318          return;
319        }
320      }
321    }
322  }
323}
324
325Status Version::Get(const ReadOptions& options, const LookupKey& k,
326                    std::string* value, GetStats* stats) {
327  stats->seek_file = nullptr;
328  stats->seek_file_level = -1;
329
330  struct State {
331    Saver saver;
332    GetStats* stats;
333    const ReadOptions* options;
334    Slice ikey;
335    FileMetaData* last_file_read;
336    int last_file_read_level;
337
338    VersionSet* vset;
339    Status s;
340    bool found;
341
342    static bool Match(void* arg, int level, FileMetaData* f) {
343      State* state = reinterpret_cast<State*>(arg);
344
345      if (state->stats->seek_file == nullptr &&
346          state->last_file_read != nullptr) {
347        // We have had more than one seek for this read.  Charge the 1st file.
348        state->stats->seek_file = state->last_file_read;
349        state->stats->seek_file_level = state->last_file_read_level;
350      }
351
352      state->last_file_read = f;
353      state->last_file_read_level = level;
354
355      state->s = state->vset->table_cache_->Get(*state->options, f->number,
356                                                f->file_size, state->ikey,
357                                                &state->saver, SaveValue);
358      if (!state->s.ok()) {
359        state->found = true;
360        return false;
361      }
362      switch (state->saver.state) {
363        case kNotFound:
364          return true;  // Keep searching in other files
365        case kFound:
366          state->found = true;
367          return false;
368        case kDeleted:
369          return false;
370        case kCorrupt:
371          state->s =
372              Status::Corruption("corrupted key for ", state->saver.user_key);
373          state->found = true;
374          return false;
375      }
376
377      // Not reached. Added to avoid false compilation warnings of
378      // "control reaches end of non-void function".
379      return false;
380    }
381  };
382
383  State state;
384  state.found = false;
385  state.stats = stats;
386  state.last_file_read = nullptr;
387  state.last_file_read_level = -1;
388
389  state.options = &options;
390  state.ikey = k.internal_key();
391  state.vset = vset_;
392
393  state.saver.state = kNotFound;
394  state.saver.ucmp = vset_->icmp_.user_comparator();
395  state.saver.user_key = k.user_key();
396  state.saver.value = value;
397
398  ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
399
400  return state.found ? state.s : Status::NotFound(Slice());
401}
402
403bool Version::UpdateStats(const GetStats& /*stats*/) {
404  // Disable automatic compactions triggered by read seek counters.
405  // The heuristic was tuned for expensive random seeks and can create
406  // severe write amplification on large random-key databases.
407  // Size and manual compactions still run.
408  return false;
409}
410
411bool Version::RecordReadSample(Slice internal_key) {
412  ParsedInternalKey ikey;
413  if (!ParseInternalKey(internal_key, &ikey)) {
414    return false;
415  }
416
417  struct State {
418    GetStats stats;  // Holds first matching file
419    int matches;
420
421    static bool Match(void* arg, int level, FileMetaData* f) {
422      State* state = reinterpret_cast<State*>(arg);
423      state->matches++;
424      if (state->matches == 1) {
425        // Remember first match.
426        state->stats.seek_file = f;
427        state->stats.seek_file_level = level;
428      }
429      // We can stop iterating once we have a second match.
430      return state->matches < 2;
431    }
432  };
433
434  State state;
435  state.matches = 0;
436  ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);
437
438  // Must have at least two matches since we want to merge across
439  // files. But what if we have a single file that contains many
440  // overwrites and deletions?  Should we have another mechanism for
441  // finding such files?
442  if (state.matches >= 2) {
443    // 1MB cost is about 1 seek (see comment in Builder::Apply).
444    return UpdateStats(state.stats);
445  }
446  return false;
447}
448
449void Version::Ref() { ++refs_; }
450
451void Version::Unref() {
452  assert(this != &vset_->dummy_versions_);
453  assert(refs_ >= 1);
454  --refs_;
455  if (refs_ == 0) {
456    delete this;
457  }
458}
459
460bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
461                             const Slice* largest_user_key) {
462  return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
463                               smallest_user_key, largest_user_key);
464}
465
466int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
467                                        const Slice& largest_user_key) {
468  int level = 0;
469  if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
470    // Push to next level if there is no overlap in next level,
471    // and the #bytes overlapping in the level after that are limited.
472    InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
473    InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
474    std::vector<FileMetaData*> overlaps;
475    while (level < config::kMaxMemCompactLevel) {
476      if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
477        break;
478      }
479      if (level + 2 < config::kNumLevels) {
480        // Check that file does not overlap too many grandparent bytes.
481        GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
482        const int64_t sum = TotalFileSize(overlaps);
483        if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
484          break;
485        }
486      }
487      level++;
488    }
489  }
490  return level;
491}
492
493// Store in "*inputs" all files in "level" that overlap [begin,end]
494void Version::GetOverlappingInputs(int level, const InternalKey* begin,
495                                   const InternalKey* end,
496                                   std::vector<FileMetaData*>* inputs) {
497  assert(level >= 0);
498  assert(level < config::kNumLevels);
499  inputs->clear();
500  Slice user_begin, user_end;