atree

package module
v0.10.1 Latest Latest
Warning

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

 Go to latest Published: Aug 22, 2025 License: Apache-2.0 Imports: 15 Imported by: 36

README

Atree

Atree provides scalable arrays and scalable ordered maps. It segments, encodes, and stores data into relatively small, relatively fixed-size segments of bytes (aka payloads, registers, or slabs). This enables blockchains to only hash and transmit modified segments instead of the entire array, map, or large element.

Atree is used by Cadence in the Flow blockchain.

Inspired by patterns used in modern variants of B+ Trees, Atree provides two types of data structures: Scalable Array Type (SAT) and Ordered Map Type (OMT).

  • Scalable Array Type (SAT) is a heterogeneous variable-size array, storing any type of values into a smaller ordered list of values and provides efficient functionality to lookup, insert and remove elements anywhere in the array.

  • Ordered Map Type (OMT) is an ordered map of key-value pairs; keys can be any hashable type and values can be any serializable value type. It supports heterogeneous key or value types (e.g. first key storing a boolean and second key storing a string). OMT keeps values in specific sorted order and operations are deterministic so the state of the segments after a sequence of operations are always unique. OMT uses CircleHash64f with Deferred+Segmented BLAKE3 Digests.

Under the Hood

Atree uses new types of high-fanout B+ tree and some heuristics to balance the trade-off between latency of operations and the number of reads and writes.

Each data structure holds the data as several relatively fixed-size segments of bytes (aka payloads, registers, or slabs) forming a tree and as the size of data structures grows or shrinks, it adjusts the number of segments used. After each operation, Atree tries to keep segment size within an acceptable size range by merging segments when needed (lower than min threshold) and splitting large-size slabs (above max threshold) or moving some values to neighbouring segments (rebalancing). For ordered maps and arrays with small number of elements, Atree is designed to have a very minimal overhead in compare to less scalable standard array and ordermaps (using a single data segment at start).

In order to minimize the number of bytes touched after each operation, Atree uses a deterministic greedy approach ("Optimistic Encasing Algorithm") to postpone merge, split and rebalancing the tree as much as possible. In other words, it tolerates the tree to get unbalanced with the cost of keeping some space for future insertions or growing a segment a bit larger than what it should be which would minimize the number of segments (and bytes) that are touched at each operation.

Example

1 - An ordered map metadata slab keeps the very first key hash of any children to navigate the path. It uses a combination of linear scan and binary search to find the next slab.

2 - Similarly the array metadata slab keeps the count of each child and uses that to navigate the path.

3 - Nested structures (e.g. map holding an array under a key) are handled by storing nested map or array as separate objects and using a one-way reference from parent to the nested object.

4 - Extremely large objects are handled by storing them as an external data slab and using a pointer to the external data slab. This way we maintain the size requirements of slabs and preserve the performance of atree. In the future work external data slabs can be broken into a sequence of smaller size slabs.

5 - Atree Ordered Map uses a collision handling design that is performant and resilient against hash-flooding attacks. It uses multi-level hashing that combines a fast 64-bit non-cryptographic hash with a 256-bit cryptographic hash. For speed, the cryptographic hash is only computed if there's a collision. For smaller storage size, the digests are divided into 64-bit segments with only the minimum required being stored. Collisions that cannot be resolved by hashes will eventually use linear lookup, but that is very unlikely as it would require collisions on two different hashes (CircleHash64f + BLAKE3) from the same input.

6 - Forwarding data slab pointers are used to make sequential iterations more efficient.

OMT uses CircleHash64f with Deferred+Segmented BLAKE3 Digests

Inputs hashed by OMT are typically short inputs (usually smaller than 128 bytes). OMT uses state-of-the-art hash algorithms and a novel collision-handling design to balance speed, security, and storage space.

CircleHash64f 🏅
(seeded)		 SipHash
(seeded)		 BLAKE3 🏅
(crypto)		 SHA3-256
(crypto)
4 bytes 1.34 GB/s 0.361 GB/s 0.027 GB/s 0.00491 GB/s
8 bytes 2.70 GB/s 0.642 GB/s 0.106 GB/s 0.00984 GB/s
16 bytes 5.48 GB/s 1.03 GB/s 0.217 GB/s 0.0197 GB/s
32 bytes 8.01 GB/s 1.46 GB/s 0.462 GB/s 0.0399 GB/s
64 bytes 10.3 GB/s 1.83 GB/s 0.911 GB/s 0.0812 GB/s
128 bytes 12.8 GB/s 2.09 GB/s 1.03 GB/s 0.172 GB/s
192 bytes 14.2 GB/s 2.17 GB/s 1.04 GB/s 0.158 GB/s
256 bytes 15.0 GB/s 2.22 GB/s 1.06 GB/s 0.219 GB/s
  • Using Go 1.17.7, darwin_amd64, i7-1068NG7 CPU.
  • Results are from go test -bench=. -count=20 and benchstat.
  • Some hash libraries have slowdowns at some larger sizes.

API Reference

Atree's API is documented with godoc at pkg.go.dev and will be updated when new versions of Atree are tagged.

Contributing

If you would like to contribute to Atree, have a look at the contributing guide.

Additionally, all non-error code paths must be covered by tests. And pull requests should not lower the code coverage percent.

License

The Atree library is licensed under the terms of the Apache license. See LICENSE for more information.

Logo is based on the artwork of Raisul Hadi licensed under Creative Commons.

Copyright © 2021-2024 Flow Foundation

Documentation

Overview

Package atree provides scalable arrays and scalable ordered maps. It is used by Cadence in the Flow blockchain.

Atree is maintained at https://github.com/onflow/atree

Index

Constants

View Source 
const (
	CBORTagTypeInfoRef = 246

	CBORTagInlinedArrayExtraData      = 247
	CBORTagInlinedMapExtraData        = 248
	CBORTagInlinedCompactMapExtraData = 249

	CBORTagInlinedArray      = 250
	CBORTagInlinedMap        = 251
	CBORTagInlinedCompactMap = 252

	CBORTagInlineCollisionGroup   = 253
	CBORTagExternalCollisionGroup = 254

	CBORTagSlabID = 255
)
View Source 
const (
	SlabAddressLength = 8
	SlabIndexLength   = 8
	SlabIDLength      = SlabAddressLength + SlabIndexLength
)
View Source 
const LedgerBaseStorageSlabPrefix = "$"
View Source 
const (
	ValueIDLength = SlabIDLength
)

Variables

View Source 
var (
	AddressUndefined   = Address{}
	SlabIndexUndefined = SlabIndex{}
	SlabIDUndefined    = SlabID{}
)
View Source 
var MaxCollisionLimitPerDigest = uint32(255)

MaxCollisionLimitPerDigest is the noncryptographic hash collision limit (per digest per map) we enforce in the first level. In the same map for the same digest, having a non-intentional collision should be rare and several collisions should be extremely rare. The default limit should be high enough to ignore accidental collisions while mitigating attacks.

Functions

func CheckStorageHealth 

func CheckStorageHealth(storage SlabStorage, expectedNumberOfRootSlabs int) (map[SlabID]struct{}, error)

CheckStorageHealth checks for the health of slab storage. It traverses the slabs and checks these factors: - All non-root slabs only has a single parent reference (no double referencing) - Every child of a parent shares the same ownership (childSlabID.Address == parentSlabID.Address) - The number of root slabs are equal to the expected number (skipped if expectedNumberOfRootSlabs is -1) This should be used for testing purposes only, as it might be slow to process

func DumpArraySlabs 

func DumpArraySlabs(a *Array) ([]string, error)

func DumpMapSlabs 

func DumpMapSlabs(m *OrderedMap) ([]string, error)

func EncodeSlab added in v0.8.0 

func EncodeSlab(slab Slab, encMode cbor.EncMode) ([]byte, error)

func GetArrayStats 

func GetArrayStats(a *Array) (arrayStats, error)

GetArrayStats returns stats about array slabs.

func GetUintCBORSize 

func GetUintCBORSize(n uint64) uint32

func HasPointers 

func HasPointers(slabData []byte) (bool, error)

func HasSizeLimit 

func HasSizeLimit(slabData []byte) (bool, error)

func IsCBORTagNumberRangeAvailable added in v0.8.0 

func IsCBORTagNumberRangeAvailable(minTagNum, maxTagNum uint64) (bool, error)

IsCBORTagNumberRangeAvailable returns true if the specified range is not reserved for internal use by atree. Applications must only use available (unreserved) CBOR tag numbers to encode elements in atree managed containers.

func IsRootOfAnObject 

func IsRootOfAnObject(slabData []byte) (bool, error)

func LedgerKeyIsSlabKey 

func LedgerKeyIsSlabKey(key string) bool

func MaxInlineArrayElementSize 

func MaxInlineArrayElementSize() uint64

func MaxInlineMapElementSize added in v0.10.0 

func MaxInlineMapElementSize() uint64

func MaxInlineMapKeySize added in v0.8.0 

func MaxInlineMapKeySize() uint64

func NewCollisionLimitError added in v0.4.0 

func NewCollisionLimitError(collisionLimitPerDigest uint32) error

NewCollisionLimitError constructs a CollisionLimitError

func NewDecodingError 

func NewDecodingError(err error) error

NewDecodingError constructs a DecodingError

func NewDecodingErrorf 

func NewDecodingErrorf(msg string, args ...any) error

NewDecodingErrorf constructs a new DecodingError with error formating

func NewDuplicateKeyError 

func NewDuplicateKeyError(key any) error

func NewEncodingError 

func NewEncodingError(err error) error

NewEncodingError constructs a EncodingError

func NewEncodingErrorf 

func NewEncodingErrorf(msg string, args ...any) error

NewEncodingErrorf constructs a new EncodingError with error formating

func NewExternalError added in v0.6.0 

func NewExternalError(err error, msg string) error

func NewFatalError 

func NewFatalError(err error) error

func NewHashError 

func NewHashError(err error) error

NewHashError constructs a HashError

func NewHashLevelErrorf 

func NewHashLevelErrorf(msg string, args ...any) error

NewHashLevelError constructs a HashLevelError

func NewHashSeedUninitializedError 

func NewHashSeedUninitializedError() error

func NewIndexOutOfBoundsError 

func NewIndexOutOfBoundsError(index, min, max uint64) error

NewIndexOutOfBoundsError constructs a IndexOutOfBoundsError

func NewInvalidSliceIndexError added in v0.2.0 

func NewInvalidSliceIndexError(startIndex, endIndex uint64) error

NewInvalidSliceIndexError constructs an InvalidSliceIndexError

func NewKeyNotFoundError 

func NewKeyNotFoundError(key any) error

NewKeyNotFoundError constructs a KeyNotFoundError

func NewMapElementCountError added in v0.4.0 

func NewMapElementCountError(msg string) error

NewMapElementCountError constructs a MapElementCountError.

func NewNotApplicableError 

