diff options
| -rw-r--r-- | assert.go | 12 | ||||
| -rw-r--r-- | bucket.go | 2 | ||||
| -rw-r--r-- | cursor.go | 49 | ||||
| -rw-r--r-- | node.go | 9 | ||||
| -rw-r--r-- | page.go | 6 | ||||
| -rw-r--r-- | rwtransaction.go | 33 |
6 files changed, 74 insertions, 37 deletions
diff --git a/assert.go b/assert.go new file mode 100644 index 0000000..912e484 --- /dev/null +++ b/assert.go @@ -0,0 +1,12 @@ +package bolt + +import "fmt" + +// TODO(benbjohnson): Remove assertions before release. + +// __assert__ will panic with a given formatted message if the given condition is false. +func __assert__(condition bool, msg string, v ...interface{}) { + if !condition { + panic(fmt.Sprintf("assertion failed: " + msg, v...)) + } +} @@ -20,6 +20,6 @@ func (b *Bucket) cursor() *Cursor { return &Cursor{ transaction: b.transaction, root: b.root, - stack: make([]elem, 0), + stack: make([]pageElementRef, 0), } } @@ -8,13 +8,7 @@ import ( type Cursor struct { transaction *Transaction root pgid - stack []elem -} - -// elem represents a node on a page that's on the cursor's stack. -type elem struct { - page *page - index uint16 + stack []pageElementRef } // First moves the cursor to the first item in the bucket and returns its key and data. @@ -41,18 +35,18 @@ func (c *Cursor) Get(key []byte) []byte { } // If our target node isn't the same key as what's passed in then return nil. - if !bytes.Equal(key, c.node().key()) { + if !bytes.Equal(key, c.element().key()) { return nil } - return c.node().value() + return c.element().value() } func (c *Cursor) search(key []byte, p *page) { if (p.flags & (p_branch | p_leaf)) == 0 { panic("invalid page type: " + p.typ()) } - e := elem{page: p} + e := pageElementRef{page: p} c.stack = append(c.stack, e) // If we're on a leaf page then find the specific node. @@ -77,10 +71,10 @@ func (c *Cursor) search(key []byte, p *page) { if !exact && index > 0 { index-- } - e.index = uint16(index) + c.stack[len(c.stack)-1].index = uint16(index) // Recursively search to the next page. - c.search(key, c.transaction.page(inodes[e.index].pgid)) + c.search(key, c.transaction.page(inodes[index].pgid)) } // nsearch searches a leaf node for the index of the node that matches key. @@ -97,8 +91,8 @@ func (c *Cursor) nsearch(key []byte, p *page) { // top returns the page and leaf node that the cursor is currently pointing at. func (c *Cursor) top() (*page, uint16) { - elem := c.stack[len(c.stack)-1] - return elem.page, elem.index + ptr := c.stack[len(c.stack)-1] + return ptr.page, ptr.index } // page returns the page that the cursor is currently pointing at. @@ -106,8 +100,27 @@ func (c *Cursor) page() *page { return c.stack[len(c.stack)-1].page } -// node returns the leaf node that the cursor is currently positioned on. -func (c *Cursor) node() *leafPageElement { - elem := c.stack[len(c.stack)-1] - return elem.page.leafPageElement(elem.index) +// element returns the leaf element that the cursor is currently positioned on. +func (c *Cursor) element() *leafPageElement { + ref := c.stack[len(c.stack)-1] + return ref.page.leafPageElement(ref.index) +} + +// node returns the node that the cursor is currently positioned on. +func (c *Cursor) node(t *RWTransaction) *node { + if len(c.stack) == 0 { + return nil + } + + // Start from root and traverse down the hierarchy. + n := t.node(c.stack[0].page.id, nil) + for _, ref := range c.stack[:len(c.stack)-1] { + __assert__(!n.isLeaf, "expected branch node") + __assert__(ref.page.id == n.pgid, "node/page mismatch a: %d != %d", ref.page.id, n.childAt(ref.index).pgid) + n = n.childAt(ref.index) + } + __assert__(n.isLeaf, "expected leaf node") + __assert__(n.pgid == c.stack[len(c.stack)-1].page.id, "node/page mismatch b: %d != %d", n.pgid, c.stack[len(c.stack)-1].page.id) + return n } + @@ -8,6 +8,7 @@ import ( // node represents an in-memory, deserialized page. type node struct { + transaction *RWTransaction isLeaf bool key []byte depth int @@ -43,6 +44,12 @@ func (n *node) root() *node { return n.parent.root() } +// childAt returns the child node at a given index. +func (n *node) childAt(index uint16) *node { + __assert__(!n.isLeaf, "invalid childAt(%d) on a leaf node", index) + return n.transaction.node(n.inodes[index].pgid, n) +} + // put inserts a key/value. func (n *node) put(oldKey, newKey, value []byte, pgid pgid) { // Find insertion index. @@ -160,7 +167,7 @@ func (n *node) split(pageSize int) []*node { if len(current.inodes) >= minKeysPerPage && i < len(inodes)-minKeysPerPage && size+elemSize > threshold { size = pageHeaderSize nodes = append(nodes, current) - current = &node{isLeaf: n.isLeaf} + current = &node{transaction: n.transaction, isLeaf: n.isLeaf} } size += elemSize @@ -33,6 +33,12 @@ type page struct { ptr uintptr } +// pageElementRef represents a reference to an element on a given page. +type pageElementRef struct { + page *page + index uint16 +} + // typ returns a human readable page type string used for debugging. func (p *page) typ() string { if (p.flags & p_branch) != 0 { diff --git a/rwtransaction.go b/rwtransaction.go index fed59a6..ed44e3d 100644 --- a/rwtransaction.go +++ b/rwtransaction.go @@ -74,7 +74,7 @@ func (t *RWTransaction) Put(name string, key []byte, value []byte) error { c.Get(key) // Insert the key/value. - t.node(c.stack).put(key, key, value, 0) + c.node(t).put(key, key, value, 0) return nil } @@ -90,7 +90,7 @@ func (t *RWTransaction) Delete(name string, key []byte) error { c.Get(key) // Delete the node if we have a matching key. - t.node(c.stack).del(key) + c.node(t).del(key) return nil } @@ -186,7 +186,7 @@ func (t *RWTransaction) spill() { // If this is a root node that split then create a parent node. if n.parent == nil && len(newNodes) > 1 { - n.parent = &node{isLeaf: false} + n.parent = &node{transaction: t, isLeaf: false} nodes = append(nodes, n.parent) } @@ -261,25 +261,24 @@ func (t *RWTransaction) writeMeta() error { return nil } -// node retrieves a node based a cursor stack. -func (t *RWTransaction) node(stack []elem) *node { - if len(stack) == 0 { - return nil - } +// TODO(benbjohnson): Look up node by page id instead of by stack. Determine depth recursively by parent. +// TODO(benbjohnson): prevSibling() +// TODO(benbjohnson): nextSibling() - // Retrieve branch if it has already been fetched. - e := &stack[len(stack)-1] - id := e.page.id - if n := t.nodes[id]; n != nil { +// node creates a node from a page and associates it with a given parent. +func (t *RWTransaction) node(pgid pgid, parent *node) *node { + // Retrieve node if it has already been fetched. + if n := t.nodes[pgid]; n != nil { return n } // Otherwise create a branch and cache it. - n := &node{} - n.read(t.page(id)) - n.depth = len(stack) - 1 - n.parent = t.node(stack[:len(stack)-1]) - t.nodes[id] = n + n := &node{transaction: t, parent: parent} + if n.parent != nil { + n.depth = n.parent.depth + 1 + } + n.read(t.page(pgid)) + t.nodes[pgid] = n return n } |