go - bytewise compare varint encoded int64's -
i'm using levigo, leveldb bindings go. keys int64's , need kept sorted. default, leveldb uses bytewise comparator i'm trying use varint encoding.
func i2b(x int64) []byte { b := make([]byte, binary.maxvarintlen64) n := binary.putvarint(b, x) return key[:n] } my keys not being sorted correctly. wrote following test.
var prev int64 = 0 := int64(1); < 1e5; i++ { if bytes.compare(i2b(i), i2b(prev)) <= 0 { log.fatalf("bytewise: %d > %d", b2i(prev), i) } prev = } output: bytewise: 127 > 128
i'm not sure problem is. doing encoding wrong? varint not right encoding use?
edit:
bigendian fixed width encoding bytewise comparable
func i2b(x int64) []byte { b := make([]byte, 8) binary.bigendian.putuint64(b, uint64(x)) return b }
the varint encoding not bytewise comparable* wrt order of values caries. 1 option how write ordering/collating function (cmp bellow) example:
package main import ( "encoding/binary" "log" ) func i2b(x int64) []byte { var b [binary.maxvarintlen64]byte return b[:binary.putvarint(b[:], x)] } func cmp(a, b []byte) int64 { x, n := binary.varint(a) if n < 0 { log.fatal(n) } y, n := binary.varint(b) if n < 0 { log.fatal(n) } return x - y } func main() { var prev int64 = 0 := int64(1); < 1e5; i++ { if cmp(i2b(i), i2b(prev)) <= 0 { log.fatal("fail") } prev = } } (*) reason (also) bit fiddling performed.
Comments
Post a Comment