page

package
v0.6.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 1, 2026 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	MetaPageBodySizeLegacy       = 60
	MetaPageBodySizeCommandWALV1 = 76
	MetaPageBodySizeRevisionV1   = 92
	MetaPageBodySize             = MetaPageBodySizeRevisionV1
)
View Source 
const (
	// PageSize is the fixed size of a page in bytes.
	PageSize = 4096

	// DefaultInlineThreshold determines when a value is stored in the value log.
	DefaultInlineThreshold = 512

	// PageHeaderSize is the size of the PageHeader struct.
	PageHeaderSize = 16

	// ValuePtrSize is the size of the ValuePtr struct.
	ValuePtrSize = 16

	// PackedValuePtrSize is the on-disk size of a packed ValuePtr encoding.
	//
	// Layout: Offset32 (u32 LE) | Length (u32 LE) | FileID (u32 LE).
	// This is used by experimental leaf encodings to reduce pointer payload.
	PackedValuePtrSize = 12

	// EntryRevisionSize is the on-page size of a native raw-KV entry revision.
	EntryRevisionSize = 8
)
View Source 
const LogRecordRefSize = 18 // u32 file | u64 offset | u32 length hint | u16 sub-index
View Source 
const MaxFreeIDs = 509

MaxFreeIDs per page. PageSize (4096) - Header (16) - NextPageID (8) = 4072 bytes. Each ID = 8 bytes. 4072 / 8 = 509.

View Source 
const ValuePtrGroupedMaxRecordLen uint32 = 0x007fffff

ValuePtrGroupedMaxRecordLen is the maximum record length (excluding CRC) that can be encoded in a grouped ValuePtr length hint for new writes.

Grouped pointers embed a sub-index in the Length field, leaving 23 bits for a best-effort record length hint. Larger records must set the hint to 0 and rely on the value-log record header's ValueLen instead.

Variables

View Source 
var ErrFreelistEmpty = errors.New("freelist page is empty")
View Source 
var ErrFreelistFull = errors.New("freelist page is full")
View Source 
var ErrInvalidPageType = errors.New("invalid page type")

Functions

func CalculateChecksum 

func CalculateChecksum(data []byte) uint32

CalculateChecksum computes the checksum of the page data, treating checksum bytes 8-11 (data[8:12]) as zero.

func CalculateChecksumWithZeroGap added in v0.6.0 

func CalculateChecksumWithZeroGap(prefix []byte, gapLen int, suffix []byte) uint32

CalculateChecksumWithZeroGap computes the checksum for a logical page made of prefix + zero-filled gap + suffix. The prefix must include the checksum field at bytes 8-11, which is treated as zero.

func Checksum 

func Checksum(data []byte) uint32

Checksum returns the CRC-32/IEEE checksum of data.

func EncodeLogRecordRef added in v0.6.0 

func EncodeLogRecordRef(dst []byte, ref LogRecordRef)

func EncodePackedValuePtr added in v0.3.0 

func EncodePackedValuePtr(dst []byte, ptr ValuePtr)

EncodePackedValuePtr encodes ptr into dst using the packed 12-byte encoding. dst must be at least PackedValuePtrSize bytes.

Packed pointers store Offset as u32. Callers must ensure ptr.Offset fits.

func IsValueLogFileID 

func IsValueLogFileID(id uint32) bool

IsValueLogFileID reports whether the FileID references a value-log segment.

func UpdateChecksum added in v0.4.0 

func UpdateChecksum(data []byte) uint32

UpdateChecksum computes CRC-32/IEEE for the page while treating checksum bytes 8-11 (data[8:12]) as zero, then writes the computed checksum back into the page header. It mutates data in-place and returns the computed checksum.

func ValueLogFileID 

func ValueLogFileID(id uint32) uint32

ValueLogFileID marks a value-log segment ID for use in ValuePtr.FileID.

func ValueLogSegmentID 

func ValueLogSegmentID(id uint32) uint32

ValueLogSegmentID strips the value-log marker bit from a FileID.

func ValuePtrIsCompressed 

func ValuePtrIsCompressed(ptr ValuePtr) bool

ValuePtrIsCompressed reports whether the pointer references a compressed value.

func ValuePtrIsGrouped added in v0.2.0 

func ValuePtrIsGrouped(ptr ValuePtr) bool

ValuePtrIsGrouped reports whether the pointer references a grouped record.

func ValuePtrMarkCompressed 

func ValuePtrMarkCompressed(length uint32) uint32

