1 files changed, 59 insertions, 37 deletions

diff --git a/freelist.go b/freelist.go
index 66bc06f..27aea6a 100644
--- a/freelist.go
+++ b/freelist.go
@@ -1,7 +1,6 @@
 package bolt
 
 import (
-	"fmt"
 	"sort"
 	"unsafe"
 )
@@ -9,8 +8,17 @@ import (
 // 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[txid][]pgid
+	ids     []pgid          // all free and available free page ids.
+	pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
+	cache   map[pgid]bool   // fast lookup of all free and pending page ids.
+}
+
+// newFreelist returns an empty, initialized freelist.
+func newFreelist() *freelist {
+	return &freelist{
+		pending: make(map[txid][]pgid),
+		cache:   make(map[pgid]bool),
+	}
 }
 
 // size returns the size of the page after serialization.
@@ -78,6 +86,12 @@ func (f *freelist) allocate(n int) pgid {
 				copy(f.ids[i-n+1:], f.ids[i+1:])
 				f.ids = f.ids[:len(f.ids)-n]
 			}
+
+			// Remove from the free cache.
+			for i := pgid(0); i < pgid(n); i++ {
+				delete(f.cache, initial+i)
+			}
+
 			return initial
 		}
 
@@ -91,25 +105,15 @@ func (f *freelist) allocate(n int) pgid {
 func (f *freelist) free(txid txid, p *page) {
 	_assert(p.id > 1, "cannot free page 0 or 1: %d", p.id)
 
-	// Verify that page is not already free.
-	minid, maxid := p.id, p.id+pgid(p.overflow)
-	for _, id := range f.ids {
-		if id >= minid && id <= maxid {
-			panic(fmt.Sprintf("page %d already freed in tx", id))
-		}
-	}
-	for ptxid, m := range f.pending {
-		for _, id := range m {
-			if id >= minid && id <= maxid {
-				panic(fmt.Sprintf("tx %d: page %d already freed in tx %d", txid, id, ptxid))
-			}
-		}
-	}
-
 	// Free page and all its overflow pages.
 	var ids = f.pending[txid]
-	for i := 0; i < int(p.overflow+1); i++ {
-		ids = append(ids, p.id+pgid(i))
+	for id := p.id; id <= p.id+pgid(p.overflow); id++ {
+		// Verify that page is not already free.
+		_assert(!f.cache[id], "page %d already freed", id)
+
+		// Add to the freelist and cache.
+		ids = append(ids, id)
+		f.cache[id] = true
 	}
 	f.pending[txid] = ids
 }
@@ -118,6 +122,8 @@ func (f *freelist) free(txid txid, p *page) {
 func (f *freelist) release(txid txid) {
 	for tid, ids := range f.pending {
 		if tid <= txid {
+			// Move transaction's pending pages to the available freelist.
+			// Don't remove from the cache since the page is still free.
 			f.ids = append(f.ids, ids...)
 			delete(f.pending, tid)
 		}
@@ -127,24 +133,18 @@ func (f *freelist) release(txid txid) {
 
 // rollback removes the pages from a given pending tx.
 func (f *freelist) rollback(txid txid) {
+	// Remove page ids from cache.
+	for _, id := range f.pending[txid] {
+		delete(f.cache, id)
+	}
+
+	// Remove pages from pending list.
 	delete(f.pending, txid)
 }
 
-// isFree returns whether a given page is in the free list.
-func (f *freelist) isFree(pgid pgid) bool {
-	for _, id := range f.ids {
-		if id == pgid {
-			return true
-		}
-	}
-	for _, m := range f.pending {
-		for _, id := range m {
-			if id == pgid {
-				return true
-			}
-		}
-	}
-	return false
+// freed returns whether a given page is in the free list.
+func (f *freelist) freed(pgid pgid) bool {
+	return f.cache[pgid]
 }
 
 // read initializes the freelist from a freelist page.
@@ -153,6 +153,7 @@ func (f *freelist) read(p *page) {
 	f.ids = make([]pgid, len(ids))
 	copy(f.ids, ids)
 	sort.Sort(pgids(f.ids))
+	f.buildcache()
 }
 
 // write writes the page ids onto a freelist page. All free and pending ids are
@@ -179,15 +180,36 @@ func (f *freelist) write(p *page) error {
 func (f *freelist) reload(p *page) {
 	f.read(p)
 
-	// Filter out pending free pages.
+	// We need to filter out the pending pages from the available freelist
+	// so we rebuild the cache without the newly read freelist.
 	ids := f.ids
 	f.ids = nil
+	f.buildcache()
 
+	// Check each page in the freelist and build a new available freelist
+	// with any pages not in the pending lists.
 	var a []pgid
 	for _, id := range ids {
-		if !f.isFree(id) {
+		if !f.freed(id) {
 			a = append(a, id)
 		}
 	}
 	f.ids = a
+
+	// Once the available list is rebuilt then rebuild the free cache so that
+	// it includes the available and pending free pages.
+	f.buildcache()
+}
+
+// buildcache rebuilds the free cache based on available and pending free lists.
+func (f *freelist) buildcache() {
+	f.cache = make(map[pgid]bool)
+	for _, id := range f.ids {
+		f.cache[id] = true
+	}
+	for _, pendingIDs := range f.pending {
+		for _, pendingID := range pendingIDs {
+			f.cache[pendingID] = true
+		}
+	}
 }