From a942c1d1686f2af42a8a2f3d59d7e1b5afd0922a Mon Sep 17 00:00:00 2001 From: Ben Johnson Date: Tue, 28 Jan 2014 15:16:22 -0500 Subject: Add tpage.put() test. --- db.go | 2 +- db_test.go | 1 - mnode.go | 9 ---- mpage.go | 125 ------------------------------------------------------ rwtransaction.go | 18 ++++---- tnode.go | 8 ++++ tpage.go | 127 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ tpage_test.go | 35 +++++++++++++++ 8 files changed, 180 insertions(+), 145 deletions(-) delete mode 100644 mnode.go delete mode 100644 mpage.go create mode 100644 tnode.go create mode 100644 tpage.go create mode 100644 tpage_test.go diff --git a/db.go b/db.go index 4da4540..275c4f5 100644 --- a/db.go +++ b/db.go @@ -115,7 +115,7 @@ func (db *DB) mmap() error { info, err := db.file.Stat() if err != nil { return &Error{"mmap stat error", err} - } else if int(info.Size()) < db.pageSize * 2 { + } else if int(info.Size()) < db.pageSize*2 { return &Error{"file size too small", err} } size := int(info.Size()) diff --git a/db_test.go b/db_test.go index a68f64d..20ed51c 100644 --- a/db_test.go +++ b/db_test.go @@ -145,7 +145,6 @@ func TestDBCorruptMeta0(t *testing.T) { }) } - //-------------------------------------- // Transaction() //-------------------------------------- diff --git a/mnode.go b/mnode.go deleted file mode 100644 index 1d0abca..0000000 --- a/mnode.go +++ /dev/null @@ -1,9 +0,0 @@ -package bolt - -type mnodes []mnode - -type mnode struct { - key []byte - value []byte -} - diff --git a/mpage.go b/mpage.go deleted file mode 100644 index 7c5e048..0000000 --- a/mpage.go +++ /dev/null @@ -1,125 +0,0 @@ -package bolt - -import ( - "bytes" - "sort" - "unsafe" -) - -// mpage represents a deserialized leaf page. -// It is deserialized from an memory-mapped page and is not restricted by page size. -type mpage struct { - nodes mnodes -} - -// allocator is a function that returns a set of contiguous pages. -type allocator func(count int) (*page, error) - -// put inserts or replaces a key on a leaf page. -func (p *mpage) put(key []byte, value []byte) { - // Find insertion index. - index := sort.Search(len(p.nodes), func(i int) bool { return bytes.Compare(p.nodes[i].key, key) != -1 }) - - // If there is no existing key then add a new node. - if len(p.nodes) == 0 || !bytes.Equal(p.nodes[index].key, key) { - p.nodes = append(p.nodes, mnode{}) - copy(p.nodes[index+1:], p.nodes[index:]) - } - p.nodes[index].key = key - p.nodes[index].value = value -} - -// read initializes the node data from an on-disk page. -func (p *mpage) read(page *page) { - p.nodes = make(mnodes, page.count) - lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&page.ptr)) - for i := 0; i < int(page.count); i++ { - lnode := lnodes[i] - n := &p.nodes[i] - n.key = lnode.key() - n.value = lnode.value() - } -} - -// write writes the nodes onto one or more leaf pages. -func (p *mpage) write(pageSize int, allocate allocator) ([]*page, error) { - var pages []*page - - for _, nodes := range p.split(pageSize) { - // Determine the total page size. - var size int = pageHeaderSize - for _, node := range p.nodes { - size += lnodeSize + len(node.key) + len(node.value) - } - - // Allocate pages. - page, err := allocate(size) - if err != nil { - return nil, err - } - page.flags |= p_leaf - page.count = uint16(len(nodes)) - - // Loop over each node and write it to the page. - lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&page.ptr)) - b := (*[maxPageAllocSize]byte)(unsafe.Pointer(&page.ptr))[lnodeSize*len(nodes):] - for index, node := range nodes { - // Write node. - lnode := &lnodes[index] - lnode.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(&lnode))) - lnode.ksize = uint32(len(node.key)) - lnode.vsize = uint32(len(node.value)) - - // Write data to the end of the node. - copy(b[:], node.key) - b = b[len(node.key):] - copy(b[:], node.value) - b = b[len(node.value):] - } - - pages = append(pages, page) - } - - return pages, nil -} - -// split divides up the noes in the page into appropriately sized groups. -func (p *mpage) split(pageSize int) []mnodes { - // If we only have enough nodes for one page then just return the nodes. - if len(p.nodes) <= minKeysPerPage { - return []mnodes{p.nodes} - } - - // If we're not larger than one page then just return the nodes. - var totalSize int = pageHeaderSize - for _, node := range p.nodes { - totalSize += lnodeSize + len(node.key) + len(node.value) - } - if totalSize < pageSize { - return []mnodes{p.nodes} - } - - // Otherwise group into smaller pages and target a given fill size. - var size int - var group mnodes - var groups []mnodes - - // Set fill threshold to 25%. - threshold := pageSize >> 4 - - for _, node := range p.nodes { - nodeSize := lnodeSize + len(node.key) + len(node.value) - - // TODO(benbjohnson): Don't create a new group for just the last node. - if group == nil || (len(group) > minKeysPerPage && size+nodeSize > threshold) { - size = pageHeaderSize - group = make(mnodes, 0) - groups = append(groups, group) - } - - size += nodeSize - group = append(group, node) - } - - return groups -} diff --git a/rwtransaction.go b/rwtransaction.go index 9ecd4ee..14aceb9 100644 --- a/rwtransaction.go +++ b/rwtransaction.go @@ -8,7 +8,7 @@ import ( // Only one read/write transaction can be active for a DB at a time. type RWTransaction struct { Transaction - mpages map[pgid]*mpage + tpages map[pgid]*tpage } // TODO: Allocate scratch meta page. @@ -61,7 +61,7 @@ func (t *RWTransaction) CreateBucket(name string) error { // Insert new node. c := t.sys.cursor() c.Goto([]byte(name)) - t.mpage(c.page().id).put([]byte(name), buf[:]) + t.tpage(c.page().id).put([]byte(name), buf[:]) return nil } @@ -104,7 +104,7 @@ func (t *RWTransaction) Put(name string, key []byte, value []byte) error { // Insert a new node. c := b.cursor() c.Goto(key) - t.mpage(c.page().id).put(key, value) + t.tpage(c.page().id).put(key, value) return nil } @@ -124,18 +124,18 @@ func (t *RWTransaction) allocate(size int) (*page, error) { return nil, nil } -// mpage returns a deserialized leaf page. -func (t *RWTransaction) mpage(id pgid) *mpage { - if t.mpages != nil { - if p := t.mpages[id]; p != nil { +// tpage returns a deserialized leaf page. +func (t *RWTransaction) tpage(id pgid) *tpage { + if t.tpages != nil { + if p := t.tpages[id]; p != nil { return p } } // Read raw page and deserialize. - p := &mpage{} + p := &tpage{} p.read(t.page(id)) - t.mpages[id] = p + t.tpages[id] = p return p } diff --git a/tnode.go b/tnode.go new file mode 100644 index 0000000..fcb4782 --- /dev/null +++ b/tnode.go @@ -0,0 +1,8 @@ +package bolt + +type tnodes []tnode + +type tnode struct { + key []byte + value []byte +} diff --git a/tpage.go b/tpage.go new file mode 100644 index 0000000..c4dc83f --- /dev/null +++ b/tpage.go @@ -0,0 +1,127 @@ +package bolt + +import ( + "bytes" + "sort" + "unsafe" +) + +// tpage represents a temporary, in-memory leaf page. +// It is deserialized from an memory-mapped page and is not restricted by page size. +type tpage struct { + nodes tnodes +} + +// allocator is a function that returns a set of contiguous pages. +type allocator func(count int) (*page, error) + +// put inserts or replaces a key on a leaf page. +func (p *tpage) put(key []byte, value []byte) { + // Find insertion index. + index := sort.Search(len(p.nodes), func(i int) bool { return bytes.Compare(p.nodes[i].key, key) != -1 }) + + // If there is no existing key then add a new node. + if index == len(p.nodes) { + p.nodes = append(p.nodes, tnode{}) + } else if len(p.nodes) == 0 || !bytes.Equal(p.nodes[index].key, key) { + p.nodes = append(p.nodes, tnode{}) + copy(p.nodes[index+1:], p.nodes[index:]) + } + p.nodes[index].key = key + p.nodes[index].value = value +} + +// read initializes the node data from an on-disk page. +func (p *tpage) read(page *page) { + p.nodes = make(tnodes, page.count) + lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&page.ptr)) + for i := 0; i < int(page.count); i++ { + lnode := lnodes[i] + n := &p.nodes[i] + n.key = lnode.key() + n.value = lnode.value() + } +} + +// write writes the nodes onto one or more leaf pages. +func (p *tpage) write(pageSize int, allocate allocator) ([]*page, error) { + var pages []*page + + for _, nodes := range p.split(pageSize) { + // Determine the total page size. + var size int = pageHeaderSize + for _, node := range p.nodes { + size += lnodeSize + len(node.key) + len(node.value) + } + + // Allocate pages. + page, err := allocate(size) + if err != nil { + return nil, err + } + page.flags |= p_leaf + page.count = uint16(len(nodes)) + + // Loop over each node and write it to the page. + lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&page.ptr)) + b := (*[maxPageAllocSize]byte)(unsafe.Pointer(&page.ptr))[lnodeSize*len(nodes):] + for index, node := range nodes { + // Write node. + lnode := &lnodes[index] + lnode.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(&lnode))) + lnode.ksize = uint32(len(node.key)) + lnode.vsize = uint32(len(node.value)) + + // Write data to the end of the node. + copy(b[:], node.key) + b = b[len(node.key):] + copy(b[:], node.value) + b = b[len(node.value):] + } + + pages = append(pages, page) + } + + return pages, nil +} + +// split divides up the noes in the page into appropriately sized groups. +func (p *tpage) split(pageSize int) []tnodes { + // If we only have enough nodes for one page then just return the nodes. + if len(p.nodes) <= minKeysPerPage { + return []tnodes{p.nodes} + } + + // If we're not larger than one page then just return the nodes. + var totalSize int = pageHeaderSize + for _, node := range p.nodes { + totalSize += lnodeSize + len(node.key) + len(node.value) + } + if totalSize < pageSize { + return []tnodes{p.nodes} + } + + // Otherwise group into smaller pages and target a given fill size. + var size int + var group tnodes + var groups []tnodes + + // Set fill threshold to 25%. + threshold := pageSize >> 4 + + for _, node := range p.nodes { + nodeSize := lnodeSize + len(node.key) + len(node.value) + + // TODO(benbjohnson): Don't create a new group for just the last node. + if group == nil || (len(group) > minKeysPerPage && size+nodeSize > threshold) { + size = pageHeaderSize + group = make(tnodes, 0) + groups = append(groups, group) + } + + size += nodeSize + group = append(group, node) + } + + return groups +} diff --git a/tpage_test.go b/tpage_test.go new file mode 100644 index 0000000..d14ebdb --- /dev/null +++ b/tpage_test.go @@ -0,0 +1,35 @@ +package bolt + +import ( + "testing" + + "github.com/stretchr/testify/assert" +) + +// Ensure that a temporary page can insert a key/value. +func TestTpagePut(t *testing.T) { + p := &tpage{nodes: make(tnodes, 0)} + p.put([]byte("baz"), []byte("2")) + p.put([]byte("foo"), []byte("0")) + p.put([]byte("bar"), []byte("1")) + p.put([]byte("foo"), []byte("3")) + assert.Equal(t, len(p.nodes), 3) + assert.Equal(t, p.nodes[0], tnode{[]byte("bar"), []byte("1")}) + assert.Equal(t, p.nodes[1], tnode{[]byte("baz"), []byte("2")}) + assert.Equal(t, p.nodes[2], tnode{[]byte("foo"), []byte("3")}) +} + +// Ensure that a temporary page can deserialize from a page. +func TestTpageRead(t *testing.T) { + t.Skip("pending") +} + +// Ensure that a temporary page can serialize itself. +func TestTpageWrite(t *testing.T) { + t.Skip("pending") +} + +// Ensure that a temporary page can split into appropriate subgroups. +func TestTpageSplit(t *testing.T) { + t.Skip("pending") +} -- cgit v1.2.3