Module freelist 

Persisted free-page list (SQLR-6).

After DROP TABLE / DROP INDEX / ALTER TABLE DROP COLUMN, the next save_database no longer references the dropped object’s pages. Without a freelist those pages would either be re-numbered (every later table shifts down → high write amplification) or stranded as orphans on disk.

The freelist solves both: pages no longer referenced from sqlrite_master go on a persisted stack rooted at header.freelist_head, so subsequent saves can pull from there before extending the file. The unrelated tables that didn’t change keep their page numbers and their pages re-stage byte- identical → the diff pager skips writing them.

On-disk layout

Each freelist trunk page carries the standard 7-byte page header with page_type = PAGE_TYPE_FREELIST_TRUNK (5) and next_page pointing at the next trunk in the chain (0 = end). The 4089-byte payload area holds:

  0..2      count: u16 LE       — number of free leaf-page IDs that follow
  2..2+4*N  page_ids[N]: u32 LE — free leaf-page numbers, ascending

A trunk holds up to (PAYLOAD_PER_PAGE - 2) / 4 = 1021 free page IDs. Larger freelists chain across multiple trunks. The trunk pages themselves are part of the live page set (they hold metadata) and are not on the freelist they encode.

Constants

FREELIST_IDS_PER_TRUNK

Maximum number of free page IDs a single trunk page can hold. PAYLOAD_PER_PAGE is 4089; we reserve 2 bytes for the count and 4 bytes per ID, giving (4089 - 2) / 4 = 1021.

MIN_PAGES_FOR_AUTO_VACUUM

Auto-VACUUM (SQLR-10) does not fire on databases below this many pages. The 4 KiB page size makes 16 pages = 64 KiB — small enough that the cost of a full-file rewrite is negligible if the user genuinely wants it (manual VACUUM; still works), but large enough that single-table churn doesn’t blow past the threshold and trigger a noisy compact every few statements.

PAGE_TYPE_FREELIST_TRUNK

Page-type tag for a freelist trunk page. Distinct from existing page tags (2 = TableLeaf, 3 = Overflow, 4 = InteriorNode); 1 was retired.

Functions

encode_trunk

Encodes a single freelist trunk page into the given buffer.

freelist_to_deque

Helper: collect a freelist into a VecDeque<u32> sorted ascending — the ordering the PageAllocator uses to draw next free pages from.

read_freelist

Walks the freelist chain rooted at head and returns every free leaf-page ID. The trunk pages themselves are not included — they’re live metadata. Returns the trunk page numbers separately so the caller can release them (the next save re-encodes the freelist from scratch and frees the old trunks for reuse).

should_auto_vacuum

Returns true if the on-disk freelist (counting both leaf and trunk pages — they’re all reclaimable bytes) exceeds threshold of header.page_count, i.e. the file is bloated enough to be worth compacting. Returns false for tiny databases (under MIN_PAGES_FOR_AUTO_VACUUM) and for empty freelists, both as fast paths to keep the auto-VACUUM hook cheap on the common case.

stage_freelist

Stages the freelist chain into the pager. free_pages is the full set of pages that need persisted-on-the-freelist treatment — both the trunk pages (metadata) and the leaf entries (the actually-free leaves).