func NewNotApplicableError(typeName, interfaceName, methodName string) error

NewNotApplicableError constructs a NotImplementedError

func NewNotImplementedError 

func NewNotImplementedError(methodName string) error

NewNotImplementedError constructs a NotImplementedError

func NewNotValueError 

func NewNotValueError(id SlabID) error

NewNotValueError constructs a NotValueError.

func NewReadOnlyIteratorElementMutationError added in v0.8.0 

func NewReadOnlyIteratorElementMutationError(containerValueID, elementValueID ValueID) error

NewReadOnlyIteratorElementMutationError creates ReadOnlyIteratorElementMutationError.

func NewSlabDataError 

func NewSlabDataError(err error) error

NewSlabDataError constructs a SlabDataError

func NewSlabDataErrorf 

func NewSlabDataErrorf(msg string, args ...any) error

NewSlabDataErrorf constructs a new SlabError with error formating

func NewSlabIDError added in v0.8.0 

func NewSlabIDError(msg string) error

NewSlabIDError constructs a fatal error of SlabIDError.

func NewSlabIDErrorf added in v0.8.0 

func NewSlabIDErrorf(msg string, args ...any) error

NewSlabIDErrorf constructs a fatal error of SlabIDError.

func NewSlabMergeError 

func NewSlabMergeError(err error) error

NewSlabMergeError constructs a SlabMergeError

func NewSlabMergeErrorf 

func NewSlabMergeErrorf(msg string, args ...any) error

NewSlabMergeErrorf constructs a new SlabMergeError with error formating

func NewSlabNotFoundError 

func NewSlabNotFoundError(slabID SlabID, err error) error

NewSlabNotFoundError constructs a SlabNotFoundError

func NewSlabNotFoundErrorf 

func NewSlabNotFoundErrorf(slabID SlabID, msg string, args ...any) error

NewSlabNotFoundErrorf constructs a new SlabNotFoundError with error formating

func NewSlabRebalanceError 

func NewSlabRebalanceError(err error) error

NewSlabRebalanceError constructs a SlabRebalanceError

func NewSlabRebalanceErrorf 

func NewSlabRebalanceErrorf(msg string, args ...any) error

NewSlabErrorf constructs a new SlabError with error formating

func NewSlabSplitError 

func NewSlabSplitError(err error) error

NewSlabSplitError constructs a SlabSplitError

func NewSlabSplitErrorf 

func NewSlabSplitErrorf(msg string, args ...any) error

NewSlabSplitErrorf constructs a new SlabSplitError with error formating

func NewSliceOutOfBoundsError added in v0.2.0 

func NewSliceOutOfBoundsError(startIndex, endIndex, min, max uint64) error

NewSliceOutOfBoundsError constructs a SliceOutOfBoundsError.

func NewUnreachableError 

func NewUnreachableError() error

func NewUserError added in v0.6.0 

func NewUserError(err error) error

func PrintArray 

func PrintArray(a *Array)

PrintArray prints array slab data to stdout.

func PrintMap 

func PrintMap(m *OrderedMap)

func ReservedCBORTagNumberRange added in v0.8.0 

func ReservedCBORTagNumberRange() (minTagNum, maxTagNum uint64)

ReservedCBORTagNumberRange returns minTagNum and maxTagNum of the range of CBOR tag numbers reserved for internal use by atree.

func SetThreshold 

func SetThreshold(threshold uint64) (uint64, uint64, uint64, uint64)

func SlabIndexToLedgerKey 

func SlabIndexToLedgerKey(ind SlabIndex) []byte

func VerifyArray added in v0.8.0 

func VerifyArray(
	a *Array,
	address Address,
	typeInfo TypeInfo,
	tic TypeInfoComparator,
	hip HashInputProvider,
	inlineEnabled bool,
) error

func VerifyArraySerialization added in v0.8.0 

func VerifyArraySerialization(
	a *Array,
	cborDecMode cbor.DecMode,
	cborEncMode cbor.EncMode,
	decodeStorable StorableDecoder,
	decodeTypeInfo TypeInfoDecoder,
	compare StorableComparator,
) error

VerifyArraySerialization traverses array tree and verifies serialization by encoding, decoding, and re-encoding slabs. It compares in-memory objects of original slab with decoded slab. It also compares encoded data of original slab with encoded data of decoded slab.

func VerifyMap added in v0.8.0 

func VerifyMap(
	m *OrderedMap,
	address Address,
	typeInfo TypeInfo,
	tic TypeInfoComparator,
	hip HashInputProvider,
	inlineEnabled bool,
) error

func VerifyMapSerialization added in v0.8.0 

func VerifyMapSerialization(
	m *OrderedMap,
	cborDecMode cbor.DecMode,
	cborEncMode cbor.EncMode,
	decodeStorable StorableDecoder,
	decodeTypeInfo TypeInfoDecoder,
	compare StorableComparator,
) error

VerifyMapSerialization traverses ordered map tree and verifies serialization by encoding, decoding, and re-encoding slabs. It compares in-memory objects of original slab with decoded slab. It also compares encoded data of original slab with encoded data of decoded slab.

Types

type Address 

type Address [SlabAddressLength]byte

WARNING: Any changes to SlabID or its components (Address and SlabIndex) require updates to ValueID definition and functions.

type Array 

type Array struct {
	Storage SlabStorage
	// contains filtered or unexported fields
}

Array is a heterogeneous variable-size array, storing any type of values into a smaller ordered list of values and provides efficient functionality to lookup, insert and remove elements anywhere in the array.

Array elements can be stored in one or more relatively fixed-sized segments.

Array can be inlined into its parent container when the entire content fits in parent container's element size limit. Specifically, array with one segment which fits in size limit can be inlined, while arrays with multiple segments can't be inlined.

func NewArray 

func NewArray(storage SlabStorage, address Address, typeInfo TypeInfo) (*Array, error)

func NewArrayFromBatchData 

func NewArrayFromBatchData(storage SlabStorage, address Address, typeInfo TypeInfo, fn ArrayElementProvider) (*Array, error)

func NewArrayWithRootID 

func NewArrayWithRootID(storage SlabStorage, rootID SlabID) (*Array, error)

func (*Array) Address 

func (a *Array) Address() Address

func (*Array) Append 

func (a *Array) Append(value Value) error

func (*Array) Count 

func (a *Array) Count() uint64

func (*Array) Get 

func (a *Array) Get(i uint64) (Value, error)

func (*Array) Inlinable added in v0.8.0 

func (a *Array) Inlinable(maxInlineSize uint64) bool

func (*Array) Inlined added in v0.8.0 

func (a *Array) Inlined() bool

func (*Array) Insert 

func (a *Array) Insert(index uint64, value Value) error

func (*Array) Iterate 

func (a *Array) Iterate(fn ArrayIterationFunc) error

func (*Array) IterateRange added in v0.2.0 

func (a *Array) IterateRange(startIndex uint64, endIndex uint64, fn ArrayIterationFunc) error

func (*Array) IterateReadOnly added in v0.8.0 

func (a *Array) IterateReadOnly(fn ArrayIterationFunc) error

IterateReadOnly iterates readonly array elements. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use IterateReadOnlyWithMutationCallback().

func (*Array) IterateReadOnlyLoadedValues added in v0.8.0 

func (a *Array) IterateReadOnlyLoadedValues(fn ArrayIterationFunc) error

IterateReadOnlyLoadedValues iterates loaded array values.

func (*Array) IterateReadOnlyRange added in v0.8.0 

func (a *Array) IterateReadOnlyRange(
	startIndex uint64,
	endIndex uint64,
	fn ArrayIterationFunc,
) error

IterateReadOnlyRange iterates readonly array elements from specified startIndex to endIndex. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use IterateReadOnlyRangeWithMutatinoCallback().

func (*Array) IterateReadOnlyRangeWithMutationCallback added in v0.8.0 

func (a *Array) IterateReadOnlyRangeWithMutationCallback(
	startIndex uint64,
	endIndex uint64,
	fn ArrayIterationFunc,
	valueMutationCallback ReadOnlyArrayIteratorMutationCallback,
) error

IterateReadOnlyRangeWithMutationCallback iterates readonly array elements from specified startIndex to endIndex. valueMutationCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without this callback. If values are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - valueMutatinCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use IterateReadOnlyRange().

func (*Array) IterateReadOnlyWithMutationCallback added in v0.8.0 

func (a *Array) IterateReadOnlyWithMutationCallback(
	fn ArrayIterationFunc,
	valueMutationCallback ReadOnlyArrayIteratorMutationCallback,
) error

IterateReadOnlyWithMutationCallback iterates readonly array elements. valueMutationCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without this callback. If values are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - valueMutatinCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use IterateReadOnly().

func (*Array) Iterator 

func (a *Array) Iterator() (ArrayIterator, error)

Iterator returns mutable iterator for array elements. Mutable iterator handles: - indirect element mutation, such as modifying nested container - direct element mutation, such as overwriting existing element with new element Mutable iterator doesn't handle: - inserting new elements into the array - removing existing elements from the array NOTE: Use readonly iterator if mutation is not needed for better performance.

func (*Array) PopIterate 

func (a *Array) PopIterate(fn ArrayPopIterationFunc) error

PopIterate iterates and removes elements backward. Each element is passed to ArrayPopIterationFunc callback before removal.

func (*Array) RangeIterator added in v0.2.0 

func (a *Array) RangeIterator(startIndex uint64, endIndex uint64) (ArrayIterator, error)

func (*Array) ReadOnlyIterator added in v0.8.0 

func (a *Array) ReadOnlyIterator() (ArrayIterator, error)

ReadOnlyIterator returns readonly iterator for array elements. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use ReadOnlyIteratorWithMutationCallback().

func (*Array) ReadOnlyIteratorWithMutationCallback added in v0.8.0 

func (a *Array) ReadOnlyIteratorWithMutationCallback(
	valueMutationCallback ReadOnlyArrayIteratorMutationCallback,
) (ArrayIterator, error)

ReadOnlyIteratorWithMutationCallback returns readonly iterator for array elements. valueMutationCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without callback. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - valueMutationCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use ReadOnlyIterator().

func (*Array) ReadOnlyLoadedValueIterator added in v0.8.0 

func (a *Array) ReadOnlyLoadedValueIterator() (*ArrayLoadedValueIterator, error)

ReadOnlyLoadedValueIterator returns iterator to iterate loaded array elements.

func (*Array) ReadOnlyRangeIterator added in v0.8.0 

func (a *Array) ReadOnlyRangeIterator(
	startIndex uint64,
	endIndex uint64,
) (ArrayIterator, error)

ReadOnlyRangeIterator iterates readonly array elements from specified startIndex to endIndex. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use ReadOnlyRangeIteratorWithMutationCallback().

func (*Array) ReadOnlyRangeIteratorWithMutationCallback added in v0.8.0 

