amt

package module
v0.0.0-...-ec70b44 Latest Latest
Warning

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

 Go to latest Published: Jul 27, 2022 License: MIT Imports: 4 Imported by: 0

README

package amt

Package amt implements the Hash Array Mapped Trie (HAMT) in Go (1.18+ generics).

See "Ideal Hash Trees" (Phil Bagwell, 2001) for an overview of the implementation, advantages, and disadvantages of HAMTs.

The AMT implementation has a natural cardinality of 16 for the root trie and all sub-tries; each AMT level is indexed by 4 hash bits. The depth of a map or set will be on the order of log16(N).

This package uses unsafe pointers/pointer-arithmetic extensively, so it is inherently unsafe and not guaranteed to work today or tomorrow. Unsafe pointers enable a compact memory layout with fewer allocations, and effectively reduce the depth of a map or set by reducing the number of pointers dereferenced along the path to a key or value. No attention is paid to 32-bit architectures since it's now the year 2000, but compatibility may still be there.

An alternative approach, using an interface type to represent either a key-value pair or entry slice (sub-trie), has a few drawbacks. Interface values are the size of 2 pointers (versus 1 when using unsafe pointers), which would increase the memory overhead for key-value/sub-trie entries by 50% (e.g. 24 bytes versus 16 bytes on 64-bit architectures). If the interface value is assigned a slice of entries (sub-trie), a new allocation (the size of 3 pointers) is required for the slice-header before it can be wrapped into the interface value. Accessing an entry slice (sub-trie) through an interface value requires (1) dereferencing the interface's data pointer to get to the slice-header (among other things), then (2) dereferencing the slice-header's data pointer to access an entry in the slice. Unsafe pointers eliminate the extra allocation and overhead of (1), allowing entries to point directly to either a key-value struct or an array of entries. Generics enable a type-safe implementation, where the key-value type of a map or set is fixed after instantiation.

import "github.com/wdamron/amt"

More Info

The memory layouts of Go interfaces and slices are detailed in the following articles:

Documentation

Overview

Package amt implements the Hash Array Mapped Trie (HAMT) in Go (1.18+ generics).

See "Ideal Hash Trees" (Phil Bagwell, 2001) for an overview of the implementation, advantages, and disadvantages of HAMTs.

The AMT implementation has a natural cardinality of 16 for the root trie and all sub-tries; each AMT level is indexed by 4 hash bits. The depth of a map or set will be on the order of log16(N).

This package uses unsafe pointers/pointer-arithmetic extensively, so it is inherently unsafe and not guaranteed to work today or tomorrow. Unsafe pointers enable a compact memory layout with fewer allocations, and effectively reduce the depth of a map or set by reducing the number of pointers dereferenced along the path to a key or value. No attention is paid to 32-bit architectures since it's now the year 2000, but compatibility may still be there.

An alternative approach, using an interface type to represent either a key-value pair or entry slice (sub-trie), has a few drawbacks. Interface values are the size of 2 pointers (versus 1 when using unsafe pointers), which would increase the memory overhead for key-value/sub-trie entries by 50% (e.g. 24 bytes versus 16 bytes on 64-bit architectures). If the interface value is assigned a slice of entries (sub-trie), a new allocation (the size of 3 pointers) is required for the slice-header before it can be wrapped into the interface value. Accessing an entry slice (sub-trie) through an interface value requires (1) dereferencing the interface's data pointer to get to the slice-header (among other things), then (2) dereferencing the slice-header's data pointer to access an entry in the slice. Unsafe pointers eliminate the extra allocation and overhead of (1), allowing entries to point directly to either a key-value struct or an array of entries. Generics enable a type-safe implementation, where the key-value type of a map or set is fixed after instantiation.

The memory layouts of Go interfaces and slices are detailed in the following articles: 

Go Data Structures: Interfaces (Russ Cox): https://research.swtch.com/interfaces
Go Slices: usage and internals (Andrew Gerrand): https://go.dev/blog/slices-intro
Go internals: invariance and memory layout of slices (Eli Bendersky): https://eli.thegreenplace.net/2021/go-internals-invariance-and-memory-layout-of-slices/

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func HashBytes 

func HashBytes(key []byte, seed maphash.Seed, iter uint) uint64

HashBytes hashes key 1 or more times. The iter count indicates the number of times the key should be rehashed. For the initial hash the iter count will be zero. HashBytes may be used to implement the Hash method for the key type of a generic Map[K, V].

Types

type ArrKey 

