← Back to branch summary

~ubuntu-branches/ubuntu/raring/ceph/raring

« back to all changes in this revision

Viewing changes to src/leveldb/db/dbformat.h

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-06-08 15:54:37 UTC
  • mfrom: (1.1.8) (0.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120608155437-gy3j9k6wzv7w4gn9
Tags: 0.44.1-1ubuntu1
* Merge from Debian unstable.  Remaining changes:
  - d/control: Switch from libcryptopp to libnss as libcryptopp
    is not seeded.
  - d/control,d/rules: Move from python-support to dh_python2.
  - d/patches/manpage_updates*.patch: cherry picked upstream manpage
    updates warning about lack of encryption, per MIR review.
  - d/rules,d/control: Drop radosgw since libfcgi is not in main and
    the code may not be suitable for LTS.
  - d/rules,d/control: Drop tcmalloc since google perftools is not
    in main yet.
  - d/rules,d/control: Drop ceph-fuse entirely per MIR review
    recommendation.
* d/patches/fix-radosgw-tests.patch: Cherry picked patch from upstream
  VCS to fixup tests to conditionally use radosgw if enabled.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/leveldb/db/dbformat.h
 
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
#ifndef STORAGE_LEVELDB_DB_FORMAT_H_
 
6
#define STORAGE_LEVELDB_DB_FORMAT_H_
 
7
 
 
8
#include <stdio.h>
 
9
#include "leveldb/comparator.h"
 
10
#include "leveldb/db.h"
 
11
#include "leveldb/slice.h"
 
12
#include "leveldb/table_builder.h"
 
13
#include "util/coding.h"
 
14
#include "util/logging.h"
 
15
 
 
16
namespace leveldb {
 
17
 
 
18
// Grouping of constants.  We may want to make some of these
 
19
// parameters set via options.
 
20
namespace config {
 
21
static const int kNumLevels = 7;
 
22
 
 
23
// Level-0 compaction is started when we hit this many files.
 
24
static const int kL0_CompactionTrigger = 4;
 
25
 
 
26
// Soft limit on number of level-0 files.  We slow down writes at this point.
 
27
static const int kL0_SlowdownWritesTrigger = 8;
 
28
 
 
29
// Maximum number of level-0 files.  We stop writes at this point.
 
30
static const int kL0_StopWritesTrigger = 12;
 
31
 
 
32
// Maximum level to which a new compacted memtable is pushed if it
 
33
// does not create overlap.  We try to push to level 2 to avoid the
 
34
// relatively expensive level 0=>1 compactions and to avoid some
 
35
// expensive manifest file operations.  We do not push all the way to
 
36
// the largest level since that can generate a lot of wasted disk
 
37
// space if the same key space is being repeatedly overwritten.
 
38
static const int kMaxMemCompactLevel = 2;
 
39
 
 
40
}  // namespace config
 
41
 
 
42
class InternalKey;
 
43
 
 
44
// Value types encoded as the last component of internal keys.
 
45
// DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
 
46
// data structures.
 
47
enum ValueType {
 
48
  kTypeDeletion = 0x0,
 
49
  kTypeValue = 0x1
 
50
};
 
51
// kValueTypeForSeek defines the ValueType that should be passed when
 
52
// constructing a ParsedInternalKey object for seeking to a particular
 
53
// sequence number (since we sort sequence numbers in decreasing order
 
54
// and the value type is embedded as the low 8 bits in the sequence
 
55
// number in internal keys, we need to use the highest-numbered
 
56
// ValueType, not the lowest).
 
57
static const ValueType kValueTypeForSeek = kTypeValue;
 
58
 
 
59
typedef uint64_t SequenceNumber;
 
60
 
 
61
// We leave eight bits empty at the bottom so a type and sequence#
 
62
// can be packed together into 64-bits.
 
63
static const SequenceNumber kMaxSequenceNumber =
 
64
    ((0x1ull << 56) - 1);
 
65
 
 
66
struct ParsedInternalKey {
 
67
  Slice user_key;
 
68
  SequenceNumber sequence;
 
69
  ValueType type;
 
70
 
 
71
  ParsedInternalKey() { }  // Intentionally left uninitialized (for speed)
 
72
  ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
 
73
      : user_key(u), sequence(seq), type(t) { }
 
74
  std::string DebugString() const;
 
75
};
 
76
 
 
77
// Return the length of the encoding of "key".
 
78
inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
 
79
  return key.user_key.size() + 8;
 
80
}
 
81
 
 
82
// Append the serialization of "key" to *result.
 
83
extern void AppendInternalKey(std::string* result,
 
84
                              const ParsedInternalKey& key);
 
85
 
 
86
// Attempt to parse an internal key from "internal_key".  On success,
 
87
// stores the parsed data in "*result", and returns true.
 
88
//
 
89
// On error, returns false, leaves "*result" in an undefined state.
 
90
extern bool ParseInternalKey(const Slice& internal_key,
 
91
                             ParsedInternalKey* result);
 
92
 
 
93
// Returns the user key portion of an internal key.
 
94
inline Slice ExtractUserKey(const Slice& internal_key) {
 
95
  assert(internal_key.size() >= 8);
 
96
  return Slice(internal_key.data(), internal_key.size() - 8);
 
97
}
 
98
 
 
99
inline ValueType ExtractValueType(const Slice& internal_key) {
 
100
  assert(internal_key.size() >= 8);
 
101
  const size_t n = internal_key.size();
 
102
  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
 
103
  unsigned char c = num & 0xff;
 
104
  return static_cast<ValueType>(c);
 
105
}
 
106
 
 
107
// A comparator for internal keys that uses a specified comparator for
 
108
// the user key portion and breaks ties by decreasing sequence number.
 
109
class InternalKeyComparator : public Comparator {
 
110
 private:
 
111
  const Comparator* user_comparator_;
 
112
 public:
 
113
  explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
 
114
  virtual const char* Name() const;
 
115
  virtual int Compare(const Slice& a, const Slice& b) const;
 
116
  virtual void FindShortestSeparator(
 
117
      std::string* start,
 
118
      const Slice& limit) const;
 
119
  virtual void FindShortSuccessor(std::string* key) const;
 
120
 
 
121
  const Comparator* user_comparator() const { return user_comparator_; }
 
122
 
 
123
  int Compare(const InternalKey& a, const InternalKey& b) const;
 
124
};
 
125
 
 
126
// Modules in this directory should keep internal keys wrapped inside
 
127
// the following class instead of plain strings so that we do not
 
128
// incorrectly use string comparisons instead of an InternalKeyComparator.
 
129
class InternalKey {
 
130
 private:
 
131
  std::string rep_;
 
132
 public:
 
133
  InternalKey() { }   // Leave rep_ as empty to indicate it is invalid
 
134
  InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
 
135
    AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
 
136
  }
 
137
 
 
138
  void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }
 
