bbolt features two types of freelist: "array" and "hashmap". They are currently implemented in one monolithic struct, with their differences in functions separated into two go files.

Testing has been a pain so far, with many of the freelist details (i.e.releasing pages and serde to disk) leaking outside of the freelist struct. This makes reasoning about the implementations very difficult, too. Adding a new type of list is becoming increasingly cumbersome without a proper interface.

Quickly pulling out the existing functions into an interface could look like this:

type Freelist interface {

	// Init initializes this freelist with the given list of pages. 
        // TODO currently is "readIDs", maybe should be called Read(page *common.Page)
	Init(ids common.Pgids) 

	// Allocate returns the starting page id of a contiguous block of a given size in number of pages.
	// If a contiguous block cannot be found then 0 is returned.
	Allocate(txid common.Txid, numPages int) common.Pgid

	// Count returns the number of free pages.
	Count() int

	// FreePageIds returns all free pages.
	FreePageIds() common.Pgids

	// MergeSpans merges the given pages into the existing freelist.
	MergeSpans(ids common.Pgids) // TODO should probably named "Release" or "Free"

	// Write writes the freelist into the given page. The freelist MUST fit into the given page.
	Write(page *common.Page) error
}

Ideally we would move this into its own internal package in order to avoid leaking any more internals in the future. HashMap and Array should be two implementation as its own struct. Some shared functions (ie read/write) could be implemented in a common struct for now. Even though I expect those to become implementation dependent at some point, it seems quite inefficient to write low-digit uint64 integers without vint compression (or as a bitset), for example.