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