Add freelist.

19 files changed, 412 insertions, 100 deletions

diff --git a/Makefile b/Makefile
index decd960..a7cd5e7 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,3 @@
-PKG=./...
 TEST=.
 BENCH=.
 COVERPROFILE=/tmp/c.out
@@ -7,7 +6,7 @@ bench: benchpreq
 	go test -v -test.bench=$(BENCH) ./.bench
 
 cover: fmt
-	go test -coverprofile=$(COVERPROFILE) .
+	go test -coverprofile=$(COVERPROFILE) -test.run=$(TEST) .
 	go tool cover -html=$(COVERPROFILE)
 	rm $(COVERPROFILE)
 
@@ -15,6 +14,6 @@ fmt:
 	@go fmt ./...
 
 test: fmt
-	@go test -v -cover -test.run=$(TEST) $(PKG)
+	@go test -v -cover -test.run=$(TEST)
 
 .PHONY: bench cover fmt test
diff --git a/assert.go b/assert.go
index 8101f8a..c22b2b0 100644
--- a/assert.go
+++ b/assert.go
@@ -7,6 +7,6 @@ import "fmt"
 // _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...))
+		panic(fmt.Sprintf("assertion failed: "+msg, v...))
 	}
 }
diff --git a/bucket.go b/bucket.go
index fdaadf8..28c570e 100644
--- a/bucket.go
+++ b/bucket.go
@@ -23,17 +23,3 @@ func (b *Bucket) cursor() *Cursor {
 		stack:       make([]pageElementRef, 0),
 	}
 }
