ids

package
v1.9.5-rc.2 Latest Latest
Warning

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

 Go to latest Published: Dec 20, 2022 License: BSD-3-Clause Imports: 17 Imported by: 1,056

Documentation

Index

Constants

View Source 
const BitsPerByte = 8

BitsPerByte is the number of bits per byte

View Source 
const NodeIDPrefix = "NodeID-"
View Source 
const NumBits = 256

NumBits is the number of bits this patricia tree manages

Variables

View Source 
var AliasTests = []func(require *require.Assertions, r AliaserReader, w AliaserWriter){
	AliaserLookupErrorTest,
	AliaserLookupTest,
	AliaserAliasesEmptyTest,
	AliaserAliasesTest,
	AliaserPrimaryAliasTest,
	AliaserAliasClashTest,
	AliaserRemoveAliasTest,
}
View Source 
var (
	// Empty is a useful all zero value
	Empty = ID{}
)
View Source 
var (
	EmptyNodeID = NodeID{}
)
View Source 
var (
	ShortEmpty = ShortID{}
)

ShortEmpty is a useful all zero value

Functions

func AliaserAliasClashTest added in v1.6.2 

func AliaserAliasClashTest(require *require.Assertions, _ AliaserReader, w AliaserWriter)

func AliaserAliasesEmptyTest added in v1.6.2 

func AliaserAliasesEmptyTest(require *require.Assertions, r AliaserReader, _ AliaserWriter)

func AliaserAliasesTest added in v1.6.2 

func AliaserAliasesTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserLookupErrorTest added in v1.6.2 

func AliaserLookupErrorTest(require *require.Assertions, r AliaserReader, _ AliaserWriter)

func AliaserLookupTest added in v1.6.2 

func AliaserLookupTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserPrimaryAliasTest added in v1.6.2 

func AliaserPrimaryAliasTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserRemoveAliasTest added in v1.6.2 

func AliaserRemoveAliasTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func EqualSubset 

func EqualSubset(start, stop int, id1, id2 ID) bool

EqualSubset takes in two indices and two ids and returns if the ids are equal from bit start to bit end (non-inclusive). Bit indices are defined as: [7 6 5 4 3 2 1 0] [15 14 13 12 11 10 9 8] ... [255 254 253 252 251 250 249 248] Where index 7 is the MSB of byte 0.

func FirstDifferenceSubset 

func FirstDifferenceSubset(start, stop int, id1, id2 ID) (int, bool)

FirstDifferenceSubset takes in two indices and two ids and returns the index of the first difference between the ids inside bit start to bit end (non-inclusive). Bit indices are defined above

func GetRelevantAliases added in v1.7.6 

func GetRelevantAliases(aliaser Aliaser, ids []ID) (map[ID][]string, error)

GetRelevantAliases returns the aliases with the redundant identity alias removed (each id is aliased to at least itself).

func ShortIDsToStrings added in v1.7.11 

func ShortIDsToStrings(ids []ShortID) []string

ShortIDsToStrings converts an array of shortIDs to an array of their string representations

Types

type Aliaser 

type Aliaser interface {
	AliaserReader
	AliaserWriter
	PrimaryAliasOrDefault(id ID) string
}

Aliaser allows one to give an ID aliases and lookup the aliases given to an ID.

func NewAliaser added in v1.6.2 

func NewAliaser() Aliaser

type AliaserReader added in v1.6.2 

type AliaserReader interface {
	Lookup(alias string) (ID, error)
	PrimaryAlias(id ID) (string, error)
	Aliases(id ID) ([]string, error)
}

AliaserReader allows one to lookup the aliases given to an ID.

type AliaserWriter added in v1.6.2 

type AliaserWriter interface {
	Alias(id ID, alias string) error
	RemoveAliases(id ID)
}

Aliaser allows one to give an ID aliases. An ID can have arbitrarily many aliases; two IDs may not have the same alias.

type Bag 

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

Bag is a multiset of IDs.

A bag has the ability to split and filter on its bits for ease of use for binary voting.

func (*Bag) Add 

func (b *Bag) Add(ids ...ID)

Add increases the number of times each id has been seen by one.

func (*Bag) AddCount 

func (b *Bag) AddCount(id ID, count int)

AddCount increases the number of times the id has been seen by count.

count must be >= 0

func (*Bag) Count 

func (b *Bag) Count(id ID) int

Count returns the number of times the id has been added.

func (*Bag) Equals 

