1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/table.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <map> 851f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com#include <string> 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/dbformat.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/memtable.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/write_batch_internal.h" 12fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/db.h" 13fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/env.h" 14fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/iterator.h" 15fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/table_builder.h" 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/block.h" 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/block_builder.h" 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/format.h" 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/random.h" 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/testharness.h" 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/testutil.h" 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Return reverse of "key". 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Used to test non-lexicographic comparators. 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic std::string Reverse(const Slice& key) { 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string str(key.ToString()); 2951f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com std::string rev(""); 3051f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com for (std::string::reverse_iterator rit = str.rbegin(); 3151f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com rit != str.rend(); ++rit) { 3251f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com rev.push_back(*rit); 3351f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com } 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return rev; 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace { 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass ReverseKeyComparator : public Comparator { 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual const char* Name() const { 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "leveldb.ReverseBytewiseComparator"; 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual int Compare(const Slice& a, const Slice& b) const { 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return BytewiseComparator()->Compare(Reverse(a), Reverse(b)); 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void FindShortestSeparator( 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string* start, 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& limit) const { 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string s = Reverse(*start); 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string l = Reverse(limit); 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BytewiseComparator()->FindShortestSeparator(&s, l); 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *start = Reverse(s); 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void FindShortSuccessor(std::string* key) const { 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string s = Reverse(*key); 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BytewiseComparator()->FindShortSuccessor(&s); 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *key = Reverse(s); 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 6345b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic ReverseKeyComparator reverse_key_comparator; 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void Increment(const Comparator* cmp, std::string* key) { 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (cmp == BytewiseComparator()) { 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org key->push_back('\0'); 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(cmp == &reverse_key_comparator); 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string rev = Reverse(*key); 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rev.push_back('\0'); 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *key = Reverse(rev); 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// An STL comparator that uses a Comparator 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace { 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstruct STLLessThan { 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Comparator* cmp; 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org STLLessThan() : cmp(BytewiseComparator()) { } 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org STLLessThan(const Comparator* c) : cmp(c) { } 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool operator()(const std::string& a, const std::string& b) const { 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return cmp->Compare(Slice(a), Slice(b)) < 0; 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 8845b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass StringSink: public WritableFile { 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~StringSink() { } 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::string& contents() const { return contents_; } 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status Close() { return Status::OK(); } 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status Flush() { return Status::OK(); } 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status Sync() { return Status::OK(); } 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status Append(const Slice& data) { 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org contents_.append(data.data(), data.size()); 102179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::OK(); 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string contents_; 107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 108179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 109179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass StringSource: public RandomAccessFile { 111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org StringSource(const Slice& contents) 113179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : contents_(contents.data(), contents.size()) { 114179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 115179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 116179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual ~StringSource() { } 117179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 118f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org uint64_t Size() const { return contents_.size(); } 119179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 120179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status Read(uint64_t offset, size_t n, Slice* result, 121179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char* scratch) const { 122179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (offset > contents_.size()) { 123179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::InvalidArgument("invalid Read offset"); 124179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 125179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (offset + n > contents_.size()) { 126179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org n = contents_.size() - offset; 127179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 128179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(scratch, &contents_[offset], n); 129179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *result = Slice(scratch, n); 130179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::OK(); 131179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 132179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string contents_; 135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtypedef std::map<std::string, std::string, STLLessThan> KVMap; 138179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Helper class for tests to unify the interface between 140179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// BlockBuilder/TableBuilder and Block/Table. 141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Constructor { 142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 143179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit Constructor(const Comparator* cmp) : data_(STLLessThan(cmp)) { } 144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual ~Constructor() { } 145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 146179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Add(const std::string& key, const Slice& value) { 147179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org data_[key] = value.ToString(); 148179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 149179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 150179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Finish constructing the data structure with all the keys that have 151179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // been added so far. Returns the keys in sorted order in "*keys" 152179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // and stores the key/value pairs in "*kvmap" 153179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Finish(const Options& options, 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<std::string>* keys, 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap* kvmap) { 156179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *kvmap = data_; 157179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org keys->clear(); 158179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator it = data_.begin(); 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org it != data_.end(); 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++it) { 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org keys->push_back(it->first); 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org data_.clear(); 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = FinishImpl(options, *kvmap); 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(s.ok()) << s.ToString(); 166179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Construct the data structure from the data in "data" 169179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status FinishImpl(const Options& options, const KVMap& data) = 0; 170179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 171179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Iterator* NewIterator() const = 0; 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual const KVMap& data() { return data_; } 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 17584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org virtual DB* db() const { return NULL; } // Overridden in DBConstructor 17684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap data_; 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass BlockConstructor: public Constructor { 182179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit BlockConstructor(const Comparator* cmp) 184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : Constructor(cmp), 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org comparator_(cmp), 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org block_(NULL) { } 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~BlockConstructor() { 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete block_; 189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status FinishImpl(const Options& options, const KVMap& data) { 191179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete block_; 192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org block_ = NULL; 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BlockBuilder builder(&options); 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator it = data.begin(); 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org it != data.end(); 197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++it) { 198179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.Add(it->first, it->second); 199179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 200179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Open the block 20199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com data_ = builder.Finish().ToString(); 20299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockContents contents; 20399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com contents.data = data_; 20499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com contents.cachable = false; 20599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com contents.heap_allocated = false; 20699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com block_ = new Block(contents); 207179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::OK(); 208179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 209179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Iterator* NewIterator() const { 210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return block_->NewIterator(comparator_); 211179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 212179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 213179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 214179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Comparator* comparator_; 21599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::string data_; 216179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Block* block_; 217179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 218179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BlockConstructor(); 219179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 220179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 221179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass TableConstructor: public Constructor { 222179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 223179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableConstructor(const Comparator* cmp) 224179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : Constructor(cmp), 225179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org source_(NULL), table_(NULL) { 226179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 227179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~TableConstructor() { 228179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Reset(); 229179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 230179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status FinishImpl(const Options& options, const KVMap& data) { 231179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Reset(); 232179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org StringSink sink; 233179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableBuilder builder(options, &sink); 234179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 235179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator it = data.begin(); 236179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org it != data.end(); 237179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++it) { 238179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.Add(it->first, it->second); 239179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(builder.status().ok()); 240179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 241179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = builder.Finish(); 242179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(s.ok()) << s.ToString(); 243179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 244179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(sink.contents().size(), builder.FileSize()); 245179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 246179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Open the table 247179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org source_ = new StringSource(sink.contents()); 248179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options table_options; 249179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org table_options.comparator = options.comparator; 250f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org return Table::Open(table_options, source_, sink.contents().size(), &table_); 251179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 252179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 253179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Iterator* NewIterator() const { 254179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return table_->NewIterator(ReadOptions()); 255179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 256179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 257179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t ApproximateOffsetOf(const Slice& key) const { 258179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return table_->ApproximateOffsetOf(key); 259179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 260179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 261179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 262179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Reset() { 263179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete table_; 264179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete source_; 265179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org table_ = NULL; 266179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org source_ = NULL; 267179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 268179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 269179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org StringSource* source_; 270179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Table* table_; 271179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 272179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableConstructor(); 273179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 274179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 275179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// A helper class that converts internal format keys into user keys 276179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass KeyConvertingIterator: public Iterator { 277179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 278179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit KeyConvertingIterator(Iterator* iter) : iter_(iter) { } 279179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual ~KeyConvertingIterator() { delete iter_; } 280179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual bool Valid() const { return iter_->Valid(); } 281179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Seek(const Slice& target) { 282179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue); 283179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string encoded; 284179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org AppendInternalKey(&encoded, ikey); 285179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter_->Seek(encoded); 286179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 287179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToFirst() { iter_->SeekToFirst(); } 288179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToLast() { iter_->SeekToLast(); } 289179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Next() { iter_->Next(); } 290179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Prev() { iter_->Prev(); } 291179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 292179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Slice key() const { 293179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 294179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ParsedInternalKey key; 295179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!ParseInternalKey(iter_->key(), &key)) { 296179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org status_ = Status::Corruption("malformed internal key"); 297179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Slice("corrupted key"); 298179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 299179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return key.user_key; 300179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 301179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 302179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Slice value() const { return iter_->value(); } 303179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status status() const { 304179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return status_.ok() ? iter_->status() : status_; 305179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 306179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 307179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 308179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org mutable Status status_; 309179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter_; 310179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 311179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No copying allowed 312179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KeyConvertingIterator(const KeyConvertingIterator&); 313179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void operator=(const KeyConvertingIterator&); 314179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 315179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 316179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MemTableConstructor: public Constructor { 317179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 318179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit MemTableConstructor(const Comparator* cmp) 319179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : Constructor(cmp), 320179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org internal_comparator_(cmp) { 321179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memtable_ = new MemTable(internal_comparator_); 322a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable_->Ref(); 323179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 324179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~MemTableConstructor() { 325a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable_->Unref(); 326179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 327179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status FinishImpl(const Options& options, const KVMap& data) { 328a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable_->Unref(); 329179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memtable_ = new MemTable(internal_comparator_); 330a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable_->Ref(); 331179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int seq = 1; 332179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator it = data.begin(); 333179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org it != data.end(); 334179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++it) { 335179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memtable_->Add(seq, kTypeValue, it->first, it->second); 336179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org seq++; 337179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 338179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::OK(); 339179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 340179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Iterator* NewIterator() const { 341179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return new KeyConvertingIterator(memtable_->NewIterator()); 342179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 343179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 344179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 345179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKeyComparator internal_comparator_; 346179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MemTable* memtable_; 347179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 348179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 349179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass DBConstructor: public Constructor { 350179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 351179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit DBConstructor(const Comparator* cmp) 352179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : Constructor(cmp), 353179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org comparator_(cmp) { 354179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org db_ = NULL; 355179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org NewDB(); 356179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 357179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~DBConstructor() { 358179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete db_; 359179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 360179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status FinishImpl(const Options& options, const KVMap& data) { 361179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete db_; 362179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org db_ = NULL; 363179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org NewDB(); 364179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator it = data.begin(); 365179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org it != data.end(); 366179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++it) { 367179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org WriteBatch batch; 368179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org batch.Put(it->first, it->second); 369179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(db_->Write(WriteOptions(), &batch).ok()); 370179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 371179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::OK(); 372179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 373179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Iterator* NewIterator() const { 374179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return db_->NewIterator(ReadOptions()); 375179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 376179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 37784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org virtual DB* db() const { return db_; } 37884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 379179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 380179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void NewDB() { 381179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string name = test::TmpDir() + "/table_testdb"; 382179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 383179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options options; 384179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.comparator = comparator_; 385179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status status = DestroyDB(name, options); 386179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(status.ok()) << status.ToString(); 387179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 388179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.create_if_missing = true; 389179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.error_if_exists = true; 39084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org options.write_buffer_size = 10000; // Something small to force merging 391179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org status = DB::Open(options, name, &db_); 392179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(status.ok()) << status.ToString(); 393179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 394179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 395179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Comparator* comparator_; 396179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org DB* db_; 397179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 398179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 399179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgenum TestType { 400179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TABLE_TEST, 401179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BLOCK_TEST, 402179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MEMTABLE_TEST, 40351f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com DB_TEST 404179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 405179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 406179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstruct TestArgs { 407179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestType type; 408179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool reverse_compare; 409179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int restart_interval; 410179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 411179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 412179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic const TestArgs kTestArgList[] = { 413179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, false, 16 }, 414179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, false, 1 }, 415179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, false, 1024 }, 416179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, true, 16 }, 417179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, true, 1 }, 418179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { TABLE_TEST, true, 1024 }, 419179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 420179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, false, 16 }, 421179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, false, 1 }, 422179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, false, 1024 }, 423179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, true, 16 }, 424179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, true, 1 }, 425179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { BLOCK_TEST, true, 1024 }, 426179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 427179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Restart interval does not matter for memtables 428179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { MEMTABLE_TEST, false, 16 }, 429179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { MEMTABLE_TEST, true, 16 }, 430179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 431179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Do not bother with restart interval variations for DB 432179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { DB_TEST, false, 16 }, 433179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { DB_TEST, true, 16 }, 434179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 435179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic const int kNumTestArgs = sizeof(kTestArgList) / sizeof(kTestArgList[0]); 436179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 437179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Harness { 438179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 439179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Harness() : constructor_(NULL) { } 440179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 441179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Init(const TestArgs& args) { 442179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete constructor_; 443179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_ = NULL; 444179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options_ = Options(); 445179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 446179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options_.block_restart_interval = args.restart_interval; 447179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Use shorter block size for tests to exercise block boundary 448179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // conditions more. 449179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options_.block_size = 256; 450179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (args.reverse_compare) { 451179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options_.comparator = &reverse_key_comparator; 452179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 453179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org switch (args.type) { 454179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case TABLE_TEST: 455179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_ = new TableConstructor(options_.comparator); 456179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 457179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case BLOCK_TEST: 458179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_ = new BlockConstructor(options_.comparator); 459179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 460179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case MEMTABLE_TEST: 461179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_ = new MemTableConstructor(options_.comparator); 462179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 463179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case DB_TEST: 464179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_ = new DBConstructor(options_.comparator); 465179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 466179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 467179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 468179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 469179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~Harness() { 470179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete constructor_; 471179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 472179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 473179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Add(const std::string& key, const std::string& value) { 474179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_->Add(key, value); 475179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 476179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 477179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Test(Random* rnd) { 478179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<std::string> keys; 479179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap data; 480179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org constructor_->Finish(options_, &keys, &data); 481179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 482179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestForwardScan(keys, data); 483179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestBackwardScan(keys, data); 484179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestRandomAccess(rnd, keys, data); 485179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 486179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 487179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void TestForwardScan(const std::vector<std::string>& keys, 488179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const KVMap& data) { 489179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter = constructor_->NewIterator(); 490179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!iter->Valid()); 491179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->SeekToFirst(); 492179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_iterator model_iter = data.begin(); 493179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter != data.end(); 494179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++model_iter) { 495179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 496179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Next(); 497179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 498179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!iter->Valid()); 499179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete iter; 500179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 501179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 502179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void TestBackwardScan(const std::vector<std::string>& keys, 503179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const KVMap& data) { 504179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter = constructor_->NewIterator(); 505179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!iter->Valid()); 506179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->SeekToLast(); 507179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (KVMap::const_reverse_iterator model_iter = data.rbegin(); 508179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter != data.rend(); 509179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++model_iter) { 510179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 511179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Prev(); 512179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 513179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!iter->Valid()); 514179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete iter; 515179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 516179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 517179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void TestRandomAccess(Random* rnd, 518179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<std::string>& keys, 519179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const KVMap& data) { 520179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org static const bool kVerbose = false; 521179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter = constructor_->NewIterator(); 522179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!iter->Valid()); 523179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap::const_iterator model_iter = data.begin(); 524179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "---\n"); 525179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < 200; i++) { 526179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int toss = rnd->Uniform(5); 527179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org switch (toss) { 528179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 0: { 529179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (iter->Valid()) { 530179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "Next\n"); 531179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Next(); 532179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++model_iter; 533179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 534179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 535179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 536179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 537179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 538179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 1: { 539179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "SeekToFirst\n"); 540179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->SeekToFirst(); 541179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter = data.begin(); 542179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 543179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 544179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 545179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 546179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 2: { 547179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string key = PickRandomKey(rnd, keys); 548179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter = data.lower_bound(key); 549179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "Seek '%s'\n", 550179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org EscapeString(key).c_str()); 551179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Seek(Slice(key)); 552179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 553179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 554179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 555179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 556179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 3: { 557179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (iter->Valid()) { 558179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "Prev\n"); 559179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Prev(); 560179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (model_iter == data.begin()) { 561179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter = data.end(); // Wrap around to invalid value 562179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 563179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org --model_iter; 564179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 565179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 566179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 567179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 568179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 569179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 570179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 4: { 571179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (kVerbose) fprintf(stderr, "SeekToLast\n"); 572179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->SeekToLast(); 573179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (keys.empty()) { 574179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter = data.end(); 575179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 576179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string last = data.rbegin()->first; 577179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org model_iter = data.lower_bound(last); 578179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 579179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(ToString(data, model_iter), ToString(iter)); 580179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 581179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 582179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 583179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 584179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete iter; 585179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 586179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 587179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string ToString(const KVMap& data, const KVMap::const_iterator& it) { 588179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (it == data.end()) { 589179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "END"; 590179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 591179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "'" + it->first + "->" + it->second + "'"; 592179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 593179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 594179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 595179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string ToString(const KVMap& data, 596179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const KVMap::const_reverse_iterator& it) { 597179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (it == data.rend()) { 598179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "END"; 599179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 600179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "'" + it->first + "->" + it->second + "'"; 601179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 602179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 603179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 604179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string ToString(const Iterator* it) { 605179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!it->Valid()) { 606179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "END"; 607179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 608179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "'" + it->key().ToString() + "->" + it->value().ToString() + "'"; 609179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 610179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 611179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 612179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) { 613179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (keys.empty()) { 614179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "foo"; 615179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 616179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int index = rnd->Uniform(keys.size()); 617179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string result = keys[index]; 618179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org switch (rnd->Uniform(3)) { 619179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 0: 620179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return an existing key 621179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 622179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 1: { 623179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Attempt to return something smaller than an existing key 624179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (result.size() > 0 && result[result.size()-1] > '\0') { 625179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result[result.size()-1]--; 626179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 627179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 628179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 629179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 2: { 630179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return something larger than an existing key 631179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Increment(options_.comparator, &result); 632179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 633179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 634179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 635179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 636179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 637179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 638179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 63984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // Returns NULL if not running against a DB 64084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org DB* db() const { return constructor_->db(); } 64184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 642179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 643179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options options_; 644179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Constructor* constructor_; 645179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 646179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 647bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org// Test empty table/block. 648bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.orgTEST(Harness, Empty) { 649bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 650bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org Init(kTestArgList[i]); 651bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org Random rnd(test::RandomSeed() + 1); 652bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org Test(&rnd); 653bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org } 654bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org} 655bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org 656bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org// Special test for a block with no restart entries. The C++ leveldb 657bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org// code never generates such blocks, but the Java version of leveldb 658bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org// seems to. 659bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.orgTEST(Harness, ZeroRestartPointsInBlock) { 660bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org char data[sizeof(uint32_t)]; 661bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org memset(data, 0, sizeof(data)); 662bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org BlockContents contents; 663bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org contents.data = Slice(data, sizeof(data)); 664bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org contents.cachable = false; 665bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org contents.heap_allocated = false; 666bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org Block block(contents); 667bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org Iterator* iter = block.NewIterator(BytewiseComparator()); 668bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org iter->SeekToFirst(); 669bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org ASSERT_TRUE(!iter->Valid()); 670bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org iter->SeekToLast(); 671bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org ASSERT_TRUE(!iter->Valid()); 672bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org iter->Seek("foo"); 673bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org ASSERT_TRUE(!iter->Valid()); 674bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org delete iter; 675bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org} 676bd534e2d9ba35e6ada9afe854ad0dbcef3f27c4fdgrogan@chromium.org 677179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Test the empty key 678179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(Harness, SimpleEmptyKey) { 679179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 680179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Init(kTestArgList[i]); 681179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(test::RandomSeed() + 1); 682179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("", "v"); 683179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Test(&rnd); 684179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 685179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 686179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 687179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(Harness, SimpleSingle) { 688179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 689179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Init(kTestArgList[i]); 690179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(test::RandomSeed() + 2); 691179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("abc", "v"); 692179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Test(&rnd); 693179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 694179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 695179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 696179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(Harness, SimpleMulti) { 697179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 698179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Init(kTestArgList[i]); 699179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(test::RandomSeed() + 3); 700179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("abc", "v"); 701179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("abcd", "v"); 702179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("ac", "v2"); 703179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Test(&rnd); 704179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 705179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 706179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 707179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(Harness, SimpleSpecialKey) { 708179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 709179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Init(kTestArgList[i]); 710179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(test::RandomSeed() + 4); 711179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add("\xff\xff", "v3"); 712179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Test(&rnd); 713179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 714179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 715179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 716179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(Harness, Randomized) { 717179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kNumTestArgs; i++) { 718179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Init(kTestArgList[i]); 719179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(test::RandomSeed() + 5); 720179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int num_entries = 0; num_entries < 2000; 721179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org num_entries += (num_entries < 50 ? 1 : 200)) { 722179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if ((num_entries % 10) == 0) { 723179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org fprintf(stderr, "case %d of %d: num_entries = %d\n", 724179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (i + 1), int(kNumTestArgs), num_entries); 725179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 726179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int e = 0; e < num_entries; e++) { 727179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string v; 728179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Add(test::RandomKey(&rnd, rnd.Skewed(4)), 729179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); 730179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 731179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Test(&rnd); 732179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 733179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 734179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 735179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 73684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.orgTEST(Harness, RandomizedLongDB) { 73784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org Random rnd(test::RandomSeed()); 73884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org TestArgs args = { DB_TEST, false, 16 }; 73984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org Init(args); 74084744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org int num_entries = 100000; 74184744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org for (int e = 0; e < num_entries; e++) { 74284744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org std::string v; 74384744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org Add(test::RandomKey(&rnd, rnd.Skewed(4)), 74484744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); 74584744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org } 74684744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org Test(&rnd); 74784744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 74884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org // We must have created enough data to force merging 7498cd4ab8303620197cf24282ae8639060efbb326egabor@google.com int files = 0; 7508cd4ab8303620197cf24282ae8639060efbb326egabor@google.com for (int level = 0; level < config::kNumLevels; level++) { 7518cd4ab8303620197cf24282ae8639060efbb326egabor@google.com std::string value; 7528cd4ab8303620197cf24282ae8639060efbb326egabor@google.com char name[100]; 7538cd4ab8303620197cf24282ae8639060efbb326egabor@google.com snprintf(name, sizeof(name), "leveldb.num-files-at-level%d", level); 7548cd4ab8303620197cf24282ae8639060efbb326egabor@google.com ASSERT_TRUE(db()->GetProperty(name, &value)); 7558cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files += atoi(value.c_str()); 7568cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 7578cd4ab8303620197cf24282ae8639060efbb326egabor@google.com ASSERT_GT(files, 0); 75884744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org} 75984744ee8e3e568ca5b24eabf31be706d69d80c4djorlow@chromium.org 760179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MemTableTest { }; 761179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 762179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(MemTableTest, Simple) { 763179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKeyComparator cmp(BytewiseComparator()); 764a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org MemTable* memtable = new MemTable(cmp); 765a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable->Ref(); 766179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org WriteBatch batch; 767179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org WriteBatchInternal::SetSequence(&batch, 100); 768179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org batch.Put(std::string("k1"), std::string("v1")); 769179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org batch.Put(std::string("k2"), std::string("v2")); 770179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org batch.Put(std::string("k3"), std::string("v3")); 771179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org batch.Put(std::string("largekey"), std::string("vlarge")); 772a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org ASSERT_TRUE(WriteBatchInternal::InsertInto(&batch, memtable).ok()); 773179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 774a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org Iterator* iter = memtable->NewIterator(); 775179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->SeekToFirst(); 776179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (iter->Valid()) { 777179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org fprintf(stderr, "key: '%s' -> '%s'\n", 778179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->key().ToString().c_str(), 779179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->value().ToString().c_str()); 780179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->Next(); 781179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 782179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 783179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete iter; 784a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org memtable->Unref(); 785179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 786179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 787179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic bool Between(uint64_t val, uint64_t low, uint64_t high) { 788179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool result = (val >= low) && (val <= high); 789179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!result) { 790179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n", 791179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (unsigned long long)(val), 792179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (unsigned long long)(low), 793179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (unsigned long long)(high)); 794179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 795179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 796179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 797179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 798179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass TableTest { }; 799179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 800179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(TableTest, ApproximateOffsetOfPlain) { 801179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableConstructor c(BytewiseComparator()); 802179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k01", "hello"); 803179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k02", "hello2"); 804179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k03", std::string(10000, 'x')); 805179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k04", std::string(200000, 'x')); 806179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k05", std::string(300000, 'x')); 807179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k06", "hello3"); 808179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k07", std::string(100000, 'x')); 809179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<std::string> keys; 810179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap kvmap; 811179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options options; 812179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.block_size = 1024; 813179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.compression = kNoCompression; 814179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Finish(options, &keys, &kvmap); 815179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 816179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); 817179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); 818179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01a"), 0, 0)); 819179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); 820179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 0, 0)); 821179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 10000, 11000)); 822179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04a"), 210000, 211000)); 823179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k05"), 210000, 211000)); 824179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k06"), 510000, 511000)); 825179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k07"), 510000, 511000)); 82699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 610000, 612000)); 827179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 828179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 829179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 83007f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.orgstatic bool SnappyCompressionSupported() { 83107f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org std::string out; 83207f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org Slice in = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 83307f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org return port::Snappy_Compress(in.data(), in.size(), &out); 83407f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org} 83507f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org 836179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(TableTest, ApproximateOffsetOfCompressed) { 83707f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org if (!SnappyCompressionSupported()) { 83807f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org fprintf(stderr, "skipping compression tests\n"); 83907f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org return; 84007f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org } 841179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 842179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd(301); 843179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableConstructor c(BytewiseComparator()); 844179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string tmp; 845179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k01", "hello"); 846179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k02", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); 847179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k03", "hello3"); 848179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Add("k04", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); 849179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<std::string> keys; 850179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org KVMap kvmap; 851179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options options; 852179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.block_size = 1024; 85307f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org options.compression = kSnappyCompression; 854179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c.Finish(options, &keys, &kvmap); 855179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 856179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); 857179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); 858179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); 859179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 2000, 3000)); 860179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 2000, 3000)); 861179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 4000, 6000)); 862179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 863179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 86445b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 865179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 866179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint main(int argc, char** argv) { 867179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return leveldb::test::RunAllTests(); 868179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 869