-
-func (b *Bucket) Stat() *Stat {
-	// TODO: Calculate size, depth, page count (by type), entry count, readers, etc.
-	return nil
-}
-
-type Stat struct {
-	PageSize          int
-	Depth             int
-	BranchPageCount   int
-	LeafPageCount     int
-	OverflowPageCount int
-	EntryCount        int
-}
diff --git a/cursor.go b/cursor.go
index c76aab1..d993668 100644
--- a/cursor.go
+++ b/cursor.go
@@ -43,9 +43,7 @@ func (c *Cursor) Get(key []byte) []byte {
 }
 
 func (c *Cursor) search(key []byte, p *page) {
-	if (p.flags & (p_branch | p_leaf)) == 0 {
-		panic("invalid page type: " + p.typ())
-	}
+	_assert((p.flags&(p_branch|p_leaf)) != 0, "invalid page type: "+p.typ())
 	e := pageElementRef{page: p}
 	c.stack = append(c.stack, e)
 
@@ -95,11 +93,6 @@ func (c *Cursor) top() (*page, uint16) {
 	return ptr.page, ptr.index
 }
 
-// page returns the page that the cursor is currently pointing at.
-func (c *Cursor) page() *page {
-	return c.stack[len(c.stack)-1].page
-}
-
 // element returns the leaf element that the cursor is currently positioned on.
 func (c *Cursor) element() *leafPageElement {
 	ref := c.stack[len(c.stack)-1]
@@ -123,4 +116,3 @@ func (c *Cursor) node(t *RWTransaction) *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
 }
-
diff --git a/db.go b/db.go
index c1653fb..65879ec 100644
--- a/db.go
+++ b/db.go
@@ -25,10 +25,14 @@ type DB struct {
 	meta0         *meta
 	meta1         *meta
 	pageSize      int
-	opened bool
-	mutex sync.Mutex
+	opened        bool
 	rwtransaction *RWTransaction
 	transactions  []*Transaction
+	freelist      *freelist
+
+	rwlock   sync.Mutex   // Allows only one writer at a time.
+	metalock sync.Mutex   // Protects meta page access.
+	mmaplock sync.RWMutex // Protects mmap access during remapping.
 }
 
 // NewDB creates a new DB instance.
@@ -45,8 +49,8 @@ func (db *DB) Path() string {
 // If the file does not exist then it will be created automatically.
 func (db *DB) Open(path string, mode os.FileMode) error {
 	var err error
-	db.mutex.Lock()
-	defer db.mutex.Unlock()
+	db.metalock.Lock()
+	defer db.metalock.Unlock()
 
 	// Initialize OS/Syscall references.
 	// These are overridden by mocks during some tests.
@@ -99,6 +103,10 @@ func (db *DB) Open(path string, mode os.FileMode) error {
 		return err
 	}
 
+	// Read in the freelist.
+	db.freelist = &freelist{pending: make(map[txnid][]pgid)}
+	db.freelist.read(db.page(db.meta().freelist))
+
 	// Mark the database as opened and return.
 	db.opened = true
 	return nil
@@ -113,7 +121,7 @@ func (db *DB) mmap() error {
 		return &Error{"file size too small", err}
 	}
 
-	// TEMP(benbjohnson): Set max size to 1MB.
+	// TODO(benbjohnson): Determine appropriate mmap size by db size.
 	size := 2 << 30
 
 	// Memory-map the data file as a byte slice.
@@ -154,7 +162,7 @@ func (db *DB) init() error {
 		m.version = version
 		m.pageSize = uint32(db.pageSize)
 		m.version = version
-		m.free = 2
+		m.freelist = 2
 		m.buckets = 3
 		m.pgid = 4
 		m.txnid = txnid(i)
@@ -182,20 +190,21 @@ func (db *DB) init() error {
 
 // Close releases all resources related to the database.
 func (db *DB) Close() {
-	db.mutex.Lock()
-	defer db.mutex.Unlock()
+	db.metalock.Lock()
+	defer db.metalock.Unlock()
 	db.close()
 }
 
 func (db *DB) close() {
 	// TODO: Undo everything in Open().
+	db.freelist = nil
 }
 
 // Transaction creates a read-only transaction.
 // Multiple read-only transactions can be used concurrently.
 func (db *DB) Transaction() (*Transaction, error) {
-	db.mutex.Lock()
-	defer db.mutex.Unlock()
+	db.metalock.Lock()
+	defer db.metalock.Unlock()
 
 	// Exit if the database is not open yet.
 	if !db.opened {
@@ -206,30 +215,60 @@ func (db *DB) Transaction() (*Transaction, error) {
 	t := &Transaction{}
 	t.init(db)
 
+	// Keep track of transaction until it closes.
+	db.transactions = append(db.transactions, t)
+
 	return t, nil
 }
 
 // RWTransaction creates a read/write transaction.
 // Only one read/write transaction is allowed at a time.
 func (db *DB) RWTransaction() (*RWTransaction, error) {
-	db.mutex.Lock()
-	defer db.mutex.Unlock()
+	db.metalock.Lock()
+	defer db.metalock.Unlock()
 
-	// TODO: db.writerMutex.Lock()
-	// TODO: Add unlock to RWTransaction.Commit() / Abort()
+	// Obtain writer lock. This is released by the RWTransaction when it closes.
+	db.rwlock.Lock()
 
 	// Exit if the database is not open yet.
 	if !db.opened {
+		db.rwlock.Unlock()
 		return nil, DatabaseNotOpenError
 	}
 
 	// Create a transaction associated with the database.
 	t := &RWTransaction{nodes: make(map[pgid]*node)}
 	t.init(db)
+	db.rwtransaction = t
+
+	// Free any pages associated with closed read-only transactions.
+	var minid txnid = 0xFFFFFFFFFFFFFFFF
+	for _, t := range db.transactions {
+		if t.id() < minid {
+			minid = t.id()
+		}
+	}
+	if minid > 0 {
+		db.freelist.release(minid - 1)
+	}
 
 	return t, nil
 }
 
+// removeTransaction removes a transaction from the database.
+func (db *DB) removeTransaction(t *Transaction) {
+	db.metalock.Lock()
+	defer db.metalock.Unlock()
+
+	// Remove the transaction.
+	for i, txn := range db.transactions {
+		if txn == t {
+			db.transactions = append(db.transactions[:i], db.transactions[i+1:]...)
+			break
+		}
+	}
+}
+
 // Bucket retrieves a reference to a bucket.
 func (db *DB) Bucket(name string) (*Bucket, error) {
 	t, err := db.Transaction()
@@ -372,8 +411,32 @@ func (db *DB) meta() *meta {
 	return db.meta1
 }
 
+// allocate returns a contiguous block of memory starting at a given page.
+func (db *DB) allocate(count int) *page {
+	// Allocate a temporary buffer for the page.
+	buf := make([]byte, count*db.pageSize)
+	p := (*page)(unsafe.Pointer(&buf[0]))
+	p.overflow = uint32(count - 1)
+
+	// Use pages from the freelist if they are available.
+	if p.id = db.freelist.allocate(count); p.id != 0 {
+		return p
+	}
+
+	// TODO(benbjohnson): Resize mmap().
+
+	// If there are no free pages then allocate from the end of the file.
+	p.id = db.rwtransaction.meta.pgid
+	db.rwtransaction.meta.pgid += pgid(count)
+
+	return p
+}
+
 // sync flushes the file descriptor to disk.
 func (db *DB) sync(force bool) error {
+	if db.opened {
+		return DatabaseAlreadyOpenedError
+	}
 	if err := syscall.Fsync(int(db.file.Fd())); err != nil {
 		return err
 	}
diff --git a/db_test.go b/db_test.go
index 565adb8..8211eac 100644
--- a/db_test.go
+++ b/db_test.go
@@ -167,6 +167,26 @@ func TestDBDelete(t *testing.T) {
 	})
 }
 
+// Ensure that the database can be copied to a writer.
+func TestDBCopy(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that the database can be copied to a file path.
+func TestDBCopyFile(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that the database can sync to the file system.
+func TestDBSync(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when a database write fails.
+func TestDBWriteFail(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
 // withDB executes a function with a database reference.
 func withDB(fn func(*DB, string)) {
 	f, _ := ioutil.TempFile("", "bolt-")
diff --git a/error_test.go b/error_test.go
new file mode 100644
index 0000000..0306985
--- /dev/null
+++ b/error_test.go
@@ -0,0 +1,12 @@
+package bolt
+
+import (
+	"github.com/stretchr/testify/assert"
+	"testing"
+)
+
+// Ensure that nested errors are appropriately formatted.
+func TestError(t *testing.T) {
+	e := &Error{"one error", &Error{"two error", nil}}
+	assert.Equal(t, e.Error(), "one error: two error")
+}
diff --git a/freelist.go b/freelist.go
new file mode 100644
index 0000000..cd0bffa
--- /dev/null
+++ b/freelist.go
@@ -0,0 +1,94 @@
+package bolt
+
+import (
+	"sort"
+	"unsafe"
+)
+
+// freelist represents a list of all pages that are available for allocation.
+// It also tracks pages that have been freed but are still in use by open transactions.
+type freelist struct {
+	ids     []pgid
+	pending map[txnid][]pgid
+}
+
+// all returns a list of all free ids and all pending ids in one sorted list.
+func (f *freelist) all() []pgid {
+	ids := make([]pgid, len(f.ids))
+	copy(ids, f.ids)
+
+	for _, list := range f.pending {
+		ids = append(ids, list...)
+	}
+
+	sort.Sort(reverseSortedPgids(ids))
+	return ids
+}
+
+// allocate returns the starting page id of a contiguous list of pages of a given size.
+// If a contiguous block cannot be found then 0 is returned.
+func (f *freelist) allocate(n int) pgid {
+	var count int
+	var previd pgid = 0
+	for i, id := range f.ids {
+		// Reset count if this is not contiguous.
+		if previd == 0 || previd-id != 1 {
+			count = 1
+		}
+
+		// If we found a contiguous block then remove it and return it.
+		if count == n {
+			f.ids = append(f.ids[:i-(n-1)], f.ids[i+1:]...)
+			_assert(id > 1, "cannot allocate page 0 or 1: %d", id)
+			return id
+		}
+
+		previd = id
+		count++
+	}
+	return 0
+}
+
+// free releases a page and its overflow for a given transaction id.
+func (f *freelist) free(txnid txnid, p *page) {
+	var ids = f.pending[txnid]
+	_assert(p.id > 1, "cannot free page 0 or 1: %d", p.id)
+	for i := 0; i < int(p.overflow+1); i++ {
+		ids = append(ids, p.id+pgid(i))
+	}
+	f.pending[txnid] = ids
+}
+
+// release moves all page ids for a transaction id (or older) to the freelist.
+func (f *freelist) release(txnid txnid) {
+	for tid, ids := range f.pending {
+		if tid <= txnid {
+			f.ids = append(f.ids, ids...)
+			delete(f.pending, tid)
+		}
+	}
+	sort.Sort(reverseSortedPgids(f.ids))
+}
+
+// read initializes the freelist from a freelist page.
+func (f *freelist) read(p *page) {
+	ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0:p.count]
+	f.ids = make([]pgid, len(ids))
+	copy(f.ids, ids)
+}
+
+// write writes the page ids onto a freelist page. All free and pending ids are
+// saved to disk since in the event of a program crash, all pending ids will
+// become free.
+func (f *freelist) write(p *page) {
+	ids := f.all()
+	p.flags |= p_freelist
+	p.count = uint16(len(ids))
+	copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+}
+
+type reverseSortedPgids []pgid
+
+func (s reverseSortedPgids) Len() int           { return len(s) }
+func (s reverseSortedPgids) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+func (s reverseSortedPgids) Less(i, j int) bool { return s[i] > s[j] }
diff --git a/freelist_test.go b/freelist_test.go
new file mode 100644
index 0000000..b760acb
--- /dev/null
+++ b/freelist_test.go
@@ -0,0 +1,95 @@
+package bolt
+
+import (
+	"testing"
+	"unsafe"
+
+	"github.com/stretchr/testify/assert"
+)
+
+// Ensure that a page is added to a transaction's freelist.
+func TestFreelistFree(t *testing.T) {
+	f := &freelist{pending: make(map[txnid][]pgid)}
+	f.free(100, &page{id: 12})
+	assert.Equal(t, f.pending[100], []pgid{12})
+}
+
+// Ensure that a page and its overflow is added to a transaction's freelist.
+func TestFreelistFreeOverflow(t *testing.T) {
+	f := &freelist{pending: make(map[txnid][]pgid)}
+	f.free(100, &page{id: 12, overflow: 3})
+	assert.Equal(t, f.pending[100], []pgid{12, 13, 14, 15})
+}
+
+// Ensure that a transaction's free pages can be released.
+func TestFreelistRelease(t *testing.T) {
+	f := &freelist{pending: make(map[txnid][]pgid)}
+	f.free(100, &page{id: 12, overflow: 1})
+	f.free(100, &page{id: 9})
+	f.free(102, &page{id: 39})
+	f.release(100)
+	f.release(101)
+	assert.Equal(t, f.ids, []pgid{13, 12, 9})
+	f.release(102)
+	assert.Equal(t, f.ids, []pgid{39, 13, 12, 9})
+}
+
+// Ensure that a freelist can find contiguous blocks of pages.
+func TestFreelistAllocate(t *testing.T) {
+	f := &freelist{ids: []pgid{18, 13, 12, 9, 7, 6, 5, 4, 3}}
+	assert.Equal(t, f.allocate(2), pgid(12))
+	assert.Equal(t, f.allocate(1), pgid(18))
+	assert.Equal(t, f.allocate(3), pgid(5))
+	assert.Equal(t, f.allocate(3), pgid(0))
+	assert.Equal(t, f.allocate(2), pgid(3))
+	assert.Equal(t, f.allocate(1), pgid(9))
+	assert.Equal(t, f.allocate(0), pgid(0))
+	assert.Equal(t, f.ids, []pgid{})
+}
+
+// Ensure that a freelist can deserialize from a freelist page.
+func TestFreelistRead(t *testing.T) {
+	// Create a page.
+	var buf [4096]byte
+	page := (*page)(unsafe.Pointer(&buf[0]))
+	page.flags = p_freelist
+	page.count = 2
+
+	// Insert 2 page ids.
+	ids := (*[3]pgid)(unsafe.Pointer(&page.ptr))
+	ids[0] = 23
+	ids[1] = 50
+
+	// Deserialize page into a freelist.
+	f := &freelist{pending: make(map[txnid][]pgid)}
+	f.read(page)
+
+	// Ensure that there are two page ids in the freelist.
+	assert.Equal(t, len(f.ids), 2)
+	assert.Equal(t, f.ids[0], pgid(23))
+	assert.Equal(t, f.ids[1], pgid(50))
+}
+
+// Ensure that a freelist can serialize into a freelist page.
+func TestFreelistWrite(t *testing.T) {
+	// Create a freelist and write it to a page.
+	var buf [4096]byte
+	f := &freelist{ids: []pgid{12, 39}, pending: make(map[txnid][]pgid)}
+	f.pending[100] = []pgid{28, 11}
+	f.pending[101] = []pgid{3}
+	p := (*page)(unsafe.Pointer(&buf[0]))
+	f.write(p)
+
+	// Read the page back out.
+	f2 := &freelist{pending: make(map[txnid][]pgid)}
+	f2.read(p)
+
+	// Ensure that the freelist is correct.
+	// All pages should be present and in reverse order.
+	assert.Equal(t, len(f2.ids), 5)
+	assert.Equal(t, f2.ids[0], pgid(39))
+	assert.Equal(t, f2.ids[1], pgid(28))
+	assert.Equal(t, f2.ids[2], pgid(12))
+	assert.Equal(t, f2.ids[3], pgid(11))
+	assert.Equal(t, f2.ids[4], pgid(3))
+}
diff --git a/meta.go b/meta.go
index 5c68fa7..d4df9c4 100644
--- a/meta.go
+++ b/meta.go
@@ -8,7 +8,7 @@ type meta struct {
 	pageSize uint32
 	flags    uint32
 	buckets  pgid
-	free     pgid
+	freelist pgid
 	pgid     pgid
 	txnid    txnid
 }
@@ -28,10 +28,10 @@ func (m *meta) copy(dest *meta) {
 	dest.magic = m.magic
 	dest.version = m.version
 	dest.pageSize = m.pageSize
+	dest.buckets = m.buckets
+	dest.freelist = m.freelist
 	dest.pgid = m.pgid
-	dest.free = m.free
 	dest.txnid = m.txnid
-	dest.buckets = m.buckets
 }
 
 // write writes the meta onto a page.
diff --git a/meta_test.go b/meta_test.go
new file mode 100644
index 0000000..c082c64
--- /dev/null
+++ b/meta_test.go
@@ -0,0 +1,18 @@
+package bolt
+
+import (
+	"github.com/stretchr/testify/assert"
+	"testing"
+)
+
+// Ensure that meta with bad magic is invalid.
+func TestMetaValidateMagic(t *testing.T) {
+	m := &meta{magic: 0x01234567}
+	assert.Equal(t, m.validate(), InvalidError)
+}
+
+// Ensure that meta with a bad version is invalid.
+func TestMetaValidateVersion(t *testing.T) {
+	m := &meta{magic: magic, version: 200}
+	assert.Equal(t, m.validate(), VersionMismatchError)
+}
diff --git a/node.go b/node.go
index 15f5763..ad31f5b 100644
--- a/node.go
+++ b/node.go
@@ -9,13 +9,13 @@ import (
 // node represents an in-memory, deserialized page.
 type node struct {
 	transaction *RWTransaction
-	isLeaf bool
-	unbalanced bool
-	key    []byte
-	depth  int
-	pgid   pgid
-	parent *node
-	inodes inodes
+	isLeaf      bool
+	unbalanced  bool
+	key         []byte
+	depth       int
+	pgid        pgid
+	parent      *node
+	inodes      inodes
 }
 
 // minKeys returns the minimum number of inodes this node should have.
@@ -76,7 +76,7 @@ func (n *node) nextSibling() *node {
 		return nil
 	}
 	index := n.parent.childIndex(n)
-	if index >= n.parent.numChildren() - 1 {
+	if index >= n.parent.numChildren()-1 {
 		return nil
 	}
 	return n.parent.childAt(index + 1)
@@ -354,7 +354,3 @@ type inode struct {
 }
 
 type inodes []inode
-
-func (s inodes) Len() int           { return len(s) }
-func (s inodes) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
-func (s inodes) Less(i, j int) bool { return bytes.Compare(s[i].key, s[j].key) == -1 }
diff --git a/os.go b/os.go
index 606a207..47515eb 100644
--- a/os.go
+++ b/os.go
@@ -6,7 +6,6 @@ import (
 
 type _os interface {
 	OpenFile(name string, flag int, perm os.FileMode) (file file, err error)
-	Stat(name string) (fi os.FileInfo, err error)
 	Getpagesize() int
 }
 
@@ -23,10 +22,6 @@ func (o *sysos) OpenFile(name string, flag int, perm os.FileMode) (file file, er
 	return os.OpenFile(name, flag, perm)
 }
 
-func (o *sysos) Stat(name string) (fi os.FileInfo, err error) {
-	return os.Stat(name)
-}
-
 func (o *sysos) Getpagesize() int {
 	return os.Getpagesize()
 }
diff --git a/page.go b/page.go
index f4dd19c..2b714ee 100644
--- a/page.go
+++ b/page.go
@@ -81,11 +81,6 @@ func (p *page) branchPageElements() []branchPageElement {
 	return ((*[maxNodesPerPage]branchPageElement)(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]
-}
-
 // dump writes n bytes of the page to STDERR as hex output.
 func (p *page) hexdump(n int) {
 	buf := (*[maxAllocSize]byte)(unsafe.Pointer(p))[:n]
diff --git a/page_test.go b/page_test.go
new file mode 100644
index 0000000..05b0509
--- /dev/null
+++ b/page_test.go
@@ -0,0 +1,21 @@
+package bolt
+
+import (
+	"github.com/stretchr/testify/assert"
+	"testing"
+)
+
+// Ensure that the page type can be returned in human readable format.
+func TestPageTyp(t *testing.T) {
+	assert.Equal(t, (&page{flags: p_branch}).typ(), "branch")
+	assert.Equal(t, (&page{flags: p_leaf}).typ(), "leaf")
+	assert.Equal(t, (&page{flags: p_meta}).typ(), "meta")
+	assert.Equal(t, (&page{flags: p_buckets}).typ(), "buckets")
+	assert.Equal(t, (&page{flags: p_freelist}).typ(), "freelist")
+	assert.Equal(t, (&page{flags: 20000}).typ(), "unknown<4e20>")
+}
+
+// Ensure that the hexdump debugging function doesn't blow up.
+func TestPageDump(t *testing.T) {
+	(&page{id: 256}).hexdump(16)
+}
diff --git a/rwtransaction.go b/rwtransaction.go
index 2e1685b..5058dd3 100644
--- a/rwtransaction.go
+++ b/rwtransaction.go
@@ -49,8 +49,7 @@ func (t *RWTransaction) DeleteBucket(name string) error {
 	// Remove from buckets page.
 	t.buckets.del(name)
 
-	// TODO: Free all pages.
-	// TODO: Remove cursor.
+	// TODO(benbjohnson): Free all pages.
 	return nil
 }
 
@@ -97,8 +96,12 @@ func (t *RWTransaction) Delete(name string, key []byte) error {
 
 // Commit writes all changes to disk.
 func (t *RWTransaction) Commit() error {
+	defer t.close()
+
 	// TODO(benbjohnson): Use vectorized I/O to write out dirty pages.
 
+	// TODO(benbjohnson): Move rebalancing to occur immediately after deletion (?).
+
 	// Rebalance and spill data onto dirty pages.
 	t.rebalance()
 	t.spill()
@@ -128,26 +131,14 @@ func (t *RWTransaction) Rollback() {
 }
 
 func (t *RWTransaction) close() {
-	// Clear nodes.
-	t.nodes = nil
-
-	// TODO: Release writer lock.
+	t.db.rwlock.Unlock()
 }
 
 // allocate returns a contiguous block of memory starting at a given page.
 func (t *RWTransaction) allocate(count int) *page {
-	// TODO(benbjohnson): Use pages from the freelist.
-
-	// Allocate a set of contiguous pages from the end of the file.
-	buf := make([]byte, count*t.db.pageSize)
-	p := (*page)(unsafe.Pointer(&buf[0]))
-	p.id = t.meta.pgid
-	p.overflow = uint32(count - 1)
+	p := t.db.allocate(count)
 
-	// Increment the last page id.
-	t.meta.pgid += pgid(count)
-
-	// Save it in our page cache.
+	// Save to our page cache.
 	t.pages[p.id] = p
 
 	return p
@@ -196,6 +187,11 @@ func (t *RWTransaction) spill() {
 			nodes = append(nodes, n.parent)
 		}
 
+		// Add node's page to the freelist.
+		if n.pgid > 0 {
+			t.db.freelist.free(t.id(), t.page(n.pgid))
+		}
+
 		// Write nodes to dirty pages.
 		for i, newNode := range newNodes {
 			// Allocate contiguous space for the node.
@@ -267,10 +263,6 @@ func (t *RWTransaction) writeMeta() error {
 	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()
-
 // 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.
diff --git a/rwtransaction_test.go b/rwtransaction_test.go
index 5bf3f9f..88a246f 100644
--- a/rwtransaction_test.go
+++ b/rwtransaction_test.go
@@ -17,11 +17,12 @@ func TestRWTransaction(t *testing.T) {
 		txn, err := db.RWTransaction()
 		assert.NotNil(t, txn)
 		assert.NoError(t, err)
+		assert.Equal(t, txn.DB(), db)
 	})
 }
 
 // Ensure that a bucket can be created and retrieved.
-func TestTransactionCreateBucket(t *testing.T) {
+func TestRWTransactionCreateBucket(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
 		// Create a bucket.
 		err := db.CreateBucket("widgets")
@@ -35,7 +36,7 @@ func TestTransactionCreateBucket(t *testing.T) {
 }
 
 // Ensure that a bucket cannot be created twice.
-func TestTransactionRecreateBucket(t *testing.T) {
+func TestRWTransactionRecreateBucket(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
 		// Create a bucket.
 		err := db.CreateBucket("widgets")
@@ -48,7 +49,7 @@ func TestTransactionRecreateBucket(t *testing.T) {
 }
 
 // Ensure that a bucket is created with a non-blank name.
-func TestTransactionCreateBucketWithoutName(t *testing.T) {
+func TestRWTransactionCreateBucketWithoutName(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
 		err := db.CreateBucket("")
 		assert.Equal(t, err, &Error{"bucket name cannot be blank", nil})
@@ -56,7 +57,7 @@ func TestTransactionCreateBucketWithoutName(t *testing.T) {
 }
 
 // Ensure that a bucket name is not too long.
-func TestTransactionCreateBucketWithLongName(t *testing.T) {
+func TestRWTransactionCreateBucketWithLongName(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
 		err := db.CreateBucket(strings.Repeat("X", 255))
 		assert.NoError(t, err)
@@ -66,6 +67,36 @@ func TestTransactionCreateBucketWithLongName(t *testing.T) {
 	})
 }
 
+// Ensure that a bucket can be deleted.
+func TestRWTransactionDeleteBucket(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when inserting into a bucket that doesn't exist.
+func TestRWTransactionPutBucketNotFound(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when inserting with an empty key.
+func TestRWTransactionPutEmptyKey(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when inserting with a key that's too large.
+func TestRWTransactionPutKeyTooLarge(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when inserting with data that's too large.
+func TestRWTransactionPutDataTooLarge(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
+// Ensure that an error is returned when deleting from a bucket that doesn't exist.
+func TestRWTransactionDeleteBucketNotFound(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
 // Ensure that a bucket can write random keys and values across multiple txns.
 func TestRWTransactionPutSingle(t *testing.T) {
 	index := 0
diff --git a/transaction.go b/transaction.go
index d21693a..1b940d6 100644
--- a/transaction.go
+++ b/transaction.go
@@ -10,7 +10,6 @@ const (
 type txnid uint64
 
 type Transaction struct {
-	id      int
 	db      *DB
 	meta    *meta
 	buckets *buckets
@@ -27,8 +26,13 @@ func (t *Transaction) init(db *DB) {
 	t.buckets.read(t.page(t.meta.buckets))
 }
 
+// id returns the transaction id.
+func (t *Transaction) id() txnid {
+	return t.meta.txnid
+}
+
 func (t *Transaction) Close() {
-	// TODO: Close buckets.
+	t.db.removeTransaction(t)
 }
 
 func (t *Transaction) DB() *DB {
@@ -73,12 +77,6 @@ func (t *Transaction) Get(name string, key []byte) []byte {
 	return c.Get(key)
 }
 
-// stat returns information about a bucket's internal structure.
-func (t *Transaction) stat(name string) *Stat {
-	// TODO
-	return nil
-}
-
 // page returns a reference to the page with a given id.
 // If page has been written to then a temporary bufferred page is returned.
 func (t *Transaction) page(id pgid) *page {
diff --git a/transaction_test.go b/transaction_test.go
index 55e8bde..6041f2f 100644
--- a/transaction_test.go
+++ b/transaction_test.go
@@ -6,6 +6,11 @@ import (
 	"github.com/stretchr/testify/assert"
 )
 
+// Ensure that the database can retrieve a list of buckets.
+func TestTransactionBuckets(t *testing.T) {
+	t.Skip("pending") // TODO(benbjohnson)
+}
+
 // Ensure that a Transaction can retrieve a bucket.
 func TestTransactionBucketMissing(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
@@ -19,7 +24,7 @@ func TestTransactionBucketMissing(t *testing.T) {
 }
 
 // Ensure that a Transaction retrieving a non-existent key returns nil.
-func TestTransactionGetMising(t *testing.T) {
+func TestTransactionGetMissing(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
 		db.CreateBucket("widgets")
 		db.Put("widgets", []byte("foo"), []byte("bar"))