type ArrKey interface {
	comparable
	KeyBytes() [64]byte
}

ArrKey is a key with a method which converts the key to a fixed-size array for hashing, used as the key type of an ArrMap[K, V]. For byte-array keys with length up to 64 bytes, ArrMap[K, V] may be suitable.

type ArrMap 

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

ArrMap maps byte arrays to values. Methods on a map value will panic if the map is not initialized. A map value is safe to copy.

func NewArrMap 

func NewArrMap[K ArrKey, V any]() ArrMap[K, V]

NewArrMap returns an initialized map. The map value is safe to copy.

func (ArrMap[K, V]) All 

func (m ArrMap[K, V]) All(do func(K, *V) bool)

All ranges over values in m, applying the do callback to each value until the callback returns false or all values have been visited. The iteration order is not randomized for each call.

func (ArrMap[K, V]) Del 

func (m ArrMap[K, V]) Del(key K)

Del deletes the value for key.

func (ArrMap[K, V]) Dep 

func (m ArrMap[K, V]) Dep() float64

Dep returns the average (mean) depth of all values in m. If m is not initialized, Dep returns 0.

func (ArrMap[K, V]) Get 

func (m ArrMap[K, V]) Get(key K) (value V, ok bool)

Get returns the value for key, or a zero value and false if the key is missing.

func (ArrMap[K, V]) Len 

func (m ArrMap[K, V]) Len() uint

Len returns the number of values in m. If m is not initialized, Len returns 0.

func (ArrMap[K, V]) Mod 

func (m ArrMap[K, V]) Mod(key K, mod func(*V, bool))

Mod modifies the value for key using the mod callback. The mod callback receives a pointer to the existing or new value for key, and true if the key existed.

func (ArrMap[K, V]) Nil 

func (m ArrMap[K, V]) Nil() bool

Nil returns true if m is not initialized.

func (ArrMap[K, V]) Ptr 

func (m ArrMap[K, V]) Ptr(key K) *V

Ptr returns a pointer to the value for key, or nil if the key is missing. The value may be updated through the returned pointer.

func (ArrMap[K, V]) Set 

func (m ArrMap[K, V]) Set(key K, value V)

Set adds or updates the value for key.

func (ArrMap[K, V]) Val 

func (m ArrMap[K, V]) Val(key K) (value V)

Val returns the value for key, or a zero value if the key is missing or m is not initialized.

type ArrSet 

type ArrSet[K ArrKey] struct {
	// contains filtered or unexported fields
}

ArrSet contains a set of byte arrays. Methods on a set value will panic if the set is not initialized. A set value is safe to copy.

func NewArrSet 

func NewArrSet[K ArrKey]() ArrSet[K]

NewArrSet returns an initialized set. The set value is safe to copy.

func (ArrSet[K]) Add 

func (s ArrSet[K]) Add(key K)

Add adds key to s.

func (ArrSet[K]) All 

func (s ArrSet[K]) All(do func(K) bool)

All ranges over keys in s, applying the do callback to each key until the callback returns false or all keys have been visited. The iteration order is not randomized for each call.

func (ArrSet[K]) Del 

func (s ArrSet[K]) Del(key K)

Del deletes key from s.

func (ArrSet[K]) Dep 

func (s ArrSet[K]) Dep() float64

Dep returns the average (mean) depth of all keys in s. If s is not initialized, Dep returns 0.

func (ArrSet[K]) Has 

func (s ArrSet[K]) Has(key K) bool

Has returns true if s contains key.

func (ArrSet[K]) Len 

func (s ArrSet[K]) Len() uint

Len returns the number of keys in s. If s is not initialized, Len returns 0.

func (ArrSet[K]) Nil 

func (s ArrSet[K]) Nil() bool

Nil returns true if s is not initialized.

type Bytes 

type Bytes []byte

Bytes may be used as the key type of a generic Map[Bytes, V].

func (Bytes) Equal 

func (k Bytes) Equal(k2 Bytes) bool

func (Bytes) Hash 

func (k Bytes) Hash(seed maphash.Seed, iter uint) uint64

type BytesMap 

type BytesMap[V any] struct {
	// contains filtered or unexported fields
}

BytesMap maps byte slices to values. Methods on a map value will panic if the map is not initialized. Key slices will be retained in a map, and must not be modified after they are added. A map value is safe to copy.

func NewBytesMap 

func NewBytesMap[V any]() BytesMap[V]

NewBytesMap returns an initialized map. The map value is safe to copy.

