hamt

Documentation

Index

• Constants
• Variables
• type BitmapNode
  • func (h *BitmapNode[T]) BitPosNum(int) uint64
  • func (h *BitmapNode[T]) Index(bitPos uint64) int
  • func (h *BitmapNode[T]) Type() int
• type Entry
• type Hamt
  • func New[T any](opts ...Option) *Hamt[T]
  • func (h *Hamt[T]) Erase(key Key) bool
  • func (h *Hamt[T]) Get(key Key) (T, error)
  • func (h *Hamt[T]) Insert(key Key, value T)
  • func (h *Hamt[T]) Keys() []Key
  • func (h *Hamt[T]) StringKeys() []string
  • func (h *Hamt[T]) Traversal(visitor visitor.KvVisitor[Key, T])
• type Key
• type KvNode
  • func (h *KvNode[T]) BitPosNum(depth int) uint64
  • func (h *KvNode[T]) Type() int
• type KvPair
• type Option
  • func WithGoroutineSafe() Option
• type Options

Constants

const (
	BITMAP_NODE = 0
	KV_NODE     = 1
	Fanout      = 6 //each bitmap node has 6 bits, so the max depth of tree is 64/6 = 10.666 = 11
	Mask        = (1 << Fanout) - 1
)

Some constants

Variables

var ErrorNotFound = errors.New("not found")

Types

type BitmapNode

type BitmapNode[T any] struct {
	// contains filtered or unexported fields
}

BitmapNode defines Hamt's bitmap node

func (*BitmapNode[T]) BitPosNum

func (h *BitmapNode[T]) BitPosNum(int) uint64

BitPosNum returns the number from a bit position

func (*BitmapNode[T]) Index

func (h *BitmapNode[T]) Index(bitPos uint64) int

Index returns the index of a bitPos int bitmap

func (*BitmapNode[T]) Type

func (h *BitmapNode[T]) Type() int

Type returns the node type

type Entry

type Entry interface {
	// Type returns the node type
	Type() int

	// BitPosNum returns number from a bit position
	BitPosNum(depth int) uint64
}

Entry is a tree node interface

type Hamt

type Hamt[T any] struct {
	// contains filtered or unexported fields
}

Hamt is an implementation of hash-array-mapped-trie

func New

func New[T any](opts ...Option) *Hamt[T]

New creates a Hamt(hash array mapped trie) instance

func (*Hamt[T]) Erase

func (h *Hamt[T]) Erase(key Key) bool

Erase erases the key-value pair in hamt, and returns true if succeed.

func (*Hamt[T]) Get

func (h *Hamt[T]) Get(key Key) (T, error)

Get returns the value by the passed key if the key is in the hamt, otherwise returns nil

func (*Hamt[T]) Insert

func (h *Hamt[T]) Insert(key Key, value T)

Insert inserts a key-value pair into the hamt

func (*Hamt[T]) Keys

func (h *Hamt[T]) Keys() []Key

Keys returns keys in Hamt

func (*Hamt[T]) StringKeys

func (h *Hamt[T]) StringKeys() []string

StringKeys returns keys in Hamt

func (*Hamt[T]) Traversal

func (h *Hamt[T]) Traversal(visitor visitor.KvVisitor[Key, T])

Traversal traversals elements in Hamt, it will not stop until to the end or the visitor returns false

type Key

type Key []byte

Key is a redefinition of []byte

type KvNode

type KvNode[T any] struct {
	// contains filtered or unexported fields
}

KvNode is Hamt's key-value node

func (*KvNode[T]) BitPosNum

func (h *KvNode[T]) BitPosNum(depth int) uint64

BitPosNum returns the bit position

func (*KvNode[T]) Type

func (h *KvNode[T]) Type() int

Type returns the node type

type KvPair

type KvPair[T any] struct {
	// contains filtered or unexported fields
}

KvPair is a list node with actually value

type Option

type Option func(option *Options)

Option is a function type used to set Options

func WithGoroutineSafe

func WithGoroutineSafe() Option

WithGoroutineSafe is used to config a Hamt with goroutine-safe

type Options

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

Options holds Hamt's options