Merge pull request #219 from benbjohnson/freelist-overflow

Allow freelist overflow.

1 files changed, 26 insertions, 9 deletions

diff --git a/freelist.go b/freelist.go
index a297354..150e3e6 100644
--- a/freelist.go
+++ b/freelist.go
@@ -149,10 +149,23 @@ func (f *freelist) freed(pgid pgid) bool {
 
 // read initializes the freelist from a freelist page.
 func (f *freelist) read(p *page) {
-	ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0:p.count]
+	// If the page.count is at the max uint16 value (64k) then it's considered
+	// an overflow and the size of the freelist is stored as the first element.
+	idx, count := 0, int(p.count)
+	if count == 0xFFFF {
+		idx = 1
+		count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
+	}
+
+	// Copy the list of page ids from the freelist.
+	ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
 	f.ids = make([]pgid, len(ids))
 	copy(f.ids, ids)
+
+	// Make sure they're sorted.
 	sort.Sort(pgids(f.ids))
+
+	// Rebuild the page cache.
 	f.reindex()
 }
 
@@ -163,15 +176,19 @@ func (f *freelist) write(p *page) error {
 	// Combine the old free pgids and pgids waiting on an open transaction.
 	ids := f.all()
 
-	// Make sure that the sum of all free pages is less than the max uint16 size.
-	if len(ids) >= 65565 {
-		return ErrFreelistOverflow
-	}
-
-	// Update the header and write the ids to the page.
+	// Update the header flag.
 	p.flags |= freelistPageFlag
-	p.count = uint16(len(ids))
-	copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+
+	// The page.count can only hold up to 64k elements so if we overflow that
+	// number then we handle it by putting the size in the first element.
+	if len(ids) < 0xFFFF {
+		p.count = uint16(len(ids))
+		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
+	} else {
+		p.count = 0xFFFF
+		((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(len(ids))
+		copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:], ids)
+	}
 
 	return nil
 }