Add nested buckets.

This commit adds the ability to create buckets inside of other buckets.
It also replaces the buckets page with a root bucket.

Fixes #56.

1 files changed, 55 insertions, 25 deletions

diff --git a/cursor.go b/cursor.go
index 2887791..f6dc79c 100644
--- a/cursor.go
+++ b/cursor.go
@@ -8,39 +8,47 @@ import (
 // Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.
 // Cursors can be obtained from a transaction and are valid as long as the transaction is open.
 type Cursor struct {
-	tx    *Tx
-	root  pgid
-	stack []elemRef
+	bucket *Bucket
+	stack  []elemRef
 }
 
 // First moves the cursor to the first 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) First() (key []byte, value []byte) {
-	_assert(c.tx.db != nil, "tx closed")
+	_assert(c.bucket.tx.db != nil, "tx closed")
 	c.stack = c.stack[:0]
-	p, n := c.tx.pageNode(c.root)
+	p, n := c.bucket.pageNode(c.bucket.root)
 	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 	c.first()
-	return c.keyValue()
+	k, v, flags := c.keyValue()
+	if (flags & uint32(bucketLeafFlag)) != 0 {
+		return k, nil
+	}
+	return k, v
+
 }
 
 // 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) {
-	_assert(c.tx.db != nil, "tx closed")
+	_assert(c.bucket.tx.db != nil, "tx closed")
 	c.stack = c.stack[:0]
-	p, n := c.tx.pageNode(c.root)
+	p, n := c.bucket.pageNode(c.bucket.root)
 	ref := elemRef{page: p, node: n}
 	ref.index = ref.count() - 1
 	c.stack = append(c.stack, ref)
 	c.last()
-	return c.keyValue()
+	k, v, flags := c.keyValue()
+	if (flags & uint32(bucketLeafFlag)) != 0 {
+		return k, nil
+	}
+	return k, v
 }
 
 // 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) {
-	_assert(c.tx.db != nil, "tx closed")
+	_assert(c.bucket.tx.db != nil, "tx closed")
 
 	// 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.
@@ -60,13 +68,17 @@ func (c *Cursor) Next() (key []byte, value []byte) {
 
 	// Move down the stack to find the first element of the first leaf under this branch.
 	c.first()
-	return c.keyValue()
+	k, v, flags := c.keyValue()
+	if (flags & uint32(bucketLeafFlag)) != 0 {
+		return k, nil
+	}
+	return k, v
 }
 
 // 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) {
-	_assert(c.tx.db != nil, "tx closed")
+	_assert(c.bucket.tx.db != nil, "tx closed")
 
 	// 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.
@@ -86,25 +98,43 @@ func (c *Cursor) Prev() (key []byte, value []byte) {
 
 	// Move down the stack to find the last element of the last leaf under this branch.
 	c.last()
-	return c.keyValue()
+	k, v, flags := c.keyValue()
+	if (flags & uint32(bucketLeafFlag)) != 0 {
+		return k, nil
+	}
+	return k, v
 }
 
 // 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.
 func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
-	_assert(c.tx.db != nil, "tx closed")
+	k, v, flags := c.seek(seek)
+	if k == nil {
+		return nil, nil
+	} else if (flags & uint32(bucketLeafFlag)) != 0 {
+		return k, nil
+	}
+	return k, v
+}
+
+// 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.
+func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
+	_assert(c.bucket.tx.db != nil, "tx closed")
 
 	// Start from root page/node and traverse to correct page.
 	c.stack = c.stack[:0]
-	c.search(seek, c.root)
+	c.search(seek, c.bucket.root)
 	ref := &c.stack[len(c.stack)-1]
 
 	// If the cursor is pointing to the end of page/node then return nil.
 	if ref.index >= ref.count() {
-		return nil, nil
+		return nil, nil, 0
 	}
 
+	// If this is a bucket then return a nil value.
 	return c.keyValue()
 }
 
@@ -124,7 +154,7 @@ func (c *Cursor) first() {
 		} else {
 			pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
 		}
-		p, n := c.tx.pageNode(pgid)
+		p, n := c.bucket.pageNode(pgid)
 		c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 	}
 }
@@ -145,7 +175,7 @@ func (c *Cursor) last() {
 		} else {
 			pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
 		}
-		p, n := c.tx.pageNode(pgid)
+		p, n := c.bucket.pageNode(pgid)
 
 		var nextRef = elemRef{page: p, node: n}
 		nextRef.index = nextRef.count() - 1
@@ -155,7 +185,7 @@ func (c *Cursor) last() {
 
 // search recursively performs a binary search against a given page/node until it finds a given key.
 func (c *Cursor) search(key []byte, pgid pgid) {
-	p, n := c.tx.pageNode(pgid)
+	p, n := c.bucket.pageNode(pgid)
 	if p != nil {
 		_assert((p.flags&(branchPageFlag|leafPageFlag)) != 0, "invalid page type: "+p.typ())
 	}
@@ -241,25 +271,25 @@ func (c *Cursor) nsearch(key []byte) {
 }
 
 // keyValue returns the key and value of the current leaf element.
-func (c *Cursor) keyValue() ([]byte, []byte) {
+func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
 	ref := &c.stack[len(c.stack)-1]
 	if ref.count() == 0 || ref.index >= ref.count() {
-		return nil, nil
+		return nil, nil, 0
 	}
 
 	// Retrieve value from node.
 	if ref.node != nil {
 		inode := &ref.node.inodes[ref.index]
-		return inode.key, inode.value
+		return inode.key, inode.value, inode.flags
 	}
 
 	// Or retrieve value from page.
 	elem := ref.page.leafPageElement(uint16(ref.index))
-	return elem.key(), elem.value()
+	return elem.key(), elem.value(), elem.flags
 }
 
 // node returns the node that the cursor is currently positioned on.
-func (c *Cursor) node(tx *Tx) *node {
+func (c *Cursor) node() *node {
 	_assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")
 
 	// If the top of the stack is a leaf node then just return it.
@@ -270,7 +300,7 @@ func (c *Cursor) node(tx *Tx) *node {
 	// Start from root and traverse down the hierarchy.
 	var n = c.stack[0].node
 	if n == nil {
-		n = tx.node(c.stack[0].page.id, nil)
+		n = c.bucket.node(c.stack[0].page.id, nil)
 	}
 	for _, ref := range c.stack[:len(c.stack)-1] {
 		_assert(!n.isLeaf, "expected branch node")