func (a *Array) ReadOnlyRangeIteratorWithMutationCallback(
	startIndex uint64,
	endIndex uint64,
	valueMutationCallback ReadOnlyArrayIteratorMutationCallback,
) (ArrayIterator, error)

ReadOnlyRangeIteratorWithMutationCallback iterates readonly array elements from specified startIndex to endIndex. valueMutationCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without callback. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - valueMutationCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use ReadOnlyRangeIterator().

func (*Array) Remove 

func (a *Array) Remove(index uint64) (Storable, error)

func (*Array) Set 

func (a *Array) Set(index uint64, value Value) (Storable, error)

func (*Array) SetType added in v0.8.0 

func (a *Array) SetType(typeInfo TypeInfo) error

func (*Array) SlabID added in v0.8.0 

func (a *Array) SlabID() SlabID

func (*Array) Storable 

func (a *Array) Storable(_ SlabStorage, _ Address, maxInlineSize uint64) (Storable, error)

Storable returns array a as either: - SlabIDStorable, or - inlined data slab storable

func (*Array) String 

func (a *Array) String() string

func (*Array) Type 

func (a *Array) Type() TypeInfo

func (*Array) ValueID added in v0.8.0 

func (a *Array) ValueID() ValueID

type ArrayDataSlab 

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

ArrayDataSlab is leaf node, implementing ArraySlab.

func (*ArrayDataSlab) BorrowFromRight 

func (a *ArrayDataSlab) BorrowFromRight(slab Slab) error

BorrowFromRight rebalances slabs by moving elements from right slab to left slab.

func (*ArrayDataSlab) ByteSize 

func (a *ArrayDataSlab) ByteSize() uint32

func (*ArrayDataSlab) CanLendToLeft 

func (a *ArrayDataSlab) CanLendToLeft(size uint32) bool

CanLendToLeft returns true if elements on the left of the slab could be removed so that the slab still stores more than the min threshold.

func (*ArrayDataSlab) CanLendToRight 

func (a *ArrayDataSlab) CanLendToRight(size uint32) bool

CanLendToRight returns true if elements on the right of the slab could be removed so that the slab still stores more than the min threshold.

func (*ArrayDataSlab) ChildStorables 

func (a *ArrayDataSlab) ChildStorables() []Storable

func (*ArrayDataSlab) Encode 

func (a *ArrayDataSlab) Encode(enc *Encoder) error

Encode encodes this array data slab to the given encoder.

DataSlab Header: 

+-------------------------------+----------------------+---------------------------------+-----------------------------+
| slab version + flag (2 bytes) | extra data (if root) | inlined extra data (if present) | next slab ID (if non-empty) |
+-------------------------------+----------------------+---------------------------------+-----------------------------+

Content: 

CBOR encoded array of elements

See ArrayExtraData.Encode() for extra data section format. See InlinedExtraData.Encode() for inlined extra data section format.

func (*ArrayDataSlab) ExtraData 

func (a *ArrayDataSlab) ExtraData() *ArrayExtraData

func (*ArrayDataSlab) Get 

func (a *ArrayDataSlab) Get(_ SlabStorage, index uint64) (Storable, error)

func (*ArrayDataSlab) HasPointer added in v0.8.0 

func (a *ArrayDataSlab) HasPointer() bool

func (*ArrayDataSlab) Header 

func (a *ArrayDataSlab) Header() ArraySlabHeader

func (*ArrayDataSlab) Inlinable added in v0.8.0 

func (a *ArrayDataSlab) Inlinable(maxInlineSize uint64) bool

Inlinable returns true if - array data slab is root slab - size of inlined array data slab <= maxInlineSize

func (*ArrayDataSlab) Inline added in v0.8.0 

func (a *ArrayDataSlab) Inline(storage SlabStorage) error

Inline converts not-inlined ArrayDataSlab to inlined ArrayDataSlab and removes it from storage.

func (*ArrayDataSlab) Inlined added in v0.8.0 

func (a *ArrayDataSlab) Inlined() bool

func (*ArrayDataSlab) Insert 

func (a *ArrayDataSlab) Insert(storage SlabStorage, address Address, index uint64, value Value) error

func (*ArrayDataSlab) IsData 

func (a *ArrayDataSlab) IsData() bool

func (*ArrayDataSlab) IsFull 

func (a *ArrayDataSlab) IsFull() bool

func (*ArrayDataSlab) IsUnderflow 

func (a *ArrayDataSlab) IsUnderflow() (uint32, bool)

IsUnderflow returns the number of bytes needed for the data slab to reach the min threshold. Returns true if the min threshold has not been reached yet.

func (*ArrayDataSlab) LendToRight 

func (a *ArrayDataSlab) LendToRight(slab Slab) error

LendToRight rebalances slabs by moving elements from left slab to right slab

func (*ArrayDataSlab) Merge 

func (a *ArrayDataSlab) Merge(slab Slab) error

func (*ArrayDataSlab) PopIterate 

func (a *ArrayDataSlab) PopIterate(_ SlabStorage, fn ArrayPopIterationFunc) error

func (*ArrayDataSlab) Remove 

func (a *ArrayDataSlab) Remove(storage SlabStorage, index uint64) (Storable, error)

func (*ArrayDataSlab) RemoveExtraData 

func (a *ArrayDataSlab) RemoveExtraData() *ArrayExtraData

func (*ArrayDataSlab) Set 

func (a *ArrayDataSlab) Set(storage SlabStorage, address Address, index uint64, value Value) (Storable, error)

func (*ArrayDataSlab) SetExtraData 

func (a *ArrayDataSlab) SetExtraData(extraData *ArrayExtraData)

func (*ArrayDataSlab) SetSlabID added in v0.8.0 

func (a *ArrayDataSlab) SetSlabID(id SlabID)

func (*ArrayDataSlab) SlabID added in v0.8.0 

func (a *ArrayDataSlab) SlabID() SlabID

func (*ArrayDataSlab) Split 

func (a *ArrayDataSlab) Split(storage SlabStorage) (Slab, Slab, error)

func (*ArrayDataSlab) StoredValue 

func (a *ArrayDataSlab) StoredValue(storage SlabStorage) (Value, error)

func (*ArrayDataSlab) String 

func (a *ArrayDataSlab) String() string

func (*ArrayDataSlab) Uninline added in v0.8.0 

func (a *ArrayDataSlab) Uninline(storage SlabStorage) error

Uninline converts an inlined ArrayDataSlab to uninlined ArrayDataSlab and stores it in storage.

type ArrayElementProvider 

type ArrayElementProvider func() (Value, error)

type ArrayExtraData 

type ArrayExtraData struct {
	TypeInfo TypeInfo // array type
}

func (*ArrayExtraData) Encode 

func (a *ArrayExtraData) Encode(enc *Encoder, encodeTypeInfo encodeTypeInfo) error

Encode encodes extra data as CBOR array: 

[type info]

func (*ArrayExtraData) Type added in v0.8.0 

func (a *ArrayExtraData) Type() TypeInfo

type ArrayIterationFunc 

type ArrayIterationFunc func(element Value) (resume bool, err error)

type ArrayIterator 

type ArrayIterator interface {
	CanMutate() bool
	Next() (Value, error)
}

type ArrayLoadedValueIterator added in v0.8.0 

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

ArrayLoadedValueIterator is used to iterate over loaded array elements.

func (*ArrayLoadedValueIterator) Next added in v0.8.0 

func (i *ArrayLoadedValueIterator) Next() (Value, error)

Next iterates and returns next loaded element. It returns nil Value at end of loaded elements.

type ArrayMetaDataSlab 

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

ArrayMetaDataSlab is internal node, implementing ArraySlab.

func (*ArrayMetaDataSlab) BorrowFromRight 

func (a *ArrayMetaDataSlab) BorrowFromRight(slab Slab) error

func (*ArrayMetaDataSlab) ByteSize 

func (a *ArrayMetaDataSlab) ByteSize() uint32

func (*ArrayMetaDataSlab) CanLendToLeft 

func (a *ArrayMetaDataSlab) CanLendToLeft(size uint32) bool

func (*ArrayMetaDataSlab) CanLendToRight 

func (a *ArrayMetaDataSlab) CanLendToRight(size uint32) bool

func (*ArrayMetaDataSlab) ChildStorables 

func (a *ArrayMetaDataSlab) ChildStorables() []Storable

func (*ArrayMetaDataSlab) Encode 

func (a *ArrayMetaDataSlab) Encode(enc *Encoder) error

Encode encodes this array meta-data slab to the given encoder.

Root MetaDataSlab Header: 

+------------------------------+------------+--------------------------------+------------------------------+
| slab version + flag (2 byte) | extra data | child shared address (8 bytes) | child header count (2 bytes) |
+------------------------------+------------+--------------------------------+------------------------------+

Non-root MetaDataSlab Header (12 bytes): 

+------------------------------+--------------------------------+------------------------------+
| slab version + flag (2 byte) | child shared address (8 bytes) | child header count (2 bytes) |
+------------------------------+--------------------------------+------------------------------+

Content (n * 14 bytes): 

[[slab index (8 bytes), count (4 bytes), size (2 bytes)], ...]

See ArrayExtraData.Encode() for extra data section format.

func (*ArrayMetaDataSlab) ExtraData 

func (a *ArrayMetaDataSlab) ExtraData() *ArrayExtraData

func (*ArrayMetaDataSlab) Get 

func (a *ArrayMetaDataSlab) Get(storage SlabStorage, index uint64) (Storable, error)

func (*ArrayMetaDataSlab) Header 

func (a *ArrayMetaDataSlab) Header() ArraySlabHeader

func (*ArrayMetaDataSlab) Inlinable added in v0.8.0 

func (a *ArrayMetaDataSlab) Inlinable(_ uint64) bool

func (*ArrayMetaDataSlab) Inline added in v0.8.0 

func (a *ArrayMetaDataSlab) Inline(_ SlabStorage) error

func (*ArrayMetaDataSlab) Inlined added in v0.8.0 

func (a *ArrayMetaDataSlab) Inlined() bool

func (*ArrayMetaDataSlab) Insert 

func (a *ArrayMetaDataSlab) Insert(storage SlabStorage, address Address, index uint64, value Value) error

Insert inserts v into the correct child slab. index must be >=0 and <= a.header.count. If index == a.header.count, Insert appends v to the end of underlying slab.

func (*ArrayMetaDataSlab) IsData 

func (a *ArrayMetaDataSlab) IsData() bool

func (ArrayMetaDataSlab) IsFull 

func (a ArrayMetaDataSlab) IsFull() bool

func (ArrayMetaDataSlab) IsUnderflow 

func (a ArrayMetaDataSlab) IsUnderflow() (uint32, bool)

func (*ArrayMetaDataSlab) LendToRight 

func (a *ArrayMetaDataSlab) LendToRight(slab Slab) error

func (*ArrayMetaDataSlab) Merge 