func (b *Bag) Equals(oIDs Bag) bool

Equals returns true if the bags contain the same elements

func (*Bag) Filter 

func (b *Bag) Filter(start, end int, id ID) Bag

Filter returns the bag of ids with the same counts as this bag, except all the ids in the returned bag must have the same bits in the range [start, end) as id.

func (*Bag) Len 

func (b *Bag) Len() int

Len returns the number of times an id has been added.

func (*Bag) List 

func (b *Bag) List() []ID

List returns a list of all ids that have been added.

func (*Bag) Mode 

func (b *Bag) Mode() (ID, int)

Mode returns the id that has been seen the most and the number of times it has been seen. Ties are broken by the first id to be seen the reported number of times.

func (*Bag) PrefixedString added in v1.7.3 

func (b *Bag) PrefixedString(prefix string) string

func (*Bag) SetThreshold 

func (b *Bag) SetThreshold(threshold int)

SetThreshold sets the number of times an ID must be added to be contained in the threshold set.

func (*Bag) Split 

func (b *Bag) Split(index uint) [2]Bag

Split returns the bags of ids with the same counts a this bag, except all ids in the 0th index have a 0 at bit [index], and all ids in the 1st index have a 1 at bit [index].

func (*Bag) String 

func (b *Bag) String() string

func (*Bag) Threshold 

func (b *Bag) Threshold() set.Set[ID]

Threshold returns the ids that have been seen at least threshold times.

type BigBitSet added in v1.9.3 

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

BigBitSet is a bit-set backed by a big.Int Holds values ranging from [0, INT_MAX] (arch-dependent) Trying to use negative values will result in a panic. This implementation is NOT thread-safe.

func BigBitSetFromBytes 

func BigBitSetFromBytes(bytes []byte) BigBitSet

Inverse of BigBitSet.Bytes()

func NewBigBitSet added in v1.9.3 

func NewBigBitSet(bits ...int) BigBitSet

NewBigBitSet returns a new instance of BigBitSet with bits set to 1.

Invariants: 1. Negative bits will cause a panic. 2. Duplicate bits are allowed but will cause a no-op.

func (BigBitSet) Add added in v1.9.3 

func (b BigBitSet) Add(i int)

Add sets the [i]'th bit to 1

func (BigBitSet) Bytes 

func (b BigBitSet) Bytes() []byte

Returns the byte representation of this bitset

func (BigBitSet) Clear added in v1.9.3 

func (b BigBitSet) Clear()

Clear empties out the bitset

func (BigBitSet) Contains added in v1.9.3 

func (b BigBitSet) Contains(i int) bool

Contains returns true if the [i]'th bit is 1, and false otherwise

func (BigBitSet) Difference added in v1.9.3 

func (b BigBitSet) Difference(other BigBitSet)

Difference removes all the elements in [other] from this set

func (BigBitSet) HammingWeight added in v1.9.3 

func (b BigBitSet) HammingWeight() int

HammingWeight returns the amount of 1's in the bitset

func (BigBitSet) Intersection added in v1.9.3 

func (b BigBitSet) Intersection(other BigBitSet)

Intersection performs the set intersection with another set This sets [b] to include only elements in both [b] and [other]

func (BigBitSet) Len added in v1.9.3 

func (b BigBitSet) Len() int

Len returns the bit length of this bitset

func (BigBitSet) Remove added in v1.9.3 

func (b BigBitSet) Remove(i int)

Remove sets the [i]'th bit to 0

func (BigBitSet) String added in v1.9.3 

func (b BigBitSet) String() string

String returns the hex representation of this bitset

func (BigBitSet) Union added in v1.9.3 

func (b BigBitSet) Union(other BigBitSet)

Union performs the set union with another set. This adds all elements in [other] to [b]

type BitSet64 added in v1.8.6 

type BitSet64 uint64

BitSet64 is a set that can contain uints in the range [0, 64). All functions are O(1). The zero value is the empty set.

func (*BitSet64) Add added in v1.8.6 

func (bs *BitSet64) Add(i uint)

Add [i] to the set of ints

func (*BitSet64) Clear added in v1.8.6 

func (bs *BitSet64) Clear()

Clear removes all elements from this set

func (BitSet64) Contains added in v1.8.6 

func (bs BitSet64) Contains(i uint) bool

Contains returns true if [i] was previously added to this set

func (*BitSet64) Difference added in v1.8.6 

