← Back to branch summary

~ubuntu-branches/ubuntu/quantal/ceph/quantal

« back to all changes in this revision

Viewing changes to src/leveldb/db/memtable.cc

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-07-16 09:56:24 UTC
  • mfrom: (0.3.11)
  • mto: This revision was merged to the branch mainline in revision 17.
  • Revision ID: package-import@ubuntu.com-20120716095624-azr2w4hbhei1rxmx
Tags: upstream-0.48
Import upstream version 0.48

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/leveldb/db/memtable.cc
1
 
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2
 
// Use of this source code is governed by a BSD-style license that can be
3
 
// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
 
 
5
 
#include "db/memtable.h"
6
 
#include "db/dbformat.h"
7
 
#include "leveldb/comparator.h"
8
 
#include "leveldb/env.h"
9
 
#include "leveldb/iterator.h"
10
 
#include "util/coding.h"
11
 
 
12
 
namespace leveldb {
13
 
 
14
 
static Slice GetLengthPrefixedSlice(const char* data) {
15
 
  uint32_t len;
16
 
  const char* p = data;
17
 
  p = GetVarint32Ptr(p, p + 5, &len);  // +5: we assume "p" is not corrupted
18
 
  return Slice(p, len);
19
 
}
20
 
 
21
 
MemTable::MemTable(const InternalKeyComparator& cmp)
22
 
    : comparator_(cmp),
23
 
      refs_(0),
24
 
      table_(comparator_, &arena_) {
25
 
}
26
 
 
27
 
MemTable::~MemTable() {
28
 
  assert(refs_ == 0);
29
 
}
30
 
 
31
 
size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
32
 
 
33
 
int MemTable::KeyComparator::operator()(const char* aptr, const char* bptr)
34
 
    const {
35
 
  // Internal keys are encoded as length-prefixed strings.
36
 
  Slice a = GetLengthPrefixedSlice(aptr);
37
 
  Slice b = GetLengthPrefixedSlice(bptr);
38
 
  return comparator.Compare(a, b);
39
 
}
40
 
 
41
 
// Encode a suitable internal key target for "target" and return it.
42
 
// Uses *scratch as scratch space, and the returned pointer will point
43
 
// into this scratch space.
44
 
static const char* EncodeKey(std::string* scratch, const Slice& target) {
45
 
  scratch->clear();
46
 
  PutVarint32(scratch, target.size());
47
 
  scratch->append(target.data(), target.size());
48
 
  return scratch->data();
49
 
}
50
 
 
51
 
class MemTableIterator: public Iterator {
52
 
 public:
53
 
  explicit MemTableIterator(MemTable::Table* table) : iter_(table) { }
54
 
 
55
 
  virtual bool Valid() const { return iter_.Valid(); }
56
 
  virtual void Seek(const Slice& k) { iter_.Seek(EncodeKey(&tmp_, k)); }
57
 
  virtual void SeekToFirst() { iter_.SeekToFirst(); }
58
 
  virtual void SeekToLast() { iter_.SeekToLast(); }
59
 
  virtual void Next() { iter_.Next(); }
60
 
  virtual void Prev() { iter_.Prev(); }
61
 
  virtual Slice key() const { return GetLengthPrefixedSlice(iter_.key()); }
62
 
  virtual Slice value() const {
63
 
    Slice key_slice = GetLengthPrefixedSlice(iter_.key());
64
 
    return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
65
 
  }
66
 
 
67
 
  virtual Status status() const { return Status::OK(); }
68
 
 
69
 
 private:
70
 
  MemTable::Table::Iterator iter_;
71
 
  std::string tmp_;       // For passing to EncodeKey
72
 
 
73
 
  // No copying allowed
74
 
  MemTableIterator(const MemTableIterator&);
75
 
  void operator=(const MemTableIterator&);
76
 
};
77
 
 
78
 
Iterator* MemTable::NewIterator() {
79
 
  return new MemTableIterator(&table_);
80
 
}
81
 
 
82
 
void MemTable::Add(SequenceNumber s, ValueType type,
83
 
                   const Slice& key,
84
 
                   const Slice& value) {
85
 
  // Format of an entry is concatenation of:
86
 
  //  key_size     : varint32 of internal_key.size()
87
 
  //  key bytes    : char[internal_key.size()]
88
 
  //  value_size   : varint32 of value.size()
89
 
  //  value bytes  : char[value.size()]
90
 
  size_t key_size = key.size();
91
 
  size_t val_size = value.size();
92
 
  size_t internal_key_size = key_size + 8;
93
 
  const size_t encoded_len =
94
 
      VarintLength(internal_key_size) + internal_key_size +
95
 
      VarintLength(val_size) + val_size;
96
 
  char* buf = arena_.Allocate(encoded_len);
97
 
  char* p = EncodeVarint32(buf, internal_key_size);
98
 
  memcpy(p, key.data(), key_size);
99
 
  p += key_size;
100
 
  EncodeFixed64(p, (s << 8) | type);
101
 
  p += 8;
102
 
  p = EncodeVarint32(p, val_size);
103
 
  memcpy(p, value.data(), val_size);
104
 
  assert((p + val_size) - buf == encoded_len);
105
 
  table_.Insert(buf);
106
 
}
107
 
 
108
 
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
109
 
  Slice memkey = key.memtable_key();
110
 
  Table::Iterator iter(&table_);
111
 
  iter.Seek(memkey.data());
112
 
  if (iter.Valid()) {
113
 
    // entry format is:
114
 
    //    klength  varint32
115
 
    //    userkey  char[klength]
116
 
    //    tag      uint64
117
 
    //    vlength  varint32
118
 
    //    value    char[vlength]
119
 
    // Check that it belongs to same user key.  We do not check the
120
 
    // sequence number since the Seek() call above should have skipped
121
 
    // all entries with overly large sequence numbers.
122
 
    const char* entry = iter.key();
123
 
    uint32_t key_length;
124
 
    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
125
 
    if (comparator_.comparator.user_comparator()->Compare(
126
 
            Slice(key_ptr, key_length - 8),
127
 
            key.user_key()) == 0) {
128
 
      // Correct user key
129
 
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
130
 
      switch (static_cast<ValueType>(tag & 0xff)) {
131
 
        case kTypeValue: {
132
 
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
133
 
          value->assign(v.data(), v.size());
134
 
          return true;
135
 
        }
136
 
        case kTypeDeletion:
137
 
          *s = Status::NotFound(Slice());
138
 
          return true;
139
 
      }
140
 
    }
141
 
  }
142
 
  return false;
143
 
}
144
 
 
145
 
}  // namespace leveldb