Add branch.split()

1 files changed, 64 insertions, 0 deletions

diff --git a/branch.go b/branch.go
index c9fc7ca..7cba9d4 100644
--- a/branch.go
+++ b/branch.go
@@ -11,6 +11,15 @@ type branch struct {
 	items branchItems
 }
 
+// size returns the size of the branch after serialization.
+func (b *branch) size() int {
+	var size int = pageHeaderSize
+	for _, item := range b.items {
+		size += bnodeSize + len(item.key)
+	}
+	return size
+}
+
 // put adds a new node or replaces an existing node.
 func (b *branch) put(id pgid, newid pgid, key []byte, replace bool) {
 	var index int
@@ -40,10 +49,65 @@ func (b *branch) read(page *page) {
 	for i := 0; i < ncount; i++ {
 		bnode := &bnodes[i]
 		item := &b.items[i]
+		item.pgid = bnode.pgid
 		item.key = bnode.key()
 	}
 }
 
+// write writes the items onto a branch page.
+func (b *branch) write(p *page) {
+	// Initialize page.
+	p.flags |= p_branch
+	p.count = uint16(len(b.items))
+
+	// Loop over each item and write it to the page.
+	bnodes := (*[maxNodesPerPage]bnode)(unsafe.Pointer(&p.ptr))
+	buf := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[lnodeSize*len(b.items):]
+	for index, item := range b.items {
+		// Write node.
+		bnode := &bnodes[index]
+		bnode.pgid = item.pgid
+		bnode.pos = uint32(uintptr(unsafe.Pointer(&buf[0])) - uintptr(unsafe.Pointer(bnode)))
+		bnode.ksize = uint32(len(item.key))
+
+		// Write key to the end of the page.
+		copy(buf[0:], item.key)
+		buf = buf[len(item.key):]
+	}
+}
+
+// split divides up the noes in the branch into appropriately sized groups.
+func (b *branch) split(pageSize int) []*branch {
+	// Ignore the split if the page doesn't have at least enough nodes for
+	// multiple pages or if the data can fit on a single page.
+	if len(b.items) <= (minKeysPerPage * 2) || b.size() < pageSize {
+		return []*branch{b}
+	}
+
+	// Set fill threshold to 50%.
+	threshold := pageSize / 2
+
+	// Otherwise group into smaller pages and target a given fill size.
+	size := 0
+	current := &branch{}
+	branches := make([]*branch, 0)
+
+	for index, item := range b.items {
+		nodeSize := bnodeSize + len(item.key)
+
+		if (len(current.items) >= minKeysPerPage && index < len(b.items)-minKeysPerPage && size+nodeSize > threshold) {
+			size = pageHeaderSize
+			branches = append(branches, current)
+			current = &branch{}
+		}
+
+		size += nodeSize
+		current.items = append(current.items, item)
+	}
+	branches = append(branches, current)
+
+	return branches
+}
 
 type branchItems []branchItem