func (a *ArrayMetaDataSlab) Merge(slab Slab) error

func (*ArrayMetaDataSlab) MergeOrRebalanceChildSlab 

func (a *ArrayMetaDataSlab) MergeOrRebalanceChildSlab(
	storage SlabStorage,
	child ArraySlab,
	childHeaderIndex int,
	underflowSize uint32,
) error

MergeOrRebalanceChildSlab merges or rebalances child slab. If merged, then parent slab's data is adjusted.

+-----------------------+-----------------------+----------------------+-----------------------+ | | no left sibling (sib) | left sib can't lend | left sib can lend | +=======================+=======================+======================+=======================+ | no right sib | panic | merge with left | rebalance with left | +-----------------------+-----------------------+----------------------+-----------------------+ | right sib can't lend | merge with right | merge with smaller | rebalance with left | +-----------------------+-----------------------+----------------------+-----------------------+ | right sib can lend | rebalance with right | rebalance with right | rebalance with bigger | +-----------------------+-----------------------+----------------------+-----------------------+

func (*ArrayMetaDataSlab) PopIterate 

func (a *ArrayMetaDataSlab) PopIterate(storage SlabStorage, fn ArrayPopIterationFunc) error

func (*ArrayMetaDataSlab) Remove 

func (a *ArrayMetaDataSlab) Remove(storage SlabStorage, index uint64) (Storable, error)

func (*ArrayMetaDataSlab) RemoveExtraData 

func (a *ArrayMetaDataSlab) RemoveExtraData() *ArrayExtraData

func (*ArrayMetaDataSlab) Set 

func (a *ArrayMetaDataSlab) Set(storage SlabStorage, address Address, index uint64, value Value) (Storable, error)

func (*ArrayMetaDataSlab) SetExtraData 

func (a *ArrayMetaDataSlab) SetExtraData(extraData *ArrayExtraData)

func (*ArrayMetaDataSlab) SetSlabID added in v0.8.0 

func (a *ArrayMetaDataSlab) SetSlabID(id SlabID)

func (*ArrayMetaDataSlab) SlabID added in v0.8.0 

func (a *ArrayMetaDataSlab) SlabID() SlabID

func (*ArrayMetaDataSlab) Split 

func (a *ArrayMetaDataSlab) Split(storage SlabStorage) (Slab, Slab, error)

func (*ArrayMetaDataSlab) SplitChildSlab 

func (a *ArrayMetaDataSlab) SplitChildSlab(storage SlabStorage, child ArraySlab, childHeaderIndex int) error

func (*ArrayMetaDataSlab) StoredValue 

func (a *ArrayMetaDataSlab) StoredValue(storage SlabStorage) (Value, error)

func (*ArrayMetaDataSlab) String 

func (a *ArrayMetaDataSlab) String() string

func (*ArrayMetaDataSlab) Uninline added in v0.8.0 

func (a *ArrayMetaDataSlab) Uninline(_ SlabStorage) error

type ArrayPopIterationFunc 

type ArrayPopIterationFunc func(Storable)

type ArraySlab 

type ArraySlab interface {
	Slab

	Get(storage SlabStorage, index uint64) (Storable, error)
	Set(storage SlabStorage, address Address, index uint64, value Value) (Storable, error)
	Insert(storage SlabStorage, address Address, index uint64, value Value) error
	Remove(storage SlabStorage, index uint64) (Storable, error)

	IsData() bool

	IsFull() bool
	IsUnderflow() (uint32, bool)
	CanLendToLeft(size uint32) bool
	CanLendToRight(size uint32) bool

	SetSlabID(SlabID)

	Header() ArraySlabHeader

	ExtraData() *ArrayExtraData
	RemoveExtraData() *ArrayExtraData
	SetExtraData(*ArrayExtraData)

	PopIterate(SlabStorage, ArrayPopIterationFunc) error

	Inlined() bool
	Inlinable(maxInlineSize uint64) bool
	Inline(SlabStorage) error
	Uninline(SlabStorage) error
}

type ArraySlabHeader 

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

type BaseStorage 

type BaseStorage interface {
	Store(SlabID, []byte) error
	Retrieve(SlabID) ([]byte, bool, error)
	Remove(SlabID) error
	GenerateSlabID(Address) (SlabID, error)
	SegmentCounts() int // number of segments stored in the storage
	Size() int          // total byte size stored
	BaseStorageUsageReporter
}

type BaseStorageUsageReporter 

type BaseStorageUsageReporter interface {
	BytesRetrieved() int
	BytesStored() int
	SegmentsReturned() int
	SegmentsUpdated() int
	SegmentsTouched() int
	ResetReporter()
}

type BasicSlabStorage 

type BasicSlabStorage struct {
	Slabs map[SlabID]Slab

	DecodeStorable StorableDecoder
	DecodeTypeInfo TypeInfoDecoder
	// contains filtered or unexported fields
}

func NewBasicSlabStorage 

func NewBasicSlabStorage(
	cborEncMode cbor.EncMode,
	cborDecMode cbor.DecMode,
	decodeStorable StorableDecoder,
	decodeTypeInfo TypeInfoDecoder,
) *BasicSlabStorage

func (*BasicSlabStorage) Count 

func (s *BasicSlabStorage) Count() int

func (*BasicSlabStorage) Encode 

func (s *BasicSlabStorage) Encode() (map[SlabID][]byte, error)

Encode returns serialized slabs in storage. This is currently used for testing.

func (*BasicSlabStorage) GenerateSlabID added in v0.8.0 

func (s *BasicSlabStorage) GenerateSlabID(address Address) (SlabID, error)

func (*BasicSlabStorage) Remove 

func (s *BasicSlabStorage) Remove(id SlabID) error

func (*BasicSlabStorage) Retrieve 

func (s *BasicSlabStorage) Retrieve(id SlabID) (Slab, bool, error)

func (*BasicSlabStorage) RetrieveIfLoaded added in v0.8.0 

func (s *BasicSlabStorage) RetrieveIfLoaded(id SlabID) Slab

func (*BasicSlabStorage) SlabIDs added in v0.8.0 

func (s *BasicSlabStorage) SlabIDs() []SlabID

func (*BasicSlabStorage) SlabIterator 

func (s *BasicSlabStorage) SlabIterator() (SlabIterator, error)

func (*BasicSlabStorage) Store 

func (s *BasicSlabStorage) Store(id SlabID, slab Slab) error

type CollisionLimitError added in v0.4.0 

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

CollisionLimitError is a fatal error returned when a noncryptographic hash collision would exceed collision limit (per digest per map) we enforce in the first level.

func (*CollisionLimitError) Error added in v0.4.0 

func (e *CollisionLimitError) Error() string

type ComparableStorable added in v0.8.0 

type ComparableStorable interface {
	Storable

	// Equal returns true if the given storable is equal to this storable.
	Equal(Storable) bool

	// Less returns true if the given storable is less than this storable.
	Less(Storable) bool

	// ID returns a unique identifier.
	ID() string

	Copy() Storable
}

ComparableStorable is an interface that supports comparison and cloning of Storable. This is only used for compact keys.

type ContainerStorable added in v0.8.0 

type ContainerStorable interface {
	Storable

	// HasPointer returns true if any of its child storables is SlabIDStorable
	// (references to another slab).  This function is used during encoding.
	HasPointer() bool
}

ContainerStorable is an interface that supports Storable containing other storables.

type DecodingError 

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

DecodingError is a fatal error returned when a decoding operation fails

func (*DecodingError) Error 

func (e *DecodingError) Error() string

type Digest 

type Digest uint64

type Digester 

type Digester interface {
	// DigestPrefix returns digests before specified level.
	// If level is 0, DigestPrefix returns nil.
	DigestPrefix(level uint) ([]Digest, error)

	// Digest returns digest at specified level.
	Digest(level uint) (Digest, error)

	// Reset data for reuse
	Reset()

	Levels() uint
}

type DigesterBuilder 

type DigesterBuilder interface {
	SetSeed(k0 uint64, k1 uint64)
	Digest(HashInputProvider, Value) (Digester, error)
}

func NewDefaultDigesterBuilder 

func NewDefaultDigesterBuilder() DigesterBuilder

type DuplicateKeyError 

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

DuplicateKeyError is returned when the duplicate key is found in the dictionary when none is expected.

func (*DuplicateKeyError) Error 

func (e *DuplicateKeyError) Error() string

type Encoder 

type Encoder struct {
	io.Writer
	CBOR    *cbor.StreamEncoder
	Scratch [64]byte
	// contains filtered or unexported fields
}

Encoder writes atree slabs to io.Writer.

func NewEncoder 

func NewEncoder(w io.Writer, encMode cbor.EncMode) *Encoder

type EncodingError 

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

EncodingError is a fatal error returned when a encoding operation fails

func (*EncodingError) Error 

func (e *EncodingError) Error() string

type ExternalError added in v0.6.0 

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

func (*ExternalError) Error added in v0.6.0 

func (e *ExternalError) Error() string

func (*ExternalError) Unwrap added in v0.6.0 

func (e *ExternalError) Unwrap() error

type ExtraData added in v0.8.0 

type ExtraData interface {
	Type() TypeInfo
	Encode(enc *Encoder, encodeTypeInfo encodeTypeInfo) error
	// contains filtered or unexported methods
}

type FatalError 

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

func (*FatalError) Error 

func (e *FatalError) Error() string

func (*FatalError) Unwrap 

func (e *FatalError) Unwrap() error

type HashError 

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

HashError is a fatal error returned when hash calculation fails

func (*HashError) Error 

func (e *HashError) Error() string

type HashInputProvider 

type HashInputProvider func(value Value, buffer []byte) ([]byte, error)

type HashLevelError 

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

HashLevelError is a fatal error returned when hash level is wrong.

func (*HashLevelError) Error 

func (e *HashLevelError) Error() string

type HashSeedUninitializedError 

type HashSeedUninitializedError struct {
}

HashSeedUninitializedError is a fatal error returned when hash seed is uninitialized.

func (*HashSeedUninitializedError) Error 

func (e *HashSeedUninitializedError) Error() string

type IndexOutOfBoundsError 

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

IndexOutOfBoundsError is returned when get, insert or delete operation is attempted on an array index which is out of bounds

func (*IndexOutOfBoundsError) Error 

func (e *IndexOutOfBoundsError) Error() string

type InlinedExtraData added in v0.8.0 

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

func (*InlinedExtraData) Encode added in v0.8.0 

func (ied *InlinedExtraData) Encode(enc *Encoder) error

Encode encodes inlined extra data as 2-element array: 

+-----------------------+------------------------+
| [+ inlined type info] | [+ inlined extra data] |
+-----------------------+------------------------+

type InvalidSliceIndexError added in v0.2.0 

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

InvalidSliceIndexError is returned when array slice index is invalid, such as startIndex > endIndex This error can be returned even when startIndex and endIndex are both within bounds.

