btree

package
v0.0.0-...-c110fa1 Latest Latest
Warning

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

 Go to latest Published: Jan 14, 2026 License: Apache-2.0 Imports: 12 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllLeaves 

func AllLeaves[
	TMessage any,
	TMessagePtr interface {
		*TMessage
		proto.Message
	},
	TReference any,
](
	ctx context.Context,
	reader model_parser.MessageObjectReader[TReference, []TMessagePtr],
	root model_core.Message[[]TMessagePtr, TReference],
	traverser Traverser[TMessagePtr, TReference],
	errOut *error,
) iter.Seq[model_core.Message[TMessagePtr, TReference]]

AllLeaves can be used to iterate all leaf entries contained in a B-tree.

func AllLeavesSkippingDuplicateParents 

func AllLeavesSkippingDuplicateParents[
	TMessage any,
	TMessagePtr interface {
		*TMessage
		proto.Message
	},
	TReference object.BasicReference,
](
	ctx context.Context,
	reader model_parser.MessageObjectReader[TReference, []TMessagePtr],
	root model_core.Message[[]TMessagePtr, TReference],
	traverser Traverser[TMessagePtr, TReference],
	parentsSeen map[model_core.Decodable[object.LocalReference]]struct{},
	errOut *error,
) iter.Seq[model_core.Message[TMessagePtr, TReference]]

AllLeavesSkippingDuplicateParents is identical to AllLeaves(), except that it only traverses the first occurrence of a parent object. This can be used to traverse structures that contain a large amount of redundancy, such as depsets.

Note that this function does not perform deduplication of leaves. Only parents are deduplicated.

func Find 

func Find[
	TMessage any,
	TMessagePtr interface {
		*TMessage
		proto.Message
	},
	TReference any,
](
	ctx context.Context,
	reader model_parser.MessageObjectReader[TReference, []TMessagePtr],
	list model_core.Message[[]TMessagePtr, TReference],
	cmp func(model_core.Message[TMessagePtr, TReference]) (int, *model_core_pb.DecodableReference),
) (model_core.Message[TMessagePtr, TReference], error)

Find an entry contained in a B-tree.

func MaybeMergeNodes 

func MaybeMergeNodes[TNode proto.Message, TMetadata model_core.ReferenceMetadata](
	nodes []TNode,
	externalObject *model_core.Decodable[model_core.CreatedObject[TMetadata]],
	patcher *model_core.ReferenceMessagePatcher[TMetadata],
	parentNodeComputer ParentNodeComputer[TNode, TMetadata],
) ([]TNode, error)

MaybeMergeNodes either returns the top-level elements of a B-tree in literal form, or emits a single parent node referring to the elements stored in a separate object.

This function is typically used in combination with inlinedtree.Build() to spill the top-level elements of a B-tree into a separate object, if storing them inline would cause the parent object to become too large.

Types

type Builder 

