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

2 files changed, 78 insertions, 19 deletions

diff --git a/cursor.go b/cursor.go
index 006c548..1be9f35 100644
--- a/cursor.go
+++ b/cursor.go
@@ -34,6 +34,13 @@ func (c *Cursor) First() (key []byte, value []byte) {
 	p, n := c.bucket.pageNode(c.bucket.root)
 	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 	c.first()
+
+	// If we land on an empty page then move to the next value.
+	// https://github.com/boltdb/bolt/issues/450
+	if c.stack[len(c.stack)-1].count() == 0 {
+		c.next()
+	}
+
 	k, v, flags := c.keyValue()
 	if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
@@ -209,28 +216,37 @@ func (c *Cursor) last() {
 // next moves to the next leaf element and returns the key and value.
 // If the cursor is at the last leaf element then it stays there and returns nil.
 func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
-	// Attempt to move over one element until we're successful.
-	// Move up the stack as we hit the end of each page in our stack.
-	var i int
-	for i = len(c.stack) - 1; i >= 0; i-- {
-		elem := &c.stack[i]
-		if elem.index < elem.count()-1 {
-			elem.index++
-			break
+	for {
+		// Attempt to move over one element until we're successful.
+		// Move up the stack as we hit the end of each page in our stack.
+		var i int
+		for i = len(c.stack) - 1; i >= 0; i-- {
+			elem := &c.stack[i]
+			if elem.index < elem.count()-1 {
+				elem.index++
+				break
+			}
 		}
-	}
 
-	// If we've hit the root page then stop and return. This will leave the
-	// cursor on the last element of the last page.
-	if i == -1 {
-		return nil, nil, 0
-	}
+		// If we've hit the root page then stop and return. This will leave the
+		// cursor on the last element of the last page.
+		if i == -1 {
+			return nil, nil, 0
+		}
 
-	// Otherwise start from where we left off in the stack and find the
-	// first element of the first leaf page.
-	c.stack = c.stack[:i+1]
-	c.first()
-	return c.keyValue()
+		// Otherwise start from where we left off in the stack and find the
+		// first element of the first leaf page.
+		c.stack = c.stack[:i+1]
+		c.first()
+
+		// If this is an empty page then restart and move back up the stack.
+		// https://github.com/boltdb/bolt/issues/450
+		if c.stack[len(c.stack)-1].count() == 0 {
+			continue
+		}
+
+		return c.keyValue()
+	}
 }
 
 // search recursively performs a binary search against a given page/node until it finds a given key.
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 {