139
  Slice Encode() const {
 
140
    assert(!rep_.empty());
 
141
    return rep_;
 
142
  }
 
143
 
 
144
  Slice user_key() const { return ExtractUserKey(rep_); }
 
145
 
 
146
  void SetFrom(const ParsedInternalKey& p) {
 
147
    rep_.clear();
 
148
    AppendInternalKey(&rep_, p);
 
149
  }
 
150
 
 
151
  void Clear() { rep_.clear(); }
 
152
 
 
153
  std::string DebugString() const;
 
154
};
 
155
 
 
156
inline int InternalKeyComparator::Compare(
 
157
    const InternalKey& a, const InternalKey& b) const {
 
158
  return Compare(a.Encode(), b.Encode());
 
159
}
 
160
 
 
161
inline bool ParseInternalKey(const Slice& internal_key,
 
162
                             ParsedInternalKey* result) {
 
163
  const size_t n = internal_key.size();
 
164
  if (n < 8) return false;
 
165
  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
 
166
  unsigned char c = num & 0xff;
 
167
  result->sequence = num >> 8;
 
168
  result->type = static_cast<ValueType>(c);
 
169
  result->user_key = Slice(internal_key.data(), n - 8);
 
170
  return (c <= static_cast<unsigned char>(kTypeValue));
 
171
}
 
172
 
 
173
// A helper class useful for DBImpl::Get()
 
174
class LookupKey {
 
175
 public:
 
176
  // Initialize *this for looking up user_key at a snapshot with
 
177
  // the specified sequence number.
 
178
  LookupKey(const Slice& user_key, SequenceNumber sequence);
 
179
 
 
180
  ~LookupKey();
 
181
 
 
182
  // Return a key suitable for lookup in a MemTable.
 
183
  Slice memtable_key() const { return Slice(start_, end_ - start_); }
 
184
 
 
185
  // Return an internal key (suitable for passing to an internal iterator)
 
186
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
 
187
 
 
188
  // Return the user key
 
189
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
 
190
 
 
191
 private:
 
192
  // We construct a char array of the form:
 
193
  //    klength  varint32               <-- start_
 
194
  //    userkey  char[klength]          <-- kstart_
 
195
  //    tag      uint64
 
196
  //                                    <-- end_
 
197
  // The array is a suitable MemTable key.
 
198
  // The suffix starting with "userkey" can be used as an InternalKey.
 
199
  const char* start_;
 
200
  const char* kstart_;
 
201
  const char* end_;
 
202
  char space_[200];      // Avoid allocation for short keys
 
203
 
 
204
  // No copying allowed
 
205
  LookupKey(const LookupKey&);
 
206
  void operator=(const LookupKey&);
 
207
};
 
208
 
 
209
inline LookupKey::~LookupKey() {
 
210
  if (start_ != space_) delete[] start_;
 
211
}
 
212
 
 
213
}  // namespace leveldb
 
214
 
 
215
#endif  // STORAGE_LEVELDB_DB_FORMAT_H_