trieutils

package
v0.15.14 Latest Latest
Warning

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

 Go to latest Published: Dec 1, 2025 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	MaxBitArraySize = 33 // (1 + 4 * 8) bytes
)
View Source 
const PathSize = MaxBitArraySize

Variables

This section is empty.

Functions

func DeleteNodeByPath 

func DeleteNodeByPath(w db.KeyValueWriter, bucket db.Bucket, owner *felt.Felt, path *Path, isLeaf bool) error

func DeleteStateID 

func DeleteStateID(w db.KeyValueWriter, root *felt.Felt) error

func DeleteStorageNodesByPath 

func DeleteStorageNodesByPath(w db.KeyValueRangeDeleter, owner felt.Felt) error

func GetNodeByHash added in v0.14.6 

func GetNodeByHash(r db.KeyValueReader, bucket db.Bucket, owner *felt.Felt, path *Path, hash *felt.Felt, isLeaf bool) ([]byte, error)

func GetNodeByPath 

func GetNodeByPath(r db.KeyValueReader, bucket db.Bucket, owner *felt.Felt, path *Path, isLeaf bool) ([]byte, error)

func ReadPersistedStateID 

func ReadPersistedStateID(r db.KeyValueReader) (uint64, error)

func ReadStateID 

func ReadStateID(r db.KeyValueReader, root *felt.Felt) (uint64, error)

func ReadTrieJournal 

func ReadTrieJournal(r db.KeyValueReader) ([]byte, error)

func WriteNodeByHash added in v0.14.6 

func WriteNodeByHash(w db.KeyValueWriter, bucket db.Bucket, owner *felt.Felt, path *Path, hash *felt.Felt, isLeaf bool, blob []byte) error

func WriteNodeByPath 

func WriteNodeByPath(w db.KeyValueWriter, bucket db.Bucket, owner *felt.Felt, path *Path, isLeaf bool, blob []byte) error

func WritePersistedStateID 

func WritePersistedStateID(w db.KeyValueWriter, id uint64) error

func WriteStateID 

func WriteStateID(w db.KeyValueWriter, root *felt.Felt, id uint64) error

func WriteTrieJournal 

func WriteTrieJournal(w db.KeyValueWriter, journal []byte) error

Types

type BitArray 

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

Represents a bit array with length representing the number of used bits. It uses a little endian representation to do bitwise operations of the words efficiently. For example, if len is 10, it means that the 2^9, 2^8, ..., 2^0 bits are used. The max length is 255 bits (uint8), because our use case only need up to 251 bits for a given trie key. Although words can be used to represent 256 bits, we don't want to add an additional byte for the length.

func NewBitArray 

func NewBitArray(length uint8, val uint64) BitArray

func (*BitArray) ActiveBytes added in v0.14.6 

func (b *BitArray) ActiveBytes() []byte

Returns a slice containing only the bytes that are actually used by the bit array, as specified by the length. The returned slice is in big-endian order.

Example: 

len = 10, words = [0x3FF, 0, 0, 0] -> [0x03, 0xFF]

func (*BitArray) And 

func (b *BitArray) And(x, y *BitArray) *BitArray

func (*BitArray) Append 

func (b *BitArray) Append(x, y *BitArray) *BitArray

Sets the bit array to the concatenation of x and y and returns the bit array. For example: 

x = 000 (len=3)
y = 111 (len=3)
Append(x,y) = 000111 (len=6)

func (*BitArray) AppendBit 

func (b *BitArray) AppendBit(x *BitArray, bit uint8) *BitArray

Sets the bit array to the concatenation of x and a single bit.

func (*BitArray) AppendZeros 

func (b *BitArray) AppendZeros(x *BitArray, n uint8) *BitArray

Sets the bit array to the concatenation of x and n zeros.

func (*BitArray) Bit 

func (b *BitArray) Bit(n uint8) uint8

Returns the bit value at position n, where n = 0 is MSB. If n is out of bounds, returns 0.

func (*BitArray) BitFromLSB 

func (b *BitArray) BitFromLSB(n uint8) uint8

Returns the bit value at position n, where n = 0 is LSB. If n is out of bounds, returns 0.

func (*BitArray) Bytes 

func (b *BitArray) Bytes() [32]byte

Returns the bytes representation of the bit array in big endian format

func (*BitArray) Cmp 

func (b *BitArray) Cmp(x *BitArray) int

Cmp compares two bit arrays lexicographically. The comparison is first done by length, then by content if lengths are equal. Returns: 

-1 if b < x
 0 if b == x
 1 if b > x

func (*BitArray) CommonMSBs 

func (b *BitArray) CommonMSBs(x, y *BitArray) *BitArray

Sets the bit array to the longest sequence of matching most significant bits between two bit arrays. For example: 

x = 1101 0111 (len=8)
y = 1101 0000 (len=8)
CommonMSBs(x,y) = 1101 (len=4)

func (*BitArray) Copy 

func (b *BitArray) Copy() BitArray

Returns a deep copy of the bit array.

func (*BitArray) EncodedBytes 

