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 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/dbformat.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/logging.h" 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/testharness.h" 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic std::string IKey(const std::string& user_key, 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t seq, 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ValueType vt) { 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string encoded; 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt)); 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return encoded; 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic std::string Shorten(const std::string& s, const std::string& l) { 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string result = s; 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKeyComparator(BytewiseComparator()).FindShortestSeparator(&result, l); 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic std::string ShortSuccessor(const std::string& s) { 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string result = s; 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result); 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void TestKey(const std::string& key, 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t seq, 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ValueType vt) { 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string encoded = IKey(key, seq, vt); 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice in(encoded); 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ParsedInternalKey decoded("", 0, kTypeValue); 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(ParseInternalKey(in, &decoded)); 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(key, decoded.user_key.ToString()); 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(seq, decoded.sequence); 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(vt, decoded.type); 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded)); 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass FormatTest { }; 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(FormatTest, InternalKey_EncodeDecode) { 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const char* keys[] = { "", "k", "hello", "longggggggggggggggggggggg" }; 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const uint64_t seq[] = { 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1, 2, 3, 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (1ull << 8) - 1, 1ull << 8, (1ull << 8) + 1, 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (1ull << 16) - 1, 1ull << 16, (1ull << 16) + 1, 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (1ull << 32) - 1, 1ull << 32, (1ull << 32) + 1 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org }; 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) { 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) { 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestKey(keys[k], seq[s], kTypeValue); 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TestKey("hello", 1, kTypeDeletion); 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(FormatTest, InternalKeyShortSeparator) { 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When user keys are same 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foo", 99, kTypeValue))); 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foo", 101, kTypeValue))); 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foo", 100, kTypeValue))); 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foo", 100, kTypeDeletion))); 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When user keys are misordered 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("bar", 99, kTypeValue))); 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When user keys are different, but correctly ordered 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek), 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("hello", 200, kTypeValue))); 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When start user key is prefix of limit user key 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foo", 100, kTypeValue), 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foo", 100, kTypeValue), 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foobar", 200, kTypeValue))); 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When limit user key is prefix of start user key 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("foobar", 100, kTypeValue), 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Shorten(IKey("foobar", 100, kTypeValue), 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org IKey("foo", 200, kTypeValue))); 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTEST(FormatTest, InternalKeyShortestSuccessor) { 102179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek), 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ShortSuccessor(IKey("foo", 100, kTypeValue))); 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue), 105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ShortSuccessor(IKey("\xff\xff", 100, kTypeValue))); 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 10845b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 109179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint main(int argc, char** argv) { 111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return leveldb::test::RunAllTests(); 112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 113