Bidirectional cursors.

4 files changed, 134 insertions, 4 deletions

diff --git a/README.md b/README.md
index f99546f..a2cda41 100644
--- a/README.md
+++ b/README.md
@@ -30,11 +30,11 @@ Bolt is inspired by [LMDB](http://symas.com/mdb/) so there are many similarities
 
 There are also several differences between Bolt and LMDB:
 
-1. LMDB supports more additional features such as multi-value keys, fixed length keys, multi-key insert, direct writes, and bi-directional cursors. Bolt only supports basic `Get()`, `Put()`, and `Delete()` operations and unidirectional cursors.
+1. LMDB supports more additional features such as multi-value keys, fixed length keys, multi-key insert, and direct writes. Bolt only supports basic `Get()`, `Put()`, and `Delete()` operations and bidirectional cursors.
 
-2. LMDB databases can be shared between processes. Bolt only allows a single process to use a database at a time.
+2. LMDB databases can be shared between processes. Bolt only allows a single process access.
 
-3. LMDB is written in C and extremely fast. Bolt is written in pure Go and, while it's fast, it is not as fast as LMDB.
+3. LMDB is written in C and extremely fast. Bolt is fast but not as fast as LMDB.
 
 4. LMDB is a more mature library and is used heavily in projects such as [OpenLDAP](http://www.openldap.org/).
 
diff --git a/cursor.go b/cursor.go
index 410bb89..9a527af 100644
--- a/cursor.go
+++ b/cursor.go
@@ -19,11 +19,24 @@ func (c *Cursor) First() (key []byte, value []byte) {
 	if len(c.stack) > 0 {
 		c.stack = c.stack[:0]
 	}
-	c.stack = append(c.stack, pageElementRef{page: c.transaction.page(c.root), index: 0})
+	p := c.transaction.page(c.root)
+	c.stack = append(c.stack, pageElementRef{page: p, index: 0})
 	c.first()
 	return c.keyValue()
 }
 
+// Last moves the cursor to the last item in the bucket and returns its key and value.
+// If the bucket is empty then a nil key and value are returned.
+func (c *Cursor) Last() (key []byte, value []byte) {
+	if len(c.stack) > 0 {
+		c.stack = c.stack[:0]
+	}
+	p := c.transaction.page(c.root)
+	c.stack = append(c.stack, pageElementRef{page: p, index: p.count - 1})
+	c.last()
+	return c.keyValue()
+}
+
 // Next moves the cursor to the next item in the bucket and returns its key and value.
 // If the cursor is at the end of the bucket then a nil key and value are returned.
 func (c *Cursor) Next() (key []byte, value []byte) {
@@ -48,6 +61,30 @@ func (c *Cursor) Next() (key []byte, value []byte) {
 	return c.keyValue()
 }
 
+// Prev moves the cursor to the previous item in the bucket and returns its key and value.
+// If the cursor is at the beginning of the bucket then a nil key and value are returned.
+func (c *Cursor) Prev() (key []byte, value []byte) {
+	// Attempt to move back one element until we're successful.
+	// Move up the stack as we hit the beginning of each page in our stack.
+	for i := len(c.stack) - 1; i >= 0; i-- {
+		elem := &c.stack[i]
+		if elem.index > 0 {
+			elem.index--
+			break
+		}
+		c.stack = c.stack[:i]
+	}
+
+	// If we've hit the end then return nil.
+	if len(c.stack) == 0 {
+		return nil, nil
+	}
+
+	// Move down the stack to find the last element of the last leaf under this branch.
+	c.last()
+	return c.keyValue()
+}
+
 // Seek moves the cursor to a given key and returns it.
 // If the key does not exist then the next key is used. If no keys
 // follow, a nil value is returned.
@@ -80,6 +117,21 @@ func (c *Cursor) first() {
 	}
 }
 
+// last moves the cursor to the last leaf element under the last page in the stack.
+func (c *Cursor) last() {
+	p := c.stack[len(c.stack)-1].page
+	for {
+		// Exit when we hit a leaf page.
+		if (p.flags & leafPageFlag) != 0 {
+			break
+		}
+
+		// Keep adding pages pointing to the last element in the stack.
+		p = c.transaction.page(p.branchPageElement(c.stack[len(c.stack)-1].index).pgid)
+		c.stack = append(c.stack, pageElementRef{page: p, index: p.count - 1})
+	}
+}
+
 // search recursively performs a binary search against a given page until it finds a given key.
 func (c *Cursor) search(key []byte, p *page) {
 	_assert((p.flags&(branchPageFlag|leafPageFlag)) != 0, "invalid page type: "+p.typ())
diff --git a/quick_test.go b/quick_test.go
index 3db0b6c..cda7b30 100644
--- a/quick_test.go
+++ b/quick_test.go
@@ -55,6 +55,12 @@ func (t testdata) Generate(rand *rand.Rand, size int) reflect.Value {
 	return reflect.ValueOf(items)
 }
 
+type revtestdata []testdataitem
+
+func (t revtestdata) Len() int           { return len(t) }
+func (t revtestdata) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }
+func (t revtestdata) Less(i, j int) bool { return bytes.Compare(t[i].Key, t[j].Key) == 1 }
+
 type testdataitem struct {
 	Key   []byte
 	Value []byte
diff --git a/transaction_test.go b/transaction_test.go
index 30274d5..4a7170c 100644
--- a/transaction_test.go
+++ b/transaction_test.go
@@ -109,6 +109,41 @@ func TestTransactionCursorLeafRoot(t *testing.T) {
 	})
 }
 
+// Ensure that a Transaction cursor can iterate in reverse over a single root with a couple elements.
+func TestTransactionCursorLeafRootReverse(t *testing.T) {
+	withOpenDB(func(db *DB, path string) {
+		db.CreateBucket("widgets")
+		db.Put("widgets", []byte("baz"), []byte{})
+		db.Put("widgets", []byte("foo"), []byte{0})
+		db.Put("widgets", []byte("bar"), []byte{1})
+		txn, _ := db.Transaction()
+		c, err := txn.Cursor("widgets")
+		assert.NoError(t, err)
+
+		k, v := c.Last()
+		assert.Equal(t, string(k), "foo")
+		assert.Equal(t, v, []byte{0})
+
+		k, v = c.Prev()
+		assert.Equal(t, string(k), "baz")
+		assert.Equal(t, v, []byte{})
+
+		k, v = c.Prev()
+		assert.Equal(t, string(k), "bar")
+		assert.Equal(t, v, []byte{1})
+
+		k, v = c.Prev()
+		assert.Nil(t, k)
+		assert.Nil(t, v)
+
+		k, v = c.Prev()
+		assert.Nil(t, k)
+		assert.Nil(t, v)
+
+		txn.Close()
+	})
+}
+
 // Ensure that a Transaction cursor can restart from the beginning.
 func TestTransactionCursorRestart(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
@@ -172,3 +207,40 @@ func TestTransactionCursorIterate(t *testing.T) {
 	}
 	fmt.Fprint(os.Stderr, "\n")
 }
+
+// Ensure that a transaction can iterate over all elements in a bucket in reverse.
+func TestTransactionCursorIterateReverse(t *testing.T) {
+	f := func(items testdata) bool {
+		withOpenDB(func(db *DB, path string) {
+			// Bulk insert all values.
+			db.CreateBucket("widgets")
+			rwtxn, _ := db.RWTransaction()
+			for _, item := range items {
+				assert.NoError(t, rwtxn.Put("widgets", item.Key, item.Value))
+			}
+			assert.NoError(t, rwtxn.Commit())
+
+			// Sort test data.
+			sort.Sort(revtestdata(items))
+
+			// Iterate over all items and check consistency.
+			var index = 0
+			txn, _ := db.Transaction()
+			c, err := txn.Cursor("widgets")
+			assert.NoError(t, err)
+			for k, v := c.Last(); k != nil && index < len(items); k, v = c.Prev() {
+				assert.Equal(t, k, items[index].Key)
+				assert.Equal(t, v, items[index].Value)
+				index++
+			}
+			assert.Equal(t, len(items), index)
+			txn.Close()
+		})
+		fmt.Fprint(os.Stderr, ".")
+		return true
+	}
+	if err := quick.Check(f, qconfig()); err != nil {
+		t.Error(err)
+	}
+	fmt.Fprint(os.Stderr, "\n")
+}