vendor/github.com/syndtr/goleveldb/leveldb/key.go

   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
   7 package leveldb
   8
   9 import (
  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.
  18 type ErrInternalKeyCorrupted struct {
  19         Ikey   []byte
  20         Reason string
  21 }
  22
  23 func (e *ErrInternalKeyCorrupted) Error() string {
  24         return fmt.Sprintf("leveldb: internal key %q corrupted: %s", e.Ikey, e.Reason)
  25 }
  26
  27 func newErrInternalKeyCorrupted(ikey []byte, reason string) error {
  28         return errors.NewErrCorrupted(storage.FileDesc{}, &ErrInternalKeyCorrupted{append([]byte{}, ikey...), reason})
  29 }
  30
  31 type keyType uint
  32
  33 func (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.
  45 const (
  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).
  55 const keyTypeSeek = keyTypeVal
  56
  57 const (
  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.
  67 var keyMaxNumBytes = make([]byte, 8)
  68
  69 func init() {
  70         binary.LittleEndian.PutUint64(keyMaxNumBytes, keyMaxNum)
  71 }
  72
  73 type internalKey []byte
  74
  75 func 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
  88 func 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
 101 func validInternalKey(ik []byte) bool {
 102         _, _, _, err := parseInternalKey(ik)
 103         return err == nil
 104 }
 105
 106 func (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
 115 func (ik internalKey) ukey() []byte {
 116         ik.assert()
 117         return ik[:len(ik)-8]
 118 }
 119
 120 func (ik internalKey) num() uint64 {
 121         ik.assert()
 122         return binary.LittleEndian.Uint64(ik[len(ik)-8:])
 123 }
 124
 125 func (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
 134 func (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 }