1// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
2// All rights reserved.
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7package leveldb
8
9import (
10	"encoding/binary"
11	"fmt"
12
13	"github.com/syndtr/goleveldb/leveldb/errors"
14	"github.com/syndtr/goleveldb/leveldb/storage"
15)
16
17// ErrInternalKeyCorrupted records internal key corruption.
18type ErrInternalKeyCorrupted struct {
19	Ikey   []byte
20	Reason string
21}
22
23func (e *ErrInternalKeyCorrupted) Error() string {
24	return fmt.Sprintf("leveldb: internal key %q corrupted: %s", e.Ikey, e.Reason)
25}
26
27func newErrInternalKeyCorrupted(ikey []byte, reason string) error {
28	return errors.NewErrCorrupted(storage.FileDesc{}, &ErrInternalKeyCorrupted{append([]byte{}, ikey...), reason})
29}
30
31type keyType uint
32
33func (kt keyType) String() string {
34	switch kt {
35	case keyTypeDel:
36		return "d"
37	case keyTypeVal:
38		return "v"
39	}
40	return fmt.Sprintf("<invalid:%#x>", uint(kt))
41}
42
43// Value types encoded as the last component of internal keys.
44// Don't modify; this value are saved to disk.
45const (
46	keyTypeDel = keyType(0)
47	keyTypeVal = keyType(1)
48)
49
50// keyTypeSeek defines the keyType that should be passed when constructing an
51// internal key for seeking to a particular sequence number (since we
52// sort sequence numbers in decreasing order and the value type is
53// embedded as the low 8 bits in the sequence number in internal keys,
54// we need to use the highest-numbered ValueType, not the lowest).
55const keyTypeSeek = keyTypeVal
56
57const (
58	// Maximum value possible for sequence number; the 8-bits are
59	// used by value type, so its can packed together in single
60	// 64-bit integer.
61	keyMaxSeq = (uint64(1) << 56) - 1
62	// Maximum value possible for packed sequence number and type.
63	keyMaxNum = (keyMaxSeq << 8) | uint64(keyTypeSeek)
64)
65
66// Maximum number encoded in bytes.
67var keyMaxNumBytes = make([]byte, 8)
68
69func init() {
70	binary.LittleEndian.PutUint64(keyMaxNumBytes, keyMaxNum)
71}
72
73type internalKey []byte
74
75func makeInternalKey(dst, ukey []byte, seq uint64, kt keyType) internalKey {
76	if seq > keyMaxSeq {
77		panic("leveldb: invalid sequence number")
78	} else if kt > keyTypeVal {
79		panic("leveldb: invalid type")
80	}
81
82	dst = ensureBuffer(dst, len(ukey)+8)
83	copy(dst, ukey)
84	binary.LittleEndian.PutUint64(dst[len(ukey):], (seq<<8)|uint64(kt))
85	return internalKey(dst)
86}
87
88func parseInternalKey(ik []byte) (ukey []byte, seq uint64, kt keyType, err error) {
89	if len(ik) < 8 {
90		return nil, 0, 0, newErrInternalKeyCorrupted(ik, "invalid length")
91	}
92	num := binary.LittleEndian.Uint64(ik[len(ik)-8:])
93	seq, kt = uint64(num>>8), keyType(num&0xff)
94	if kt > keyTypeVal {
95		return nil, 0, 0, newErrInternalKeyCorrupted(ik, "invalid type")
96	}
97	ukey = ik[:len(ik)-8]
98	return
99}
100
101func validInternalKey(ik []byte) bool {
102	_, _, _, err := parseInternalKey(ik)
103	return err == nil
104}
105
106func (ik internalKey) assert() {
107	if ik == nil {
108		panic("leveldb: nil internalKey")
109	}
110	if len(ik) < 8 {
111		panic(fmt.Sprintf("leveldb: internal key %q, len=%d: invalid length", []byte(ik), len(ik)))
112	}
113}
114
115func (ik internalKey) ukey() []byte {
116	ik.assert()
117	return ik[:len(ik)-8]
118}
119
120func (ik internalKey) num() uint64 {
121	ik.assert()
122	return binary.LittleEndian.Uint64(ik[len(ik)-8:])
123}
124
125func (ik internalKey) parseNum() (seq uint64, kt keyType) {
126	num := ik.num()
127	seq, kt = uint64(num>>8), keyType(num&0xff)
128	if kt > keyTypeVal {
129		panic(fmt.Sprintf("leveldb: internal key %q, len=%d: invalid type %#x", []byte(ik), len(ik), kt))
130	}
131	return
132}
133
134func (ik internalKey) String() string {
135	if ik == nil {
136		return "<nil>"
137	}
138
139	if ukey, seq, kt, err := parseInternalKey(ik); err == nil {
140		return fmt.Sprintf("%s,%s%d", shorten(string(ukey)), kt, seq)
141	}
142	return fmt.Sprintf("<invalid:%#x>", []byte(ik))
143}
144