func (b *BitArray) EncodedBytes() []byte

Returns the encoded bytes of the bit array.

func (*BitArray) EncodedLen 

func (b *BitArray) EncodedLen() uint

Returns the length of the encoded bit array in bytes.

func (*BitArray) EncodedString 

func (b *BitArray) EncodedString() string

Returns the encoded string representation of the bit array.

func (*BitArray) Equal 

func (b *BitArray) Equal(x *BitArray) bool

Checks if two bit arrays are equal

func (*BitArray) EqualMSBs 

func (b *BitArray) EqualMSBs(x *BitArray) bool

Checks if the current bit array share the same most significant bits with another, where the length of the check is determined by the shorter array. Returns true if either array has length 0, or if the first min(b.len, x.len) MSBs are identical.

For example: 

a = 1101 (len=4)
b = 11010111 (len=8)
a.EqualMSBs(b) = true  // First 4 MSBs match

a = 1100 (len=4)
b = 1101 (len=4)
a.EqualMSBs(b) = false // All bits compared, not equal

a = 1100 (len=4)
b = [] (len=0)
a.EqualMSBs(b) = true  // Zero length is always a prefix match

func (*BitArray) Felt 

func (b *BitArray) Felt() felt.Felt

Returns the felt representation of the bit array.

func (*BitArray) IsBitSet 

func (b *BitArray) IsBitSet(n uint8) bool

func (*BitArray) IsBitSetFromLSB 

func (b *BitArray) IsBitSetFromLSB(n uint8) bool

Returns true if bit n-th is set, where n = 0 is LSB.

func (*BitArray) IsEmpty 

func (b *BitArray) IsEmpty() bool

func (*BitArray) LSB 

func (b *BitArray) LSB() uint8

func (*BitArray) LSBs 

func (b *BitArray) LSBs(x *BitArray, n uint8) *BitArray

Returns the least significant bits of `x` with `n` counted from the most significant bit, starting at 0. Think of this method as array[n:] For example: 

x = 11001011 (len=8)
LSBs(x, 1) = 1001011 (len=7)
LSBs(x, 10) = 0 (len=0)
LSBs(x, 0) = 11001011 (len=8, original x)

func (*BitArray) LSBsFromLSB 

func (b *BitArray) LSBsFromLSB(x *BitArray, n uint8) *BitArray

Sets the bit array to the least significant 'n' bits of x. n is counted from the least significant bit, starting at 0. If length >= x.len, the bit array is an exact copy of x. For example: 

x = 11001011 (len=8)
LSBsFromLSB(x, 4) = 1011 (len=4)
LSBsFromLSB(x, 10) = 11001011 (len=8, original x)
LSBsFromLSB(x, 0) = 0 (len=0)

func (*BitArray) Len 

func (b *BitArray) Len() uint8

func (*BitArray) Lsh 

func (b *BitArray) Lsh(x *BitArray, n uint8) *BitArray

Lsh sets the bit array to x << n and returns the bit array.

func (*BitArray) MSB 

func (b *BitArray) MSB() uint8

Returns the bit value at the most significant bit

func (*BitArray) MSBs 

func (b *BitArray) MSBs(x *BitArray, n uint8) *BitArray

Sets the bit array to the most significant 'n' bits of x, that is position 0 to n (exclusive). If n >= x.len, the bit array is an exact copy of x. Think of this method as array[0:n] For example: 

x = 11001011 (len=8)
MSBs(x, 4) = 1100 (len=4)
MSBs(x, 10) = 11001011 (len=8, original x)
MSBs(x, 0) = 0 (len=0)

func (*BitArray) Ones 

func (b *BitArray) Ones(length uint8) *BitArray

Sets the bit array to a sequence of ones of the specified length.

func (*BitArray) Or 

func (b *BitArray) Or(x, y *BitArray) *BitArray

Sets the bit array to x | y and returns the bit array.

func (*BitArray) Rsh 

func (b *BitArray) Rsh(x *BitArray, n uint8) *BitArray

Sets the bit array to x >> n and returns the bit array.

func (*BitArray) Set 

func (b *BitArray) Set(x *BitArray) *BitArray

Sets the bit array to the same value as x.

func (*BitArray) SetBit 

func (b *BitArray) SetBit(bit uint8) *BitArray

Sets the bit array to a single bit.

func (*BitArray) SetBytes 

func (b *BitArray) SetBytes(length uint8, data []byte) *BitArray

Interprets the data as the big-endian bytes, sets the bit array to that value and returns it. If the data is larger than 32 bytes, only the first 32 bytes are used.

func (*BitArray) SetFelt 

func (b *BitArray) SetFelt(length uint8, f *felt.Felt) *BitArray

Sets the bit array to the bytes representation of a felt.

func (*BitArray) SetFelt251 

func (b *BitArray) SetFelt251(f *felt.Felt) *BitArray

Sets the bit array to the bytes representation of a felt with length 251.

func (*BitArray) SetUint64 

func (b *BitArray) SetUint64(length uint8, data uint64) *BitArray

Sets the bit array to the uint64 representation of a bit array.

