table: fix Reader.Find() that incorrectly returns if key sought is equal to shortened index key
Fixes #153.
diff --git a/leveldb/external_test.go b/leveldb/external_test.go
index 53d6038..669d77f 100644
--- a/leveldb/external_test.go
+++ b/leveldb/external_test.go
@@ -32,7 +32,7 @@
db := newTestingDB(o, nil, nil)
t := testutil.DBTesting{
DB: db,
- Deleted: testutil.KeyValue_Generate(nil, 500, 1, 50, 5, 5).Clone(),
+ Deleted: testutil.KeyValue_Generate(nil, 500, 1, 1, 50, 5, 5).Clone(),
}
testutil.DoDBTesting(&t)
db.TestClose()
@@ -66,7 +66,7 @@
Expect(err).NotTo(HaveOccurred())
t0 := &testutil.DBTesting{
DB: tr,
- Deleted: testutil.KeyValue_Generate(nil, 200, 1, 50, 5, 5).Clone(),
+ Deleted: testutil.KeyValue_Generate(nil, 200, 1, 1, 50, 5, 5).Clone(),
}
testutil.DoDBTesting(t0)
testutil.TestGet(tr, t0.Present)
diff --git a/leveldb/iterator/array_iter_test.go b/leveldb/iterator/array_iter_test.go
index 1ed6d07..f16d014 100644
--- a/leveldb/iterator/array_iter_test.go
+++ b/leveldb/iterator/array_iter_test.go
@@ -17,7 +17,7 @@
Describe("Array iterator", func() {
It("Should iterates and seeks correctly", func() {
// Build key/value.
- kv := testutil.KeyValue_Generate(nil, 70, 1, 5, 3, 3)
+ kv := testutil.KeyValue_Generate(nil, 70, 1, 1, 5, 3, 3)
// Test the iterator.
t := testutil.IteratorTesting{
diff --git a/leveldb/iterator/indexed_iter_test.go b/leveldb/iterator/indexed_iter_test.go
index f37e34e..fde8016 100644
--- a/leveldb/iterator/indexed_iter_test.go
+++ b/leveldb/iterator/indexed_iter_test.go
@@ -52,7 +52,7 @@
for _, x := range n {
sum += x
}
- kv := testutil.KeyValue_Generate(nil, sum, 1, 10, 4, 4)
+ kv := testutil.KeyValue_Generate(nil, sum, 1, 1, 10, 4, 4)
for i, j := 0, 0; i < len(n); i++ {
for x := n[i]; x > 0; x-- {
key, value := kv.Index(j)
diff --git a/leveldb/iterator/merged_iter_test.go b/leveldb/iterator/merged_iter_test.go
index a992f79..ee40881 100644
--- a/leveldb/iterator/merged_iter_test.go
+++ b/leveldb/iterator/merged_iter_test.go
@@ -24,7 +24,7 @@
// Build key/value.
filledKV := make([]testutil.KeyValue, filled)
- kv := testutil.KeyValue_Generate(nil, 100, 1, 10, 4, 4)
+ kv := testutil.KeyValue_Generate(nil, 100, 1, 1, 10, 4, 4)
kv.Iterate(func(i int, key, value []byte) {
filledKV[rnd.Intn(filled)].Put(key, value)
})
diff --git a/leveldb/memdb/memdb_test.go b/leveldb/memdb/memdb_test.go
index 5dd6dbc..3f0a31e 100644
--- a/leveldb/memdb/memdb_test.go
+++ b/leveldb/memdb/memdb_test.go
@@ -73,7 +73,7 @@
db := New(comparer.DefaultComparer, 0)
t := testutil.DBTesting{
DB: db,
- Deleted: testutil.KeyValue_Generate(nil, 1000, 1, 30, 5, 5).Clone(),
+ Deleted: testutil.KeyValue_Generate(nil, 1000, 1, 1, 30, 5, 5).Clone(),
PostFn: func(t *testutil.DBTesting) {
Expect(db.Len()).Should(Equal(t.Present.Len()))
Expect(db.Size()).Should(Equal(t.Present.Size()))
diff --git a/leveldb/table/reader.go b/leveldb/table/reader.go
index 1edf4e2..67de650 100644
--- a/leveldb/table/reader.go
+++ b/leveldb/table/reader.go
@@ -61,7 +61,7 @@
func (b *block) seek(cmp comparer.Comparer, rstart, rlimit int, key []byte) (index, offset int, err error) {
index = sort.Search(b.restartsLen-rstart-(b.restartsLen-rlimit), func(i int) bool {
offset := int(binary.LittleEndian.Uint32(b.data[b.restartsOffset+4*(rstart+i):]))
- offset += 1 // shared always zero, since this is a restart point
+ offset++ // shared always zero, since this is a restart point
v1, n1 := binary.Uvarint(b.data[offset:]) // key length
_, n2 := binary.Uvarint(b.data[offset+n1:]) // value length
m := offset + n1 + n2
@@ -356,7 +356,7 @@
i.value = nil
offset := i.block.restartOffset(ri)
if offset == i.offset {
- ri -= 1
+ ri--
if ri < 0 {
i.dir = dirSOI
return false
@@ -826,18 +826,21 @@
index := r.newBlockIter(indexBlock, nil, nil, true)
defer index.Release()
+
if !index.Seek(key) {
- err = index.Error()
- if err == nil {
+ if err = index.Error(); err == nil {
err = ErrNotFound
}
return
}
+
dataBH, n := decodeBlockHandle(index.Value())
if n == 0 {
r.err = r.newErrCorruptedBH(r.indexBH, "bad data block handle")
- return
+ return nil, nil, r.err
}
+
+ // The filter should only used for exact match.
if filtered && r.filter != nil {
filterBlock, frel, ferr := r.getFilterBlock(true)
if ferr == nil {
@@ -847,30 +850,53 @@
}
frel.Release()
} else if !errors.IsCorrupted(ferr) {
- err = ferr
+ return nil, nil, ferr
+ }
+ }
+
+ data := r.getDataIter(dataBH, nil, r.verifyChecksum, !ro.GetDontFillCache())
+ if !data.Seek(key) {
+ data.Release()
+ if err = data.Error(); err != nil {
+ return
+ }
+
+ // The nearest greater-than key is the first key of the next block.
+ if !index.Next() {
+ if err = index.Error(); err == nil {
+ err = ErrNotFound
+ }
+ return
+ }
+
+ dataBH, n = decodeBlockHandle(index.Value())
+ if n == 0 {
+ r.err = r.newErrCorruptedBH(r.indexBH, "bad data block handle")
+ return nil, nil, r.err
+ }
+
+ data = r.getDataIter(dataBH, nil, r.verifyChecksum, !ro.GetDontFillCache())
+ if !data.Next() {
+ data.Release()
+ if err = data.Error(); err == nil {
+ err = ErrNotFound
+ }
return
}
}
- data := r.getDataIter(dataBH, nil, r.verifyChecksum, !ro.GetDontFillCache())
- defer data.Release()
- if !data.Seek(key) {
- err = data.Error()
- if err == nil {
- err = ErrNotFound
- }
- return
- }
- // Don't use block buffer, no need to copy the buffer.
+
+ // Key doesn't use block buffer, no need to copy the buffer.
rkey = data.Key()
if !noValue {
if r.bpool == nil {
value = data.Value()
} else {
- // Use block buffer, and since the buffer will be recycled, the buffer
- // need to be copied.
+ // Value does use block buffer, and since the buffer will be
+ // recycled, it need to be copied.
value = append([]byte{}, data.Value()...)
}
}
+ data.Release()
return
}
@@ -1039,9 +1065,8 @@
if errors.IsCorrupted(err) {
r.err = err
return r, nil
- } else {
- return nil, err
}
+ return nil, err
}
// Set data end.
@@ -1086,9 +1111,8 @@
if errors.IsCorrupted(err) {
r.err = err
return r, nil
- } else {
- return nil, err
}
+ return nil, err
}
if r.filter != nil {
r.filterBlock, err = r.readFilterBlock(r.filterBH)
diff --git a/leveldb/table/table_test.go b/leveldb/table/table_test.go
index 1bc73ed..232efcd 100644
--- a/leveldb/table/table_test.go
+++ b/leveldb/table/table_test.go
@@ -111,7 +111,7 @@
}
testutil.AllKeyValueTesting(nil, Build, nil, nil)
- Describe("with one key per block", Test(testutil.KeyValue_Generate(nil, 9, 1, 10, 512, 512), func(r *Reader) {
+ Describe("with one key per block", Test(testutil.KeyValue_Generate(nil, 9, 1, 1, 10, 512, 512), func(r *Reader) {
It("should have correct blocks number", func() {
indexBlock, err := r.readBlock(r.indexBH, true)
Expect(err).To(BeNil())
diff --git a/leveldb/testutil/kv.go b/leveldb/testutil/kv.go
index 471d570..608cbf3 100644
--- a/leveldb/testutil/kv.go
+++ b/leveldb/testutil/kv.go
@@ -292,7 +292,7 @@
var keymap = []byte("012345678ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy")
-func KeyValue_Generate(rnd *rand.Rand, n, minlen, maxlen, vminlen, vmaxlen int) *KeyValue {
+func KeyValue_Generate(rnd *rand.Rand, n, incr, minlen, maxlen, vminlen, vmaxlen int) *KeyValue {
if rnd == nil {
rnd = NewRand()
}
@@ -308,7 +308,7 @@
}
kv := &KeyValue{}
- endC := byte(len(keymap) - 1)
+ endC := byte(len(keymap) - incr)
gen := make([]byte, 0, maxlen)
for i := 0; i < n; i++ {
m := rrand(minlen, maxlen)
@@ -325,8 +325,8 @@
if c == endC {
continue
}
- gen[j] = c + 1
- for j += 1; j < m; j++ {
+ gen[j] = c + byte(incr)
+ for j++; j < m; j++ {
gen[j] = 0
}
goto ok
diff --git a/leveldb/testutil/kvtest.go b/leveldb/testutil/kvtest.go
index e6687d6..f7563dc 100644
--- a/leveldb/testutil/kvtest.go
+++ b/leveldb/testutil/kvtest.go
@@ -23,15 +23,15 @@
// Using exact key.
rkey, rvalue, err := db.TestFind(key)
- Expect(err).ShouldNot(HaveOccurred(), "Error for key %q", key)
+ Expect(err).ShouldNot(HaveOccurred(), "Error for exact key %q", key)
Expect(rkey).Should(Equal(key), "Key")
- Expect(rvalue).Should(Equal(value), "Value for key %q", key)
+ Expect(rvalue).Should(Equal(value), "Value for exact key %q", key)
// Using inexact key.
rkey, rvalue, err = db.TestFind(key_)
- Expect(err).ShouldNot(HaveOccurred(), "Error for key %q (%q)", key_, key)
- Expect(rkey).Should(Equal(key))
- Expect(rvalue).Should(Equal(value), "Value for key %q (%q)", key_, key)
+ Expect(err).ShouldNot(HaveOccurred(), "Error for inexact key %q (%q)", key_, key)
+ Expect(rkey).Should(Equal(key), "Key for inexact key %q (%q)", key_, key)
+ Expect(rvalue).Should(Equal(value), "Value for inexact key %q (%q)", key_, key)
})
}
@@ -207,5 +207,6 @@
Describe("with big value", Test(KeyValue_BigValue()))
Describe("with special key", Test(KeyValue_SpecialKey()))
Describe("with multiple key/value", Test(KeyValue_MultipleKeyValue()))
- Describe("with generated key/value", Test(KeyValue_Generate(nil, 120, 1, 50, 10, 120)))
+ Describe("with generated key/value 2-incr", Test(KeyValue_Generate(nil, 120, 2, 1, 50, 10, 120)))
+ Describe("with generated key/value 3-incr", Test(KeyValue_Generate(nil, 120, 3, 1, 50, 10, 120)))
}