func (*InvalidSliceIndexError) Error added in v0.2.0 

func (e *InvalidSliceIndexError) Error() string

type KeyNotFoundError 

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

KeyNotFoundError is returned when the key not found in the dictionary

func (*KeyNotFoundError) Error 

func (e *KeyNotFoundError) Error() string

type Ledger 

type Ledger interface {
	// GetValue gets a value for the given key in the storage, owned by the given account.
	GetValue(owner, key []byte) (value []byte, err error)
	// SetValue sets a value for the given key in the storage, owned by the given account.
	SetValue(owner, key, value []byte) (err error)
	// ValueExists returns true if the given key exists in the storage, owned by the given account.
	ValueExists(owner, key []byte) (exists bool, err error)
	// AllocateSlabIndex allocates a new slab index under the given account.
	AllocateSlabIndex(owner []byte) (SlabIndex, error)
}

type LedgerBaseStorage 

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

func NewLedgerBaseStorage 

func NewLedgerBaseStorage(ledger Ledger) *LedgerBaseStorage

func (*LedgerBaseStorage) BytesRetrieved 

func (s *LedgerBaseStorage) BytesRetrieved() int

func (*LedgerBaseStorage) BytesStored 

func (s *LedgerBaseStorage) BytesStored() int

func (*LedgerBaseStorage) GenerateSlabID added in v0.8.0 

func (s *LedgerBaseStorage) GenerateSlabID(address Address) (SlabID, error)

func (*LedgerBaseStorage) Remove 

func (s *LedgerBaseStorage) Remove(id SlabID) error

func (*LedgerBaseStorage) ResetReporter 

func (s *LedgerBaseStorage) ResetReporter()

func (*LedgerBaseStorage) Retrieve 

func (s *LedgerBaseStorage) Retrieve(id SlabID) ([]byte, bool, error)

func (*LedgerBaseStorage) SegmentCounts 

func (s *LedgerBaseStorage) SegmentCounts() int

func (*LedgerBaseStorage) SegmentsReturned 

func (s *LedgerBaseStorage) SegmentsReturned() int

func (*LedgerBaseStorage) SegmentsTouched 

func (s *LedgerBaseStorage) SegmentsTouched() int

func (*LedgerBaseStorage) SegmentsUpdated 

func (s *LedgerBaseStorage) SegmentsUpdated() int

func (*LedgerBaseStorage) Size 

func (s *LedgerBaseStorage) Size() int

func (*LedgerBaseStorage) Store 

func (s *LedgerBaseStorage) Store(id SlabID, data []byte) error

type MapDataSlab 

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

MapDataSlab is leaf node, implementing MapSlab. anySize is true for data slab that isn't restricted by size requirement.

func (*MapDataSlab) BorrowFromRight 

func (m *MapDataSlab) BorrowFromRight(slab Slab) error

func (*MapDataSlab) ByteSize 

func (m *MapDataSlab) ByteSize() uint32

func (*MapDataSlab) CanLendToLeft 

func (m *MapDataSlab) CanLendToLeft(size uint32) bool

CanLendToLeft returns true if elements on the left of the slab could be removed so that the slab still stores more than the min threshold.

func (*MapDataSlab) CanLendToRight 

func (m *MapDataSlab) CanLendToRight(size uint32) bool

CanLendToRight returns true if elements on the right of the slab could be removed so that the slab still stores more than the min threshold.

func (*MapDataSlab) ChildStorables 

func (m *MapDataSlab) ChildStorables() []Storable

func (*MapDataSlab) Encode 

func (m *MapDataSlab) Encode(enc *Encoder) error

Encode encodes this map data slab to the given encoder.

Root DataSlab Header: 

+-------------------------------+----------------------+---------------------------------+-----------------------------+
| slab version + flag (2 bytes) | extra data (if root) | inlined extra data (if present) | next slab ID (if non-empty) |
+-------------------------------+----------------------+---------------------------------+-----------------------------+

Content: 

CBOR encoded elements

See MapExtraData.Encode() for extra data section format. See InlinedExtraData.Encode() for inlined extra data section format. See hkeyElements.Encode() and singleElements.Encode() for elements section format.

func (*MapDataSlab) ExtraData 

func (m *MapDataSlab) ExtraData() *MapExtraData

func (*MapDataSlab) HasPointer added in v0.8.0 

func (m *MapDataSlab) HasPointer() bool

func (*MapDataSlab) Header 

func (m *MapDataSlab) Header() MapSlabHeader

func (*MapDataSlab) Inlinable added in v0.8.0 

func (m *MapDataSlab) Inlinable(maxInlineSize uint64) bool

Inlinable returns true if - map data slab is root slab - size of inlined map data slab <= maxInlineSize

func (*MapDataSlab) Inline added in v0.8.0 

func (m *MapDataSlab) Inline(storage SlabStorage) error

inline converts not-inlined MapDataSlab to inlined MapDataSlab and removes it from storage.

func (*MapDataSlab) Inlined added in v0.8.0 

func (m *MapDataSlab) Inlined() bool

func (*MapDataSlab) IsData 

func (m *MapDataSlab) IsData() bool

func (*MapDataSlab) IsFull 

func (m *MapDataSlab) IsFull() bool

func (*MapDataSlab) IsUnderflow 

func (m *MapDataSlab) IsUnderflow() (uint32, bool)

IsUnderflow returns the number of bytes needed for the data slab to reach the min threshold. Returns true if the min threshold has not been reached yet.

func (*MapDataSlab) LendToRight 

func (m *MapDataSlab) LendToRight(slab Slab) error

func (*MapDataSlab) Merge 

func (m *MapDataSlab) Merge(slab Slab) error

func (*MapDataSlab) PopIterate 

func (m *MapDataSlab) PopIterate(storage SlabStorage, fn MapPopIterationFunc) error

func (*MapDataSlab) Remove 

func (m *MapDataSlab) Remove(storage SlabStorage, digester Digester, level uint, hkey Digest, comparator ValueComparator, key Value) (MapKey, MapValue, error)

func (*MapDataSlab) RemoveExtraData 

func (m *MapDataSlab) RemoveExtraData() *MapExtraData

func (*MapDataSlab) Set 

func (m *MapDataSlab) Set(
	storage SlabStorage,
	b DigesterBuilder,
	digester Digester,
	level uint,
	hkey Digest,
	comparator ValueComparator,
	hip HashInputProvider,
	key Value,
	value Value,
) (MapKey, MapValue, error)

func (*MapDataSlab) SetExtraData 

func (m *MapDataSlab) SetExtraData(extraData *MapExtraData)

func (*MapDataSlab) SetSlabID added in v0.8.0 

func (m *MapDataSlab) SetSlabID(id SlabID)

func (*MapDataSlab) SlabID added in v0.8.0 

func (m *MapDataSlab) SlabID() SlabID

func (*MapDataSlab) Split 

func (m *MapDataSlab) Split(storage SlabStorage) (Slab, Slab, error)

func (*MapDataSlab) StoredValue 

func (m *MapDataSlab) StoredValue(storage SlabStorage) (Value, error)

func (*MapDataSlab) String 

func (m *MapDataSlab) String() string

func (*MapDataSlab) Uninline added in v0.8.0 

func (m *MapDataSlab) Uninline(storage SlabStorage) error

uninline converts an inlined MapDataSlab to uninlined MapDataSlab and stores it in storage.

type MapElementCountError added in v0.4.0 

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

MapElementCountError is a fatal error returned when element count is unexpected. It is an implementation error.

func (*MapElementCountError) Error added in v0.4.0 

func (e *MapElementCountError) Error() string

type MapElementIterationFunc 

type MapElementIterationFunc func(Value) (resume bool, err error)

type MapElementProvider 

type MapElementProvider func() (Value, Value, error)

type MapEntryIterationFunc 

type MapEntryIterationFunc func(Value, Value) (resume bool, err error)

type MapExtraData 

type MapExtraData struct {
	TypeInfo TypeInfo
	Count    uint64
	Seed     uint64
}

func (*MapExtraData) Encode 

func (m *MapExtraData) Encode(enc *Encoder, encodeTypeInfo encodeTypeInfo) error

Encode encodes extra data as CBOR array: 

[type info, count, seed]

func (*MapExtraData) Type added in v0.8.0 

func (m *MapExtraData) Type() TypeInfo

type MapIterator 

type MapIterator interface {
	CanMutate() bool
	Next() (Value, Value, error)
	NextKey() (Value, error)
	NextValue() (Value, error)
}

type MapKey 

type MapKey Storable

type MapLoadedValueIterator added in v0.8.0 

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

MapLoadedValueIterator is used to iterate loaded map elements.

func (*MapLoadedValueIterator) Next added in v0.8.0 

func (i *MapLoadedValueIterator) Next() (Value, Value, error)

Next iterates and returns next loaded element. It returns nil Value at end of loaded elements.

type MapMetaDataSlab 

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

MapMetaDataSlab is internal node, implementing MapSlab.

func (*MapMetaDataSlab) BorrowFromRight 

func (m *MapMetaDataSlab) BorrowFromRight(slab Slab) error

func (*MapMetaDataSlab) ByteSize 

func (m *MapMetaDataSlab) ByteSize() uint32

func (*MapMetaDataSlab) CanLendToLeft 

func (m *MapMetaDataSlab) CanLendToLeft(size uint32) bool

func (*MapMetaDataSlab) CanLendToRight 

func (m *MapMetaDataSlab) CanLendToRight(size uint32) bool

func (*MapMetaDataSlab) ChildStorables 

func (m *MapMetaDataSlab) ChildStorables() []Storable

func (*MapMetaDataSlab) Encode 

func (m *MapMetaDataSlab) Encode(enc *Encoder) error

Encode encodes map meta-data slab to the given encoder.

Root MetaDataSlab Header: 

+------------------------------+------------+--------------------------------+------------------------------+
| slab version + flag (2 byte) | extra data | child shared address (8 bytes) | child header count (2 bytes) |
+------------------------------+------------+--------------------------------+------------------------------+

Non-root MetaDataSlab Header (12 bytes): 

+------------------------------+--------------------------------+------------------------------+
| slab version + flag (2 byte) | child shared address (8 bytes) | child header count (2 bytes) |
+------------------------------+--------------------------------+------------------------------+

Content (n * 18 bytes): 

[ +[slab index (8 bytes), first key (8 bytes), size (2 bytes)]]

See MapExtraData.Encode() for extra data section format.

func (*MapMetaDataSlab) ExtraData 

func (m *MapMetaDataSlab) ExtraData() *MapExtraData

func (*MapMetaDataSlab) Get 

func (m *MapMetaDataSlab) Get(storage SlabStorage, digester Digester, level uint, hkey Digest, comparator ValueComparator, key Value) (MapKey, MapValue, error)

func (*MapMetaDataSlab) Header 

func (m *MapMetaDataSlab) Header() MapSlabHeader

