jldb/mdb/pfile/freelist.go

package pfile

import "container/heap"

// ----------------------------------------------------------------------------
// The intHeap is used to store the free list.
// ----------------------------------------------------------------------------

type intHeap []uint64

func (h intHeap) Len() int           { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h intHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *intHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(uint64))
}

func (h *intHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// ----------------------------------------------------------------------------
// Free list
// ----------------------------------------------------------------------------

type freeList struct {
	h        intHeap
	nextPage uint64
}

// newFreeList creates a new free list that will return available pages from
// smallest to largest. If there are no available pages, it will return new
// pages starting from nextPage.
func newFreeList(pageCount uint64) *freeList {
	return &freeList{
		h:        []uint64{},
		nextPage: pageCount,
	}
}

func (f *freeList) Push(pages ...uint64) {
	for _, page := range pages {
		heap.Push(&f.h, page)
	}
}

func (f *freeList) SetNextPage(nextPage uint64) {
	f.nextPage = nextPage
}

func (f *freeList) Pop(count int, out []uint64) []uint64 {
	out = out[:0]

	for len(out) < count && len(f.h) > 0 {
		out = append(out, heap.Pop(&f.h).(uint64))
	}

	for len(out) < count {
		out = append(out, f.nextPage)
		f.nextPage++
	}

	return out
}