ValuePtrMarkCompressed sets the compression flag on a record length.

func ValuePtrMarkGrouped added in v0.2.0 

func ValuePtrMarkGrouped(length uint32, subIndex uint8) uint32

ValuePtrMarkGrouped sets the grouped flag and sub-index on a record length.

func ValuePtrRecordLength 

func ValuePtrRecordLength(ptr ValuePtr) uint32

ValuePtrRecordLength returns the record length with internal flags stripped.

func ValuePtrRecordLengthHintMatches added in v0.4.0 

func ValuePtrRecordLengthHintMatches(ptr ValuePtr, expected uint32) bool

ValuePtrRecordLengthHintMatches reports whether the encoded record-length hint matches expected.

A zero hint means "omitted hint" and always matches.

func ValuePtrSubIndex added in v0.2.0 

func ValuePtrSubIndex(ptr ValuePtr) uint8

ValuePtrSubIndex returns the row index within a grouped record.

func VerifyChecksumNonMutating 

func VerifyChecksumNonMutating(data []byte) bool

VerifyChecksumNonMutating verifies that the page checksum matches the data, assuming checksum bytes 8-11 (data[8:12]) are zero for the calculation. It avoids modifying the underlying buffer.

Types

type ChildRef added in v0.6.0 

type ChildRef struct {
	Kind ChildRefKind
	Page uint64
	Log  LogRecordRef
}

ChildRef is a typed child reference used by tree/internal-node code.

func LeafLogChildRef added in v0.6.0 

func LeafLogChildRef(ptr LogRecordRef) ChildRef

func PageChildRef added in v0.6.0 

func PageChildRef(pageID uint64) ChildRef

func (ChildRef) IsLeafLog added in v0.6.0 

func (r ChildRef) IsLeafLog() bool

func (ChildRef) IsPage added in v0.6.0 

func (r ChildRef) IsPage() bool

type ChildRefKind added in v0.6.0 

type ChildRefKind uint8

ChildRefKind identifies the storage class of an internal-page child.

TODO(treedb-format): This is currently modeled explicitly in memory. For on-disk internal pages, the kind is page-level rather than per child, and a future compact format can encode that more densely. 

const (
	ChildRefPage ChildRefKind = iota
	ChildRefLeafLog
)

type EntryRevision added in v0.6.1 

type EntryRevision uint64

EntryRevision is TreeDB's monotonic visible-entry token for raw KV values.

A zero revision means legacy/no-revision metadata. Non-zero revisions travel with native write data and leaf entries instead of through a side index. 

const LegacyEntryRevision EntryRevision = 0

type FreelistPageBody 

type FreelistPageBody struct {
	NextPageID uint64
	FreeIDs    []uint64
}

FreelistPageBody represents the body of a Freelist Page. Layout: NextPageID (8 bytes) Count (2 bytes) -- Wait, Header has Count? Standard Header has `Count`. We can use that. But we need to encode the array. NextPageID (8 bytes) + Array[uint64]

func DecodeFreelistBody 

func DecodeFreelistBody(buf []byte, count uint16) FreelistPageBody

func (*FreelistPageBody) Encode 

func (f *FreelistPageBody) Encode(buf []byte)

type LeafLogPtr added in v0.5.0 

type LeafLogPtr = LogRecordRef

LeafLogPtr is retained as the public/internal name for leaf-log records while the underlying representation becomes explicit.

func LeafLogPtrFromValuePtr added in v0.5.0 

func LeafLogPtrFromValuePtr(ptr ValuePtr) (LeafLogPtr, error)

type LogRecordRef added in v0.6.0 

type LogRecordRef struct {
	FileID uint32
	Offset uint64
	// RecordLengthHint stores the value-log pointer length hint, including any
	// ValuePtr grouping/compression flags needed to reconstruct a ValuePtr.
	RecordLengthHint uint32
	SubIndex         uint16
}

LogRecordRef points to a record inside a persistent TreeDB value/leaf log.

This is intentionally wider and more explicit than the historical packed LeafRef page-id encoding. TreeDB is pre-alpha, so prefer first-class fields over bit stealing here; compact page-local encodings can be added after the format is easier to reason about.

func DecodeLogRecordRef added in v0.6.0 

func DecodeLogRecordRef(src []byte) LogRecordRef

func (LogRecordRef) IsGrouped added in v0.6.0 

func (ptr LogRecordRef) IsGrouped() bool

func (LogRecordRef) RecordLength added in v0.6.0 

func (ptr LogRecordRef) RecordLength() uint32