func (BytesMap[V]) All 

func (m BytesMap[V]) All(do func([]byte, *V) bool)

All ranges over values in m, applying the do callback to each value until the callback returns false or all values have been visited. The iteration order is not randomized for each call.

func (BytesMap[V]) Del 

func (m BytesMap[V]) Del(key []byte)

Del deletes the value for key.

func (BytesMap[V]) Dep 

func (m BytesMap[V]) Dep() float64

Dep returns the average (mean) depth of all values in m. If m is not initialized, Dep returns 0.

func (BytesMap[V]) Get 

func (m BytesMap[V]) Get(key []byte) (value V, ok bool)

Get returns the value for key, or a zero value and false if the key is missing.

func (BytesMap[V]) Len 

func (m BytesMap[V]) Len() uint

Len returns the number of values in m. If m is not initialized, Len returns 0.

func (BytesMap[V]) Mod 

func (m BytesMap[V]) Mod(key []byte, mod func(*V, bool))

Mod modifies the value for key using the mod callback. The mod callback receives a pointer to the existing or new value for key, and true if the key existed. The key slice may be retained in m, and must not be modified after the key is added.

func (BytesMap[V]) Nil 

func (m BytesMap[V]) Nil() bool

Nil returns true if m is not initialized.

func (BytesMap[V]) Ptr 

func (m BytesMap[V]) Ptr(key []byte) *V

Ptr returns a pointer to the value for key, or nil if the key is missing. The value may be updated through the returned pointer.

func (BytesMap[V]) Set 

func (m BytesMap[V]) Set(key []byte, value V)

Set adds or updates the value for key. The key slice will be retained in m, and must not be modified after the key is added.

func (BytesMap[V]) Val 

func (m BytesMap[V]) Val(key []byte) (value V)

Val returns the value for key, or a zero value if the key is missing or m is not initialized.

type BytesSet 

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

BytesSet contains a set of byte slices. Methods on a set value will panic if the set is not initialized. Key slices will be retained in a set, and must not be modified after they are added. A set value is safe to copy.

func NewBytesSet 

func NewBytesSet() BytesSet

NewBytesSet returns an initialized set. The set value is safe to copy.

func (BytesSet) Add 

func (s BytesSet) Add(key []byte)

Add adds key to s. The key slice will be retained in s, and must not be modified after the key is added.

func (BytesSet) All 

func (s BytesSet) All(do func([]byte) bool)

All ranges over keys in s, applying the do callback to each key until the callback returns false or all keys have been visited. The iteration order is not randomized for each call.

func (BytesSet) Del 

func (s BytesSet) Del(key []byte)

Del deletes key from s.

func (BytesSet) Dep 

func (s BytesSet) Dep() float64

Dep returns the average (mean) depth of all keys in s. If s is not initialized, Dep returns 0.

func (BytesSet) Has 

func (s BytesSet) Has(key []byte) bool

Has returns true if s contains key.

func (BytesSet) Len 

func (s BytesSet) Len() uint

Len returns the number of keys in s. If s is not initialized, Len returns 0.

func (BytesSet) Nil 

func (s BytesSet) Nil() bool

Nil returns true if s is not initialized.

type Int 

type Int int

Int may be used as the key type of a generic Map[Int, V].

func (Int) Hash 

func (i Int) Hash(seed maphash.Seed, iter uint) uint64

type IntKey 

type IntKey = int64

IntKey is an alias for int64, the key type for IntMap[V].

type IntMap 

type IntMap[V any] struct {
	// contains filtered or unexported fields
}

IntMap maps integers to values. Methods on a map value will panic if the map is not initialized. A map value is safe to copy.

func NewIntMap 

func NewIntMap[V any]() IntMap[V]

NewIntMap returns an initialized map. The map value is safe to copy.

func (IntMap[V]) All 

func (m IntMap[V]) All(do func(IntKey, *V) bool)

All ranges over values in m, applying the do callback to each value until the callback returns false or all values have been visited. The iteration order is not randomized for each call.

func (IntMap[V]) Del 

func (m IntMap[V]) Del(key IntKey)

Del deletes the value for key.

func (IntMap[V]) Dep 

func (m IntMap[V]) Dep() float64

Dep returns the average (mean) depth of all values in m. If m is not initialized, Dep returns 0.

func (IntMap[V]) Get 

func (m IntMap[V]) Get(key IntKey) (value V, ok bool)

Get returns the value for key, or a zero value and false if the key is missing.

func (IntMap[V]) Len 