func (*MapMetaDataSlab) Inlinable added in v0.8.0 

func (m *MapMetaDataSlab) Inlinable(_ uint64) bool

func (*MapMetaDataSlab) Inline added in v0.8.0 

func (m *MapMetaDataSlab) Inline(_ SlabStorage) error

func (*MapMetaDataSlab) Inlined added in v0.8.0 

func (m *MapMetaDataSlab) Inlined() bool

func (MapMetaDataSlab) IsData 

func (m MapMetaDataSlab) IsData() bool

func (MapMetaDataSlab) IsFull 

func (m MapMetaDataSlab) IsFull() bool

func (MapMetaDataSlab) IsUnderflow 

func (m MapMetaDataSlab) IsUnderflow() (uint32, bool)

func (*MapMetaDataSlab) LendToRight 

func (m *MapMetaDataSlab) LendToRight(slab Slab) error

func (*MapMetaDataSlab) Merge 

func (m *MapMetaDataSlab) Merge(slab Slab) error

func (*MapMetaDataSlab) MergeOrRebalanceChildSlab 

func (m *MapMetaDataSlab) MergeOrRebalanceChildSlab(
	storage SlabStorage,
	child MapSlab,
	childHeaderIndex int,
	underflowSize uint32,
) error

MergeOrRebalanceChildSlab merges or rebalances child slab. parent slab's data is adjusted. If merged, then parent slab's data is adjusted.

+-----------------------+-----------------------+----------------------+-----------------------+ | | no left sibling (sib) | left sib can't lend | left sib can lend | +=======================+=======================+======================+=======================+ | no right sib | panic | merge with left | rebalance with left | +-----------------------+-----------------------+----------------------+-----------------------+ | right sib can't lend | merge with right | merge with smaller | rebalance with left | +-----------------------+-----------------------+----------------------+-----------------------+ | right sib can lend | rebalance with right | rebalance with right | rebalance with bigger | +-----------------------+-----------------------+----------------------+-----------------------+

func (*MapMetaDataSlab) PopIterate 

func (m *MapMetaDataSlab) PopIterate(storage SlabStorage, fn MapPopIterationFunc) error

func (*MapMetaDataSlab) Remove 

func (m *MapMetaDataSlab) Remove(storage SlabStorage, digester Digester, level uint, hkey Digest, comparator ValueComparator, key Value) (MapKey, MapValue, error)

func (*MapMetaDataSlab) RemoveExtraData 

func (m *MapMetaDataSlab) RemoveExtraData() *MapExtraData

func (*MapMetaDataSlab) Set 

func (m *MapMetaDataSlab) Set(
	storage SlabStorage,
	b DigesterBuilder,
	digester Digester,
	level uint,
	hkey Digest,
	comparator ValueComparator,
	hip HashInputProvider,
	key Value,
	value Value,
) (MapKey, MapValue, error)

func (*MapMetaDataSlab) SetExtraData 

func (m *MapMetaDataSlab) SetExtraData(extraData *MapExtraData)

func (*MapMetaDataSlab) SetSlabID added in v0.8.0 

func (m *MapMetaDataSlab) SetSlabID(id SlabID)

func (*MapMetaDataSlab) SlabID added in v0.8.0 

func (m *MapMetaDataSlab) SlabID() SlabID

func (*MapMetaDataSlab) Split 

func (m *MapMetaDataSlab) Split(storage SlabStorage) (Slab, Slab, error)

func (*MapMetaDataSlab) SplitChildSlab 

func (m *MapMetaDataSlab) SplitChildSlab(storage SlabStorage, child MapSlab, childHeaderIndex int) error

func (*MapMetaDataSlab) StoredValue 

func (m *MapMetaDataSlab) StoredValue(storage SlabStorage) (Value, error)

func (*MapMetaDataSlab) String 

func (m *MapMetaDataSlab) String() string

func (*MapMetaDataSlab) Uninline added in v0.8.0 

func (m *MapMetaDataSlab) Uninline(_ SlabStorage) error

type MapPopIterationFunc 

type MapPopIterationFunc func(Storable, Storable)

type MapSlab 

type MapSlab interface {
	Slab

	Get(
		storage SlabStorage,
		digester Digester,
		level uint,
		hkey Digest,
		comparator ValueComparator,
		key Value,
	) (MapKey, MapValue, error)

	Set(
		storage SlabStorage,
		b DigesterBuilder,
		digester Digester,
		level uint,
		hkey Digest,
		comparator ValueComparator,
		hip HashInputProvider,
		key Value,
		value Value,
	) (MapKey, MapValue, error)

	Remove(
		storage SlabStorage,
		digester Digester,
		level uint,
		hkey Digest,
		comparator ValueComparator,
		key Value,
	) (MapKey, MapValue, error)

	IsData() bool

	IsFull() bool
	IsUnderflow() (uint32, bool)
	CanLendToLeft(size uint32) bool
	CanLendToRight(size uint32) bool

	SetSlabID(SlabID)

	Header() MapSlabHeader

	ExtraData() *MapExtraData
	RemoveExtraData() *MapExtraData
	SetExtraData(*MapExtraData)

	PopIterate(SlabStorage, MapPopIterationFunc) error

	Inlined() bool
	Inlinable(maxInlineSize uint64) bool
	Inline(SlabStorage) error
	Uninline(SlabStorage) error
	// contains filtered or unexported methods
}

type MapSlabHeader 

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

type MapStats 

type MapStats struct {
	Levels                 uint64
	ElementCount           uint64
	MetaDataSlabCount      uint64
	DataSlabCount          uint64
	CollisionDataSlabCount uint64
	StorableSlabCount      uint64
}

func GetMapStats 

func GetMapStats(m *OrderedMap) (MapStats, error)

GetMapStats returns stats about the map slabs.

func (*MapStats) SlabCount 

func (s *MapStats) SlabCount() uint64

type MapValue 

type MapValue Storable

type NotApplicableError 

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

NotApplicableError is a fatal error returned when a not applicable method is called

func (*NotApplicableError) Error 

func (e *NotApplicableError) Error() string

type NotImplementedError 

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

NotImplementedError is a fatal error returned when a method is called which is not yet implemented this is a temporary error

func (*NotImplementedError) Error 

func (e *NotImplementedError) Error() string

type NotValueError 

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

NotValueError is returned when we try to create Value objects from non-root slabs.

func (*NotValueError) Error 

func (e *NotValueError) Error() string

type OrderedMap 

type OrderedMap struct {
	Storage SlabStorage
	// contains filtered or unexported fields
}

OrderedMap is an ordered map of key-value pairs; keys can be any hashable type and values can be any serializable value type. It supports heterogeneous key or value types (e.g. first key storing a boolean and second key storing a string). OrderedMap keeps values in specific sorted order and operations are deterministic so the state of the segments after a sequence of operations are always unique.

OrderedMap key-value pairs can be stored in one or more relatively fixed-sized segments.

OrderedMap can be inlined into its parent container when the entire content fits in parent container's element size limit. Specifically, OrderedMap with one segment which fits in size limit can be inlined, while OrderedMap with multiple segments can't be inlined.

func NewMap 

func NewMap(storage SlabStorage, address Address, digestBuilder DigesterBuilder, typeInfo TypeInfo) (*OrderedMap, error)

func NewMapFromBatchData 

func NewMapFromBatchData(
	storage SlabStorage,
	address Address,
	digesterBuilder DigesterBuilder,
	typeInfo TypeInfo,
	comparator ValueComparator,
	hip HashInputProvider,
	seed uint64,
	fn MapElementProvider,
) (
	*OrderedMap,
	error,
)

NewMapFromBatchData returns a new map with elements provided by fn callback. Provided seed must be the same seed used to create the original map. And callback function must return elements in the same order as the original map. New map uses and stores the same seed as the original map. This function should only be used for copying a map.

func NewMapWithRootID 

func NewMapWithRootID(storage SlabStorage, rootID SlabID, digestBuilder DigesterBuilder) (*OrderedMap, error)

func (*OrderedMap) Address 

func (m *OrderedMap) Address() Address

func (*OrderedMap) Count 

func (m *OrderedMap) Count() uint64

func (*OrderedMap) Get 

func (m *OrderedMap) Get(comparator ValueComparator, hip HashInputProvider, key Value) (Value, error)

func (*OrderedMap) Has 

func (m *OrderedMap) Has(comparator ValueComparator, hip HashInputProvider, key Value) (bool, error)

func (*OrderedMap) Inlinable added in v0.8.0 

func (m *OrderedMap) Inlinable(maxInlineSize uint64) bool

func (*OrderedMap) Inlined added in v0.8.0 

func (m *OrderedMap) Inlined() bool

func (*OrderedMap) Iterate 

func (m *OrderedMap) Iterate(comparator ValueComparator, hip HashInputProvider, fn MapEntryIterationFunc) error

func (*OrderedMap) IterateKeys 

func (m *OrderedMap) IterateKeys(comparator ValueComparator, hip HashInputProvider, fn MapElementIterationFunc) error

func (*OrderedMap) IterateReadOnly added in v0.8.0 

func (m *OrderedMap) IterateReadOnly(
	fn MapEntryIterationFunc,
) error

IterateReadOnly iterates readonly map elements. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use IterateReadOnlyWithMutationCallback().

func (*OrderedMap) IterateReadOnlyKeys added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyKeys(
	fn MapElementIterationFunc,
) error

IterateReadOnlyKeys iterates readonly map keys. If keys are mutated: - those changes are not guaranteed to persist. - mutation functions of key containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use IterateReadOnlyKeysWithMutationCallback().

func (*OrderedMap) IterateReadOnlyKeysWithMutationCallback added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyKeysWithMutationCallback(
	fn MapElementIterationFunc,
	keyMutatinCallback ReadOnlyMapIteratorMutationCallback,
) error

IterateReadOnlyKeysWithMutationCallback iterates readonly map keys. keyMutatinCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without this callback. If keys are mutated: - those changes are not guaranteed to persist. - mutation functions of key containers return ReadOnlyIteratorElementMutationError. - keyMutatinCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use IterateReadOnlyKeys().

func (*OrderedMap) IterateReadOnlyLoadedValues added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyLoadedValues(fn MapEntryIterationFunc) error

IterateReadOnlyLoadedValues iterates loaded map values.

func (*OrderedMap) IterateReadOnlyValues added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyValues(
	fn MapElementIterationFunc,
) error

IterateReadOnlyValues iterates readonly map values. If values are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use IterateReadOnlyValuesWithMutationCallback().

func (*OrderedMap) IterateReadOnlyValuesWithMutationCallback added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyValuesWithMutationCallback(
	fn MapElementIterationFunc,
	valueMutationCallback ReadOnlyMapIteratorMutationCallback,
) error

IterateReadOnlyValuesWithMutationCallback iterates readonly map values. valueMutationCallback is useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without this callback. If values are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - keyMutatinCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use IterateReadOnlyValues().

