leveldb/testutil/kv.go - third_party/goleveldb - Git at Google

 // Copyright (c) 2014, Suryandaru Triandana <syndtr@gmail.com>
 // All rights reserved.
 //
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 package testutil

 import (
 	"fmt"
 	"math/rand"
 	"sort"
 	"strings"

 	"github.com/syndtr/goleveldb/leveldb/util"
 )

 type KeyValueEntry struct {
 	key, value []byte
 }

 type KeyValue struct {
 	entries []KeyValueEntry
 	nbytes  int
 }

 func (kv *KeyValue) Put(key, value []byte) {
 	if n := len(kv.entries); n > 0 && cmp.Compare(kv.entries[n-1].key, key) >= 0 {
 		panic(fmt.Sprintf("Put: keys are not in increasing order: %q, %q", kv.entries[n-1].key, key))
 	}
 	kv.entries = append(kv.entries, KeyValueEntry{key, value})
 	kv.nbytes += len(key) + len(value)
 }

 func (kv *KeyValue) PutString(key, value string) {
 	kv.Put([]byte(key), []byte(value))
 }

 func (kv *KeyValue) PutU(key, value []byte) bool {
 	if i, exist := kv.Get(key); !exist {
 		if i < kv.Len() {
 			kv.entries = append(kv.entries[:i+1], kv.entries[i:]...)
 			kv.entries[i] = KeyValueEntry{key, value}
 		} else {
 			kv.entries = append(kv.entries, KeyValueEntry{key, value})
 		}
 		kv.nbytes += len(key) + len(value)
 		return true
 	} else {
 		kv.nbytes += len(value) - len(kv.ValueAt(i))
 		kv.entries[i].value = value
 	}
 	return false
 }

 func (kv *KeyValue) PutUString(key, value string) bool {
 	return kv.PutU([]byte(key), []byte(value))
 }

 func (kv *KeyValue) Delete(key []byte) (exist bool, value []byte) {
 	i, exist := kv.Get(key)
 	if exist {
 		value = kv.entries[i].value
 		kv.DeleteIndex(i)
 	}
 	return
 }

 func (kv *KeyValue) DeleteIndex(i int) bool {
 	if i < kv.Len() {
 		kv.nbytes -= len(kv.KeyAt(i)) + len(kv.ValueAt(i))
 		kv.entries = append(kv.entries[:i], kv.entries[i+1:]...)
 		return true
 	}
 	return false
 }

 func (kv KeyValue) Len() int {
 	return len(kv.entries)
 }

 func (kv *KeyValue) Size() int {
 	return kv.nbytes
 }

 func (kv KeyValue) KeyAt(i int) []byte {
 	return kv.entries[i].key
 }

 func (kv KeyValue) ValueAt(i int) []byte {
 	return kv.entries[i].value
 }

 func (kv KeyValue) Index(i int) (key, value []byte) {
 	if i < 0 || i >= len(kv.entries) {
 		panic(fmt.Sprintf("Index #%d: out of range", i))
 	}
 	return kv.entries[i].key, kv.entries[i].value
 }

 func (kv KeyValue) IndexInexact(i int) (key_, key, value []byte) {
 	key, value = kv.Index(i)
 	var key0 []byte
 	var key1 = kv.KeyAt(i)
 	if i > 0 {
 		key0 = kv.KeyAt(i - 1)
 	}
 	key_ = BytesSeparator(key0, key1)
 	return
 }

 func (kv KeyValue) IndexOrNil(i int) (key, value []byte) {
 	if i >= 0 && i < len(kv.entries) {
 		return kv.entries[i].key, kv.entries[i].value
 	}
 	return nil, nil
 }

 func (kv KeyValue) IndexString(i int) (key, value string) {
 	key_, _value := kv.Index(i)
 	return string(key_), string(_value)
 }

 func (kv KeyValue) Search(key []byte) int {
 	return sort.Search(kv.Len(), func(i int) bool {
 		return cmp.Compare(kv.KeyAt(i), key) >= 0
 	})
 }

 func (kv KeyValue) SearchString(key string) int {
 	return kv.Search([]byte(key))
 }

 func (kv KeyValue) Get(key []byte) (i int, exist bool) {
 	i = kv.Search(key)
 	if i < kv.Len() && cmp.Compare(kv.KeyAt(i), key) == 0 {
 		exist = true
 	}
 	return
 }

 func (kv KeyValue) GetString(key string) (i int, exist bool) {
 	return kv.Get([]byte(key))
 }

 func (kv KeyValue) Iterate(fn func(i int, key, value []byte)) {
 	for i, x := range kv.entries {
 		fn(i, x.key, x.value)
 	}
 }

 func (kv KeyValue) IterateString(fn func(i int, key, value string)) {
 	kv.Iterate(func(i int, key, value []byte) {
 		fn(i, string(key), string(value))
 	})
 }

 func (kv KeyValue) IterateShuffled(rnd *rand.Rand, fn func(i int, key, value []byte)) {
 	ShuffledIndex(rnd, kv.Len(), 1, func(i int) {
 		fn(i, kv.entries[i].key, kv.entries[i].value)
 	})
 }

 func (kv KeyValue) IterateShuffledString(rnd *rand.Rand, fn func(i int, key, value string)) {
 	kv.IterateShuffled(rnd, func(i int, key, value []byte) {
 		fn(i, string(key), string(value))
 	})
 }

 func (kv KeyValue) IterateInexact(fn func(i int, key_, key, value []byte)) {
 	for i := range kv.entries {
 		key_, key, value := kv.IndexInexact(i)
 		fn(i, key_, key, value)
 	}
 }

 func (kv KeyValue) IterateInexactString(fn func(i int, key_, key, value string)) {
 	kv.IterateInexact(func(i int, key_, key, value []byte) {
 		fn(i, string(key_), string(key), string(value))
 	})
 }

 func (kv KeyValue) Clone() KeyValue {
 	return KeyValue{append([]KeyValueEntry{}, kv.entries...), kv.nbytes}
 }

 func (kv KeyValue) Slice(start, limit int) KeyValue {
 	if start < 0 || limit > kv.Len() {
 		panic(fmt.Sprintf("Slice %d .. %d: out of range", start, limit))
 	} else if limit < start {
 		panic(fmt.Sprintf("Slice %d .. %d: invalid range", start, limit))
 	}
 	return KeyValue{append([]KeyValueEntry{}, kv.entries[start:limit]...), kv.nbytes}
 }

 func (kv KeyValue) SliceKey(start, limit []byte) KeyValue {
 	start_ := 0
 	limit_ := kv.Len()
 	if start != nil {
 		start_ = kv.Search(start)
 	}
 	if limit != nil {
 		limit_ = kv.Search(limit)
 	}
 	return kv.Slice(start_, limit_)
 }

 func (kv KeyValue) SliceKeyString(start, limit string) KeyValue {
 	return kv.SliceKey([]byte(start), []byte(limit))
 }

 func (kv KeyValue) SliceRange(r *util.Range) KeyValue {
 	if r != nil {
 		return kv.SliceKey(r.Start, r.Limit)
 	}
 	return kv.Clone()
 }

 func (kv KeyValue) Range(start, limit int) (r util.Range) {
 	if kv.Len() > 0 {
 		if start == kv.Len() {
 			r.Start = BytesAfter(kv.KeyAt(start - 1))
 		} else {
 			r.Start = kv.KeyAt(start)
 		}
 	}
 	if limit < kv.Len() {
 		r.Limit = kv.KeyAt(limit)
 	}
 	return
 }

 func KeyValue_EmptyKey() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("", "v")
 	return kv
 }

 func KeyValue_EmptyValue() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("abc", "")
 	kv.PutString("abcd", "")
 	return kv
 }

 func KeyValue_OneKeyValue() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("abc", "v")
 	return kv
 }

 func KeyValue_BigValue() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("big1", strings.Repeat("1", 200000))
 	return kv
 }

 func KeyValue_SpecialKey() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("\xff\xff", "v3")
 	return kv
 }

 func KeyValue_MultipleKeyValue() *KeyValue {
 	kv := &KeyValue{}
 	kv.PutString("a", "v")
 	kv.PutString("aa", "v1")
 	kv.PutString("aaa", "v2")
 	kv.PutString("aaacccccccccc", "v2")
 	kv.PutString("aaaccccccccccd", "v3")
 	kv.PutString("aaaccccccccccf", "v4")
 	kv.PutString("aaaccccccccccfg", "v5")
 	kv.PutString("ab", "v6")
 	kv.PutString("abc", "v7")
 	kv.PutString("abcd", "v8")
 	kv.PutString("accccccccccccccc", "v9")
 	kv.PutString("b", "v10")
 	kv.PutString("bb", "v11")
 	kv.PutString("bc", "v12")
 	kv.PutString("c", "v13")
 	kv.PutString("c1", "v13")
 	kv.PutString("czzzzzzzzzzzzzz", "v14")
 	kv.PutString("fffffffffffffff", "v15")
 	kv.PutString("g11", "v15")
 	kv.PutString("g111", "v15")
 	kv.PutString("g111\xff", "v15")
 	kv.PutString("zz", "v16")
 	kv.PutString("zzzzzzz", "v16")
 	kv.PutString("zzzzzzzzzzzzzzzz", "v16")
 	return kv
 }

 var keymap = []byte("012345678ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy")

 func KeyValue_Generate(rnd *rand.Rand, n, minlen, maxlen, vminlen, vmaxlen int) *KeyValue {
 	if rnd == nil {
 		rnd = NewRand()
 	}
 	if maxlen < minlen {
 		panic("max len should >= min len")
 	}

 	rrand := func(min, max int) int {
 		if min == max {
 			return max
 		}
 		return rnd.Intn(max-min) + min
 	}

 	kv := &KeyValue{}
 	endC := byte(len(keymap) - 1)
 	gen := make([]byte, 0, maxlen)
 	for i := 0; i < n; i++ {
 		m := rrand(minlen, maxlen)
 		last := gen
 	retry:
 		gen = last[:m]
 		if k := len(last); m > k {
 			for j := k; j < m; j++ {
 				gen[j] = 0
 			}
 		} else {
 			for j := m - 1; j >= 0; j-- {
 				c := last[j]
 				if c == endC {
 					continue
 				}
 				gen[j] = c + 1
 				for j += 1; j < m; j++ {
 					gen[j] = 0
 				}
 				goto ok
 			}
 			if m < maxlen {
 				m++
 				goto retry
 			}
 			panic(fmt.Sprintf("only able to generate %d keys out of %d keys, try increasing max len", kv.Len(), n))
 		ok:
 		}
 		key := make([]byte, m)
 		for j := 0; j < m; j++ {
 			key[j] = keymap[gen[j]]
 		}
 		value := make([]byte, rrand(vminlen, vmaxlen))
 		for n := copy(value, []byte(fmt.Sprintf("v%d", i))); n < len(value); n++ {
 			value[n] = 'x'
 		}
 		kv.Put(key, value)
 	}
 	return kv
 }
	// Copyright (c) 2014, Suryandaru Triandana <syndtr@gmail.com>
	// All rights reserved.
	//
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	package testutil

	import (
	"fmt"
	"math/rand"
	"sort"
	"strings"

	"github.com/syndtr/goleveldb/leveldb/util"
	)

	type KeyValueEntry struct {
	key, value []byte
	}

	type KeyValue struct {
	entries []KeyValueEntry
	nbytes int
	}

	func (kv *KeyValue) Put(key, value []byte) {
	if n := len(kv.entries); n > 0 && cmp.Compare(kv.entries[n-1].key, key) >= 0 {
	panic(fmt.Sprintf("Put: keys are not in increasing order: %q, %q", kv.entries[n-1].key, key))
	}
	kv.entries = append(kv.entries, KeyValueEntry{key, value})
	kv.nbytes += len(key) + len(value)
	}

	func (kv *KeyValue) PutString(key, value string) {
	kv.Put([]byte(key), []byte(value))
	}

	func (kv *KeyValue) PutU(key, value []byte) bool {
	if i, exist := kv.Get(key); !exist {
	if i < kv.Len() {
	kv.entries = append(kv.entries[:i+1], kv.entries[i:]...)
	kv.entries[i] = KeyValueEntry{key, value}
	} else {
	kv.entries = append(kv.entries, KeyValueEntry{key, value})
	}
	kv.nbytes += len(key) + len(value)
	return true
	} else {
	kv.nbytes += len(value) - len(kv.ValueAt(i))
	kv.entries[i].value = value
	}
	return false
	}

	func (kv *KeyValue) PutUString(key, value string) bool {
	return kv.PutU([]byte(key), []byte(value))
	}

	func (kv *KeyValue) Delete(key []byte) (exist bool, value []byte) {
	i, exist := kv.Get(key)
	if exist {
	value = kv.entries[i].value
	kv.DeleteIndex(i)
	}
	return
	}

	func (kv *KeyValue) DeleteIndex(i int) bool {
	if i < kv.Len() {
	kv.nbytes -= len(kv.KeyAt(i)) + len(kv.ValueAt(i))
	kv.entries = append(kv.entries[:i], kv.entries[i+1:]...)
	return true
	}
	return false
	}

	func (kv KeyValue) Len() int {
	return len(kv.entries)
	}

	func (kv *KeyValue) Size() int {
	return kv.nbytes
	}

	func (kv KeyValue) KeyAt(i int) []byte {
	return kv.entries[i].key
	}

	func (kv KeyValue) ValueAt(i int) []byte {
	return kv.entries[i].value
	}

	func (kv KeyValue) Index(i int) (key, value []byte) {
	if i < 0 \|\| i >= len(kv.entries) {
	panic(fmt.Sprintf("Index #%d: out of range", i))
	}
	return kv.entries[i].key, kv.entries[i].value
	}

	func (kv KeyValue) IndexInexact(i int) (key_, key, value []byte) {
	key, value = kv.Index(i)
	var key0 []byte
	var key1 = kv.KeyAt(i)
	if i > 0 {
	key0 = kv.KeyAt(i - 1)
	}
	key_ = BytesSeparator(key0, key1)
	return
	}

	func (kv KeyValue) IndexOrNil(i int) (key, value []byte) {
	if i >= 0 && i < len(kv.entries) {
	return kv.entries[i].key, kv.entries[i].value
	}
	return nil, nil
	}

	func (kv KeyValue) IndexString(i int) (key, value string) {
	key_, _value := kv.Index(i)
	return string(key_), string(_value)
	}

	func (kv KeyValue) Search(key []byte) int {
	return sort.Search(kv.Len(), func(i int) bool {
	return cmp.Compare(kv.KeyAt(i), key) >= 0
	})
	}

	func (kv KeyValue) SearchString(key string) int {
	return kv.Search([]byte(key))
	}

	func (kv KeyValue) Get(key []byte) (i int, exist bool) {
	i = kv.Search(key)
	if i < kv.Len() && cmp.Compare(kv.KeyAt(i), key) == 0 {
	exist = true
	}
	return
	}

	func (kv KeyValue) GetString(key string) (i int, exist bool) {
	return kv.Get([]byte(key))
	}

	func (kv KeyValue) Iterate(fn func(i int, key, value []byte)) {
	for i, x := range kv.entries {
	fn(i, x.key, x.value)
	}
	}

	func (kv KeyValue) IterateString(fn func(i int, key, value string)) {
	kv.Iterate(func(i int, key, value []byte) {
	fn(i, string(key), string(value))
	})
	}

	func (kv KeyValue) IterateShuffled(rnd *rand.Rand, fn func(i int, key, value []byte)) {
	ShuffledIndex(rnd, kv.Len(), 1, func(i int) {
	fn(i, kv.entries[i].key, kv.entries[i].value)
	})
	}

	func (kv KeyValue) IterateShuffledString(rnd *rand.Rand, fn func(i int, key, value string)) {
	kv.IterateShuffled(rnd, func(i int, key, value []byte) {
	fn(i, string(key), string(value))
	})
	}

	func (kv KeyValue) IterateInexact(fn func(i int, key_, key, value []byte)) {
	for i := range kv.entries {
	key_, key, value := kv.IndexInexact(i)
	fn(i, key_, key, value)
	}
	}

	func (kv KeyValue) IterateInexactString(fn func(i int, key_, key, value string)) {
	kv.IterateInexact(func(i int, key_, key, value []byte) {
	fn(i, string(key_), string(key), string(value))
	})
	}

	func (kv KeyValue) Clone() KeyValue {
	return KeyValue{append([]KeyValueEntry{}, kv.entries...), kv.nbytes}
	}

	func (kv KeyValue) Slice(start, limit int) KeyValue {
	if start < 0 \|\| limit > kv.Len() {
	panic(fmt.Sprintf("Slice %d .. %d: out of range", start, limit))
	} else if limit < start {
	panic(fmt.Sprintf("Slice %d .. %d: invalid range", start, limit))
	}
	return KeyValue{append([]KeyValueEntry{}, kv.entries[start:limit]...), kv.nbytes}
	}

	func (kv KeyValue) SliceKey(start, limit []byte) KeyValue {
	start_ := 0
	limit_ := kv.Len()
	if start != nil {
	start_ = kv.Search(start)
	}
	if limit != nil {
	limit_ = kv.Search(limit)
	}
	return kv.Slice(start_, limit_)
	}

	func (kv KeyValue) SliceKeyString(start, limit string) KeyValue {
	return kv.SliceKey([]byte(start), []byte(limit))
	}

	func (kv KeyValue) SliceRange(r *util.Range) KeyValue {
	if r != nil {
	return kv.SliceKey(r.Start, r.Limit)
	}
	return kv.Clone()
	}

	func (kv KeyValue) Range(start, limit int) (r util.Range) {
	if kv.Len() > 0 {
	if start == kv.Len() {
	r.Start = BytesAfter(kv.KeyAt(start - 1))
	} else {
	r.Start = kv.KeyAt(start)
	}
	}
	if limit < kv.Len() {
	r.Limit = kv.KeyAt(limit)
	}
	return
	}

	func KeyValue_EmptyKey() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("", "v")
	return kv
	}

	func KeyValue_EmptyValue() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("abc", "")
	kv.PutString("abcd", "")
	return kv
	}

	func KeyValue_OneKeyValue() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("abc", "v")
	return kv
	}

	func KeyValue_BigValue() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("big1", strings.Repeat("1", 200000))
	return kv
	}

	func KeyValue_SpecialKey() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("\xff\xff", "v3")
	return kv
	}

	func KeyValue_MultipleKeyValue() *KeyValue {
	kv := &KeyValue{}
	kv.PutString("a", "v")
	kv.PutString("aa", "v1")
	kv.PutString("aaa", "v2")
	kv.PutString("aaacccccccccc", "v2")
	kv.PutString("aaaccccccccccd", "v3")
	kv.PutString("aaaccccccccccf", "v4")
	kv.PutString("aaaccccccccccfg", "v5")
	kv.PutString("ab", "v6")
	kv.PutString("abc", "v7")
	kv.PutString("abcd", "v8")
	kv.PutString("accccccccccccccc", "v9")
	kv.PutString("b", "v10")
	kv.PutString("bb", "v11")
	kv.PutString("bc", "v12")
	kv.PutString("c", "v13")
	kv.PutString("c1", "v13")
	kv.PutString("czzzzzzzzzzzzzz", "v14")
	kv.PutString("fffffffffffffff", "v15")
	kv.PutString("g11", "v15")
	kv.PutString("g111", "v15")
	kv.PutString("g111\xff", "v15")
	kv.PutString("zz", "v16")
	kv.PutString("zzzzzzz", "v16")
	kv.PutString("zzzzzzzzzzzzzzzz", "v16")
	return kv
	}

	var keymap = []byte("012345678ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy")

	func KeyValue_Generate(rnd rand.Rand, n, minlen, maxlen, vminlen, vmaxlen int) KeyValue {
	if rnd == nil {
	rnd = NewRand()
	}
	if maxlen < minlen {
	panic("max len should >= min len")
	}

	rrand := func(min, max int) int {
	if min == max {
	return max
	}
	return rnd.Intn(max-min) + min
	}

	kv := &KeyValue{}
	endC := byte(len(keymap) - 1)
	gen := make([]byte, 0, maxlen)
	for i := 0; i < n; i++ {
	m := rrand(minlen, maxlen)
	last := gen
	retry:
	gen = last[:m]
	if k := len(last); m > k {
	for j := k; j < m; j++ {
	gen[j] = 0
	}
	} else {
	for j := m - 1; j >= 0; j-- {
	c := last[j]
	if c == endC {
	continue
	}
	gen[j] = c + 1
	for j += 1; j < m; j++ {
	gen[j] = 0
	}
	goto ok
	}
	if m < maxlen {
	m++
	goto retry
	}
	panic(fmt.Sprintf("only able to generate %d keys out of %d keys, try increasing max len", kv.Len(), n))
	ok:
	}
	key := make([]byte, m)
	for j := 0; j < m; j++ {
	key[j] = keymap[gen[j]]
	}
	value := make([]byte, rrand(vminlen, vmaxlen))
	for n := copy(value, []byte(fmt.Sprintf("v%d", i))); n < len(value); n++ {
	value[n] = 'x'
	}
	kv.Put(key, value)
	}
	return kv
	}