diff options
| -rw-r--r-- | bucket.go | 18 | ||||
| -rw-r--r-- | cursor.go | 45 | ||||
| -rw-r--r-- | db.go | 13 | ||||
| -rw-r--r-- | db_test.go | 1 | ||||
| -rw-r--r-- | meta.go | 4 | ||||
| -rw-r--r-- | page.go | 10 | ||||
| -rw-r--r-- | rwtransaction.go | 53 | ||||
| -rw-r--r-- | rwtransaction_test.go | 48 | ||||
| -rw-r--r-- | transaction.go | 2 | ||||
| -rw-r--r-- | transaction_test.go | 15 |
10 files changed, 156 insertions, 53 deletions
@@ -4,29 +4,27 @@ type Bucket struct { *bucket name string transaction *Transaction - cursors []*Cursor } type bucket struct { root pgid } +// Name returns the name of the bucket. +func (b *Bucket) Name() string { + return b.name +} + // Get retrieves the value for a key in the bucket. func (b *Bucket) Get(key []byte) []byte { - return b.cursor().Get(key) + return b.Cursor().Get(key) } // Cursor creates a new cursor for this bucket. func (b *Bucket) Cursor() *Cursor { - c := b.cursor() - b.cursors = append(b.cursors, c) - return c -} - -// cursor creates a new untracked cursor for this bucket. -func (b *Bucket) cursor() *Cursor { return &Cursor{ - bucket: b, + transaction: b.transaction, + root: b.root, stack: make([]elem, 0), } } @@ -1,7 +1,13 @@ package bolt +import ( + "bytes" + "sort" +) + type Cursor struct { - bucket *Bucket + transaction *Transaction + root pgid stack []elem } @@ -11,10 +17,6 @@ type elem struct { index int } -func (c *Cursor) Bucket() *Bucket { - return c.bucket -} - // First moves the cursor to the first item in the bucket and returns its key and data. func (c *Cursor) First() ([]byte, []byte) { // TODO: Traverse to the first key. @@ -39,11 +41,42 @@ func (c *Cursor) Get(key []byte) []byte { func (c *Cursor) Goto(key []byte) bool { // TODO(benbjohnson): Optimize for specific use cases. - // TODO: Start from root page and traverse to correct page. + // Start from root page and traverse to correct page. + c.stack = c.stack[:0] + c.search(key, c.transaction.page(c.root)) return false } +func (c *Cursor) search(key []byte, p *page) { + e := elem{page: p} + c.stack = append(c.stack, e) + + // If we're on a leaf page then find the specific node. + if (p.flags & p_leaf) != 0 { + c.nsearch(key, p) + return + } + + // Binary search for the correct branch node. + nodes := p.bnodes() + e.index = sort.Search(int(p.count)-1, func(i int) bool { return bytes.Compare(nodes[i+1].key(), key) != -1 }) + + // Recursively search to the next page. + c.search(key, c.transaction.page(nodes[e.index].pgid)) +} + +// nsearch searches a leaf node for the index of the node that matches key. +func (c *Cursor) nsearch(key []byte, p *page) { + e := &c.stack[len(c.stack)-1] + + // Binary search for the correct leaf node index. + nodes := p.lnodes() + e.index = sort.Search(int(p.count), func(i int) bool { + return bytes.Compare(nodes[i].key(), key) != -1 + }) +} + // top returns the page and leaf node that the cursor is currently pointing at. func (c *Cursor) top() (*page, *lnode) { elem := c.stack[len(c.stack)-1] @@ -158,19 +158,19 @@ func (db *DB) init() error { m.version = Version m.pageSize = uint32(db.pageSize) m.version = Version - m.free = 3 - m.sys.root = 4 + m.free = 2 + m.sys.root = 3 } // Write an empty freelist at page 3. p := db.pageInBuffer(buf[:], pgid(2)) - p.id = pgid(3) + p.id = pgid(2) p.flags = p_freelist p.count = 0 // Write an empty leaf page at page 4. p = db.pageInBuffer(buf[:], pgid(3)) - p.id = pgid(4) + p.id = pgid(3) p.flags = p_leaf p.count = 0 @@ -226,7 +226,10 @@ func (db *DB) RWTransaction() (*RWTransaction, error) { } // Create a transaction associated with the database. - t := &RWTransaction{} + t := &RWTransaction{ + branches: make(map[pgid]*branch), + leafs: make(map[pgid]*leaf), + } t.init(db, db.meta()) return t, nil @@ -146,7 +146,6 @@ func TestDBCorruptMeta0(t *testing.T) { // Open the database. err := db.Open(path, 0666) - warn(err) assert.Equal(t, err, &Error{"meta error", InvalidError}) }) } @@ -5,7 +5,7 @@ var ( VersionMismatchError = &Error{"version mismatch", nil} ) -const magic uint32 = 0xC0DEC0DE +const magic uint32 = 0xDEADC0DE const version uint32 = 1 type meta struct { @@ -13,8 +13,8 @@ type meta struct { version uint32 pageSize uint32 pgid pgid - txnid txnid free pgid + txnid txnid sys bucket } @@ -37,11 +37,21 @@ func (p *page) lnode(index int) *lnode { return &((*[maxNodesPerPage]lnode)(unsafe.Pointer(&p.ptr)))[index] } +// lnodes retrieves a list of leaf nodes. +func (p *page) lnodes() []lnode { + return ((*[maxNodesPerPage]lnode)(unsafe.Pointer(&p.ptr)))[:] +} + // bnode retrieves the branch node by index func (p *page) bnode(index int) *bnode { return &((*[maxNodesPerPage]bnode)(unsafe.Pointer(&p.ptr)))[index] } +// bnodes retrieves a list of branch nodes. +func (p *page) bnodes() []bnode { + return ((*[maxNodesPerPage]bnode)(unsafe.Pointer(&p.ptr)))[:] +} + // freelist retrieves a list of page ids from a freelist page. func (p *page) freelist() []pgid { return ((*[maxNodesPerPage]pgid)(unsafe.Pointer(&p.ptr)))[0:p.count] diff --git a/rwtransaction.go b/rwtransaction.go index 5ec0d6e..c57ebdb 100644 --- a/rwtransaction.go +++ b/rwtransaction.go @@ -24,10 +24,12 @@ func (t *RWTransaction) CreateBucket(name string) error { var raw = (*bucket)(unsafe.Pointer(&buf[0])) raw.root = 0 - // Insert new node. - c := t.sys.cursor() + // Move cursor to insertion location. + c := t.sys.Cursor() c.Goto([]byte(name)) - t.leaf(c.page().id).put([]byte(name), buf[:]) + + // Load the leaf node from the cursor and insert the key/value. + t.leaf(c).put([]byte(name), buf[:]) return nil } @@ -57,9 +59,9 @@ func (t *RWTransaction) Put(name string, key []byte, value []byte) error { } // Insert a new node. - c := b.cursor() + c := b.Cursor() c.Goto(key) - t.leaf(c.page().id).put(key, value) + t.leaf(c).put(key, value) return nil } @@ -75,7 +77,6 @@ func (t *RWTransaction) Delete(key []byte) error { func (t *RWTransaction) Commit() error { // TODO(benbjohnson): Use vectorized I/O to write out dirty pages. - // TODO: Flush data. // TODO: Update meta. @@ -104,18 +105,44 @@ func (t *RWTransaction) allocate(size int) (*page, error) { return nil, nil } -// leaf returns a deserialized leaf page. -func (t *RWTransaction) leaf(id pgid) *leaf { - if t.leafs != nil { - if l := t.leafs[id]; l != nil { - return l - } +// leaf retrieves a leaf object based on the current position of a cursor. +func (t *RWTransaction) leaf(c *Cursor) *leaf { + e := c.stack[len(c.stack)-1] + id := e.page.id + + // Retrieve leaf if it has already been fetched. + if l := t.leafs[id]; l != nil { + return l } - // Read raw page and deserialize. + // Otherwise create a leaf and cache it. l := &leaf{} l.read(t.page(id)) + l.parent = t.branch(c.stack[:len(c.stack)-1]) t.leafs[id] = l return l } + +// branch retrieves a branch object based a cursor stack. +// This should only be called from leaf(). +func (t *RWTransaction) branch(stack []elem) *branch { + if len(stack) == 0 { + return nil + } + + // Retrieve branch if it has already been fetched. + e := &stack[len(stack)-1] + id := e.page.id + if b := t.branches[id]; b != nil { + return b + } + + // Otherwise create a branch and cache it. + b := &branch{} + b.read(t.page(id)) + b.parent = t.branch(stack[:len(stack)-1]) + t.branches[id] = b + + return b +} diff --git a/rwtransaction_test.go b/rwtransaction_test.go new file mode 100644 index 0000000..19952e8 --- /dev/null +++ b/rwtransaction_test.go @@ -0,0 +1,48 @@ +package bolt + +import ( + "testing" + + "github.com/stretchr/testify/assert" +) + +// Ensure that a RWTransaction can be retrieved. +func TestRWTransaction(t *testing.T) { + withOpenDB(func(db *DB, path string) { + txn, err := db.RWTransaction() + assert.NotNil(t, txn) + assert.NoError(t, err) + }) +} + +// Ensure that a bucket can be created and retrieved. +func TestTransactionCreateBucket(t *testing.T) { + withOpenDB(func(db *DB, path string) { + // Create a bucket. + txn, _ := db.RWTransaction() + err := txn.CreateBucket("widgets") + assert.NoError(t, err) + + // Commit the transaction. + err = txn.Commit() + assert.NoError(t, err) + + /* + // Open a separate read-only transaction. + rtxn, err := db.Transaction() + assert.NotNil(t, txn) + assert.NoError(t, err) + + b, err := rtxn.Bucket("widgets") + assert.NoError(t, err) + if assert.NotNil(t, b) { + assert.Equal(t, b.Name(), "widgets") + } + */ + }) +} + +// Ensure that an existing bucket cannot be created. +func TestTransactionCreateExistingBucket(t *testing.T) { + t.Skip("pending") +} diff --git a/transaction.go b/transaction.go index 171508f..3b03328 100644 --- a/transaction.go +++ b/transaction.go @@ -54,7 +54,7 @@ func (t *Transaction) Bucket(name string) *Bucket { } // Retrieve bucket data from the system bucket. - value := t.sys.cursor().Get([]byte(name)) + value := t.sys.Cursor().Get([]byte(name)) if value == nil { return nil } diff --git a/transaction_test.go b/transaction_test.go deleted file mode 100644 index e3d2e87..0000000 --- a/transaction_test.go +++ /dev/null @@ -1,15 +0,0 @@ -package bolt - -import ( - "testing" -) - -// Ensure that a bucket can be created and retrieved. -func TestTransactionCreateBucket(t *testing.T) { - t.Skip("pending") -} - -// Ensure that an existing bucket cannot be created. -func TestTransactionCreateExistingBucket(t *testing.T) { - t.Skip("pending") -} |