Inside Bitcoin

501          break;
502        }
503
504        case 1: {
505          if (kVerbose) fprintf(stderr, "SeekToFirst\n");
506          iter->SeekToFirst();
507          model_iter = data.begin();
508          ASSERT_EQ(ToString(data, model_iter), ToString(iter));
509          break;
510        }
511
512        case 2: {
513          std::string key = PickRandomKey(rnd, keys);
514          model_iter = data.lower_bound(key);
515          if (kVerbose)
516            fprintf(stderr, "Seek '%s'\n", EscapeString(key).c_str());
517          iter->Seek(Slice(key));
518          ASSERT_EQ(ToString(data, model_iter), ToString(iter));
519          break;
520        }
521
522        case 3: {
523          if (iter->Valid()) {
524            if (kVerbose) fprintf(stderr, "Prev\n");
525            iter->Prev();
526            if (model_iter == data.begin()) {
527              model_iter = data.end();  // Wrap around to invalid value
528            } else {
529              --model_iter;
530            }
531            ASSERT_EQ(ToString(data, model_iter), ToString(iter));
532          }
533          break;
534        }
535
536        case 4: {
537          if (kVerbose) fprintf(stderr, "SeekToLast\n");
538          iter->SeekToLast();
539          if (keys.empty()) {
540            model_iter = data.end();
541          } else {
542            std::string last = data.rbegin()->first;
543            model_iter = data.lower_bound(last);
544          }
545          ASSERT_EQ(ToString(data, model_iter), ToString(iter));
546          break;
547        }
548      }
549    }
550    delete iter;
551  }
552
553  std::string ToString(const KVMap& data, const KVMap::const_iterator& it) {
554    if (it == data.end()) {
555      return "END";
556    } else {
557      return "'" + it->first + "->" + it->second + "'";
558    }
559  }
560
561  std::string ToString(const KVMap& data,
562                       const KVMap::const_reverse_iterator& it) {
563    if (it == data.rend()) {
564      return "END";
565    } else {
566      return "'" + it->first + "->" + it->second + "'";
567    }
568  }
569
570  std::string ToString(const Iterator* it) {
571    if (!it->Valid()) {
572      return "END";
573    } else {
574      return "'" + it->key().ToString() + "->" + it->value().ToString() + "'";
575    }
576  }
577
578  std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) {
579    if (keys.empty()) {
580      return "foo";
581    } else {
582      const int index = rnd->Uniform(keys.size());
583      std::string result = keys[index];
584      switch (rnd->Uniform(3)) {
585        case 0:
586          // Return an existing key
587          break;
588        case 1: {
589          // Attempt to return something smaller than an existing key
590          if (!result.empty() && result[result.size() - 1] > '\0') {
591            result[result.size() - 1]--;
592          }
593          break;
594        }
595        case 2: {
596          // Return something larger than an existing key
597          Increment(options_.comparator, &result);
598          break;
599        }
600      }
601      return result;
602    }
603  }
604
605  // Returns nullptr if not running against a DB
606  DB* db() const { return constructor_->db(); }
607
608 private:
609  Options options_;
610  Constructor* constructor_;
611};
612
613// Test empty table/block.
614TEST(Harness, Empty) {
615  for (int i = 0; i < kNumTestArgs; i++) {
616    Init(kTestArgList[i]);
617    Random rnd(test::RandomSeed() + 1);
618    Test(&rnd);
619  }
620}
621
622// Special test for a block with no restart entries.  The C++ leveldb
623// code never generates such blocks, but the Java version of leveldb
624// seems to.
625TEST(Harness, ZeroRestartPointsInBlock) {
626  char data[sizeof(uint32_t)];
627  memset(data, 0, sizeof(data));
628  BlockContents contents;
629  contents.data = Slice(data, sizeof(data));
630  contents.cachable = false;
631  contents.heap_allocated = false;
632  Block block(contents);
633  Iterator* iter = block.NewIterator(BytewiseComparator());
634  iter->SeekToFirst();
635  ASSERT_TRUE(!iter->Valid());
636  iter->SeekToLast();
637  ASSERT_TRUE(!iter->Valid());
638  iter->Seek("foo");
639  ASSERT_TRUE(!iter->Valid());
640  delete iter;
641}
642
643// Test the empty key
644TEST(Harness, SimpleEmptyKey) {
645  for (int i = 0; i < kNumTestArgs; i++) {
646    Init(kTestArgList[i]);
647    Random rnd(test::RandomSeed() + 1);
648    Add("", "v");
649    Test(&rnd);
650  }
651}
652
653TEST(Harness, SimpleSingle) {
654  for (int i = 0; i < kNumTestArgs; i++) {
655    Init(kTestArgList[i]);
656    Random rnd(test::RandomSeed() + 2);
657    Add("abc", "v");
658    Test(&rnd);
659  }
660}
661
662TEST(Harness, SimpleMulti) {
663  for (int i = 0; i < kNumTestArgs; i++) {
664    Init(kTestArgList[i]);
665    Random rnd(test::RandomSeed() + 3);
666    Add("abc", "v");
667    Add("abcd", "v");
668    Add("ac", "v2");
669    Test(&rnd);
670  }
671}
672
673TEST(Harness, SimpleSpecialKey) {
674  for (int i = 0; i < kNumTestArgs; i++) {
675    Init(kTestArgList[i]);
676    Random rnd(test::RandomSeed() + 4);
677    Add("\xff\xff", "v3");
678    Test(&rnd);
679  }
680}
681
682TEST(Harness, Randomized) {
683  for (int i = 0; i < kNumTestArgs; i++) {
684    Init(kTestArgList[i]);
685    Random rnd(test::RandomSeed() + 5);
686    for (int num_entries = 0; num_entries < 2000;
687         num_entries += (num_entries < 50 ? 1 : 200)) {
688      if ((num_entries % 10) == 0) {
689        fprintf(stderr, "case %d of %d: num_entries = %d\n", (i + 1),
690                int(kNumTestArgs), num_entries);
691      }
692      for (int e = 0; e < num_entries; e++) {
693        std::string v;
694        Add(test::RandomKey(&rnd, rnd.Skewed(4)),
695            test::RandomString(&rnd, rnd.Skewed(5), &v).ToString());
696      }
697      Test(&rnd);
698    }
699  }
700}
701
702TEST(Harness, RandomizedLongDB) {
703  Random rnd(test::RandomSeed());
704  TestArgs args = {DB_TEST, false, 16};
705  Init(args);
706  int num_entries = 100000;
707  for (int e = 0; e < num_entries; e++) {
708    std::string v;
709    Add(test::RandomKey(&rnd, rnd.Skewed(4)),
710        test::RandomString(&rnd, rnd.Skewed(5), &v).ToString());
711  }
712  Test(&rnd);
713
714  // We must have created enough data to force merging
715  int files = 0;
716  for (int level = 0; level < config::kNumLevels; level++) {
717    std::string value;
718    char name[100];
719    snprintf(name, sizeof(name), "leveldb.num-files-at-level%d", level);
720    ASSERT_TRUE(db()->GetProperty(name, &value));
721    files += atoi(value.c_str());
722  }
723  ASSERT_GT(files, 0);
724}
725
726class MemTableTest {};
727
728TEST(MemTableTest, Simple) {
729  InternalKeyComparator cmp(BytewiseComparator());
730  MemTable* memtable = new MemTable(cmp);
731  memtable->Ref();
732  WriteBatch batch;
733  WriteBatchInternal::SetSequence(&batch, 100);
734  batch.Put(std::string("k1"), std::string("v1"));
735  batch.Put(std::string("k2"), std::string("v2"));
736  batch.Put(std::string("k3"), std::string("v3"));
737  batch.Put(std::string("largekey"), std::string("vlarge"));
738  ASSERT_TRUE(WriteBatchInternal::InsertInto(&batch, memtable).ok());
739
740  Iterator* iter = memtable->NewIterator();
741  iter->SeekToFirst();
742  while (iter->Valid()) {
743    fprintf(stderr, "key: '%s' -> '%s'\n", iter->key().ToString().c_str(),
744            iter->value().ToString().c_str());
745    iter->Next();
746  }
747
748  delete iter;
749  memtable->Unref();
750}