func (bs *BitSet64) Difference(s BitSet64)

Difference removes all the elements in [s] from this set

func (*BitSet64) Intersection added in v1.8.6 

func (bs *BitSet64) Intersection(s BitSet64)

Intersection takes the intersection of [s] with this set

func (BitSet64) Len added in v1.8.6 

func (bs BitSet64) Len() int

Len returns the number of elements in this set

func (*BitSet64) Remove added in v1.8.6 

func (bs *BitSet64) Remove(i uint)

Remove [i] from the set of ints

func (BitSet64) String added in v1.8.6 

func (bs BitSet64) String() string

func (*BitSet64) Union added in v1.8.6 

func (bs *BitSet64) Union(s BitSet64)

Union adds all the elements in [s] to this set

type ID 

type ID [32]byte

ID wraps a 32 byte hash used as an identifier

func FromString 

func FromString(idStr string) (ID, error)

FromString is the inverse of ID.String()

func GenerateTestID added in v0.8.0 

func GenerateTestID() ID

GenerateTestID returns a new ID that should only be used for testing

func ToID 

func ToID(bytes []byte) (ID, error)

ToID attempt to convert a byte slice into an id

func (ID) Bit 

func (id ID) Bit(i uint) int

Bit returns the bit value at the ith index of the byte array. Returns 0 or 1

func (ID) Hex 

func (id ID) Hex() string

Hex returns a hex encoded string of this id.

func (ID) Less added in v1.9.4 

func (id ID) Less(other ID) bool

func (ID) MarshalJSON 

func (id ID) MarshalJSON() ([]byte, error)

func (ID) MarshalText added in v1.5.0 

func (id ID) MarshalText() ([]byte, error)

func (ID) Prefix 

func (id ID) Prefix(prefixes ...uint64) ID

Prefix this id to create a more selective id. This can be used to store multiple values under the same key. For example: prefix1(id) -> confidence prefix2(id) -> vertex This will return a new id and not modify the original id.

func (ID) String 

func (id ID) String() string

func (*ID) UnmarshalJSON 

func (id *ID) UnmarshalJSON(b []byte) error

func (*ID) UnmarshalText added in v1.4.10 

func (id *ID) UnmarshalText(text []byte) error

type NodeID added in v1.7.11 

type NodeID ShortID

func GenerateTestNodeID added in v1.7.11 

func GenerateTestNodeID() NodeID

GenerateTestNodeID returns a new ID that should only be used for testing

func NodeIDFromCert added in v1.7.11 

func NodeIDFromCert(cert *x509.Certificate) NodeID

func NodeIDFromString added in v1.7.11 

func NodeIDFromString(nodeIDStr string) (NodeID, error)

NodeIDFromString is the inverse of NodeID.String()

func ToNodeID added in v1.7.11 

func ToNodeID(bytes []byte) (NodeID, error)

ToNodeID attempt to convert a byte slice into a node id

func (NodeID) Bytes added in v1.7.11 

func (id NodeID) Bytes() []byte

func (NodeID) Less added in v1.9.4 

func (id NodeID) Less(other NodeID) bool

func (NodeID) MarshalJSON added in v1.7.11 

func (id NodeID) MarshalJSON() ([]byte, error)

func (NodeID) MarshalText added in v1.7.11 

func (id NodeID) MarshalText() ([]byte, error)

func (NodeID) String added in v1.7.11 

func (id NodeID) String() string

func (*NodeID) UnmarshalJSON added in v1.7.11 

func (id *NodeID) UnmarshalJSON(b []byte) error

func (*NodeID) UnmarshalText added in v1.7.11 

func (id *NodeID) UnmarshalText(text []byte) error

type NodeIDBag added in v1.7.11 

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

NodeIDBag is a multiset of NodeIDs.

func (*NodeIDBag) Add added in v1.7.11 

func (b *NodeIDBag) Add(ids ...NodeID)

Add increases the number of times each id has been seen by one.

func (*NodeIDBag) AddCount added in v1.7.11 

func (b *NodeIDBag) AddCount(id NodeID, count int)

AddCount increases the nubmer of times the id has been seen by count.

count must be >= 0

func (*NodeIDBag) Count added in v1.7.11 

func (b *NodeIDBag) Count(id NodeID) int

Count returns the number of times the id has been added.

func (*NodeIDBag) Equals added in v1.7.11 

func (b *NodeIDBag) Equals(oIDs NodeIDBag) bool

