You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@nifi.apache.org by je...@apache.org on 2017/10/09 16:25:18 UTC
[38/51] [partial] nifi-minifi-cpp git commit: MINIFI-372: Replace
leveldb with RocksDB
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/table/table_test.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/table/table_test.cc b/thirdparty/leveldb-1.18/table/table_test.cc
deleted file mode 100755
index d46c079..0000000
--- a/thirdparty/leveldb-1.18/table/table_test.cc
+++ /dev/null
@@ -1,868 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "leveldb/table.h"
-
-#include <map>
-#include <string>
-#include "db/dbformat.h"
-#include "db/memtable.h"
-#include "db/write_batch_internal.h"
-#include "leveldb/db.h"
-#include "leveldb/env.h"
-#include "leveldb/iterator.h"
-#include "leveldb/table_builder.h"
-#include "table/block.h"
-#include "table/block_builder.h"
-#include "table/format.h"
-#include "util/random.h"
-#include "util/testharness.h"
-#include "util/testutil.h"
-
-namespace leveldb {
-
-// Return reverse of "key".
-// Used to test non-lexicographic comparators.
-static std::string Reverse(const Slice& key) {
- std::string str(key.ToString());
- std::string rev("");
- for (std::string::reverse_iterator rit = str.rbegin();
- rit != str.rend(); ++rit) {
- rev.push_back(*rit);
- }
- return rev;
-}
-
-namespace {
-class ReverseKeyComparator : public Comparator {
- public:
- virtual const char* Name() const {
- return "leveldb.ReverseBytewiseComparator";
- }
-
- virtual int Compare(const Slice& a, const Slice& b) const {
- return BytewiseComparator()->Compare(Reverse(a), Reverse(b));
- }
-
- virtual void FindShortestSeparator(
- std::string* start,
- const Slice& limit) const {
- std::string s = Reverse(*start);
- std::string l = Reverse(limit);
- BytewiseComparator()->FindShortestSeparator(&s, l);
- *start = Reverse(s);
- }
-
- virtual void FindShortSuccessor(std::string* key) const {
- std::string s = Reverse(*key);
- BytewiseComparator()->FindShortSuccessor(&s);
- *key = Reverse(s);
- }
-};
-} // namespace
-static ReverseKeyComparator reverse_key_comparator;
-
-static void Increment(const Comparator* cmp, std::string* key) {
- if (cmp == BytewiseComparator()) {
- key->push_back('\0');
- } else {
- assert(cmp == &reverse_key_comparator);
- std::string rev = Reverse(*key);
- rev.push_back('\0');
- *key = Reverse(rev);
- }
-}
-
-// An STL comparator that uses a Comparator
-namespace {
-struct STLLessThan {
- const Comparator* cmp;
-
- STLLessThan() : cmp(BytewiseComparator()) { }
- STLLessThan(const Comparator* c) : cmp(c) { }
- bool operator()(const std::string& a, const std::string& b) const {
- return cmp->Compare(Slice(a), Slice(b)) < 0;
- }
-};
-} // namespace
-
-class StringSink: public WritableFile {
- public:
- ~StringSink() { }
-
- const std::string& contents() const { return contents_; }
-
- virtual Status Close() { return Status::OK(); }
- virtual Status Flush() { return Status::OK(); }
- virtual Status Sync() { return Status::OK(); }
-
- virtual Status Append(const Slice& data) {
- contents_.append(data.data(), data.size());
- return Status::OK();
- }
-
- private:
- std::string contents_;
-};
-
-
-class StringSource: public RandomAccessFile {
- public:
- StringSource(const Slice& contents)
- : contents_(contents.data(), contents.size()) {
- }
-
- virtual ~StringSource() { }
-
- uint64_t Size() const { return contents_.size(); }
-
- virtual Status Read(uint64_t offset, size_t n, Slice* result,
- char* scratch) const {
- if (offset > contents_.size()) {
- return Status::InvalidArgument("invalid Read offset");
- }
- if (offset + n > contents_.size()) {
- n = contents_.size() - offset;
- }
- memcpy(scratch, &contents_[offset], n);
- *result = Slice(scratch, n);
- return Status::OK();
- }
-
- private:
- std::string contents_;
-};
-
-typedef std::map<std::string, std::string, STLLessThan> KVMap;
-
-// Helper class for tests to unify the interface between
-// BlockBuilder/TableBuilder and Block/Table.
-class Constructor {
- public:
- explicit Constructor(const Comparator* cmp) : data_(STLLessThan(cmp)) { }
- virtual ~Constructor() { }
-
- void Add(const std::string& key, const Slice& value) {
- data_[key] = value.ToString();
- }
-
- // Finish constructing the data structure with all the keys that have
- // been added so far. Returns the keys in sorted order in "*keys"
- // and stores the key/value pairs in "*kvmap"
- void Finish(const Options& options,
- std::vector<std::string>* keys,
- KVMap* kvmap) {
- *kvmap = data_;
- keys->clear();
- for (KVMap::const_iterator it = data_.begin();
- it != data_.end();
- ++it) {
- keys->push_back(it->first);
- }
- data_.clear();
- Status s = FinishImpl(options, *kvmap);
- ASSERT_TRUE(s.ok()) << s.ToString();
- }
-
- // Construct the data structure from the data in "data"
- virtual Status FinishImpl(const Options& options, const KVMap& data) = 0;
-
- virtual Iterator* NewIterator() const = 0;
-
- virtual const KVMap& data() { return data_; }
-
- virtual DB* db() const { return NULL; } // Overridden in DBConstructor
-
- private:
- KVMap data_;
-};
-
-class BlockConstructor: public Constructor {
- public:
- explicit BlockConstructor(const Comparator* cmp)
- : Constructor(cmp),
- comparator_(cmp),
- block_(NULL) { }
- ~BlockConstructor() {
- delete block_;
- }
- virtual Status FinishImpl(const Options& options, const KVMap& data) {
- delete block_;
- block_ = NULL;
- BlockBuilder builder(&options);
-
- for (KVMap::const_iterator it = data.begin();
- it != data.end();
- ++it) {
- builder.Add(it->first, it->second);
- }
- // Open the block
- data_ = builder.Finish().ToString();
- BlockContents contents;
- contents.data = data_;
- contents.cachable = false;
- contents.heap_allocated = false;
- block_ = new Block(contents);
- return Status::OK();
- }
- virtual Iterator* NewIterator() const {
- return block_->NewIterator(comparator_);
- }
-
- private:
- const Comparator* comparator_;
- std::string data_;
- Block* block_;
-
- BlockConstructor();
-};
-
-class TableConstructor: public Constructor {
- public:
- TableConstructor(const Comparator* cmp)
- : Constructor(cmp),
- source_(NULL), table_(NULL) {
- }
- ~TableConstructor() {
- Reset();
- }
- virtual Status FinishImpl(const Options& options, const KVMap& data) {
- Reset();
- StringSink sink;
- TableBuilder builder(options, &sink);
-
- for (KVMap::const_iterator it = data.begin();
- it != data.end();
- ++it) {
- builder.Add(it->first, it->second);
- ASSERT_TRUE(builder.status().ok());
- }
- Status s = builder.Finish();
- ASSERT_TRUE(s.ok()) << s.ToString();
-
- ASSERT_EQ(sink.contents().size(), builder.FileSize());
-
- // Open the table
- source_ = new StringSource(sink.contents());
- Options table_options;
- table_options.comparator = options.comparator;
- return Table::Open(table_options, source_, sink.contents().size(), &table_);
- }
-
- virtual Iterator* NewIterator() const {
- return table_->NewIterator(ReadOptions());
- }
-
- uint64_t ApproximateOffsetOf(const Slice& key) const {
- return table_->ApproximateOffsetOf(key);
- }
-
- private:
- void Reset() {
- delete table_;
- delete source_;
- table_ = NULL;
- source_ = NULL;
- }
-
- StringSource* source_;
- Table* table_;
-
- TableConstructor();
-};
-
-// A helper class that converts internal format keys into user keys
-class KeyConvertingIterator: public Iterator {
- public:
- explicit KeyConvertingIterator(Iterator* iter) : iter_(iter) { }
- virtual ~KeyConvertingIterator() { delete iter_; }
- virtual bool Valid() const { return iter_->Valid(); }
- virtual void Seek(const Slice& target) {
- ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue);
- std::string encoded;
- AppendInternalKey(&encoded, ikey);
- iter_->Seek(encoded);
- }
- virtual void SeekToFirst() { iter_->SeekToFirst(); }
- virtual void SeekToLast() { iter_->SeekToLast(); }
- virtual void Next() { iter_->Next(); }
- virtual void Prev() { iter_->Prev(); }
-
- virtual Slice key() const {
- assert(Valid());
- ParsedInternalKey key;
- if (!ParseInternalKey(iter_->key(), &key)) {
- status_ = Status::Corruption("malformed internal key");
- return Slice("corrupted key");
- }
- return key.user_key;
- }
-
- virtual Slice value() const { return iter_->value(); }
- virtual Status status() const {
- return status_.ok() ? iter_->status() : status_;
- }
-
- private:
- mutable Status status_;
- Iterator* iter_;
-
- // No copying allowed
- KeyConvertingIterator(const KeyConvertingIterator&);
- void operator=(const KeyConvertingIterator&);
-};
-
-class MemTableConstructor: public Constructor {
- public:
- explicit MemTableConstructor(const Comparator* cmp)
- : Constructor(cmp),
- internal_comparator_(cmp) {
- memtable_ = new MemTable(internal_comparator_);
- memtable_->Ref();
- }
- ~MemTableConstructor() {
- memtable_->Unref();
- }
- virtual Status FinishImpl(const Options& options, const KVMap& data) {
- memtable_->Unref();
- memtable_ = new MemTable(internal_comparator_);
- memtable_->Ref();
- int seq = 1;
- for (KVMap::const_iterator it = data.begin();
- it != data.end();
- ++it) {
- memtable_->Add(seq, kTypeValue, it->first, it->second);
- seq++;
- }
- return Status::OK();
- }
- virtual Iterator* NewIterator() const {
- return new KeyConvertingIterator(memtable_->NewIterator());
- }
-
- private:
- InternalKeyComparator internal_comparator_;
- MemTable* memtable_;
-};
-
-class DBConstructor: public Constructor {
- public:
- explicit DBConstructor(const Comparator* cmp)
- : Constructor(cmp),
- comparator_(cmp) {
- db_ = NULL;
- NewDB();
- }
- ~DBConstructor() {
- delete db_;
- }
- virtual Status FinishImpl(const Options& options, const KVMap& data) {
- delete db_;
- db_ = NULL;
- NewDB();
- for (KVMap::const_iterator it = data.begin();
- it != data.end();
- ++it) {
- WriteBatch batch;
- batch.Put(it->first, it->second);
- ASSERT_TRUE(db_->Write(WriteOptions(), &batch).ok());
- }
- return Status::OK();
- }
- virtual Iterator* NewIterator() const {
- return db_->NewIterator(ReadOptions());
- }
-
- virtual DB* db() const { return db_; }
-
- private:
- void NewDB() {
- std::string name = test::TmpDir() + "/table_testdb";
-
- Options options;
- options.comparator = comparator_;
- Status status = DestroyDB(name, options);
- ASSERT_TRUE(status.ok()) << status.ToString();
-
- options.create_if_missing = true;
- options.error_if_exists = true;
- options.write_buffer_size = 10000; // Something small to force merging
- status = DB::Open(options, name, &db_);
- ASSERT_TRUE(status.ok()) << status.ToString();
- }
-
- const Comparator* comparator_;
- DB* db_;
-};
-
-enum TestType {
- TABLE_TEST,
- BLOCK_TEST,
- MEMTABLE_TEST,
- DB_TEST
-};
-
-struct TestArgs {
- TestType type;
- bool reverse_compare;
- int restart_interval;
-};
-
-static const TestArgs kTestArgList[] = {
- { TABLE_TEST, false, 16 },
- { TABLE_TEST, false, 1 },
- { TABLE_TEST, false, 1024 },
- { TABLE_TEST, true, 16 },
- { TABLE_TEST, true, 1 },
- { TABLE_TEST, true, 1024 },
-
- { BLOCK_TEST, false, 16 },
- { BLOCK_TEST, false, 1 },
- { BLOCK_TEST, false, 1024 },
- { BLOCK_TEST, true, 16 },
- { BLOCK_TEST, true, 1 },
- { BLOCK_TEST, true, 1024 },
-
- // Restart interval does not matter for memtables
- { MEMTABLE_TEST, false, 16 },
- { MEMTABLE_TEST, true, 16 },
-
- // Do not bother with restart interval variations for DB
- { DB_TEST, false, 16 },
- { DB_TEST, true, 16 },
-};
-static const int kNumTestArgs = sizeof(kTestArgList) / sizeof(kTestArgList[0]);
-
-class Harness {
- public:
- Harness() : constructor_(NULL) { }
-
- void Init(const TestArgs& args) {
- delete constructor_;
- constructor_ = NULL;
- options_ = Options();
-
- options_.block_restart_interval = args.restart_interval;
- // Use shorter block size for tests to exercise block boundary
- // conditions more.
- options_.block_size = 256;
- if (args.reverse_compare) {
- options_.comparator = &reverse_key_comparator;
- }
- switch (args.type) {
- case TABLE_TEST:
- constructor_ = new TableConstructor(options_.comparator);
- break;
- case BLOCK_TEST:
- constructor_ = new BlockConstructor(options_.comparator);
- break;
- case MEMTABLE_TEST:
- constructor_ = new MemTableConstructor(options_.comparator);
- break;
- case DB_TEST:
- constructor_ = new DBConstructor(options_.comparator);
- break;
- }
- }
-
- ~Harness() {
- delete constructor_;
- }
-
- void Add(const std::string& key, const std::string& value) {
- constructor_->Add(key, value);
- }
-
- void Test(Random* rnd) {
- std::vector<std::string> keys;
- KVMap data;
- constructor_->Finish(options_, &keys, &data);
-
- TestForwardScan(keys, data);
- TestBackwardScan(keys, data);
- TestRandomAccess(rnd, keys, data);
- }
-
- void TestForwardScan(const std::vector<std::string>& keys,
- const KVMap& data) {
- Iterator* iter = constructor_->NewIterator();
- ASSERT_TRUE(!iter->Valid());
- iter->SeekToFirst();
- for (KVMap::const_iterator model_iter = data.begin();
- model_iter != data.end();
- ++model_iter) {
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- iter->Next();
- }
- ASSERT_TRUE(!iter->Valid());
- delete iter;
- }
-
- void TestBackwardScan(const std::vector<std::string>& keys,
- const KVMap& data) {
- Iterator* iter = constructor_->NewIterator();
- ASSERT_TRUE(!iter->Valid());
- iter->SeekToLast();
- for (KVMap::const_reverse_iterator model_iter = data.rbegin();
- model_iter != data.rend();
- ++model_iter) {
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- iter->Prev();
- }
- ASSERT_TRUE(!iter->Valid());
- delete iter;
- }
-
- void TestRandomAccess(Random* rnd,
- const std::vector<std::string>& keys,
- const KVMap& data) {
- static const bool kVerbose = false;
- Iterator* iter = constructor_->NewIterator();
- ASSERT_TRUE(!iter->Valid());
- KVMap::const_iterator model_iter = data.begin();
- if (kVerbose) fprintf(stderr, "---\n");
- for (int i = 0; i < 200; i++) {
- const int toss = rnd->Uniform(5);
- switch (toss) {
- case 0: {
- if (iter->Valid()) {
- if (kVerbose) fprintf(stderr, "Next\n");
- iter->Next();
- ++model_iter;
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- }
- break;
- }
-
- case 1: {
- if (kVerbose) fprintf(stderr, "SeekToFirst\n");
- iter->SeekToFirst();
- model_iter = data.begin();
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- break;
- }
-
- case 2: {
- std::string key = PickRandomKey(rnd, keys);
- model_iter = data.lower_bound(key);
- if (kVerbose) fprintf(stderr, "Seek '%s'\n",
- EscapeString(key).c_str());
- iter->Seek(Slice(key));
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- break;
- }
-
- case 3: {
- if (iter->Valid()) {
- if (kVerbose) fprintf(stderr, "Prev\n");
- iter->Prev();
- if (model_iter == data.begin()) {
- model_iter = data.end(); // Wrap around to invalid value
- } else {
- --model_iter;
- }
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- }
- break;
- }
-
- case 4: {
- if (kVerbose) fprintf(stderr, "SeekToLast\n");
- iter->SeekToLast();
- if (keys.empty()) {
- model_iter = data.end();
- } else {
- std::string last = data.rbegin()->first;
- model_iter = data.lower_bound(last);
- }
- ASSERT_EQ(ToString(data, model_iter), ToString(iter));
- break;
- }
- }
- }
- delete iter;
- }
-
- std::string ToString(const KVMap& data, const KVMap::const_iterator& it) {
- if (it == data.end()) {
- return "END";
- } else {
- return "'" + it->first + "->" + it->second + "'";
- }
- }
-
- std::string ToString(const KVMap& data,
- const KVMap::const_reverse_iterator& it) {
- if (it == data.rend()) {
- return "END";
- } else {
- return "'" + it->first + "->" + it->second + "'";
- }
- }
-
- std::string ToString(const Iterator* it) {
- if (!it->Valid()) {
- return "END";
- } else {
- return "'" + it->key().ToString() + "->" + it->value().ToString() + "'";
- }
- }
-
- std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) {
- if (keys.empty()) {
- return "foo";
- } else {
- const int index = rnd->Uniform(static_cast<int>(keys.size()));
- std::string result = keys[index];
- switch (rnd->Uniform(3)) {
- case 0:
- // Return an existing key
- break;
- case 1: {
- // Attempt to return something smaller than an existing key
- if (result.size() > 0 && result[result.size()-1] > '\0') {
- result[result.size()-1]--;
- }
- break;
- }
- case 2: {
- // Return something larger than an existing key
- Increment(options_.comparator, &result);
- break;
- }
- }
- return result;
- }
- }
-
- // Returns NULL if not running against a DB
- DB* db() const { return constructor_->db(); }
-
- private:
- Options options_;
- Constructor* constructor_;
-};
-
-// Test empty table/block.
-TEST(Harness, Empty) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 1);
- Test(&rnd);
- }
-}
-
-// Special test for a block with no restart entries. The C++ leveldb
-// code never generates such blocks, but the Java version of leveldb
-// seems to.
-TEST(Harness, ZeroRestartPointsInBlock) {
- char data[sizeof(uint32_t)];
- memset(data, 0, sizeof(data));
- BlockContents contents;
- contents.data = Slice(data, sizeof(data));
- contents.cachable = false;
- contents.heap_allocated = false;
- Block block(contents);
- Iterator* iter = block.NewIterator(BytewiseComparator());
- iter->SeekToFirst();
- ASSERT_TRUE(!iter->Valid());
- iter->SeekToLast();
- ASSERT_TRUE(!iter->Valid());
- iter->Seek("foo");
- ASSERT_TRUE(!iter->Valid());
- delete iter;
-}
-
-// Test the empty key
-TEST(Harness, SimpleEmptyKey) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 1);
- Add("", "v");
- Test(&rnd);
- }
-}
-
-TEST(Harness, SimpleSingle) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 2);
- Add("abc", "v");
- Test(&rnd);
- }
-}
-
-TEST(Harness, SimpleMulti) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 3);
- Add("abc", "v");
- Add("abcd", "v");
- Add("ac", "v2");
- Test(&rnd);
- }
-}
-
-TEST(Harness, SimpleSpecialKey) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 4);
- Add("\xff\xff", "v3");
- Test(&rnd);
- }
-}
-
-TEST(Harness, Randomized) {
- for (int i = 0; i < kNumTestArgs; i++) {
- Init(kTestArgList[i]);
- Random rnd(test::RandomSeed() + 5);
- for (int num_entries = 0; num_entries < 2000;
- num_entries += (num_entries < 50 ? 1 : 200)) {
- if ((num_entries % 10) == 0) {
- fprintf(stderr, "case %d of %d: num_entries = %d\n",
- (i + 1), int(kNumTestArgs), num_entries);
- }
- for (int e = 0; e < num_entries; e++) {
- std::string v;
- Add(test::RandomKey(&rnd, rnd.Skewed(4)),
- test::RandomString(&rnd, rnd.Skewed(5), &v).ToString());
- }
- Test(&rnd);
- }
- }
-}
-
-TEST(Harness, RandomizedLongDB) {
- Random rnd(test::RandomSeed());
- TestArgs args = { DB_TEST, false, 16 };
- Init(args);
- int num_entries = 100000;
- for (int e = 0; e < num_entries; e++) {
- std::string v;
- Add(test::RandomKey(&rnd, rnd.Skewed(4)),
- test::RandomString(&rnd, rnd.Skewed(5), &v).ToString());
- }
- Test(&rnd);
-
- // We must have created enough data to force merging
- int files = 0;
- for (int level = 0; level < config::kNumLevels; level++) {
- std::string value;
- char name[100];
- snprintf(name, sizeof(name), "leveldb.num-files-at-level%d", level);
- ASSERT_TRUE(db()->GetProperty(name, &value));
- files += atoi(value.c_str());
- }
- ASSERT_GT(files, 0);
-}
-
-class MemTableTest { };
-
-TEST(MemTableTest, Simple) {
- InternalKeyComparator cmp(BytewiseComparator());
- MemTable* memtable = new MemTable(cmp);
- memtable->Ref();
- WriteBatch batch;
- WriteBatchInternal::SetSequence(&batch, 100);
- batch.Put(std::string("k1"), std::string("v1"));
- batch.Put(std::string("k2"), std::string("v2"));
- batch.Put(std::string("k3"), std::string("v3"));
- batch.Put(std::string("largekey"), std::string("vlarge"));
- ASSERT_TRUE(WriteBatchInternal::InsertInto(&batch, memtable).ok());
-
- Iterator* iter = memtable->NewIterator();
- iter->SeekToFirst();
- while (iter->Valid()) {
- fprintf(stderr, "key: '%s' -> '%s'\n",
- iter->key().ToString().c_str(),
- iter->value().ToString().c_str());
- iter->Next();
- }
-
- delete iter;
- memtable->Unref();
-}
-
-static bool Between(uint64_t val, uint64_t low, uint64_t high) {
- bool result = (val >= low) && (val <= high);
- if (!result) {
- fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n",
- (unsigned long long)(val),
- (unsigned long long)(low),
- (unsigned long long)(high));
- }
- return result;
-}
-
-class TableTest { };
-
-TEST(TableTest, ApproximateOffsetOfPlain) {
- TableConstructor c(BytewiseComparator());
- c.Add("k01", "hello");
- c.Add("k02", "hello2");
- c.Add("k03", std::string(10000, 'x'));
- c.Add("k04", std::string(200000, 'x'));
- c.Add("k05", std::string(300000, 'x'));
- c.Add("k06", "hello3");
- c.Add("k07", std::string(100000, 'x'));
- std::vector<std::string> keys;
- KVMap kvmap;
- Options options;
- options.block_size = 1024;
- options.compression = kNoCompression;
- c.Finish(options, &keys, &kvmap);
-
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01a"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 10000, 11000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04a"), 210000, 211000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k05"), 210000, 211000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k06"), 510000, 511000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k07"), 510000, 511000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 610000, 612000));
-
-}
-
-static bool SnappyCompressionSupported() {
- std::string out;
- Slice in = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
- return port::Snappy_Compress(in.data(), in.size(), &out);
-}
-
-TEST(TableTest, ApproximateOffsetOfCompressed) {
- if (!SnappyCompressionSupported()) {
- fprintf(stderr, "skipping compression tests\n");
- return;
- }
-
- Random rnd(301);
- TableConstructor c(BytewiseComparator());
- std::string tmp;
- c.Add("k01", "hello");
- c.Add("k02", test::CompressibleString(&rnd, 0.25, 10000, &tmp));
- c.Add("k03", "hello3");
- c.Add("k04", test::CompressibleString(&rnd, 0.25, 10000, &tmp));
- std::vector<std::string> keys;
- KVMap kvmap;
- Options options;
- options.block_size = 1024;
- options.compression = kSnappyCompression;
- c.Finish(options, &keys, &kvmap);
-
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 2000, 3000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 2000, 3000));
- ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 4000, 6000));
-}
-
-} // namespace leveldb
-
-int main(int argc, char** argv) {
- return leveldb::test::RunAllTests();
-}
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/table/two_level_iterator.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/table/two_level_iterator.cc b/thirdparty/leveldb-1.18/table/two_level_iterator.cc
deleted file mode 100755
index 7822eba..0000000
--- a/thirdparty/leveldb-1.18/table/two_level_iterator.cc
+++ /dev/null
@@ -1,182 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "table/two_level_iterator.h"
-
-#include "leveldb/table.h"
-#include "table/block.h"
-#include "table/format.h"
-#include "table/iterator_wrapper.h"
-
-namespace leveldb {
-
-namespace {
-
-typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);
-
-class TwoLevelIterator: public Iterator {
- public:
- TwoLevelIterator(
- Iterator* index_iter,
- BlockFunction block_function,
- void* arg,
- const ReadOptions& options);
-
- virtual ~TwoLevelIterator();
-
- virtual void Seek(const Slice& target);
- virtual void SeekToFirst();
- virtual void SeekToLast();
- virtual void Next();
- virtual void Prev();
-
- virtual bool Valid() const {
- return data_iter_.Valid();
- }
- virtual Slice key() const {
- assert(Valid());
- return data_iter_.key();
- }
- virtual Slice value() const {
- assert(Valid());
- return data_iter_.value();
- }
- virtual Status status() const {
- // It'd be nice if status() returned a const Status& instead of a Status
- if (!index_iter_.status().ok()) {
- return index_iter_.status();
- } else if (data_iter_.iter() != NULL && !data_iter_.status().ok()) {
- return data_iter_.status();
- } else {
- return status_;
- }
- }
-
- private:
- void SaveError(const Status& s) {
- if (status_.ok() && !s.ok()) status_ = s;
- }
- void SkipEmptyDataBlocksForward();
- void SkipEmptyDataBlocksBackward();
- void SetDataIterator(Iterator* data_iter);
- void InitDataBlock();
-
- BlockFunction block_function_;
- void* arg_;
- const ReadOptions options_;
- Status status_;
- IteratorWrapper index_iter_;
- IteratorWrapper data_iter_; // May be NULL
- // If data_iter_ is non-NULL, then "data_block_handle_" holds the
- // "index_value" passed to block_function_ to create the data_iter_.
- std::string data_block_handle_;
-};
-
-TwoLevelIterator::TwoLevelIterator(
- Iterator* index_iter,
- BlockFunction block_function,
- void* arg,
- const ReadOptions& options)
- : block_function_(block_function),
- arg_(arg),
- options_(options),
- index_iter_(index_iter),
- data_iter_(NULL) {
-}
-
-TwoLevelIterator::~TwoLevelIterator() {
-}
-
-void TwoLevelIterator::Seek(const Slice& target) {
- index_iter_.Seek(target);
- InitDataBlock();
- if (data_iter_.iter() != NULL) data_iter_.Seek(target);
- SkipEmptyDataBlocksForward();
-}
-
-void TwoLevelIterator::SeekToFirst() {
- index_iter_.SeekToFirst();
- InitDataBlock();
- if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
- SkipEmptyDataBlocksForward();
-}
-
-void TwoLevelIterator::SeekToLast() {
- index_iter_.SeekToLast();
- InitDataBlock();
- if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
- SkipEmptyDataBlocksBackward();
-}
-
-void TwoLevelIterator::Next() {
- assert(Valid());
- data_iter_.Next();
- SkipEmptyDataBlocksForward();
-}
-
-void TwoLevelIterator::Prev() {
- assert(Valid());
- data_iter_.Prev();
- SkipEmptyDataBlocksBackward();
-}
-
-
-void TwoLevelIterator::SkipEmptyDataBlocksForward() {
- while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
- // Move to next block
- if (!index_iter_.Valid()) {
- SetDataIterator(NULL);
- return;
- }
- index_iter_.Next();
- InitDataBlock();
- if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
- }
-}
-
-void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
- while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
- // Move to next block
- if (!index_iter_.Valid()) {
- SetDataIterator(NULL);
- return;
- }
- index_iter_.Prev();
- InitDataBlock();
- if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
- }
-}
-
-void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
- if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
- data_iter_.Set(data_iter);
-}
-
-void TwoLevelIterator::InitDataBlock() {
- if (!index_iter_.Valid()) {
- SetDataIterator(NULL);
- } else {
- Slice handle = index_iter_.value();
- if (data_iter_.iter() != NULL && handle.compare(data_block_handle_) == 0) {
- // data_iter_ is already constructed with this iterator, so
- // no need to change anything
- } else {
- Iterator* iter = (*block_function_)(arg_, options_, handle);
- data_block_handle_.assign(handle.data(), handle.size());
- SetDataIterator(iter);
- }
- }
-}
-
-} // namespace
-
-Iterator* NewTwoLevelIterator(
- Iterator* index_iter,
- BlockFunction block_function,
- void* arg,
- const ReadOptions& options) {
- return new TwoLevelIterator(index_iter, block_function, arg, options);
-}
-
-} // namespace leveldb
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/table/two_level_iterator.h
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/table/two_level_iterator.h b/thirdparty/leveldb-1.18/table/two_level_iterator.h
deleted file mode 100755
index 629ca34..0000000
--- a/thirdparty/leveldb-1.18/table/two_level_iterator.h
+++ /dev/null
@@ -1,34 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#ifndef STORAGE_LEVELDB_TABLE_TWO_LEVEL_ITERATOR_H_
-#define STORAGE_LEVELDB_TABLE_TWO_LEVEL_ITERATOR_H_
-
-#include "leveldb/iterator.h"
-
-namespace leveldb {
-
-struct ReadOptions;
-
-// Return a new two level iterator. A two-level iterator contains an
-// index iterator whose values point to a sequence of blocks where
-// each block is itself a sequence of key,value pairs. The returned
-// two-level iterator yields the concatenation of all key/value pairs
-// in the sequence of blocks. Takes ownership of "index_iter" and
-// will delete it when no longer needed.
-//
-// Uses a supplied function to convert an index_iter value into
-// an iterator over the contents of the corresponding block.
-extern Iterator* NewTwoLevelIterator(
- Iterator* index_iter,
- Iterator* (*block_function)(
- void* arg,
- const ReadOptions& options,
- const Slice& index_value),
- void* arg,
- const ReadOptions& options);
-
-} // namespace leveldb
-
-#endif // STORAGE_LEVELDB_TABLE_TWO_LEVEL_ITERATOR_H_
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/arena.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/arena.cc b/thirdparty/leveldb-1.18/util/arena.cc
deleted file mode 100755
index 9367f71..0000000
--- a/thirdparty/leveldb-1.18/util/arena.cc
+++ /dev/null
@@ -1,68 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "util/arena.h"
-#include <assert.h>
-
-namespace leveldb {
-
-static const int kBlockSize = 4096;
-
-Arena::Arena() {
- blocks_memory_ = 0;
- alloc_ptr_ = NULL; // First allocation will allocate a block
- alloc_bytes_remaining_ = 0;
-}
-
-Arena::~Arena() {
- for (size_t i = 0; i < blocks_.size(); i++) {
- delete[] blocks_[i];
- }
-}
-
-char* Arena::AllocateFallback(size_t bytes) {
- if (bytes > kBlockSize / 4) {
- // Object is more than a quarter of our block size. Allocate it separately
- // to avoid wasting too much space in leftover bytes.
- char* result = AllocateNewBlock(bytes);
- return result;
- }
-
- // We waste the remaining space in the current block.
- alloc_ptr_ = AllocateNewBlock(kBlockSize);
- alloc_bytes_remaining_ = kBlockSize;
-
- char* result = alloc_ptr_;
- alloc_ptr_ += bytes;
- alloc_bytes_remaining_ -= bytes;
- return result;
-}
-
-char* Arena::AllocateAligned(size_t bytes) {
- const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
- assert((align & (align-1)) == 0); // Pointer size should be a power of 2
- size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
- size_t slop = (current_mod == 0 ? 0 : align - current_mod);
- size_t needed = bytes + slop;
- char* result;
- if (needed <= alloc_bytes_remaining_) {
- result = alloc_ptr_ + slop;
- alloc_ptr_ += needed;
- alloc_bytes_remaining_ -= needed;
- } else {
- // AllocateFallback always returned aligned memory
- result = AllocateFallback(bytes);
- }
- assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
- return result;
-}
-
-char* Arena::AllocateNewBlock(size_t block_bytes) {
- char* result = new char[block_bytes];
- blocks_memory_ += block_bytes;
- blocks_.push_back(result);
- return result;
-}
-
-} // namespace leveldb
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/arena.h
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/arena.h b/thirdparty/leveldb-1.18/util/arena.h
deleted file mode 100755
index 73bbf1c..0000000
--- a/thirdparty/leveldb-1.18/util/arena.h
+++ /dev/null
@@ -1,68 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#ifndef STORAGE_LEVELDB_UTIL_ARENA_H_
-#define STORAGE_LEVELDB_UTIL_ARENA_H_
-
-#include <vector>
-#include <assert.h>
-#include <stddef.h>
-#include <stdint.h>
-
-namespace leveldb {
-
-class Arena {
- public:
- Arena();
- ~Arena();
-
- // Return a pointer to a newly allocated memory block of "bytes" bytes.
- char* Allocate(size_t bytes);
-
- // Allocate memory with the normal alignment guarantees provided by malloc
- char* AllocateAligned(size_t bytes);
-
- // Returns an estimate of the total memory usage of data allocated
- // by the arena (including space allocated but not yet used for user
- // allocations).
- size_t MemoryUsage() const {
- return blocks_memory_ + blocks_.capacity() * sizeof(char*);
- }
-
- private:
- char* AllocateFallback(size_t bytes);
- char* AllocateNewBlock(size_t block_bytes);
-
- // Allocation state
- char* alloc_ptr_;
- size_t alloc_bytes_remaining_;
-
- // Array of new[] allocated memory blocks
- std::vector<char*> blocks_;
-
- // Bytes of memory in blocks allocated so far
- size_t blocks_memory_;
-
- // No copying allowed
- Arena(const Arena&);
- void operator=(const Arena&);
-};
-
-inline char* Arena::Allocate(size_t bytes) {
- // The semantics of what to return are a bit messy if we allow
- // 0-byte allocations, so we disallow them here (we don't need
- // them for our internal use).
- assert(bytes > 0);
- if (bytes <= alloc_bytes_remaining_) {
- char* result = alloc_ptr_;
- alloc_ptr_ += bytes;
- alloc_bytes_remaining_ -= bytes;
- return result;
- }
- return AllocateFallback(bytes);
-}
-
-} // namespace leveldb
-
-#endif // STORAGE_LEVELDB_UTIL_ARENA_H_
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/arena_test.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/arena_test.cc b/thirdparty/leveldb-1.18/util/arena_test.cc
deleted file mode 100755
index 58e870e..0000000
--- a/thirdparty/leveldb-1.18/util/arena_test.cc
+++ /dev/null
@@ -1,68 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "util/arena.h"
-
-#include "util/random.h"
-#include "util/testharness.h"
-
-namespace leveldb {
-
-class ArenaTest { };
-
-TEST(ArenaTest, Empty) {
- Arena arena;
-}
-
-TEST(ArenaTest, Simple) {
- std::vector<std::pair<size_t, char*> > allocated;
- Arena arena;
- const int N = 100000;
- size_t bytes = 0;
- Random rnd(301);
- for (int i = 0; i < N; i++) {
- size_t s;
- if (i % (N / 10) == 0) {
- s = i;
- } else {
- s = rnd.OneIn(4000) ? rnd.Uniform(6000) :
- (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20));
- }
- if (s == 0) {
- // Our arena disallows size 0 allocations.
- s = 1;
- }
- char* r;
- if (rnd.OneIn(10)) {
- r = arena.AllocateAligned(s);
- } else {
- r = arena.Allocate(s);
- }
-
- for (size_t b = 0; b < s; b++) {
- // Fill the "i"th allocation with a known bit pattern
- r[b] = i % 256;
- }
- bytes += s;
- allocated.push_back(std::make_pair(s, r));
- ASSERT_GE(arena.MemoryUsage(), bytes);
- if (i > N/10) {
- ASSERT_LE(arena.MemoryUsage(), bytes * 1.10);
- }
- }
- for (size_t i = 0; i < allocated.size(); i++) {
- size_t num_bytes = allocated[i].first;
- const char* p = allocated[i].second;
- for (size_t b = 0; b < num_bytes; b++) {
- // Check the "i"th allocation for the known bit pattern
- ASSERT_EQ(int(p[b]) & 0xff, i % 256);
- }
- }
-}
-
-} // namespace leveldb
-
-int main(int argc, char** argv) {
- return leveldb::test::RunAllTests();
-}
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/bloom.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/bloom.cc b/thirdparty/leveldb-1.18/util/bloom.cc
deleted file mode 100755
index 27a2b08..0000000
--- a/thirdparty/leveldb-1.18/util/bloom.cc
+++ /dev/null
@@ -1,95 +0,0 @@
-// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "leveldb/filter_policy.h"
-
-#include "leveldb/slice.h"
-#include "util/hash.h"
-
-namespace leveldb {
-
-namespace {
-static uint32_t BloomHash(const Slice& key) {
- return Hash(reinterpret_cast<const unsigned char *>(key.data()), key.size(), 0xbc9f1d34);
-}
-
-class BloomFilterPolicy : public FilterPolicy {
- private:
- size_t bits_per_key_;
- size_t k_;
-
- public:
- explicit BloomFilterPolicy(int bits_per_key)
- : bits_per_key_(bits_per_key) {
- // We intentionally round down to reduce probing cost a little bit
- k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
- if (k_ < 1) k_ = 1;
- if (k_ > 30) k_ = 30;
- }
-
- virtual const char* Name() const {
- return "leveldb.BuiltinBloomFilter2";
- }
-
- virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
- // Compute bloom filter size (in both bits and bytes)
- size_t bits = n * bits_per_key_;
-
- // For small n, we can see a very high false positive rate. Fix it
- // by enforcing a minimum bloom filter length.
- if (bits < 64) bits = 64;
-
- size_t bytes = (bits + 7) / 8;
- bits = bytes * 8;
-
- const size_t init_size = dst->size();
- dst->resize(init_size + bytes, 0);
- dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
- char* array = &(*dst)[init_size];
- for (size_t i = 0; i < n; i++) {
- // Use double-hashing to generate a sequence of hash values.
- // See analysis in [Kirsch,Mitzenmacher 2006].
- uint32_t h = BloomHash(keys[i]);
- const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
- for (size_t j = 0; j < k_; j++) {
- const uint32_t bitpos = h % bits;
- array[bitpos/8] |= (1 << (bitpos % 8));
- h += delta;
- }
- }
- }
-
- virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
- const size_t len = bloom_filter.size();
- if (len < 2) return false;
-
- const char* array = bloom_filter.data();
- const size_t bits = (len - 1) * 8;
-
- // Use the encoded k so that we can read filters generated by
- // bloom filters created using different parameters.
- const size_t k = array[len-1];
- if (k > 30) {
- // Reserved for potentially new encodings for short bloom filters.
- // Consider it a match.
- return true;
- }
-
- uint32_t h = BloomHash(key);
- const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits
- for (size_t j = 0; j < k; j++) {
- const uint32_t bitpos = h % bits;
- if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
- h += delta;
- }
- return true;
- }
-};
-}
-
-const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) {
- return new BloomFilterPolicy(bits_per_key);
-}
-
-} // namespace leveldb
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/bloom_test.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/bloom_test.cc b/thirdparty/leveldb-1.18/util/bloom_test.cc
deleted file mode 100755
index bfb9306..0000000
--- a/thirdparty/leveldb-1.18/util/bloom_test.cc
+++ /dev/null
@@ -1,161 +0,0 @@
-// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "leveldb/filter_policy.h"
-
-#include "util/coding.h"
-#include "util/logging.h"
-#include "util/testharness.h"
-#include "util/testutil.h"
-
-namespace leveldb {
-
-static const int kVerbose = 1;
-
-static Slice Key(int i, char* buffer) {
- EncodeFixed32(buffer, i);
- return Slice(buffer, sizeof(uint32_t));
-}
-
-class BloomTest {
- private:
- const FilterPolicy* policy_;
- std::string filter_;
- std::vector<std::string> keys_;
-
- public:
- BloomTest() : policy_(NewBloomFilterPolicy(10)) { }
-
- ~BloomTest() {
- delete policy_;
- }
-
- void Reset() {
- keys_.clear();
- filter_.clear();
- }
-
- void Add(const Slice& s) {
- keys_.push_back(s.ToString());
- }
-
- void Build() {
- std::vector<Slice> key_slices;
- for (size_t i = 0; i < keys_.size(); i++) {
- key_slices.push_back(Slice(keys_[i]));
- }
- filter_.clear();
- policy_->CreateFilter(&key_slices[0], static_cast<int>(key_slices.size()), &filter_);
- keys_.clear();
- if (kVerbose >= 2) DumpFilter();
- }
-
- size_t FilterSize() const {
- return filter_.size();
- }
-
- void DumpFilter() {
- fprintf(stderr, "F(");
- for (size_t i = 0; i+1 < filter_.size(); i++) {
- const unsigned int c = static_cast<unsigned int>(filter_[i]);
- for (int j = 0; j < 8; j++) {
- fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.');
- }
- }
- fprintf(stderr, ")\n");
- }
-
- bool Matches(const Slice& s) {
- if (!keys_.empty()) {
- Build();
- }
- return policy_->KeyMayMatch(s, filter_);
- }
-
- double FalsePositiveRate() {
- char buffer[sizeof(int)];
- int result = 0;
- for (int i = 0; i < 10000; i++) {
- if (Matches(Key(i + 1000000000, buffer))) {
- result++;
- }
- }
- return result / 10000.0;
- }
-};
-
-TEST(BloomTest, EmptyFilter) {
- ASSERT_TRUE(! Matches("hello"));
- ASSERT_TRUE(! Matches("world"));
-}
-
-TEST(BloomTest, Small) {
- Add("hello");
- Add("world");
- ASSERT_TRUE(Matches("hello"));
- ASSERT_TRUE(Matches("world"));
- ASSERT_TRUE(! Matches("x"));
- ASSERT_TRUE(! Matches("foo"));
-}
-
-static int NextLength(int length) {
- if (length < 10) {
- length += 1;
- } else if (length < 100) {
- length += 10;
- } else if (length < 1000) {
- length += 100;
- } else {
- length += 1000;
- }
- return length;
-}
-
-TEST(BloomTest, VaryingLengths) {
- char buffer[sizeof(int)];
-
- // Count number of filters that significantly exceed the false positive rate
- int mediocre_filters = 0;
- int good_filters = 0;
-
- for (int length = 1; length <= 10000; length = NextLength(length)) {
- Reset();
- for (int i = 0; i < length; i++) {
- Add(Key(i, buffer));
- }
- Build();
-
- ASSERT_LE(FilterSize(), static_cast<size_t>((length * 10 / 8) + 40))
- << length;
-
- // All added keys must match
- for (int i = 0; i < length; i++) {
- ASSERT_TRUE(Matches(Key(i, buffer)))
- << "Length " << length << "; key " << i;
- }
-
- // Check false positive rate
- double rate = FalsePositiveRate();
- if (kVerbose >= 1) {
- fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
- rate*100.0, length, static_cast<int>(FilterSize()));
- }
- ASSERT_LE(rate, 0.02); // Must not be over 2%
- if (rate > 0.0125) mediocre_filters++; // Allowed, but not too often
- else good_filters++;
- }
- if (kVerbose >= 1) {
- fprintf(stderr, "Filters: %d good, %d mediocre\n",
- good_filters, mediocre_filters);
- }
- ASSERT_LE(mediocre_filters, good_filters/5);
-}
-
-// Different bits-per-byte
-
-} // namespace leveldb
-
-int main(int argc, char** argv) {
- return leveldb::test::RunAllTests();
-}
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/cache.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/cache.cc b/thirdparty/leveldb-1.18/util/cache.cc
deleted file mode 100755
index ff8d2fc..0000000
--- a/thirdparty/leveldb-1.18/util/cache.cc
+++ /dev/null
@@ -1,327 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#include "leveldb/cache.h"
-#include "port/port.h"
-#include "util/hash.h"
-#include "util/mutexlock.h"
-
-namespace leveldb {
-
-Cache::~Cache() {
-}
-
-namespace {
-
-// LRU cache implementation
-
-// An entry is a variable length heap-allocated structure. Entries
-// are kept in a circular doubly linked list ordered by access time.
-struct LRUHandle {
- void* value;
- void (*deleter)(const Slice&, void* value);
- LRUHandle* next_hash;
- LRUHandle* next;
- LRUHandle* prev;
- size_t charge; // TODO(opt): Only allow uint32_t?
- size_t key_length;
- uint32_t refs;
- uint32_t hash; // Hash of key(); used for fast sharding and comparisons
- char key_data[1]; // Beginning of key
-
- Slice key() const {
- // For cheaper lookups, we allow a temporary Handle object
- // to store a pointer to a key in "value".
- if (next == this) {
- return *(reinterpret_cast<Slice*>(value));
- } else {
- return Slice(key_data, key_length);
- }
- }
-};
-
-// We provide our own simple hash table since it removes a whole bunch
-// of porting hacks and is also faster than some of the built-in hash
-// table implementations in some of the compiler/runtime combinations
-// we have tested. E.g., readrandom speeds up by ~5% over the g++
-// 4.4.3's builtin hashtable.
-class HandleTable {
- public:
- HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); }
- ~HandleTable() { delete[] list_; }
-
- LRUHandle* Lookup(const Slice& key, uint32_t hash) {
- return *FindPointer(key, hash);
- }
-
- LRUHandle* Insert(LRUHandle* h) {
- LRUHandle** ptr = FindPointer(h->key(), h->hash);
- LRUHandle* old = *ptr;
- h->next_hash = (old == NULL ? NULL : old->next_hash);
- *ptr = h;
- if (old == NULL) {
- ++elems_;
- if (elems_ > length_) {
- // Since each cache entry is fairly large, we aim for a small
- // average linked list length (<= 1).
- Resize();
- }
- }
- return old;
- }
-
- LRUHandle* Remove(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = FindPointer(key, hash);
- LRUHandle* result = *ptr;
- if (result != NULL) {
- *ptr = result->next_hash;
- --elems_;
- }
- return result;
- }
-
- private:
- // The table consists of an array of buckets where each bucket is
- // a linked list of cache entries that hash into the bucket.
- uint32_t length_;
- uint32_t elems_;
- LRUHandle** list_;
-
- // Return a pointer to slot that points to a cache entry that
- // matches key/hash. If there is no such cache entry, return a
- // pointer to the trailing slot in the corresponding linked list.
- LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = &list_[hash & (length_ - 1)];
- while (*ptr != NULL &&
- ((*ptr)->hash != hash || key != (*ptr)->key())) {
- ptr = &(*ptr)->next_hash;
- }
- return ptr;
- }
-
- void Resize() {
- uint32_t new_length = 4;
- while (new_length < elems_) {
- new_length *= 2;
- }
- LRUHandle** new_list = new LRUHandle*[new_length];
- memset(new_list, 0, sizeof(new_list[0]) * new_length);
- uint32_t count = 0;
- for (uint32_t i = 0; i < length_; i++) {
- LRUHandle* h = list_[i];
- while (h != NULL) {
- LRUHandle* next = h->next_hash;
- uint32_t hash = h->hash;
- LRUHandle** ptr = &new_list[hash & (new_length - 1)];
- h->next_hash = *ptr;
- *ptr = h;
- h = next;
- count++;
- }
- }
- assert(elems_ == count);
- delete[] list_;
- list_ = new_list;
- length_ = new_length;
- }
-};
-
-// A single shard of sharded cache.
-class LRUCache {
- public:
- LRUCache();
- ~LRUCache();
-
- // Separate from constructor so caller can easily make an array of LRUCache
- void SetCapacity(size_t capacity) { capacity_ = capacity; }
-
- // Like Cache methods, but with an extra "hash" parameter.
- Cache::Handle* Insert(const Slice& key, uint32_t hash,
- void* value, size_t charge,
- void (*deleter)(const Slice& key, void* value));
- Cache::Handle* Lookup(const Slice& key, uint32_t hash);
- void Release(Cache::Handle* handle);
- void Erase(const Slice& key, uint32_t hash);
-
- private:
- void LRU_Remove(LRUHandle* e);
- void LRU_Append(LRUHandle* e);
- void Unref(LRUHandle* e);
-
- // Initialized before use.
- size_t capacity_;
-
- // mutex_ protects the following state.
- port::Mutex mutex_;
- size_t usage_;
-
- // Dummy head of LRU list.
- // lru.prev is newest entry, lru.next is oldest entry.
- LRUHandle lru_;
-
- HandleTable table_;
-};
-
-LRUCache::LRUCache()
- : usage_(0) {
- // Make empty circular linked list
- lru_.next = &lru_;
- lru_.prev = &lru_;
-}
-
-LRUCache::~LRUCache() {
- for (LRUHandle* e = lru_.next; e != &lru_; ) {
- LRUHandle* next = e->next;
- assert(e->refs == 1); // Error if caller has an unreleased handle
- Unref(e);
- e = next;
- }
-}
-
-void LRUCache::Unref(LRUHandle* e) {
- assert(e->refs > 0);
- e->refs--;
- if (e->refs <= 0) {
- usage_ -= e->charge;
- (*e->deleter)(e->key(), e->value);
- free(e);
- }
-}
-
-void LRUCache::LRU_Remove(LRUHandle* e) {
- e->next->prev = e->prev;
- e->prev->next = e->next;
-}
-
-void LRUCache::LRU_Append(LRUHandle* e) {
- // Make "e" newest entry by inserting just before lru_
- e->next = &lru_;
- e->prev = lru_.prev;
- e->prev->next = e;
- e->next->prev = e;
-}
-
-Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
- MutexLock l(&mutex_);
- LRUHandle* e = table_.Lookup(key, hash);
- if (e != NULL) {
- e->refs++;
- LRU_Remove(e);
- LRU_Append(e);
- }
- return reinterpret_cast<Cache::Handle*>(e);
-}
-
-void LRUCache::Release(Cache::Handle* handle) {
- MutexLock l(&mutex_);
- Unref(reinterpret_cast<LRUHandle*>(handle));
-}
-
-Cache::Handle* LRUCache::Insert(
- const Slice& key, uint32_t hash, void* value, size_t charge,
- void (*deleter)(const Slice& key, void* value)) {
- MutexLock l(&mutex_);
-
- LRUHandle* e = reinterpret_cast<LRUHandle*>(
- malloc(sizeof(LRUHandle)-1 + key.size()));
- e->value = value;
- e->deleter = deleter;
- e->charge = charge;
- e->key_length = key.size();
- e->hash = hash;
- e->refs = 2; // One from LRUCache, one for the returned handle
- memcpy(e->key_data, key.data(), key.size());
- LRU_Append(e);
- usage_ += charge;
-
- {
- LRUHandle* old = table_.Insert(e);
- if (old != NULL) {
- LRU_Remove(old);
- Unref(old);
- }
- }
-
- while (usage_ > capacity_ && lru_.next != &lru_) {
- LRUHandle* old = lru_.next;
- LRU_Remove(old);
- table_.Remove(old->key(), old->hash);
- Unref(old);
- }
-
- return reinterpret_cast<Cache::Handle*>(e);
-}
-
-void LRUCache::Erase(const Slice& key, uint32_t hash) {
- MutexLock l(&mutex_);
- LRUHandle* e = table_.Remove(key, hash);
- if (e != NULL) {
- LRU_Remove(e);
- Unref(e);
- }
-}
-
-static const int kNumShardBits = 4;
-static const int kNumShards = 1 << kNumShardBits;
-
-class ShardedLRUCache : public Cache {
- private:
- LRUCache shard_[kNumShards];
- port::Mutex id_mutex_;
- uint64_t last_id_;
-
- static inline uint32_t HashSlice(const Slice& s) {
- return Hash(reinterpret_cast<const unsigned char *>(s.data()), s.size(), 0);
- }
-
- static uint32_t Shard(uint32_t hash) {
- return hash >> (32 - kNumShardBits);
- }
-
- public:
- explicit ShardedLRUCache(size_t capacity)
- : last_id_(0) {
- const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
- for (int s = 0; s < kNumShards; s++) {
- shard_[s].SetCapacity(per_shard);
- }
- }
- virtual ~ShardedLRUCache() { }
- virtual Handle* Insert(const Slice& key, void* value, size_t charge,
- void (*deleter)(const Slice& key, void* value)) {
- const uint32_t hash = HashSlice(key);
- return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
- }
- virtual Handle* Lookup(const Slice& key) {
- const uint32_t hash = HashSlice(key);
- return shard_[Shard(hash)].Lookup(key, hash);
- }
- virtual void Release(Handle* handle) {
- LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
- shard_[Shard(h->hash)].Release(handle);
- }
- virtual void Erase(const Slice& key) {
- const uint32_t hash = HashSlice(key);
- shard_[Shard(hash)].Erase(key, hash);
- }
- virtual void* Value(Handle* handle) {
- return reinterpret_cast<LRUHandle*>(handle)->value;
- }
- virtual uint64_t NewId() {
- MutexLock l(&id_mutex_);
- return ++(last_id_);
- }
-};
-
-} // end anonymous namespace
-
-Cache* NewLRUCache(size_t capacity) {
- return new ShardedLRUCache(capacity);
-}
-
-} // namespace leveldb
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/cache_test.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/cache_test.cc b/thirdparty/leveldb-1.18/util/cache_test.cc
deleted file mode 100755
index d9b9057..0000000
--- a/thirdparty/leveldb-1.18/util/cache_test.cc
+++ /dev/null
@@ -1,186 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "leveldb/cache.h"
-
-#include <vector>
-#include "util/coding.h"
-#include "util/testharness.h"
-
-namespace leveldb {
-
-// Conversions between numeric keys/values and the types expected by Cache.
-static std::string EncodeKey(intptr_t k) {
- std::string result;
- PutFixed32(&result, static_cast<uint32_t>(k));
- return result;
-}
-static int DecodeKey(const Slice& k) {
- assert(k.size() == 4);
- return DecodeFixed32(k.data());
-}
-static void* EncodeValue(intptr_t v) { return reinterpret_cast<void*>(v); }
-static intptr_t DecodeValue(void* v) { return reinterpret_cast<intptr_t>(v); }
-
-class CacheTest {
- public:
- static CacheTest* current_;
-
- static void Deleter(const Slice& key, void* v) {
- current_->deleted_keys_.push_back(DecodeKey(key));
- current_->deleted_values_.push_back(DecodeValue(v));
- }
-
- static const int kCacheSize = 1000;
- std::vector<intptr_t> deleted_keys_;
- std::vector<intptr_t> deleted_values_;
- Cache* cache_;
-
- CacheTest() : cache_(NewLRUCache(kCacheSize)) {
- current_ = this;
- }
-
- ~CacheTest() {
- delete cache_;
- }
-
- intptr_t Lookup(int key) {
- Cache::Handle* handle = cache_->Lookup(EncodeKey(key));
- const intptr_t r = (handle == NULL) ? -1 : DecodeValue(cache_->Value(handle));
- if (handle != NULL) {
- cache_->Release(handle);
- }
- return r;
- }
-
- void Insert(int key, int value, int charge = 1) {
- cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge,
- &CacheTest::Deleter));
- }
-
- void Erase(int key) {
- cache_->Erase(EncodeKey(key));
- }
-};
-CacheTest* CacheTest::current_;
-
-TEST(CacheTest, HitAndMiss) {
- ASSERT_EQ(-1, Lookup(100));
-
- Insert(100, 101);
- ASSERT_EQ(101, Lookup(100));
- ASSERT_EQ(-1, Lookup(200));
- ASSERT_EQ(-1, Lookup(300));
-
- Insert(200, 201);
- ASSERT_EQ(101, Lookup(100));
- ASSERT_EQ(201, Lookup(200));
- ASSERT_EQ(-1, Lookup(300));
-
- Insert(100, 102);
- ASSERT_EQ(102, Lookup(100));
- ASSERT_EQ(201, Lookup(200));
- ASSERT_EQ(-1, Lookup(300));
-
- ASSERT_EQ(1, deleted_keys_.size());
- ASSERT_EQ(100, deleted_keys_[0]);
- ASSERT_EQ(101, deleted_values_[0]);
-}
-
-TEST(CacheTest, Erase) {
- Erase(200);
- ASSERT_EQ(0, deleted_keys_.size());
-
- Insert(100, 101);
- Insert(200, 201);
- Erase(100);
- ASSERT_EQ(-1, Lookup(100));
- ASSERT_EQ(201, Lookup(200));
- ASSERT_EQ(1, deleted_keys_.size());
- ASSERT_EQ(100, deleted_keys_[0]);
- ASSERT_EQ(101, deleted_values_[0]);
-
- Erase(100);
- ASSERT_EQ(-1, Lookup(100));
- ASSERT_EQ(201, Lookup(200));
- ASSERT_EQ(1, deleted_keys_.size());
-}
-
-TEST(CacheTest, EntriesArePinned) {
- Insert(100, 101);
- Cache::Handle* h1 = cache_->Lookup(EncodeKey(100));
- ASSERT_EQ(101, DecodeValue(cache_->Value(h1)));
-
- Insert(100, 102);
- Cache::Handle* h2 = cache_->Lookup(EncodeKey(100));
- ASSERT_EQ(102, DecodeValue(cache_->Value(h2)));
- ASSERT_EQ(0, deleted_keys_.size());
-
- cache_->Release(h1);
- ASSERT_EQ(1, deleted_keys_.size());
- ASSERT_EQ(100, deleted_keys_[0]);
- ASSERT_EQ(101, deleted_values_[0]);
-
- Erase(100);
- ASSERT_EQ(-1, Lookup(100));
- ASSERT_EQ(1, deleted_keys_.size());
-
- cache_->Release(h2);
- ASSERT_EQ(2, deleted_keys_.size());
- ASSERT_EQ(100, deleted_keys_[1]);
- ASSERT_EQ(102, deleted_values_[1]);
-}
-
-TEST(CacheTest, EvictionPolicy) {
- Insert(100, 101);
- Insert(200, 201);
-
- // Frequently used entry must be kept around
- for (int i = 0; i < kCacheSize + 100; i++) {
- Insert(1000+i, 2000+i);
- ASSERT_EQ(2000+i, Lookup(1000+i));
- ASSERT_EQ(101, Lookup(100));
- }
- ASSERT_EQ(101, Lookup(100));
- ASSERT_EQ(-1, Lookup(200));
-}
-
-TEST(CacheTest, HeavyEntries) {
- // Add a bunch of light and heavy entries and then count the combined
- // size of items still in the cache, which must be approximately the
- // same as the total capacity.
- const int kLight = 1;
- const int kHeavy = 10;
- int added = 0;
- int index = 0;
- while (added < 2*kCacheSize) {
- const int weight = (index & 1) ? kLight : kHeavy;
- Insert(index, 1000+index, weight);
- added += weight;
- index++;
- }
-
- intptr_t cached_weight = 0;
- for (int i = 0; i < index; i++) {
- const intptr_t weight = (i & 1 ? kLight : kHeavy);
- intptr_t r = Lookup(i);
- if (r >= 0) {
- cached_weight += weight;
- ASSERT_EQ(1000+i, r);
- }
- }
- ASSERT_LE(cached_weight, kCacheSize + kCacheSize/10);
-}
-
-TEST(CacheTest, NewId) {
- uint64_t a = cache_->NewId();
- uint64_t b = cache_->NewId();
- ASSERT_NE(a, b);
-}
-
-} // namespace leveldb
-
-int main(int argc, char** argv) {
- return leveldb::test::RunAllTests();
-}
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/coding.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/coding.cc b/thirdparty/leveldb-1.18/util/coding.cc
deleted file mode 100755
index dfa826a..0000000
--- a/thirdparty/leveldb-1.18/util/coding.cc
+++ /dev/null
@@ -1,194 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "util/coding.h"
-
-namespace leveldb {
-
-void EncodeFixed32(char* buf, uint32_t value) {
- if (port::kLittleEndian) {
- memcpy(buf, &value, sizeof(value));
- } else {
- buf[0] = value & 0xff;
- buf[1] = (value >> 8) & 0xff;
- buf[2] = (value >> 16) & 0xff;
- buf[3] = (value >> 24) & 0xff;
- }
-}
-
-void EncodeFixed64(char* buf, uint64_t value) {
- if (port::kLittleEndian) {
- memcpy(buf, &value, sizeof(value));
- } else {
- buf[0] = value & 0xff;
- buf[1] = (value >> 8) & 0xff;
- buf[2] = (value >> 16) & 0xff;
- buf[3] = (value >> 24) & 0xff;
- buf[4] = (value >> 32) & 0xff;
- buf[5] = (value >> 40) & 0xff;
- buf[6] = (value >> 48) & 0xff;
- buf[7] = (value >> 56) & 0xff;
- }
-}
-
-void PutFixed32(std::string* dst, uint32_t value) {
- char buf[sizeof(value)];
- EncodeFixed32(buf, value);
- dst->append(buf, sizeof(buf));
-}
-
-void PutFixed64(std::string* dst, uint64_t value) {
- char buf[sizeof(value)];
- EncodeFixed64(buf, value);
- dst->append(buf, sizeof(buf));
-}
-
-char* EncodeVarint32(char* dst, uint32_t v) {
- // Operate on characters as unsigneds
- unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
- static const int B = 128;
- if (v < (1<<7)) {
- *(ptr++) = v;
- } else if (v < (1<<14)) {
- *(ptr++) = v | B;
- *(ptr++) = v>>7;
- } else if (v < (1<<21)) {
- *(ptr++) = v | B;
- *(ptr++) = (v>>7) | B;
- *(ptr++) = v>>14;
- } else if (v < (1<<28)) {
- *(ptr++) = v | B;
- *(ptr++) = (v>>7) | B;
- *(ptr++) = (v>>14) | B;
- *(ptr++) = v>>21;
- } else {
- *(ptr++) = v | B;
- *(ptr++) = (v>>7) | B;
- *(ptr++) = (v>>14) | B;
- *(ptr++) = (v>>21) | B;
- *(ptr++) = v>>28;
- }
- return reinterpret_cast<char*>(ptr);
-}
-
-void PutVarint32(std::string* dst, uint32_t v) {
- char buf[5];
- char* ptr = EncodeVarint32(buf, v);
- dst->append(buf, ptr - buf);
-}
-
-char* EncodeVarint64(char* dst, uint64_t v) {
- static const int B = 128;
- unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
- while (v >= B) {
- *(ptr++) = (v & (B-1)) | B;
- v >>= 7;
- }
- *(ptr++) = static_cast<unsigned char>(v);
- return reinterpret_cast<char*>(ptr);
-}
-
-void PutVarint64(std::string* dst, uint64_t v) {
- char buf[10];
- char* ptr = EncodeVarint64(buf, v);
- dst->append(buf, ptr - buf);
-}
-
-void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {
- PutVarint32(dst, static_cast<uint32_t>(value.size()));
- dst->append(value.data(), value.size());
-}
-
-int VarintLength(uint64_t v) {
- int len = 1;
- while (v >= 128) {
- v >>= 7;
- len++;
- }
- return len;
-}
-
-const char* GetVarint32PtrFallback(const char* p,
- const char* limit,
- uint32_t* value) {
- uint32_t result = 0;
- for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
- uint32_t byte = *(reinterpret_cast<const unsigned char*>(p));
- p++;
- if (byte & 128) {
- // More bytes are present
- result |= ((byte & 127) << shift);
- } else {
- result |= (byte << shift);
- *value = result;
- return reinterpret_cast<const char*>(p);
- }
- }
- return NULL;
-}
-
-bool GetVarint32(Slice* input, uint32_t* value) {
- const char* p = input->data();
- const char* limit = p + input->size();
- const char* q = GetVarint32Ptr(p, limit, value);
- if (q == NULL) {
- return false;
- } else {
- *input = Slice(q, limit - q);
- return true;
- }
-}
-
-const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
- uint64_t result = 0;
- for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
- uint64_t byte = *(reinterpret_cast<const unsigned char*>(p));
- p++;
- if (byte & 128) {
- // More bytes are present
- result |= ((byte & 127) << shift);
- } else {
- result |= (byte << shift);
- *value = result;
- return reinterpret_cast<const char*>(p);
- }
- }
- return NULL;
-}
-
-bool GetVarint64(Slice* input, uint64_t* value) {
- const char* p = input->data();
- const char* limit = p + input->size();
- const char* q = GetVarint64Ptr(p, limit, value);
- if (q == NULL) {
- return false;
- } else {
- *input = Slice(q, limit - q);
- return true;
- }
-}
-
-const char* GetLengthPrefixedSlice(const char* p, const char* limit,
- Slice* result) {
- uint32_t len;
- p = GetVarint32Ptr(p, limit, &len);
- if (p == NULL) return NULL;
- if (p + len > limit) return NULL;
- *result = Slice(p, len);
- return p + len;
-}
-
-bool GetLengthPrefixedSlice(Slice* input, Slice* result) {
- uint32_t len;
- if (GetVarint32(input, &len) &&
- input->size() >= len) {
- *result = Slice(input->data(), len);
- input->remove_prefix(len);
- return true;
- } else {
- return false;
- }
-}
-
-} // namespace leveldb
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/coding.h
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/coding.h b/thirdparty/leveldb-1.18/util/coding.h
deleted file mode 100755
index 3da94df..0000000
--- a/thirdparty/leveldb-1.18/util/coding.h
+++ /dev/null
@@ -1,107 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-//
-// Endian-neutral encoding:
-// * Fixed-length numbers are encoded with least-significant byte first
-// * In addition we support variable length "varint" encoding
-// * Strings are encoded prefixed by their length in varint format
-
-#ifndef STORAGE_LEVELDB_UTIL_CODING_H_
-#define STORAGE_LEVELDB_UTIL_CODING_H_
-
-#include <stdint.h>
-#include <string.h>
-#include <string>
-#include "leveldb/slice.h"
-#include "port/port.h"
-
-namespace leveldb {
-
-// Standard Put... routines append to a string
-extern void PutFixed32(std::string* dst, uint32_t value);
-extern void PutFixed64(std::string* dst, uint64_t value);
-extern void PutVarint32(std::string* dst, uint32_t value);
-extern void PutVarint64(std::string* dst, uint64_t value);
-extern void PutLengthPrefixedSlice(std::string* dst, const Slice& value);
-
-// Standard Get... routines parse a value from the beginning of a Slice
-// and advance the slice past the parsed value.
-extern bool GetVarint32(Slice* input, uint32_t* value);
-extern bool GetVarint64(Slice* input, uint64_t* value);
-extern bool GetLengthPrefixedSlice(Slice* input, Slice* result);
-
-// Pointer-based variants of GetVarint... These either store a value
-// in *v and return a pointer just past the parsed value, or return
-// NULL on error. These routines only look at bytes in the range
-// [p..limit-1]
-extern const char* GetVarint32Ptr(const char* p,const char* limit, uint32_t* v);
-extern const char* GetVarint64Ptr(const char* p,const char* limit, uint64_t* v);
-
-// Returns the length of the varint32 or varint64 encoding of "v"
-extern int VarintLength(uint64_t v);
-
-// Lower-level versions of Put... that write directly into a character buffer
-// REQUIRES: dst has enough space for the value being written
-extern void EncodeFixed32(char* dst, uint32_t value);
-extern void EncodeFixed64(char* dst, uint64_t value);
-
-// Lower-level versions of Put... that write directly into a character buffer
-// and return a pointer just past the last byte written.
-// REQUIRES: dst has enough space for the value being written
-extern char* EncodeVarint32(char* dst, uint32_t value);
-extern char* EncodeVarint64(char* dst, uint64_t value);
-
-// Lower-level versions of Get... that read directly from a character buffer
-// without any bounds checking.
-
-inline uint32_t DecodeFixed32(const void* ptr) {
- if (port::kLittleEndian) {
- // Load the raw bytes
- uint32_t result;
- memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load
- return result;
- } else {
- const unsigned char * const p = static_cast<const unsigned char *>(ptr);
-
- return ((static_cast<uint32_t>(p[0]))
- | (static_cast<uint32_t>(p[1]) << 8)
- | (static_cast<uint32_t>(p[2]) << 16)
- | (static_cast<uint32_t>(p[3]) << 24));
- }
-}
-
-inline uint64_t DecodeFixed64(const void* ptr) {
- if (port::kLittleEndian) {
- // Load the raw bytes
- uint64_t result;
- memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load
- return result;
- } else {
- const unsigned char * const p = static_cast<const unsigned char *>(ptr);
- uint64_t lo = DecodeFixed32(p);
- uint64_t hi = DecodeFixed32(p + 4);
- return (hi << 32) | lo;
- }
-}
-
-// Internal routine for use by fallback path of GetVarint32Ptr
-extern const char* GetVarint32PtrFallback(const char* p,
- const char* limit,
- uint32_t* value);
-inline const char* GetVarint32Ptr(const char* p,
- const char* limit,
- uint32_t* value) {
- if (p < limit) {
- uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
- if ((result & 128) == 0) {
- *value = result;
- return p + 1;
- }
- }
- return GetVarint32PtrFallback(p, limit, value);
-}
-
-} // namespace leveldb
-
-#endif // STORAGE_LEVELDB_UTIL_CODING_H_
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/coding_test.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/coding_test.cc b/thirdparty/leveldb-1.18/util/coding_test.cc
deleted file mode 100755
index 521541e..0000000
--- a/thirdparty/leveldb-1.18/util/coding_test.cc
+++ /dev/null
@@ -1,196 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include "util/coding.h"
-
-#include "util/testharness.h"
-
-namespace leveldb {
-
-class Coding { };
-
-TEST(Coding, Fixed32) {
- std::string s;
- for (uint32_t v = 0; v < 100000; v++) {
- PutFixed32(&s, v);
- }
-
- const char* p = s.data();
- for (uint32_t v = 0; v < 100000; v++) {
- uint32_t actual = DecodeFixed32(p);
- ASSERT_EQ(v, actual);
- p += sizeof(uint32_t);
- }
-}
-
-TEST(Coding, Fixed64) {
- std::string s;
- for (int power = 0; power <= 63; power++) {
- uint64_t v = static_cast<uint64_t>(1) << power;
- PutFixed64(&s, v - 1);
- PutFixed64(&s, v + 0);
- PutFixed64(&s, v + 1);
- }
-
- const char* p = s.data();
- for (int power = 0; power <= 63; power++) {
- uint64_t v = static_cast<uint64_t>(1) << power;
- uint64_t actual;
- actual = DecodeFixed64(p);
- ASSERT_EQ(v-1, actual);
- p += sizeof(uint64_t);
-
- actual = DecodeFixed64(p);
- ASSERT_EQ(v+0, actual);
- p += sizeof(uint64_t);
-
- actual = DecodeFixed64(p);
- ASSERT_EQ(v+1, actual);
- p += sizeof(uint64_t);
- }
-}
-
-// Test that encoding routines generate little-endian encodings
-TEST(Coding, EncodingOutput) {
- std::string dst;
- PutFixed32(&dst, 0x04030201);
- ASSERT_EQ(4, dst.size());
- ASSERT_EQ(0x01, static_cast<int>(dst[0]));
- ASSERT_EQ(0x02, static_cast<int>(dst[1]));
- ASSERT_EQ(0x03, static_cast<int>(dst[2]));
- ASSERT_EQ(0x04, static_cast<int>(dst[3]));
-
- dst.clear();
- PutFixed64(&dst, 0x0807060504030201ull);
- ASSERT_EQ(8, dst.size());
- ASSERT_EQ(0x01, static_cast<int>(dst[0]));
- ASSERT_EQ(0x02, static_cast<int>(dst[1]));
- ASSERT_EQ(0x03, static_cast<int>(dst[2]));
- ASSERT_EQ(0x04, static_cast<int>(dst[3]));
- ASSERT_EQ(0x05, static_cast<int>(dst[4]));
- ASSERT_EQ(0x06, static_cast<int>(dst[5]));
- ASSERT_EQ(0x07, static_cast<int>(dst[6]));
- ASSERT_EQ(0x08, static_cast<int>(dst[7]));
-}
-
-TEST(Coding, Varint32) {
- std::string s;
- for (uint32_t i = 0; i < (32 * 32); i++) {
- uint32_t v = (i / 32) << (i % 32);
- PutVarint32(&s, v);
- }
-
- const char* p = s.data();
- const char* limit = p + s.size();
- for (uint32_t i = 0; i < (32 * 32); i++) {
- uint32_t expected = (i / 32) << (i % 32);
- uint32_t actual;
- const char* start = p;
- p = GetVarint32Ptr(p, limit, &actual);
- ASSERT_TRUE(p != NULL);
- ASSERT_EQ(expected, actual);
- ASSERT_EQ(VarintLength(actual), p - start);
- }
- ASSERT_EQ(p, s.data() + s.size());
-}
-
-TEST(Coding, Varint64) {
- // Construct the list of values to check
- std::vector<uint64_t> values;
- // Some special values
- values.push_back(0);
- values.push_back(100);
- values.push_back(~static_cast<uint64_t>(0));
- values.push_back(~static_cast<uint64_t>(0) - 1);
- for (uint32_t k = 0; k < 64; k++) {
- // Test values near powers of two
- const uint64_t power = 1ull << k;
- values.push_back(power);
- values.push_back(power-1);
- values.push_back(power+1);
- }
-
- std::string s;
- for (size_t i = 0; i < values.size(); i++) {
- PutVarint64(&s, values[i]);
- }
-
- const char* p = s.data();
- const char* limit = p + s.size();
- for (size_t i = 0; i < values.size(); i++) {
- ASSERT_TRUE(p < limit);
- uint64_t actual;
- const char* start = p;
- p = GetVarint64Ptr(p, limit, &actual);
- ASSERT_TRUE(p != NULL);
- ASSERT_EQ(values[i], actual);
- ASSERT_EQ(VarintLength(actual), p - start);
- }
- ASSERT_EQ(p, limit);
-
-}
-
-TEST(Coding, Varint32Overflow) {
- uint32_t result;
- std::string input("\x81\x82\x83\x84\x85\x11");
- ASSERT_TRUE(GetVarint32Ptr(input.data(), input.data() + input.size(), &result)
- == NULL);
-}
-
-TEST(Coding, Varint32Truncation) {
- uint32_t large_value = (1u << 31) + 100;
- std::string s;
- PutVarint32(&s, large_value);
- uint32_t result;
- for (size_t len = 0; len < s.size() - 1; len++) {
- ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + len, &result) == NULL);
- }
- ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + s.size(), &result) != NULL);
- ASSERT_EQ(large_value, result);
-}
-
-TEST(Coding, Varint64Overflow) {
- uint64_t result;
- std::string input("\x81\x82\x83\x84\x85\x81\x82\x83\x84\x85\x11");
- ASSERT_TRUE(GetVarint64Ptr(input.data(), input.data() + input.size(), &result)
- == NULL);
-}
-
-TEST(Coding, Varint64Truncation) {
- uint64_t large_value = (1ull << 63) + 100ull;
- std::string s;
- PutVarint64(&s, large_value);
- uint64_t result;
- for (size_t len = 0; len < s.size() - 1; len++) {
- ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + len, &result) == NULL);
- }
- ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + s.size(), &result) != NULL);
- ASSERT_EQ(large_value, result);
-}
-
-TEST(Coding, Strings) {
- std::string s;
- PutLengthPrefixedSlice(&s, Slice(""));
- PutLengthPrefixedSlice(&s, Slice("foo"));
- PutLengthPrefixedSlice(&s, Slice("bar"));
- PutLengthPrefixedSlice(&s, Slice(std::string(200, 'x')));
-
- Slice input(s);
- Slice v;
- ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
- ASSERT_EQ("", v.ToString());
- ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
- ASSERT_EQ("foo", v.ToString());
- ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
- ASSERT_EQ("bar", v.ToString());
- ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
- ASSERT_EQ(std::string(200, 'x'), v.ToString());
- ASSERT_EQ("", input.ToString());
-}
-
-} // namespace leveldb
-
-int main(int argc, char** argv) {
- return leveldb::test::RunAllTests();
-}
http://git-wip-us.apache.org/repos/asf/nifi-minifi-cpp/blob/48867732/thirdparty/leveldb-1.18/util/comparator.cc
----------------------------------------------------------------------
diff --git a/thirdparty/leveldb-1.18/util/comparator.cc b/thirdparty/leveldb-1.18/util/comparator.cc
deleted file mode 100755
index 5397929..0000000
--- a/thirdparty/leveldb-1.18/util/comparator.cc
+++ /dev/null
@@ -1,88 +0,0 @@
-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file. See the AUTHORS file for names of contributors.
-
-#include <algorithm>
-#include <stdint.h>
-#include "leveldb/comparator.h"
-#include "leveldb/slice.h"
-#include "port/port.h"
-#include "util/logging.h"
-
-namespace leveldb {
-
-Comparator::~Comparator() { }
-
-namespace {
-class BytewiseComparatorImpl : public Comparator {
- public:
- BytewiseComparatorImpl() { }
-
- virtual const char* Name() const {
- return "leveldb.BytewiseComparator";
- }
-
- virtual int Compare(const Slice& a, const Slice& b) const {
- return a.compare(b);
- }
-
- virtual void FindShortestSeparator(
- std::string* start,
- const Slice& limit) const {
- // Find length of common prefix
- size_t min_length = std::min(start->size(), limit.size());
- size_t diff_index = 0;
- while ((diff_index < min_length) &&
- ((*start)[diff_index] == limit[diff_index])) {
- diff_index++;
- }
-
- if (diff_index >= min_length) {
- // Do not shorten if one string is a prefix of the other
- } else {
- uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
- if (diff_byte < static_cast<uint8_t>(0xff) &&
- diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
- (*start)[diff_index]++;
- start->resize(diff_index + 1);
- assert(Compare(*start, limit) < 0);
- }
- }
- }
-
- virtual void FindShortSuccessor(std::string* key) const {
- // Find first character that can be incremented
- size_t n = key->size();
- for (size_t i = 0; i < n; i++) {
- const uint8_t byte = (*key)[i];
- if (byte != static_cast<uint8_t>(0xff)) {
- (*key)[i] = byte + 1;
- key->resize(i+1);
- return;
- }
- }
- // *key is a run of 0xffs. Leave it alone.
- }
-};
-} // namespace
-
-static port::OnceType once = LEVELDB_ONCE_INIT;
-static const Comparator* bytewise;
-
-static void InitModule() {
- bytewise = new BytewiseComparatorImpl;
-}
-
-const Comparator* BytewiseComparator() {
- port::InitOnce(&once, InitModule);
- return bytewise;
-}
-
-void UnsafeDeallocateBytewiseComparator()
-{
- once = LEVELDB_ONCE_INIT;
- delete bytewise;
- bytewise = nullptr;
-}
-
-} // namespace leveldb