type Builder[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface {
	PushChild(node model_core.PatchedMessage[TNode, TMetadata]) error
	FinalizeList() (model_core.PatchedMessage[[]TNode, TMetadata], error)
	FinalizeSingle() (model_core.PatchedMessage[TNode, TMetadata], error)
	Discard()
}

Builder of B-trees.

func NewHeightAwareBuilder 

func NewHeightAwareBuilder[TNode proto.Message, TMetadata model_core.ReferenceMetadata](chunkerFactory ChunkerFactory[TNode, TMetadata], nodeMerger NodeMerger[TNode, TMetadata]) Builder[TNode, TMetadata]

NewHeightAwareBuilder creates a B-tree builder that is in the initial state (i.e., does not contain any nodes).

Regular B-trees have a uniform depth, meaning that all leaves are stored at the same distance from the root. However, this implementation differs from that in that it stores leaves may be stored at higher levels in the tree, depending on their own height. This ensures that the overall height of the tree is minimized.

type CapturedParentNodeComputer 

type CapturedParentNodeComputer[TNode any, TMetadata model_core.ReferenceMetadata] func(
	createdObject model_core.Decodable[model_core.MetadataEntry[TMetadata]],
	childNodes model_core.Message[[]TNode, object.LocalReference],
) model_core.PatchedMessage[TNode, TMetadata]

CapturedParentNodeComputer is a simplified version of ParentNodeAppender that receives an already captured object, as opposed to receiving the literal contents of the created object. This is sufficient for most parent node computers.

type Chunker 

type Chunker[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface {
	PushSingle(node model_core.PatchedMessage[TNode, TMetadata]) error
	PopMultiple(threshold PopThreshold) model_core.PatchedMessageList[TNode, TMetadata]
	Discard()
}

Chunker is responsible for determining how nodes at a given level in the B-tree are chunked and spread out across sibling objects at the same level.

type ChunkerFactory 

type ChunkerFactory[TNode proto.Message, TMetadata model_core.ReferenceMetadata] interface {
	NewChunker() Chunker[TNode, TMetadata]
}

ChunkerFactory is a factory type for creating chunkers of individual levels of a B-tree.

func NewProllyChunkerFactory 

func NewProllyChunkerFactory[TMetadata model_core.ReferenceMetadata, TNode proto.Message](
	minimumSizeBytes, maximumSizeBytes int,
	isParent func(TNode) bool,
) ChunkerFactory[TNode, TMetadata]

NewProllyChunkerFactory returns a ChunkerFactory that is capable of creating Chunkers that perform probabilistic chunking, leading to the creation of a Prolly Tree:

https://docs.dolthub.com/architecture/storage-engine/prolly-tree

For each node that is inserted, an FNV-1a hash is computed based on the node's message contents and outgoing references. A cut is made after the node where the hash is maximal.

The size computation that is used by this type assumes that the resulting nodes are stored in an object where each node is prefixed with a variable length integer indicating the node's size.

type ChunkerFactoryForTesting 

type ChunkerFactoryForTesting ChunkerFactory[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

ChunkerFactoryForTesting is an instantiation of ChunkerFactory for generating mocks to be used by tests.

type ChunkerForTesting 

type ChunkerForTesting Chunker[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

ChunkerForTesting is an instantiation of Chunker for generating mocks to be used by tests.

type NodeMerger 

type NodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata] func(model_core.PatchedMessage[[]TNode, TMetadata]) (model_core.PatchedMessage[TNode, TMetadata], error)

NodeMerger is invoked whenever a list of tree nodes is gathered that should be placed as siblings in a single B-tree object. It is responsible for constructing the B-tree object and yielding a message that can be placed in the parent object to reference it.

func NewObjectCreatingNodeMerger 

func NewObjectCreatingNodeMerger[TNode proto.Message, TMetadata model_core.ReferenceMetadata](encoder model_encoding.DeterministicBinaryEncoder, referenceFormat object.ReferenceFormat, parentNodeComputer ParentNodeComputer[TNode, TMetadata]) NodeMerger[TNode, TMetadata]

NewObjectCreatingNodeMerger creates a NodeMerger that can be used in combination with Builder to construct B-trees that are backed by storage objects that reference each other.

type NodeMergerForTesting 

type NodeMergerForTesting NodeMerger[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

NodeMergerForTesting is an instantiation of NodeMerger for generating mocks to be used by tests.

type ParentNodeComputer 

type ParentNodeComputer[TNode any, TMetadata model_core.ReferenceMetadata] func(
	createdObject model_core.Decodable[model_core.CreatedObject[TMetadata]],
	childNodes []TNode,
) (model_core.PatchedMessage[TNode, TMetadata], error)

ParentNodeComputer can be used by ObjectCreatingNodeMerger to combine the values of nodes stored in an object into a single node that can be stored in its parent.

func Capturing 

func Capturing[TNode any, TMetadata model_core.ReferenceMetadata](
	ctx context.Context,
	capturer model_core.CreatedObjectCapturer[TMetadata],
	parentNodeComputer CapturedParentNodeComputer[TNode, TMetadata],
) ParentNodeComputer[TNode, TMetadata]

Capturing converts a CapturedParentNodeComputer to a plain ParentNodeComputer.

type ParentNodeComputerForTesting 

type ParentNodeComputerForTesting ParentNodeComputer[*model_filesystem_pb.FileContents, model_core.ReferenceMetadata]

ParentNodeComputerForTesting is an instantiation of ParentNodeComputer for generating mocks to be used by tests.

type PopThreshold 

type PopThreshold int

PopThreshold can be provided to Chunker.PopMultiple() to control how up to which node that was pushed chunks may be returned. 

const (
	// PopDefinitive only pops chunks of nodes if it is certain that
	// no future pushes will affect the chunking process up to that
	// point. This can be used to flush definitive parts of a B-tree
	// to storage, so that memory usage remains bounded.
	PopDefinitive PopThreshold = iota
	// PopChild only pops chunks of nodes if it is certain that the
	// current level of the B-tree is not going to be the root.
	PopChild
	// PopLargeEnough only pops chunks of nodes if they are at least as
	// large as the desired minimum size.
	PopLargeEnough
	// PopAll pop chunks containing all nodes that were pushed, even
	// if it leads to chunks that are smaller than the desired
	// minimum size. This can be used to finalize a B-tree.
	PopAll
)

type Traverser 

type Traverser[TMessage, TReference any] func(model_core.Message[TMessage, TReference]) (*model_core_pb.DecodableReference, error)

Traverser is called by AllLeaves() to extract references of nested parent objects from B-tree entries.

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.