func (m IntMap[V]) Len() uint

Len returns the number of values in m. If m is not initialized, Len returns 0.

func (IntMap[V]) Mod 

func (m IntMap[V]) Mod(key IntKey, mod func(*V, bool))

Mod modifies the value for key using the mod callback. The mod callback receives a pointer to the existing or new value for key, and true if the key existed.

func (IntMap[V]) Nil 

func (m IntMap[V]) Nil() bool

Nil returns true if m is not initialized.

func (IntMap[V]) Ptr 

func (m IntMap[V]) Ptr(key IntKey) *V

Ptr returns a pointer to the value for key, or nil if the key is missing. The value may be updated through the returned pointer.

func (IntMap[V]) Set 

func (m IntMap[V]) Set(key IntKey, value V)

Set adds or updates the value for key.

func (IntMap[V]) Val 

func (m IntMap[V]) Val(key IntKey) (value V)

Val returns the value for key, or a zero value if the key is missing or m is not initialized.

type IntSet 

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

IntSet contains a set of integers. Methods on a set value will panic if the set is not initialized. A set value is safe to copy.

func NewIntSet 

func NewIntSet() IntSet

NewIntSet returns an initialized set. The set value is safe to copy.

func (IntSet) Add 

func (s IntSet) Add(key IntKey)

Add adds key to s.

func (IntSet) All 

func (s IntSet) All(do func(IntKey) bool)

All ranges over keys in s, applying the do callback to each key until the callback returns false or all keys have been visited. The iteration order is not randomized for each call.

func (IntSet) Del 

func (s IntSet) Del(key IntKey)

Del deletes key from s.

func (IntSet) Dep 

func (s IntSet) Dep() float64

Dep returns the average (mean) depth of all keys in s. If s is not initialized, Dep returns 0.

func (IntSet) Has 

func (s IntSet) Has(key IntKey) bool

Has returns true if s contains key.

func (IntSet) Len 

func (s IntSet) Len() uint

Len returns the number of keys in s. If s is not initialized, Len returns 0.

func (IntSet) Nil 

func (s IntSet) Nil() bool

Nil returns true if s is not initialized.

type Key 

type Key[K any] interface {
	// Equal must return true if the key is equal to a comparison key.
	Equal(K) bool
	// Hash must hash the key 1 or more times. The iter count indicates the number of times the key
	// must be rehashed. For the initial hash the iter count will be zero.
	Hash(seed maphash.Seed, iter uint) uint64
}

Key may be used as the key type of a generic Map[K, V].

type Map 

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

Map maps hashable keys to values. Methods on a map value will panic if the map is not initialized. A map value is safe to copy.

func NewMap 

func NewMap[K Key[K], V any]() Map[K, V]

NewMap returns an initialized map. The map value is safe to copy.

func (Map[K, V]) All 

func (m Map[K, V]) All(do func(K, *V) bool)

All ranges over values in m, applying the do callback to each value until the callback returns false or all values have been visited. The iteration order is not randomized for each call.

func (Map[K, V]) Del 

func (m Map[K, V]) Del(key K)

Del deletes the value for key.

func (Map[K, V]) Dep 

func (m Map[K, V]) Dep() float64

Dep returns the average (mean) depth of all values in m. If m is not initialized, Dep returns 0.

func (Map[K, V]) Get 

func (m Map[K, V]) Get(key K) (value V, ok bool)

Get returns the value for key, or a zero value and false if the key is missing.

func (Map[K, V]) Len 

func (m Map[K, V]) Len() uint

Len returns the number of values in m. If m is not initialized, Len returns 0.

func (Map[K, V]) Mod 

func (m Map[K, V]) Mod(key K, mod func(*V, bool))

Mod modifies the value for key using the mod callback. The mod callback receives a pointer to the existing or new value for key, and true if the key existed.

func (Map[K, V]) Nil 

func (m Map[K, V]) Nil() bool

Nil returns true if m is not initialized.

func (Map[K, V]) Ptr 

func (m Map[K, V]) Ptr(key K) *V

Ptr returns a pointer to the value for key, or nil if the key is missing. The value may be updated through the returned pointer.

func (Map[K, V]) Set 

func (m Map[K, V]) Set(key K, value V)

Set adds or updates the value for key.

func (Map[K, V]) Val 

func (m Map[K, V]) Val(key K) (value V)

Val returns the value for key, or a zero value if the key is missing or m is not initialized.

type Set 

type Set[K Key[K]] struct {
	// contains filtered or unexported fields
}