func (*OrderedMap) IterateReadOnlyWithMutationCallback added in v0.8.0 

func (m *OrderedMap) IterateReadOnlyWithMutationCallback(
	fn MapEntryIterationFunc,
	keyMutatinCallback ReadOnlyMapIteratorMutationCallback,
	valueMutationCallback ReadOnlyMapIteratorMutationCallback,
) error

IterateReadOnlyWithMutationCallback iterates readonly map elements. keyMutatinCallback and valueMutationCallback are useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without these callbacks. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - keyMutatinCallback/valueMutationCallback is called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use IterateReadOnly().

func (*OrderedMap) IterateValues 

func (m *OrderedMap) IterateValues(comparator ValueComparator, hip HashInputProvider, fn MapElementIterationFunc) error

func (*OrderedMap) Iterator 

func (m *OrderedMap) Iterator(comparator ValueComparator, hip HashInputProvider) (MapIterator, error)

Iterator returns mutable iterator for map elements. Mutable iterator handles: - indirect element mutation, such as modifying nested container - direct element mutation, such as overwriting existing element with new element Mutable iterator doesn't handle: - inserting new elements into the map - removing existing elements from the map NOTE: Use readonly iterator if mutation is not needed for better performance.

func (*OrderedMap) PopIterate 

func (m *OrderedMap) PopIterate(fn MapPopIterationFunc) error

PopIterate iterates and removes elements backward. Each element is passed to MapPopIterationFunc callback before removal.

func (*OrderedMap) ReadOnlyIterator added in v0.8.0 

func (m *OrderedMap) ReadOnlyIterator() (MapIterator, error)

ReadOnlyIterator returns readonly iterator for map elements. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. NOTE: Use readonly iterator if mutation is not needed for better performance. If callback is needed (e.g. for logging mutation, etc.), use ReadOnlyIteratorWithMutationCallback().

func (*OrderedMap) ReadOnlyIteratorWithMutationCallback added in v0.8.0 

func (m *OrderedMap) ReadOnlyIteratorWithMutationCallback(
	keyMutatinCallback ReadOnlyMapIteratorMutationCallback,
	valueMutationCallback ReadOnlyMapIteratorMutationCallback,
) (MapIterator, error)

ReadOnlyIteratorWithMutationCallback returns readonly iterator for map elements. keyMutatinCallback and valueMutationCallback are useful for logging, etc. with more context when mutation occurs. Mutation handling here is the same with or without these callbacks. If elements are mutated: - those changes are not guaranteed to persist. - mutation functions of child containers return ReadOnlyIteratorElementMutationError. - keyMutatinCallback and valueMutationCallback are called if provided NOTE: Use readonly iterator if mutation is not needed for better performance. If callback isn't needed, use ReadOnlyIterator().

func (*OrderedMap) ReadOnlyLoadedValueIterator added in v0.8.0 

func (m *OrderedMap) ReadOnlyLoadedValueIterator() (*MapLoadedValueIterator, error)

ReadOnlyLoadedValueIterator returns iterator to iterate loaded map elements.

func (*OrderedMap) Remove 

func (m *OrderedMap) Remove(comparator ValueComparator, hip HashInputProvider, key Value) (Storable, Storable, error)

func (*OrderedMap) Seed 

func (m *OrderedMap) Seed() uint64

func (*OrderedMap) Set 

func (m *OrderedMap) Set(comparator ValueComparator, hip HashInputProvider, key Value, value Value) (Storable, error)

func (*OrderedMap) SetType added in v0.8.0 

func (m *OrderedMap) SetType(typeInfo TypeInfo) error

func (*OrderedMap) SlabID added in v0.8.0 

func (m *OrderedMap) SlabID() SlabID

func (*OrderedMap) Storable 

func (m *OrderedMap) Storable(_ SlabStorage, _ Address, maxInlineSize uint64) (Storable, error)

Storable returns OrderedMap m as either: - SlabIDStorable, or - inlined data slab storable

func (*OrderedMap) String 

func (m *OrderedMap) String() string

func (*OrderedMap) Type 

func (m *OrderedMap) Type() TypeInfo

func (*OrderedMap) ValueID added in v0.8.0 

func (m *OrderedMap) ValueID() ValueID

type PersistentSlabStorage 

type PersistentSlabStorage struct {
	DecodeStorable StorableDecoder
	DecodeTypeInfo TypeInfoDecoder
	// contains filtered or unexported fields
}

func NewPersistentSlabStorage 

func NewPersistentSlabStorage(
	base BaseStorage,
	cborEncMode cbor.EncMode,
	cborDecMode cbor.DecMode,
	decodeStorable StorableDecoder,
	decodeTypeInfo TypeInfoDecoder,
	opts ...StorageOption,
) *PersistentSlabStorage

func (*PersistentSlabStorage) BatchPreload added in v0.8.0 

func (s *PersistentSlabStorage) BatchPreload(ids []SlabID, numWorkers int) error

BatchPreload decodeds and caches slabs of given ids in parallel. This is useful for storage health or data validation in migration programs.

func (*PersistentSlabStorage) Commit 

func (s *PersistentSlabStorage) Commit() error

func (*PersistentSlabStorage) Count 

func (s *PersistentSlabStorage) Count() int

Warning Counts doesn't consider new segments in the deltas and only returns committed values

func (*PersistentSlabStorage) Deltas added in v0.4.0 

func (s *PersistentSlabStorage) Deltas() uint

Deltas returns number of uncommitted slabs, including slabs with temp addresses.

func (*PersistentSlabStorage) DeltasSizeWithoutTempAddresses added in v0.5.0 

func (s *PersistentSlabStorage) DeltasSizeWithoutTempAddresses() uint64

DeltasSizeWithoutTempAddresses returns total size of uncommitted slabs (in bytes), excluding slabs with temp addresses.

func (*PersistentSlabStorage) DeltasWithoutTempAddresses added in v0.4.0 

func (s *PersistentSlabStorage) DeltasWithoutTempAddresses() uint

DeltasWithoutTempAddresses returns number of uncommitted slabs, excluding slabs with temp addresses.

func (*PersistentSlabStorage) DropCache 

func (s *PersistentSlabStorage) DropCache()

func (*PersistentSlabStorage) DropDeltas 

func (s *PersistentSlabStorage) DropDeltas()

func (*PersistentSlabStorage) FastCommit 

func (s *PersistentSlabStorage) FastCommit(numWorkers int) error

func (*PersistentSlabStorage) FixLoadedBrokenReferences added in v0.8.0 

func (s *PersistentSlabStorage) FixLoadedBrokenReferences(needToFix func(old Value) bool) (
	fixedSlabIDs map[SlabID][]SlabID,
	skippedSlabIDs map[SlabID][]SlabID,
	err error,
)

FixLoadedBrokenReferences traverses loaded slabs and fixes broken references in maps. A broken reference is a SlabID referencing a non-existent slab. To fix a map containing broken references, this function replaces broken map with empty map having the same SlabID and also removes all slabs in the old map. Limitations: - only fix broken references in map - only traverse loaded slabs in deltas and cache NOTE: The intended use case is to enable migration programs in onflow/flow-go to fix broken references. As of April 2024, only 10 registers in testnet (not mainnet) were found to have broken references and they seem to have resulted from a bug that was fixed 2 years ago by https://github.com/onflow/cadence/pull/1565.

func (*PersistentSlabStorage) GenerateSlabID added in v0.8.0 

func (s *PersistentSlabStorage) GenerateSlabID(address Address) (SlabID, error)

func (*PersistentSlabStorage) GetAllChildReferences added in v0.8.0 

func (s *PersistentSlabStorage) GetAllChildReferences(id SlabID) (
	references []SlabID,
	brokenReferences []SlabID,
	err error,
)

GetAllChildReferences returns child references of given slab (all levels), including nested container and theirs child references.

func (*PersistentSlabStorage) HasUnsavedChanges added in v0.8.1 

func (s *PersistentSlabStorage) HasUnsavedChanges(address Address) bool

HasUnsavedChanges returns true if there are any modified and unsaved slabs in storage with given address.

func (*PersistentSlabStorage) NondeterministicFastCommit added in v0.8.0 

func (s *PersistentSlabStorage) NondeterministicFastCommit(numWorkers int) error

NondeterministicFastCommit commits changed slabs in nondeterministic order. Encoded slab data is deterministic (e.g. array and map iteration is deterministic). IMPORTANT: This function is used by migration programs when commit order of slabs is not required to be deterministic (while preserving deterministic array and map iteration).

func (*PersistentSlabStorage) Remove 

func (s *PersistentSlabStorage) Remove(id SlabID) error

func (*PersistentSlabStorage) Retrieve 

func (s *PersistentSlabStorage) Retrieve(id SlabID) (Slab, bool, error)

func (*PersistentSlabStorage) RetrieveIfLoaded added in v0.8.0 

func (s *PersistentSlabStorage) RetrieveIfLoaded(id SlabID) Slab

func (*PersistentSlabStorage) RetrieveIgnoringDeltas 

func (s *PersistentSlabStorage) RetrieveIgnoringDeltas(id SlabID, cache bool) (Slab, bool, error)

func (*PersistentSlabStorage) SlabIterator 

func (s *PersistentSlabStorage) SlabIterator() (SlabIterator, error)

func (*PersistentSlabStorage) Store 

func (s *PersistentSlabStorage) Store(id SlabID, slab Slab) error

type ReadOnlyArrayIteratorMutationCallback added in v0.8.0 

type ReadOnlyArrayIteratorMutationCallback func(mutatedValue Value)

type ReadOnlyIteratorElementMutationError added in v0.8.0 

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

ReadOnlyIteratorElementMutationError is the error returned when readonly iterator element is mutated.

func (*ReadOnlyIteratorElementMutationError) Error added in v0.8.0 

func (e *ReadOnlyIteratorElementMutationError) Error() string

type ReadOnlyMapIteratorMutationCallback added in v0.8.0 

type ReadOnlyMapIteratorMutationCallback func(mutatedValue Value)

type Slab 

type Slab interface {
	Storable
	fmt.Stringer

	SlabID() SlabID
	Split(SlabStorage) (Slab, Slab, error)
	Merge(Slab) error
	// LendToRight rebalances slabs by moving elements from left to right
	LendToRight(Slab) error
	// BorrowFromRight rebalances slabs by moving elements from right to left
	BorrowFromRight(Slab) error
}

func DecodeSlab 

func DecodeSlab(
	id SlabID,
	data []byte,
	decMode cbor.DecMode,
	decodeStorable StorableDecoder,
	decodeTypeInfo TypeInfoDecoder,
) (
	Slab,
	error,
)

type SlabDataError 

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

SlabError is a always fatal error returned when something is wrong with the content or type of the slab you can make this a fatal error by calling Fatal()

func (*SlabDataError) Error 

