omap

Documentation

Overview

Package omap defines a generic-based type for creating ordered maps. It exports a "Sorter" interface, allowing the creation of sorted maps with custom key and value types.

See impl.go for examples.

## Motivation

Ensuring deterministic behavior is crucial in blockchain systems, as all nodes must reach a consensus on the state of the blockchain. Every action, given the same input, should consistently yield the same result. A divergence in state could impede the ability of nodes to validate a block, prohibiting the addition of the block to the chain, which could lead to chain halts.

Index

• func SorterLeq[K comparable](sorter Sorter[K], a, b K) bool
• type SortedMap
  • func SortedMap_EthAddress[V any](data map[gethcommon.Address]V) SortedMap[gethcommon.Address, V]
  • func SortedMap_Pair[V any](data map[asset.Pair]V) SortedMap[asset.Pair, V]
  • func SortedMap_String[V any](data map[string]V) SortedMap[string, V]
  • func (om *SortedMap[K, V]) BuildFrom(data map[K]V, sorter Sorter[K]) *SortedMap[K, V]
  • func (om *SortedMap[K, V]) Data() map[K]V
  • func (om *SortedMap[K, V]) Delete(key K)
  • func (om *SortedMap[K, V]) Get(key K) (val V, exists bool)
  • func (om *SortedMap[K, V]) Has(key K) bool
  • func (om *SortedMap[K, V]) InternalData() map[K]V
  • func (om *SortedMap[K, V]) Keys() []K
  • func (om *SortedMap[K, V]) Len() int
  • func (om *SortedMap[K, V]) Range() <-chan (K)
  • func (om *SortedMap[K, V]) Set(key K, val V)
  • func (om *SortedMap[K, V]) Union(kvMap map[K]V)
• type Sorter

Functions

func SorterLeq

func SorterLeq[K comparable](sorter Sorter[K], a, b K) bool

SorterLeq is true if a <= b implements "less than or equal" using "Less"

Types

type SortedMap

type SortedMap[K comparable, V any] struct {
	// contains filtered or unexported fields
}

SortedMap is a wrapper struct around the built-in map that has guarantees about order because it sorts its keys with a custom sorter. It has a public API that mirrors that functionality of `map`. SortedMap is built with generics, so it can hold various combinations of key-value types.

func SortedMap_EthAddress

func SortedMap_EthAddress[V any](
	data map[gethcommon.Address]V,
) SortedMap[gethcommon.Address, V]

func SortedMap_Pair

func SortedMap_Pair[V any](
	data map[asset.Pair]V,
) SortedMap[asset.Pair, V]

func SortedMap_String

func SortedMap_String[V any](data map[string]V) SortedMap[string, V]

func (*SortedMap[K, V]) BuildFrom

func (om *SortedMap[K, V]) BuildFrom(
	data map[K]V, sorter Sorter[K],
) *SortedMap[K, V]

BuildFrom is a method that builds an OrderedMap from a given map and a sorter for the keys. This function is useful for creating new OrderedMap types with typed keys.

func (*SortedMap[K, V]) Data

func (om *SortedMap[K, V]) Data() map[K]V

Data returns a copy of the underlying map (unordered, unsorted)

func (*SortedMap[K, V]) Delete

func (om *SortedMap[K, V]) Delete(key K)

Delete removes a key-value pair from the map if the key exists.

func (*SortedMap[K, V]) Get

func (om *SortedMap[K, V]) Get(key K) (val V, exists bool)

func (*SortedMap[K, V]) Has

func (om *SortedMap[K, V]) Has(key K) bool

Has checks whether a key exists in the map.

func (*SortedMap[K, V]) InternalData

func (om *SortedMap[K, V]) InternalData() map[K]V

InternalData returns the SortedMap's private map.

func (*SortedMap[K, V]) Keys

func (om *SortedMap[K, V]) Keys() []K

Keys returns a slice of the keys in their sorted order.

func (*SortedMap[K, V]) Len

func (om *SortedMap[K, V]) Len() int

Len returns the number of items in the map.

func (*SortedMap[K, V]) Range

func (om *SortedMap[K, V]) Range() <-chan (K)

Range returns a channel of keys in their sorted order. This allows you to iterate over the map in a deterministic order. Using a channel here makes it so that the iteration is done lazily rather loading the entire map (OrderedMap.data) into memory and then iterating.

func (*SortedMap[K, V]) Set

func (om *SortedMap[K, V]) Set(key K, val V)

Set adds a key-value pair to the map, or updates the value if the key already exists. It ensures the keys are ordered after the operation.

func (*SortedMap[K, V]) Union

func (om *SortedMap[K, V]) Union(kvMap map[K]V)

Union combines new key-value pairs into the ordered map.

type Sorter

type Sorter[K any] interface {
	// Returns true if 'a' is less than 'b' Less needs to be defined for the
	// key type, K, to provide a comparison operation.
	Less(a K, b K) bool
}

Sorter is an interface used for ordering the keys in the OrderedMap.