1 files changed, 25 insertions, 18 deletions

diff --git a/freelist.go b/freelist.go
index ebe2810..0d79bb4 100644
--- a/freelist.go
+++ b/freelist.go
@@ -26,30 +26,42 @@ func (f *freelist) all() []pgid {
 		ids = append(ids, list...)
 	}
 
-	sort.Sort(reverseSortedPgids(ids))
+	sort.Sort(pgids(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
+	if len(f.ids) == 0 {
+		return 0
+	}
+
+	var initial, previd pgid
 	for i, id := range f.ids {
-		// Reset count if this is not contiguous.
-		if previd == 0 || previd-id != 1 {
-			count = 1
+		_assert(id > 1, "invalid page allocation: %d", id)
+
+		// Reset initial page if this is not contiguous.
+		if previd == 0 || id-previd != 1 {
+			initial = id
 		}
 
 		// 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
+		if (id-initial)+1 == pgid(n) {
+			// If we're allocating off the beginning then take the fast path
+			// and just adjust the existing slice. This will use extra memory
+			// temporarily but the append() in free() will realloc the slice
+			// as is necessary.
+			if (i + 1) == n {
+				f.ids = f.ids[i+1:]
+			} else {
+				copy(f.ids[i-1:], f.ids[i+n-1:])
+				f.ids = f.ids[:len(f.ids)-n]
+			}
+			return initial
 		}
 
 		previd = id
-		count++
 	}
 	return 0
 }
@@ -74,7 +86,7 @@ func (f *freelist) release(txid txid) {
 			delete(f.pending, tid)
 		}
 	}
-	sort.Sort(reverseSortedPgids(f.ids))
+	sort.Sort(pgids(f.ids))
 }
 
 // isFree returns whether a given page is in the free list.
@@ -99,6 +111,7 @@ 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)
+	sort.Sort(pgids(ids))
 }
 
 // write writes the page ids onto a freelist page. All free and pending ids are
@@ -133,9 +146,3 @@ func (f *freelist) check() {
 	}
 }
 */
-
-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] }