func (e *SlabDataError) Error() string

type SlabID added in v0.8.0 

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

SlabID identifies slab in storage. SlabID should only be used to retrieve, store, and remove slab in storage.

func NewSlabID added in v0.8.0 

func NewSlabID(address Address, index SlabIndex) SlabID

func NewSlabIDFromRawBytes added in v0.8.0 

func NewSlabIDFromRawBytes(b []byte) (SlabID, error)

func (SlabID) Address added in v0.8.0 

func (id SlabID) Address() Address

Address returns the address of SlabID.

func (SlabID) AddressAsUint64 added in v0.8.0 

func (id SlabID) AddressAsUint64() uint64

func (SlabID) Compare added in v0.8.0 

func (id SlabID) Compare(other SlabID) int

func (SlabID) HasTempAddress added in v0.8.0 

func (id SlabID) HasTempAddress() bool

func (SlabID) Index added in v0.8.0 

func (id SlabID) Index() SlabIndex

func (SlabID) IndexAsUint64 added in v0.8.0 

func (id SlabID) IndexAsUint64() uint64

func (SlabID) String added in v0.8.0 

func (id SlabID) String() string

func (SlabID) ToRawBytes added in v0.8.0 

func (id SlabID) ToRawBytes(b []byte) (int, error)

func (SlabID) Valid added in v0.8.0 

func (id SlabID) Valid() error

type SlabIDError added in v0.8.0 

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

SlabIDError is returned when slab id can't be created or it's invalid.

func (*SlabIDError) Error added in v0.8.0 

func (e *SlabIDError) Error() string

type SlabIDStorable added in v0.8.0 

type SlabIDStorable SlabID

func (SlabIDStorable) ByteSize added in v0.8.0 

func (v SlabIDStorable) ByteSize() uint32

func (SlabIDStorable) ChildStorables added in v0.8.0 

func (v SlabIDStorable) ChildStorables() []Storable

func (SlabIDStorable) Encode added in v0.8.0 

func (v SlabIDStorable) Encode(enc *Encoder) error

Encode encodes SlabIDStorable as 

cbor.Tag{
		Number:  cborTagSlabID,
		Content: byte(v),
}

func (SlabIDStorable) HasPointer added in v0.8.0 

func (v SlabIDStorable) HasPointer() bool

func (SlabIDStorable) StoredValue added in v0.8.0 

func (v SlabIDStorable) StoredValue(storage SlabStorage) (Value, error)

func (SlabIDStorable) String added in v0.8.0 

func (v SlabIDStorable) String() string

type SlabIndex added in v0.8.0 

type SlabIndex [SlabIndexLength]byte

WARNING: Any changes to SlabID or its components (Address and SlabIndex) require updates to ValueID definition and functions.

func (SlabIndex) Next added in v0.8.0 

func (index SlabIndex) Next() SlabIndex

Next returns new SlabIndex with index+1 value. The caller is responsible for preventing overflow by checking if the index value is valid before calling this function.

type SlabIterator 

type SlabIterator func() (SlabID, Slab)

type SlabMergeError 

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

SlabMergeError is always a fatal error returned when merging two slabs fails

func (*SlabMergeError) Error 

func (e *SlabMergeError) Error() string

type SlabNotFoundError 

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

SlabNotFoundError is always a fatal error returned when an slab is not found

func (*SlabNotFoundError) Error 

func (e *SlabNotFoundError) Error() string

type SlabRebalanceError 

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

SlabRebalanceError is always a fatal error returned when rebalancing a slab has failed

func (*SlabRebalanceError) Error 

func (e *SlabRebalanceError) Error() string

type SlabSplitError 

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

SlabSplitError is always a fatal error returned when splitting an slab has failed

func (*SlabSplitError) Error 

func (e *SlabSplitError) Error() string

type SlabStorage 

type SlabStorage interface {
	Store(SlabID, Slab) error
	Retrieve(SlabID) (Slab, bool, error)
	RetrieveIfLoaded(SlabID) Slab
	Remove(SlabID) error
	GenerateSlabID(address Address) (SlabID, error)
	Count() int
	SlabIterator() (SlabIterator, error)
}

type SliceOutOfBoundsError added in v0.2.0 

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

SliceOutOfBoundsError is returned when index for array slice is out of bounds.

func (*SliceOutOfBoundsError) Error added in v0.2.0 

func (e *SliceOutOfBoundsError) Error() string

type Storable 

type Storable interface {
	Encode(*Encoder) error

	ByteSize() uint32

	StoredValue(storage SlabStorage) (Value, error)

	// ChildStorables only returns child storables in this storable
	// (not recursive).  This function shouldn't load extra slabs.
	ChildStorables() []Storable
}

func DecodeInlinedArrayStorable added in v0.8.0 

func DecodeInlinedArrayStorable(
	dec *cbor.StreamDecoder,
	decodeStorable StorableDecoder,
	parentSlabID SlabID,
	inlinedExtraData []ExtraData,
) (
	Storable,
	error,
)

DecodeInlinedArrayStorable decodes inlined array data slab. Encoding is version 1 with CBOR tag having tag number CBORTagInlinedArray, and tag contant as 3-element array: 

+------------------+----------------+----------+
| extra data index | value ID index | elements |
+------------------+----------------+----------+

NOTE: This function doesn't decode tag number because tag number is decoded in the caller and decoder only contains tag content.

func DecodeInlinedCompactMapStorable added in v0.8.0 

func DecodeInlinedCompactMapStorable(
	dec *cbor.StreamDecoder,
	decodeStorable StorableDecoder,
	parentSlabID SlabID,
	inlinedExtraData []ExtraData,
) (
	Storable,
	error,
)

DecodeInlinedCompactMapStorable decodes inlined compact map data. Encoding is version 1 with CBOR tag having tag number CBORTagInlinedCompactMap, and tag contant as 3-element array:

- index of inlined extra data - value ID index - CBOR array of elements

NOTE: This function doesn't decode tag number because tag number is decoded in the caller and decoder only contains tag content.

func DecodeInlinedMapStorable added in v0.8.0 

func DecodeInlinedMapStorable(
	dec *cbor.StreamDecoder,
	decodeStorable StorableDecoder,
	parentSlabID SlabID,
	inlinedExtraData []ExtraData,
) (
	Storable,
	error,
)

DecodeInlinedMapStorable decodes inlined map data slab. Encoding is version 1 with CBOR tag having tag number CBORTagInlinedMap, and tag contant as 3-element array: 

+------------------+----------------+----------+
| extra data index | value ID index | elements |
+------------------+----------------+----------+

NOTE: This function doesn't decode tag number because tag number is decoded in the caller and decoder only contains tag content.

func DecodeSlabIDStorable added in v0.8.0 

func DecodeSlabIDStorable(dec *cbor.StreamDecoder) (Storable, error)

func NewStorableSlab added in v0.8.0 

func NewStorableSlab(storage SlabStorage, address Address, storable Storable) (Storable, error)

type StorableComparator 

type StorableComparator func(Storable, Storable) bool

type StorableDecoder 

type StorableDecoder func(
	decoder *cbor.StreamDecoder,
	storableSlabID SlabID,
	inlinedExtraData []ExtraData,
) (
	Storable,
	error,
)

type StorableSlab 

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

StorableSlab allows storing storables (CBOR encoded data) directly in a slab. Eventually we will only have a dictionary at the account storage root, so this won't be needed, but during the refactor we have the need to store other non-dictionary values (e.g. strings, integers, etc.) directly in accounts (i.e. directly in slabs aka registers)

func (*StorableSlab) BorrowFromRight 

func (*StorableSlab) BorrowFromRight(_ Slab) error

func (*StorableSlab) ByteSize 

func (s *StorableSlab) ByteSize() uint32

func (*StorableSlab) ChildStorables 

func (s *StorableSlab) ChildStorables() []Storable

func (*StorableSlab) Encode 

func (s *StorableSlab) Encode(enc *Encoder) error

func (*StorableSlab) LendToRight 

func (*StorableSlab) LendToRight(_ Slab) error

func (*StorableSlab) Merge 

func (*StorableSlab) Merge(_ Slab) error

func (*StorableSlab) SlabID added in v0.8.0 

func (s *StorableSlab) SlabID() SlabID

func (*StorableSlab) Split 

func (*StorableSlab) Split(_ SlabStorage) (Slab, Slab, error)

func (*StorableSlab) StoredValue 

func (s *StorableSlab) StoredValue(storage SlabStorage) (Value, error)

func (*StorableSlab) String added in v0.8.0 

func (s *StorableSlab) String() string

type StorageOption 

type StorageOption func(st *PersistentSlabStorage) *PersistentSlabStorage

type TypeInfo 

type TypeInfo interface {
	Encode(*cbor.StreamEncoder) error
	IsComposite() bool
	Copy() TypeInfo
}

type TypeInfoComparator 

type TypeInfoComparator func(TypeInfo, TypeInfo) bool

type TypeInfoDecoder 

type TypeInfoDecoder func(
	decoder *cbor.StreamDecoder,
) (
	TypeInfo,
	error,
)

type UnreachableError 

type UnreachableError struct {
	Stack []byte
}

UnreachableError is used by panic when unreachable code is reached. This is copied from Cadence.

func (UnreachableError) Error 

func (e UnreachableError) Error() string

type UserError added in v0.6.0 

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

func (*UserError) Error added in v0.6.0 

func (e *UserError) Error() string

func (*UserError) Unwrap added in v0.6.0 

func (e *UserError) Unwrap() error

type Value 

type Value interface {
	Storable(SlabStorage, Address, uint64) (Storable, error)
}

type ValueComparator 

type ValueComparator func(SlabStorage, Value, Storable) (bool, error)

type ValueID added in v0.8.0 

type ValueID [ValueIDLength]byte

ValueID identifies an Array or OrderedMap. ValueID is consistent independent of inlining status, while ValueID and SlabID are used differently despite having the same size and content under the hood. By contrast, SlabID is affected by inlining because it identifies a slab in storage. Given this, ValueID should be used for resource tracking, etc.

func (ValueID) String added in v0.8.0 

func (vid ValueID) String() string

type WrapperStorable added in v0.9.0 

type WrapperStorable interface {
	Storable

	// UnwrapAtreeStorable returns innermost wrapped Storable.
	UnwrapAtreeStorable() Storable

	// WrapAtreeStorable returns a new WrapperStorable with given storable as innermost wrapped storable.
	WrapAtreeStorable(Storable) Storable
}

WrapperStorable is an interface that supports storable wrapping another storable.

type WrapperValue added in v0.9.0 

type WrapperValue interface {
	Value

	// UnwrapAtreeValue returns innermost wrapped Value and wrapper size.
	UnwrapAtreeValue() (Value, uint64)
}

WrapperValue is an interface that supports value wrapping another value.

Source Files

View all Source files

Directories

Path Synopsis
cmd
smoke command

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.