Set contains a set of keys. Methods on a set value will panic if the set is not initialized. A set value is safe to copy.

func NewSet 

func NewSet[K Key[K]]() Set[K]

NewSet returns an initialized set. The set value is safe to copy.

func (Set[K]) Add 

func (s Set[K]) Add(key K)

Add adds key to s.

func (Set[K]) All 

func (s Set[K]) All(do func(K) bool)

All ranges over keys in s, applying the do callback to each key until the callback returns false or all keys have been visited. The iteration order is not randomized for each call.

func (Set[K]) Del 

func (s Set[K]) Del(key K)

Del deletes key from s.

func (Set[K]) Dep 

func (s Set[K]) Dep() float64

Dep returns the average (mean) depth of all keys in s. If s is not initialized, Dep returns 0.

func (Set[K]) Has 

func (s Set[K]) Has(key K) bool

Has returns true if s contains key.

func (Set[K]) Len 

func (s Set[K]) Len() uint

Len returns the number of keys in s. If s is not initialized, Len returns 0.

func (Set[K]) Nil 

func (s Set[K]) Nil() bool

Nil returns true if s is not initialized.

type String 

type String string

String may be used as the key type of a generic Map[String, V].

func (String) Equal 

func (k String) Equal(k2 String) bool

func (String) Hash 

func (k String) Hash(seed maphash.Seed, iter uint) uint64

type StringMap 

type StringMap[V any] struct {
	// contains filtered or unexported fields
}

StringMap maps strings to values. Methods on a map value will panic if the map is not initialized. A map value is safe to copy.

func NewStringMap 

func NewStringMap[V any]() StringMap[V]

NewStringMap returns an initialized map. The map value is safe to copy.

func (StringMap[V]) All 

func (m StringMap[V]) All(do func(string, *V) bool)

All ranges over values in m, applying the do callback to each value until the callback returns false or all values have been visited. The iteration order is not randomized for each call.

func (StringMap[V]) Del 

func (m StringMap[V]) Del(key string)

Del deletes the value for key.

func (StringMap[V]) Dep 

func (m StringMap[V]) Dep() float64

Dep returns the average (mean) depth of all values in m. If m is not initialized, Dep returns 0.

func (StringMap[V]) Get 

func (m StringMap[V]) Get(key string) (value V, ok bool)

Get returns the value for key, or a zero value and false if the key is missing.

func (StringMap[V]) Len 

func (m StringMap[V]) Len() uint

Len returns the number of values in m. If m is not initialized, Len returns 0.

func (StringMap[V]) Mod 

func (m StringMap[V]) Mod(key string, mod func(*V, bool))

Mod modifies the value for key using the mod callback. The mod callback receives a pointer to the existing or new value for key, and true if the key existed.

func (StringMap[V]) Nil 

func (m StringMap[V]) Nil() bool

Nil returns true if m is not initialized.

func (StringMap[V]) Ptr 

func (m StringMap[V]) Ptr(key string) *V

Ptr returns a pointer to the value for key, or nil if the key is missing. The value may be updated through the returned pointer.

func (StringMap[V]) Set 

func (m StringMap[V]) Set(key string, value V)

Set adds or updates the value for key.

func (StringMap[V]) Val 

func (m StringMap[V]) Val(key string) (value V)

Val returns the value for key, or a zero value if the key is missing or m is not initialized.

type StringSet 

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

StringSet contains a set of strings. Methods on a set value will panic if the set is not initialized. A set value is safe to copy.

func NewStringSet 

func NewStringSet() StringSet

NewStringSet returns an initialized set. The set value is safe to copy.

func (StringSet) Add 

func (s StringSet) Add(key string)

Add adds key to s.

func (StringSet) All 

func (s StringSet) All(do func(string) bool)

All ranges over keys in s, applying the do callback to each key until the callback returns false or all keys have been visited. The iteration order is not randomized for each call.

func (StringSet) Del 

func (s StringSet) Del(key string)

Del deletes key from s.

func (StringSet) Dep 

func (s StringSet) Dep() float64

Dep returns the average (mean) depth of all keys in s. If s is not initialized, Dep returns 0.

func (StringSet) Has 

func (s StringSet) Has(key string) bool

Has returns true if s contains key.

func (StringSet) Len 

func (s StringSet) Len() uint

Len returns the number of keys in s. If s is not initialized, Len returns 0.

func (StringSet) Nil 

func (s StringSet) Nil() bool

Nil returns true if s is not initialized.

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.