// 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 "db/dbformat.h"

#include <stdio.h>

#include <sstream>

#include "port/port.h"

#include "util/coding.h"

namespace leveldb {

static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {

  assert(seq <= kMaxSequenceNumber);

  Branch (17:3): [True: 2.02M, False: 42.4k]

  assert(t <= kValueTypeForSeek);

  Branch (18:3): [True: 2.00M, False: 21.7k]

  return (seq << 8) | t;

}

void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {

  result->append(key.user_key.data(), key.user_key.size());

  PutFixed64(result, PackSequenceAndType(key.sequence, key.type));

}

std::string ParsedInternalKey::DebugString() const {

  std::ostringstream ss;

  ss << '\'' << EscapeString(user_key.ToString()) << "' @ " << sequence << " : "

     << static_cast<int>(type);

  return ss.str();

}

std::string InternalKey::DebugString() const {

  ParsedInternalKey parsed;

  if (ParseInternalKey(rep_, &parsed)) {

  Branch (36:7): [True: 0, False: 0]

    return parsed.DebugString();

  }

  std::ostringstream ss;

  ss << "(bad)" << EscapeString(rep_);

  return ss.str();

}

const char* InternalKeyComparator::Name() const {

  return "leveldb.InternalKeyComparator";

}

int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {

  // Order by:

  //    increasing user key (according to user-supplied comparator)

  //    decreasing sequence number

  //    decreasing type (though sequence# should be enough to disambiguate)

  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));

  if (r == 0) {

  Branch (54:7): [True: 24.0M, False: 3.35M]

    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);

    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);

    if (anum > bnum) {

  Branch (57:9): [True: 2.55M, False: 21.4M]

      r = -1;

    } else if (anum < bnum) {

  Branch (59:16): [True: 21.4M, False: 18.4E]

      r = +1;

    }

  }

  return r;

}

void InternalKeyComparator::FindShortestSeparator(std::string* start,

                                                  const Slice& limit) const {

  // Attempt to shorten the user portion of the key

  Slice user_start = ExtractUserKey(*start);

  Slice user_limit = ExtractUserKey(limit);

  std::string tmp(user_start.data(), user_start.size());

  user_comparator_->FindShortestSeparator(&tmp, user_limit);

  if (tmp.size() < user_start.size() &&

  Branch (73:7): [True: 1.77k, False: 16.9k]
  Branch (73:7): [True: 1.77k, False: 16.9k]

      user_comparator_->Compare(user_start, tmp) < 0) {

  Branch (74:7): [True: 1.77k, False: 0]

    // User key has become shorter physically, but larger logically.

    // Tack on the earliest possible number to the shortened user key.

    PutFixed64(&tmp,

               PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));

    assert(this->Compare(*start, tmp) < 0);

  Branch (79:5): [True: 1.77k, False: 0]

    assert(this->Compare(tmp, limit) < 0);

  Branch (80:5): [True: 1.77k, False: 0]

    start->swap(tmp);

  }

}

void InternalKeyComparator::FindShortSuccessor(std::string* key) const {

  Slice user_key = ExtractUserKey(*key);

  std::string tmp(user_key.data(), user_key.size());

  user_comparator_->FindShortSuccessor(&tmp);

  if (tmp.size() < user_key.size() &&

  Branch (89:7): [True: 733, False: 377]
  Branch (89:7): [True: 733, False: 377]

      user_comparator_->Compare(user_key, tmp) < 0) {

  Branch (90:7): [True: 733, False: 0]

    // User key has become shorter physically, but larger logically.

    // Tack on the earliest possible number to the shortened user key.

    PutFixed64(&tmp,

               PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));

    assert(this->Compare(*key, tmp) < 0);

  Branch (95:5): [True: 733, False: 0]

    key->swap(tmp);

  }

}

const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }

void InternalFilterPolicy::CreateFilter(const Slice* keys, int n,

                                        std::string* dst) const {

  // We rely on the fact that the code in table.cc does not mind us

  // adjusting keys[].

  Slice* mkey = const_cast<Slice*>(keys);

  for (int i = 0; i < n; i++) {

  Branch (107:19): [True: 1.71M, False: 19.8k]

    mkey[i] = ExtractUserKey(keys[i]);

    // TODO(sanjay): Suppress dups?

  }

  user_policy_->CreateFilter(keys, n, dst);

}

bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {

  return user_policy_->KeyMayMatch(ExtractUserKey(key), f);

}

LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {

  size_t usize = user_key.size();

  size_t needed = usize + 13;  // A conservative estimate

  char* dst;

  if (needed <= sizeof(space_)) {

  Branch (122:7): [True: 2.04M, False: 6.81k]

    dst = space_;

  } else {

    dst = new char[needed];

  }

  start_ = dst;

  dst = EncodeVarint32(dst, usize + 8);

  kstart_ = dst;

  memcpy(dst, user_key.data(), usize);

  dst += usize;

  EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));

  dst += 8;

  end_ = dst;

}

}  // namespace leveldb