skip empty pages during cursor seek

This commit fixes an issue where keys are skipped by cursors after
deletions occur in a bucket. This occurred because the cursor seeks
to the leaf page but does not check if it is empty.

Fixes #429, #450

1 files changed, 43 insertions, 0 deletions

diff --git a/cursor_test.go b/cursor_test.go
index b12e1f9..d748852 100644
--- a/cursor_test.go
+++ b/cursor_test.go
@@ -303,6 +303,49 @@ func TestCursor_Restart(t *testing.T) {
 	tx.Rollback()
 }
 
+// Ensure that a cursor can skip over empty pages that have been deleted.
+func TestCursor_First_EmptyPages(t *testing.T) {
+	db := NewTestDB()
+	defer db.Close()
+
+	// Create 1000 keys in the "widgets" bucket.
+	db.Update(func(tx *bolt.Tx) error {
+		b, err := tx.CreateBucket([]byte("widgets"))
+		if err != nil {
+			t.Fatal(err)
+		}
+
+		for i := 0; i < 1000; i++ {
+			if err := b.Put(u64tob(uint64(i)), []byte{}); err != nil {
+				t.Fatal(err)
+			}
+		}
+
+		return nil
+	})
+
+	// Delete half the keys and then try to iterate.
+	db.Update(func(tx *bolt.Tx) error {
+		b := tx.Bucket([]byte("widgets"))
+		for i := 0; i < 600; i++ {
+			if err := b.Delete(u64tob(uint64(i))); err != nil {
+				t.Fatal(err)
+			}
+		}
+
+		c := b.Cursor()
+		var n int
+		for k, _ := c.First(); k != nil; k, _ = c.Next() {
+			n++
+		}
+		if n != 400 {
+			t.Fatalf("unexpected key count: %d", n)
+		}
+
+		return nil
+	})
+}
+
 // Ensure that a Tx can iterate over all elements in a bucket.
 func TestCursor_QuickCheck(t *testing.T) {
 	f := func(items testdata) bool {