func (LogRecordRef) ValueLogFileID added in v0.6.0 

func (ptr LogRecordRef) ValueLogFileID() uint32

func (LogRecordRef) ValuePtr added in v0.6.0 

func (ptr LogRecordRef) ValuePtr() ValuePtr

type MetaPageBody 

type MetaPageBody struct {
	CommitSeq         uint64
	UserRootPageID    uint64
	SystemRootPageID  uint64
	FreelistHeadID    uint64
	TotalPages        uint64
	ActiveSlabID      uint32
	ActiveSlabTail    uint64
	LastCommitHeight  uint64
	AppliedCommandLSN uint64
	MaxEntryRevision  uint64
}

MetaPageBody represents the body of the Superblock.

func DecodeMetaBody 

func DecodeMetaBody(buf []byte) MetaPageBody

DecodeMetaBody decodes the legacy-safe MetaPageBody fields from the provided buffer. The command-WAL AppliedCommandLSN extension requires an explicit in-page marker and is decoded by DecodeMetaBodyCommandWALV1.

func DecodeMetaBodyCommandWALV1 added in v0.6.0 

func DecodeMetaBodyCommandWALV1(buf []byte) MetaPageBody

DecodeMetaBodyCommandWALV1 decodes marked meta extensions. Legacy pages and unmarked buffers decode with zero extension fields.

func (*MetaPageBody) Encode 

func (m *MetaPageBody) Encode(buf []byte)

EncodeMetaBody encodes the MetaPageBody into the provided buffer. 

type PageHeader struct {
	PageID   uint64
	Checksum uint32
	Flags    uint16
	Count    uint16
}

PageHeader represents the 16-byte header of a page. | PageID (8 bytes) | | Checksum (4 bytes) | | Flags (2 bytes) | | Count (2 bytes) |

func DecodeHeader 

func DecodeHeader(buf []byte) PageHeader

DecodeHeader decodes the PageHeader from the provided buffer.

func UnsafeCastHeader 

func UnsafeCastHeader(data []byte) *PageHeader

CastHeader casts the beginning of a byte slice to a PageHeader struct pointer. Use with caution: implies unsafe access and assumes strict layout matching. This is an alternative to Encode/Decode for zero-copy access if needed, but requires the struct memory layout to match the wire format (packing). Go structs usually have padding/alignment. PageHeader: 8 + 4 + 2 + 2 = 16 bytes. Naturally aligned. ValuePtr: 8 + 4 + 2 + 2 = 16 bytes. Naturally aligned. So, we can use unsafe casting if endianness matches the machine's endianness. However, the spec requires LittleEndian. If the host is BigEndian, this fails. For now, we stick to Encode/Decode or binary.LittleEndian read/write for safety across archs unless zero-copy is strictly required and we add endianness checks. The spec mentions: "Implementation Note: To maximize throughput... use unsafe.Pointer casting". This implies the on-disk format should match the in-memory struct layout, AND the machine is likely LittleEndian (standard for Cosmos/x86/ARM). Let's implement a UnsafeCastHeader for when we have the mmap slice.

func (*PageHeader) Encode 

func (h *PageHeader) Encode(buf []byte)

EncodeHeader encodes the PageHeader into the provided buffer. The buffer must be at least PageHeaderSize bytes.

type PageType 

type PageType uint16

PageType represents the type of page (Meta, Freelist, Internal, Leaf). 

const (
	PageTypeMeta     PageType = 0x01
	PageTypeFreelist PageType = 0x02
	PageTypeInternal PageType = 0x03
	PageTypeLeaf     PageType = 0x04
)

type ValuePtr 

type ValuePtr struct {
	Offset uint64
	Length uint32
	FileID uint32
}

ValuePtr points to data stored in the value log. | Offset (8 bytes) | // 8-byte aligned | Length (4 bytes) | | FileID (4 bytes) |

func DecodePackedValuePtr added in v0.3.0 

func DecodePackedValuePtr(src []byte) ValuePtr

DecodePackedValuePtr decodes a packed 12-byte ValuePtr from src. src must be at least PackedValuePtrSize bytes.

func DecodeValuePtr 

func DecodeValuePtr(buf []byte) ValuePtr

DecodeValuePtr decodes the ValuePtr from the provided buffer.

func (*ValuePtr) Encode 

func (v *ValuePtr) Encode(buf []byte)

EncodeValuePtr encodes the ValuePtr into the provided buffer. The buffer must be at least ValuePtrSize bytes.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.