27 static std::string Reverse(
const Slice& key) {
28 std::string str(key.ToString());
30 for (std::string::reverse_iterator rit = str.rbegin();
31 rit != str.rend(); ++rit) {
38 class ReverseKeyComparator :
public Comparator {
40 virtual const char* Name()
const {
41 return "leveldb.ReverseBytewiseComparator";
44 virtual int Compare(
const Slice& a,
const Slice& b)
const {
48 virtual void FindShortestSeparator(
50 const Slice& limit)
const {
51 std::string s = Reverse(*start);
52 std::string l = Reverse(limit);
57 virtual void FindShortSuccessor(std::string* key)
const {
58 std::string s = Reverse(*key);
64 static ReverseKeyComparator reverse_key_comparator;
66 static void Increment(
const Comparator*
cmp, std::string* key) {
70 assert(cmp == &reverse_key_comparator);
71 std::string rev = Reverse(*key);
80 const Comparator*
cmp;
83 STLLessThan(
const Comparator* c) : cmp(c) { }
84 bool operator()(
const std::string& a,
const std::string& b)
const {
85 return cmp->Compare(Slice(a), Slice(b)) < 0;
113 :
contents_(contents.data(), contents.size()) {
121 char* scratch)
const {
129 *result =
Slice(scratch, n);
137 typedef std::map<std::string, std::string, STLLessThan>
KVMap;
154 std::vector<std::string>* keys,
158 for (KVMap::const_iterator it =
data_.begin();
161 keys->push_back(it->first);
175 virtual DB*
db()
const {
return NULL; }
195 for (KVMap::const_iterator it = data.begin();
198 builder.
Add(it->first, it->second);
235 for (KVMap::const_iterator it = data.begin();
238 builder.
Add(it->first, it->second);
297 return Slice(
"corrupted key");
332 for (KVMap::const_iterator it = data.begin();
364 for (KVMap::const_iterator it = data.begin();
368 batch.
Put(it->first, it->second);
412 static const TestArgs kTestArgList[] = {
435 static const int kNumTestArgs =
sizeof(kTestArgList) /
sizeof(kTestArgList[0]);
473 void Add(
const std::string& key,
const std::string&
value) {
478 std::vector<std::string> keys;
492 for (KVMap::const_iterator model_iter = data.begin();
493 model_iter != data.end();
507 for (KVMap::const_reverse_iterator model_iter = data.rbegin();
508 model_iter != data.rend();
518 const std::vector<std::string>& keys,
520 static const bool kVerbose =
false;
523 KVMap::const_iterator model_iter = data.begin();
524 if (kVerbose) fprintf(stderr,
"---\n");
525 for (
int i = 0; i < 200; i++) {
526 const int toss = rnd->
Uniform(5);
530 if (kVerbose) fprintf(stderr,
"Next\n");
539 if (kVerbose) fprintf(stderr,
"SeekToFirst\n");
541 model_iter = data.begin();
548 model_iter = data.lower_bound(key);
549 if (kVerbose) fprintf(stderr,
"Seek '%s'\n",
558 if (kVerbose) fprintf(stderr,
"Prev\n");
560 if (model_iter == data.begin()) {
561 model_iter = data.end();
571 if (kVerbose) fprintf(stderr,
"SeekToLast\n");
574 model_iter = data.end();
576 std::string last = data.rbegin()->first;
577 model_iter = data.lower_bound(last);
587 std::string
ToString(
const KVMap& data,
const KVMap::const_iterator& it) {
588 if (it == data.end()) {
591 return "'" + it->first +
"->" + it->second +
"'";
596 const KVMap::const_reverse_iterator& it) {
597 if (it == data.rend()) {
600 return "'" + it->first +
"->" + it->second +
"'";
616 const int index = rnd->
Uniform(keys.size());
617 std::string result = keys[index];
624 if (result.size() > 0 && result[result.size()-1] >
'\0') {
625 result[result.size()-1]--;
649 for (
int i = 0; i < kNumTestArgs; i++) {
650 Init(kTestArgList[i]);
661 memset(data, 0,
sizeof(data));
663 contents.
data =
Slice(data,
sizeof(data));
666 Block block(contents);
679 for (
int i = 0; i < kNumTestArgs; i++) {
680 Init(kTestArgList[i]);
688 for (
int i = 0; i < kNumTestArgs; i++) {
689 Init(kTestArgList[i]);
697 for (
int i = 0; i < kNumTestArgs; i++) {
698 Init(kTestArgList[i]);
708 for (
int i = 0; i < kNumTestArgs; i++) {
709 Init(kTestArgList[i]);
711 Add(
"\xff\xff",
"v3");
717 for (
int i = 0; i < kNumTestArgs; i++) {
718 Init(kTestArgList[i]);
720 for (
int num_entries = 0; num_entries < 2000;
721 num_entries += (num_entries < 50 ? 1 : 200)) {
722 if ((num_entries % 10) == 0) {
723 fprintf(stderr,
"case %d of %d: num_entries = %d\n",
724 (i + 1),
int(kNumTestArgs), num_entries);
726 for (
int e = 0; e < num_entries; e++) {
740 int num_entries = 100000;
741 for (
int e = 0; e < num_entries; e++) {
750 for (
int level = 0; level < config::kNumLevels; level++) {
753 snprintf(name,
sizeof(name),
"leveldb.num-files-at-level%d", level);
755 files +=
atoi(value.c_str());
768 batch.
Put(std::string(
"k1"), std::string(
"v1"));
769 batch.
Put(std::string(
"k2"), std::string(
"v2"));
770 batch.
Put(std::string(
"k3"), std::string(
"v3"));
771 batch.
Put(std::string(
"largekey"), std::string(
"vlarge"));
776 while (iter->
Valid()) {
777 fprintf(stderr,
"key: '%s' -> '%s'\n",
788 bool result = (val >= low) && (val <= high);
790 fprintf(stderr,
"Value %llu is not in range [%llu, %llu]\n",
791 (
unsigned long long)(val),
792 (
unsigned long long)(low),
793 (
unsigned long long)(high));
802 c.
Add(
"k01",
"hello");
803 c.
Add(
"k02",
"hello2");
804 c.
Add(
"k03", std::string(10000,
'x'));
805 c.
Add(
"k04", std::string(200000,
'x'));
806 c.
Add(
"k05", std::string(300000,
'x'));
807 c.
Add(
"k06",
"hello3");
808 c.
Add(
"k07", std::string(100000,
'x'));
809 std::vector<std::string> keys;
814 c.
Finish(options, &keys, &kvmap);
830 static bool SnappyCompressionSupported() {
832 Slice in =
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
837 if (!SnappyCompressionSupported()) {
838 fprintf(stderr,
"skipping compression tests\n");
845 c.
Add(
"k01",
"hello");
847 c.
Add(
"k03",
"hello3");
849 std::vector<std::string> keys;
854 c.
Finish(options, &keys, &kvmap);
866 int main(
int argc,
char** argv) {
std::string PickRandomKey(Random *rnd, const std::vector< std::string > &keys)
void Add(const Slice &key, const Slice &value)
virtual ~KeyConvertingIterator()
virtual Status Write(const WriteOptions &options, WriteBatch *updates)=0
uint64_t ApproximateOffsetOf(const Slice &key) const
virtual bool Valid() const
const char * data() const
virtual Status Append(const Slice &data)
virtual Status FinishImpl(const Options &options, const KVMap &data)
void Add(const std::string &key, const Slice &value)
static Status Corruption(const Slice &msg, const Slice &msg2=Slice())
void operator=(const KeyConvertingIterator &)
virtual Iterator * NewIterator() const =0
virtual Slice value() const
void TestRandomAccess(Random *rnd, const std::vector< std::string > &keys, const KVMap &data)
InternalKeyComparator internal_comparator_
static void SetSequence(WriteBatch *batch, SequenceNumber seq)
virtual void Seek(const Slice &target)
std::map< std::string, std::string, STLLessThan > KVMap
virtual Status FinishImpl(const Options &options, const KVMap &data)
virtual Status status() const =0
Constructor * constructor_
int main(int argc, char **argv)
virtual void FindShortSuccessor(std::string *key) const =0
void Init(const TestArgs &args)
Slice CompressibleString(Random *rnd, double compressed_fraction, int len, std::string *dst)
virtual Iterator * NewIterator() const
const Comparator * comparator_
virtual Status FinishImpl(const Options &options, const KVMap &data)=0
virtual void SeekToFirst()
virtual Iterator * NewIterator() const
virtual Iterator * NewIterator(const ReadOptions &options)=0
bool ParseInternalKey(const Slice &internal_key, ParsedInternalKey *result)
void AppendInternalKey(std::string *result, const ParsedInternalKey &key)
virtual Slice value() const =0
Status DestroyDB(const std::string &dbname, const Options &options)
virtual void SeekToLast()=0
Iterator * NewIterator(const ReadOptions &) const
static Status InvalidArgument(const Slice &msg, const Slice &msg2=Slice())
Iterator * NewIterator(const Comparator *comparator)
std::string ToString(const Iterator *it)
bool Snappy_Compress(const char *input, size_t input_length, std::string *output)
virtual void SeekToLast()
KeyConvertingIterator(Iterator *iter)
StringSource(const Slice &contents)
unsigned long long uint64_t
static Status Open(const Options &options, const std::string &name, DB **dbptr)
DBConstructor(const Comparator *cmp)
TEST(CorruptionTest, Recovery)
virtual void Seek(const Slice &target)=0
std::string EscapeString(const Slice &value)
virtual void SeekToFirst()=0
uint64_t ApproximateOffsetOf(const Slice &key) const
std::string ToString(const KVMap &data, const KVMap::const_reverse_iterator &it)
uint64_t FileSize() const
virtual Iterator * NewIterator() const
uint32_t Skewed(int max_log)
const std::string & contents() const
void TestForwardScan(const std::vector< std::string > &keys, const KVMap &data)
virtual Status FinishImpl(const Options &options, const KVMap &data)
static Status InsertInto(const WriteBatch *batch, MemTable *memtable)
const Comparator * BytewiseComparator()
CompressionType compression
virtual void FindShortestSeparator(std::string *start, const Slice &limit) const =0
void TestBackwardScan(const std::vector< std::string > &keys, const KVMap &data)
virtual int Compare(const Slice &a, const Slice &b) const =0
virtual Status status() const
virtual bool Valid() const =0
const Comparator * comparator_
virtual Iterator * NewIterator() const
static Status Open(const Options &options, RandomAccessFile *file, uint64_t file_size, Table **table)
MemTableConstructor(const Comparator *cmp)
int block_restart_interval
virtual Slice key() const =0
BlockConstructor(const Comparator *cmp)
void Add(SequenceNumber seq, ValueType type, const Slice &key, const Slice &value)
void Finish(const Options &options, std::vector< std::string > *keys, KVMap *kvmap)
std::string RandomKey(Random *rnd, int len)
TableConstructor(const Comparator *cmp)
Slice RandomString(Random *rnd, int len, std::string *dst)
virtual Slice key() const
std::string ToString(const KVMap &data, const KVMap::const_iterator &it)
std::string ToString() const
virtual Status FinishImpl(const Options &options, const KVMap &data)
virtual const KVMap & data()
void Put(const Slice &key, const Slice &value)
const Comparator * comparator
void Add(const Slice &key, const Slice &value)
int atoi(const std::string &str)
void Add(const std::string &key, const std::string &value)
virtual Status Read(uint64_t offset, size_t n, Slice *result, char *scratch) const
Constructor(const Comparator *cmp)
std::string ToString() const