Merge pull request #154 from benbjohnson/inline-buckets

(wip) Add inline bucket support.

1 files changed, 43 insertions, 3 deletions

diff --git a/node.go b/node.go
index fd737ea..1bc889d 100644
--- a/node.go
+++ b/node.go
@@ -2,6 +2,8 @@ package bolt
 
 import (
 	"bytes"
+	"fmt"
+	"io"
 	"sort"
 	"unsafe"
 )
@@ -191,6 +193,8 @@ func (n *node) write(p *page) {
 		copy(b[0:], item.value)
 		b = b[len(item.value):]
 	}
+
+	// DEBUG ONLY: n.dump(os.Stderr)
 }
 
 // split breaks up a node into smaller nodes, if appropriate.
@@ -261,6 +265,7 @@ func (n *node) spill() error {
 	// Add node's page to the freelist if it's not new.
 	if n.pgid > 0 {
 		tx.db.freelist.free(tx.id(), tx.page(n.pgid))
+		n.pgid = 0
 	}
 
 	// Spill nodes by deepest first.
@@ -273,8 +278,8 @@ func (n *node) spill() error {
 		}
 
 		// Write the node.
-		node.write(p)
 		node.pgid = p.id
+		node.write(p)
 
 		// Insert into parent inodes.
 		if node.parent != nil {
@@ -302,8 +307,8 @@ func (n *node) spill() error {
 		}
 
 		// Write the new root.
-		parent.write(p)
 		parent.pgid = p.id
+		parent.write(p)
 	}
 
 	return nil
@@ -331,7 +336,7 @@ func (n *node) rebalance() {
 		// If root node is a branch and only has one node then collapse it.
 		if !n.isLeaf && len(n.inodes) == 1 {
 			// Move root's child up.
-			child := n.bucket.nodes[n.inodes[0].pgid]
+			child := n.bucket.node(n.inodes[0].pgid, n)
 			n.isLeaf = child.isLeaf
 			n.inodes = child.inodes[:]
 			n.children = child.children
@@ -352,6 +357,16 @@ func (n *node) rebalance() {
 		return
 	}
 
+	// If node has no keys then just remove it.
+	if n.numChildren() == 0 {
+		n.parent.del(n.key)
+		n.parent.removeChild(n)
+		delete(n.bucket.nodes, n.pgid)
+		n.free()
+		n.parent.rebalance()
+		return
+	}
+
 	_assert(n.parent.numChildren() > 1, "parent must have at least 2 children")
 
 	// Destination node is right sibling if idx == 0, otherwise left sibling.
@@ -477,6 +492,31 @@ func (n *node) free() {
 	}
 }
 
+// dump writes the contents of the node for debugging purposes.
+func (n *node) dump(w io.Writer) {
+	// Write node header.
+	var typ = "branch"
+	if n.isLeaf {
+		typ = "leaf"
+	}
+	fmt.Fprintf(w, "[NODE %d {type=%s count=%d}]\n", n.pgid, typ, len(n.inodes))
+
+	// Write out abbreviated version of each item.
+	for _, item := range n.inodes {
+		if n.isLeaf {
+			if item.flags&bucketLeafFlag != 0 {
+				bucket := (*bucket)(unsafe.Pointer(&item.value[0]))
+				fmt.Fprintf(w, "[L \"%s\" -> (bucket root=%d)]\n", item.key, bucket.root)
+			} else {
+				fmt.Fprintf(w, "[L \"%s\" -> \"%s\"]\n", item.key, item.value)
+			}
+		} else {
+			fmt.Fprintf(w, "[B \"%s\" -> pgid=%d]\n", item.key, item.pgid)
+		}
+	}
+	fmt.Fprint(w, "\n")
+}
+
 // inode represents an internal node inside of a node.
 // It can be used to point to elements in a page or point
 // to an element which hasn't been added to a page yet.