func (*BitArray) String 

func (b *BitArray) String() string

Returns a string representation of the bit array. This is typically used for logging or debugging.

func (*BitArray) Subset 

func (b *BitArray) Subset(x *BitArray, startPos, endPos uint8) *BitArray

Sets the bit array to a subset of x from startPos (inclusive) to endPos (exclusive), where position 0 is the MSB. If startPos >= endPos or if startPos >= x.len, returns an empty BitArray. Think of this method as array[start:end] For example: 

x = 001011011 (len=9)
Subset(x, 2, 5) = 101 (len=3)

func (*BitArray) UnmarshalBinary 

func (b *BitArray) UnmarshalBinary(data []byte) error

Deserialises the BitArray from a bytes buffer in the following format: - First byte: length of the bit array (0-255) - Remaining bytes: the necessary bytes included in big endian order Example: 

[0x0A, 0x03, 0xFF] -> BitArray{len: 10, words: [4]uint64{0x03FF}}

func (*BitArray) Write 

func (b *BitArray) Write(buf *bytes.Buffer) (int, error)

Serialises the BitArray into a bytes buffer in the following format: - First few bytes: the necessary bytes included in big endian order - Last byte: length of the bit array (0-255) Example: 

BitArray{len: 10, words: [4]uint64{0x03FF}} -> [0x03, 0xFF, 0x0A]

func (*BitArray) Xor 

func (b *BitArray) Xor(x, y *BitArray) *BitArray

Sets the bit array to x ^ y and returns the bit array.

func (*BitArray) Zeros 

func (b *BitArray) Zeros(length uint8) *BitArray

type ClassTrieID 

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

Identifier for a class trie

func NewClassTrieID 

func NewClassTrieID(stateComm felt.Felt) ClassTrieID

func (ClassTrieID) Bucket 

func (id ClassTrieID) Bucket() db.Bucket

func (ClassTrieID) HasOwner 

func (id ClassTrieID) HasOwner() bool

func (ClassTrieID) Owner 

func (id ClassTrieID) Owner() felt.Felt

func (ClassTrieID) StateComm 

func (id ClassTrieID) StateComm() felt.Felt

func (ClassTrieID) Type 

func (id ClassTrieID) Type() TrieType

type ContractStorageTrieID 

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

Identifier for a contract storage trie

func NewContractStorageTrieID 

func NewContractStorageTrieID(stateComm, owner felt.Felt) ContractStorageTrieID

func (ContractStorageTrieID) Bucket 

func (id ContractStorageTrieID) Bucket() db.Bucket

func (ContractStorageTrieID) HasOwner 

func (id ContractStorageTrieID) HasOwner() bool

func (ContractStorageTrieID) Owner 

func (id ContractStorageTrieID) Owner() felt.Felt

func (ContractStorageTrieID) StateComm 

func (id ContractStorageTrieID) StateComm() felt.Felt

func (ContractStorageTrieID) Type 

func (id ContractStorageTrieID) Type() TrieType

type ContractTrieID 

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

Identifier for a contract trie

func NewContractTrieID 

func NewContractTrieID(stateComm felt.Felt) ContractTrieID

func (ContractTrieID) Bucket 

func (id ContractTrieID) Bucket() db.Bucket

func (ContractTrieID) HasOwner 

func (id ContractTrieID) HasOwner() bool

func (ContractTrieID) Owner 

func (id ContractTrieID) Owner() felt.Felt

func (ContractTrieID) StateComm 

func (id ContractTrieID) StateComm() felt.Felt

func (ContractTrieID) Type 

func (id ContractTrieID) Type() TrieType

type EmptyTrieID 

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

Identifier for an empty trie, only used for temporary purposes

func NewEmptyTrieID 

func NewEmptyTrieID(stateComm felt.Felt) EmptyTrieID

func (EmptyTrieID) Bucket 

func (id EmptyTrieID) Bucket() db.Bucket

func (EmptyTrieID) HasOwner 

func (id EmptyTrieID) HasOwner() bool

func (EmptyTrieID) Owner 

func (id EmptyTrieID) Owner() felt.Felt

func (EmptyTrieID) StateComm 

func (id EmptyTrieID) StateComm() felt.Felt

func (EmptyTrieID) Type 

func (id EmptyTrieID) Type() TrieType

type Path 

type Path = BitArray // Represents the path from the root to the node in the trie

type TrieID 

type TrieID interface {
	// The state commitment where this trie belongs to. Note that this is not the trie root hash.
	// Also, note that a state commitment is calculated with the combination of both class trie and contract trie.
	StateComm() felt.Felt

	HasOwner() bool   // whether the trie has an owner
	Owner() felt.Felt // the owner of the trie (e.g. contract address)

	Type() TrieType
	Bucket() db.Bucket // the database bucket prefix
}

A unique identifier for a trie type

type TrieType 

type TrieType int

Represents the type of trie on Starknet 

const (
	Empty TrieType = iota
	Class
	Contract
	ContractStorage
)

func (TrieType) String 

func (t TrieType) String() string

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.