Equals returns true if the bags contain the same elements

func (*NodeIDBag) Len added in v1.7.11 

func (b *NodeIDBag) Len() int

Len returns the number of times an id has been added.

func (*NodeIDBag) List added in v1.7.11 

func (b *NodeIDBag) List() []NodeID

List returns a list of all IDs that have been added, without duplicates. e.g. a bag with {ID1, ID1, ID2} returns ids.ShortID[]{ID1, ID2}

func (*NodeIDBag) PrefixedString added in v1.7.11 

func (b *NodeIDBag) PrefixedString(prefix string) string

func (*NodeIDBag) Remove added in v1.7.11 

func (b *NodeIDBag) Remove(id NodeID)

Remove sets the count of the provided ID to zero.

func (*NodeIDBag) String added in v1.7.11 

func (b *NodeIDBag) String() string

type RequestID added in v1.9.1 

type RequestID struct {
	// The node this request came from
	NodeID NodeID
	// The chain this request came from
	SourceChainID ID
	// The chain the expected response should come from
	DestinationChainID ID
	// The unique identifier for this request
	RequestID uint32
	// The message opcode
	Op byte
}

RequestID is a unique identifier for an in-flight request pending a response.

type ShortID 

type ShortID [20]byte

ShortID wraps a 20 byte hash as an identifier

func GenerateTestShortID added in v0.8.0 

func GenerateTestShortID() ShortID

GenerateTestShortID returns a new ID that should only be used for testing

func ShortFromPrefixedString added in v0.8.0 

func ShortFromPrefixedString(idStr, prefix string) (ShortID, error)

ShortFromPrefixedString returns a ShortID assuming the cb58 format is prefixed

func ShortFromString 

func ShortFromString(idStr string) (ShortID, error)

ShortFromString is the inverse of ShortID.String()

func ToShortID 

func ToShortID(bytes []byte) (ShortID, error)

ToShortID attempt to convert a byte slice into an id

func (ShortID) Bytes 

func (id ShortID) Bytes() []byte

Bytes returns the 20 byte hash as a slice. It is assumed this slice is not modified.

func (ShortID) Hex 

func (id ShortID) Hex() string

Hex returns a hex encoded string of this id.

func (ShortID) Less added in v1.9.4 

func (id ShortID) Less(other ShortID) bool

func (ShortID) MarshalJSON 

func (id ShortID) MarshalJSON() ([]byte, error)

func (ShortID) MarshalText added in v1.7.11 

func (id ShortID) MarshalText() ([]byte, error)

func (ShortID) PrefixedString added in v0.8.0 

func (id ShortID) PrefixedString(prefix string) string

PrefixedString returns the String representation with a prefix added

func (ShortID) String 

func (id ShortID) String() string

func (*ShortID) UnmarshalJSON 

func (id *ShortID) UnmarshalJSON(b []byte) error

func (*ShortID) UnmarshalText added in v1.7.11 

func (id *ShortID) UnmarshalText(text []byte) error

type SliceStringer added in v1.7.17 

type SliceStringer []ID

func (SliceStringer) String added in v1.7.17 

func (s SliceStringer) String() string

type UniqueBag 

type UniqueBag map[ID]BitSet64

func (*UniqueBag) Add 

func (b *UniqueBag) Add(setID uint, idSet ...ID)

func (*UniqueBag) Bag 

func (b *UniqueBag) Bag(alpha int) Bag

func (*UniqueBag) Clear added in v1.4.7 

func (b *UniqueBag) Clear()

func (*UniqueBag) Difference 

func (b *UniqueBag) Difference(diff *UniqueBag)

func (*UniqueBag) DifferenceSet 

func (b *UniqueBag) DifferenceSet(id ID, set BitSet64)

func (*UniqueBag) GetSet 

func (b *UniqueBag) GetSet(id ID) BitSet64

func (*UniqueBag) List 

func (b *UniqueBag) List() []ID

func (*UniqueBag) PrefixedString added in v1.7.3 

func (b *UniqueBag) PrefixedString(prefix string) string

func (*UniqueBag) RemoveSet added in v0.8.0 

func (b *UniqueBag) RemoveSet(id ID)

func (*UniqueBag) String 

func (b *UniqueBag) String() string

func (*UniqueBag) UnionSet 

func (b *UniqueBag) UnionSet(id ID, set BitSet64)

Source Files

View all Source files

Directories

Path Synopsis

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.