page

Documentation

Overview

Package page describes generic pages. The generic description is independent from any implementation version.

Index

• Constants
• type CellType
  • func (i CellType) String() string
• type CellTyper
• type Error
  • func (e Error) Error() string
• type ID
• type Page
  • func Load(data []byte) (*Page, error)
  • func New(id ID) *Page
  • func (p *Page) Cell(key []byte) (CellTyper, bool)
  • func (p *Page) CellCount() uint16
  • func (p *Page) Cells() (result []CellTyper)
  • func (p *Page) ClearDirty()
  • func (p *Page) Defragment()
  • func (p *Page) DeleteCell(key []byte) (bool, error)
  • func (p *Page) Dirty() bool
  • func (p *Page) FindFreeSlotForSize(dataSize uint16) (Slot, bool)
  • func (p *Page) Fragmentation() float32
  • func (p *Page) FreeSlots() (result []Slot)
  • func (p *Page) ID() ID
  • func (p *Page) MarkDirty()
  • func (p *Page) OccupiedSlots() (result []Slot)
  • func (p *Page) RawData() []byte
  • func (p *Page) StorePointerCell(cell PointerCell) error
  • func (p *Page) StoreRecordCell(cell RecordCell) error
• type PointerCell
  • func (PointerCell) Type() CellType
• type RecordCell
  • func (RecordCell) Type() CellType
• type Slot

Constants

const (
	ErrUnknownHeader   = Error("unknown header")
	ErrInvalidPageSize = Error("invalid page size")
	ErrPageFull        = Error("page is full")
)

Sentinel errors.

const (
	// Size is the fix size of a page, which is 16KB or 16384 bytes.
	Size = 1 << 14
	// HeaderSize is the fix size of a page header, which is 10 bytes.
	HeaderSize = 6
)

const (
	// SlotByteSize is the size of an Offset, in the Go memory layout as well as
	// in the serialized form.
	SlotByteSize = uint16(unsafe.Sizeof(Slot{})) // #nosec
)

Types

type CellType

type CellType uint8

CellType is the type of a page.

const (
	// CellTypeUnknown indicates a corrupted page or an incorrectly decoded
	// cell.
	CellTypeUnknown CellType = iota
	// CellTypeRecord indicates a RecordCell, which stores a key and a variable
	// size record.
	CellTypeRecord
	// CellTypePointer indicates a PointerCell, which stores a key and an
	// uint32, which points to another page.
	CellTypePointer
)

func (CellType) String

func (i CellType) String() string

type CellTyper

type CellTyper interface {
	Type() CellType
}

CellTyper describes a component that has a cell type.

type Error

type Error string

Error is a sentinel error.

func (Error) Error

func (e Error) Error() string

type ID

type ID = uint32

ID is the type of a page ID. This is mainly to avoid any confusion. Changing this will break existing database files, so only change during major version upgrades.

type Page

type Page struct {
	// contains filtered or unexported fields
}

Page is a page implementation that does not support overflow pages. It is not meant for that. Since we want to separate index and data, records should not contain datasets, but rather enough information, to find the corresponding dataset in a data file.

func Load

func Load(data []byte) (*Page, error)

Load loads the given data into the page. The length of the given data byte slice may differ from v1.PageSize, however, it cannot exceed ^uint16(0)-1 (65535 or 64KB), and must be larger than 22 (HeaderSize(=10) + 1 Offset(=4) + 1 empty cell(=8)).

func New

func New(id ID) *Page

New creates a new page with the given ID.

func (*Page) Cell

func (p *Page) Cell(key []byte) (CellTyper, bool)

Cell returns a cell from this page with the given key, or false if no such cell exists in this page. In that case, the returned page is also nil.

func (*Page) CellCount

func (p *Page) CellCount() uint16

CellCount returns the amount of stored cells in this page. This value is NOT constant.

func (*Page) Cells

func (p *Page) Cells() (result []CellTyper)

Cells decodes all cells in this page, which can be expensive, and returns all of them. The returned cells do not point back to the original page data, so don't modify them. Instead, delete the old cell and store a new one.

func (*Page) ClearDirty

func (p *Page) ClearDirty()

ClearDirty marks this page as NOT dirty.

func (*Page) Defragment

func (p *Page) Defragment()

Defragment will move the cells in the page in a way that after defragmenting, there is only a single free block, and that is located between the offsets and the cell data. After calling this method, (*Page).Fragmentation() will return 0.

func (*Page) DeleteCell

func (p *Page) DeleteCell(key []byte) (bool, error)

DeleteCell deletes a cell with the given key. If no such cell could be found, false is returned. In this implementation, an error can not occur while deleting a cell.

func (*Page) Dirty

func (p *Page) Dirty() bool

Dirty returns whether the page is dirty (needs syncing with secondary storage).

func (*Page) FindFreeSlotForSize

func (p *Page) FindFreeSlotForSize(dataSize uint16) (Slot, bool)

FindFreeSlotForSize searches for a free slot in this page, matching or exceeding the given data size. This is done by using a best-fit algorithm.

func (*Page) Fragmentation

func (p *Page) Fragmentation() float32

Fragmentation computes the page fragmentation, which is defined by 1 - (largest free block / total free size). Multiply with 100 to get the fragmentation percentage.

func (*Page) FreeSlots

func (p *Page) FreeSlots() (result []Slot)

FreeSlots computes all free addressable cell slots in this page. The free slots are sorted in ascending order by the offset in the page.

func (*Page) ID

func (p *Page) ID() ID

ID returns the ID of this page. This value must be constant.

func (*Page) MarkDirty

func (p *Page) MarkDirty()

MarkDirty marks this page as dirty.

func (*Page) OccupiedSlots

func (p *Page) OccupiedSlots() (result []Slot)

OccupiedSlots returns all occupied slots in the page. The slots all point to cells in the page. The amount of slots will always be equal to the amount of cells stored in a page. The amount of slots in the page depends on the cell count of this page, not the other way around.

func (*Page) RawData

func (p *Page) RawData() []byte

RawData returns a copy of the page's internal data, so you can modify it at will, and it won't change the original page data.

func (*Page) StorePointerCell

func (p *Page) StorePointerCell(cell PointerCell) error

StorePointerCell stores a pointer cell in this page. A pointer cell points to other page IDs.

func (*Page) StoreRecordCell

func (p *Page) StoreRecordCell(cell RecordCell) error

StoreRecordCell stores a record cell in this page. A record cell holds arbitrary, variable size data.

type PointerCell

type PointerCell struct {
	Key     []byte
	Pointer ID
}

PointerCell is a cell with CellTypePointer. It holds a key and an uint32, pointing to another page.

func (PointerCell) Type

func (PointerCell) Type() CellType

Type returns CellTypePointer.

type RecordCell

type RecordCell struct {
	Key    []byte
	Record []byte
}

RecordCell is a cell with CellTypeRecord. It holds a key and a variable size record.

func (RecordCell) Type

func (RecordCell) Type() CellType

Type returns CellTypeRecord.

type Slot

type Slot struct {
	// Offset is the Offset of the data in the page data slice. If overflow page
	// support is added, this might need to be changed to an uint32.
	Offset uint16
	// Size is the length of the data segment in the page data slice. If
	// overflow page support is added, this might need to be changed to an
	// uint32.
	Size uint16
}

Slot represents a data slot in the page. A slot consists of an offset and a size.