1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
// Copyright 2012 The LevelDB-Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package leveldb
import (
"bytes"
"github.com/golang/leveldb/db"
)
// internalKey is a key used for the in-memory and on-disk partial DBs that
// make up a leveldb DB.
//
// It consists of the user key (as given by the arbitrary code that uses
// package leveldb) followed by an 8-byte trailer:
// - 1 byte for the kind of internal key: delete or set,
// - 7 bytes for a uint56 sequence number, in little-endian format.
type internalKey []byte
type internalKeyKind uint8
const (
// These constants are part of the file format, and should not be changed.
internalKeyKindDelete internalKeyKind = 0
internalKeyKindSet internalKeyKind = 1
// This maximum value isn't part of the file format. It's unlikely,
// but future extensions may increase this value.
//
// When constructing an internal key to pass to DB.Find, internalKeyComparer
// sorts decreasing by kind (after sorting increasing by user key and
// decreasing by sequence number). Thus, use internalKeyKindMax, which sorts
// 'less than or equal to' any other valid internalKeyKind, when searching
// for any kind of internal key formed by a certain user key and seqNum.
internalKeyKindMax internalKeyKind = 1
)
// internalKeySeqNumMax is the largest valid sequence number.
const internalKeySeqNumMax = uint64(1<<56 - 1)
// makeInternalKey makes an internalKey from a user key, a kind, and a sequence
// number. The return value may be a slice of dst[:cap(dst)] if it is large
// enough. Otherwise, it may be a slice of a newly allocated buffer. In any
// case, all of dst[:cap(dst)] may be overwritten.
func makeInternalKey(dst internalKey, ukey []byte, kind internalKeyKind, seqNum uint64) internalKey {
if cap(dst) < len(ukey)+8 {
n := 256
for n < len(ukey)+8 {
n *= 2
}
dst = make(internalKey, n)
}
ikey := dst[:len(ukey)+8]
i := copy(ikey, ukey)
ikey[i+0] = uint8(kind)
ikey[i+1] = uint8(seqNum)
ikey[i+2] = uint8(seqNum >> 8)
ikey[i+3] = uint8(seqNum >> 16)
ikey[i+4] = uint8(seqNum >> 24)
ikey[i+5] = uint8(seqNum >> 32)
ikey[i+6] = uint8(seqNum >> 40)
ikey[i+7] = uint8(seqNum >> 48)
return ikey
}
// valid returns whether k is a valid internal key.
func (k internalKey) valid() bool {
i := len(k) - 8
return i >= 0 && internalKeyKind(k[i]) <= internalKeyKindMax
}
// ukey returns the user key portion of an internal key.
// ukey may panic if k is not valid.
func (k internalKey) ukey() []byte {
return []byte(k[:len(k)-8])
}
// kind returns the kind of an internal key.
// kind may panic if k is not valid.
func (k internalKey) kind() internalKeyKind {
return internalKeyKind(k[len(k)-8])
}
// seqNum returns the sequence number of an internal key.
// seqNum may panic if k is not valid.
func (k internalKey) seqNum() uint64 {
i := len(k) - 7
n := uint64(k[i+0])
n |= uint64(k[i+1]) << 8
n |= uint64(k[i+2]) << 16
n |= uint64(k[i+3]) << 24
n |= uint64(k[i+4]) << 32
n |= uint64(k[i+5]) << 40
n |= uint64(k[i+6]) << 48
return n
}
// clone returns an internalKey that has the same contents but is backed by a
// different array.
func (k internalKey) clone() internalKey {
x := make(internalKey, len(k))
copy(x, k)
return x
}
// internalKeyComparer is a db.Comparer that wraps another db.Comparer.
//
// It compares internal keys first by their user keys (as ordered by userCmp),
// then by sequence number (decreasing), then by kind (decreasing). The last
// step is only for completeness; for a given leveldb DB, no two internal keys
// should have the same sequence number.
//
// This ordering is designed so that when iterating through an internal table
// starting at (ukey0, seqNum0), one first encounters those entries with the
// same user key and lower sequence number (i.e. sets or deletes from earlier
// in time), followed by those entries with 'greater' user keys (where
// 'greater' is defined by userCmp). Specifically, one does not encounter
// entries with the same user key and higher sequence number (i.e. sets or
// deletes for ukey0 from the 'future' relative to the particular snapshot
// seqNum0 of the DB).
type internalKeyComparer struct {
userCmp db.Comparer
}
var _ db.Comparer = internalKeyComparer{}
func (c internalKeyComparer) Compare(a, b []byte) int {
ak, bk := internalKey(a), internalKey(b)
if !ak.valid() {
if bk.valid() {
return -1
}
return bytes.Compare(a, b)
}
if !bk.valid() {
return 1
}
if x := c.userCmp.Compare(ak.ukey(), bk.ukey()); x != 0 {
return x
}
if an, bn := ak.seqNum(), bk.seqNum(); an < bn {
return +1
} else if an > bn {
return -1
}
if ai, bi := ak.kind(), bk.kind(); ai < bi {
return +1
} else if ai > bi {
return -1
}
return 0
}
func (c internalKeyComparer) Name() string {
// This is the same name given by the C++ leveldb's InternalKeyComparator class.
return "leveldb.InternalKeyComparator"
}
func (c internalKeyComparer) AppendSeparator(dst, a, b []byte) []byte {
// TODO: this could be more sophisticated.
return append(dst, a...)
}
|
