hamt

Documentation

Overview

Package hamt is the gopy port of cpython/Python/hamt.c. It is the immutable persistent mapping that backs Context (see contextvar/).

The tree branches on 5 bits of a 32-bit hash per level so the maximum non-collision depth is 7. A level-7 collision node lifts the total maximum depth to 8 (MaxTreeDepth).

CPython: Python/hamt.c

Index

• Constants
• Variables
• type Hamt
  • func New() *Hamt
  • func (h *Hamt) Assoc(key, val objects.Object) (*Hamt, error)
  • func (h *Hamt) Eq(other *Hamt) (bool, error)
  • func (h *Hamt) Find(key objects.Object) (objects.Object, bool, error)
  • func (h *Hamt) Iter() *Iter
  • func (h *Hamt) Len() int
  • func (h *Hamt) Without(key objects.Object) (*Hamt, bool, error)
• type Iter
  • func (it *Iter) Next() (key, val objects.Object, ok bool, err error)

Constants

const MaxTreeDepth = 8

MaxTreeDepth caps an iterator's stack. CPython exposes the same constant as _Py_HAMT_MAX_TREE_DEPTH.

CPython: Include/internal/pycore_hamt.h:21 _Py_HAMT_MAX_TREE_DEPTH

Variables

var (
	HamtKeysType   = objects.NewType("hamt_keys", []*objects.Type{objects.ObjectType()})
	HamtValuesType = objects.NewType("hamt_values", []*objects.Type{objects.ObjectType()})
	HamtItemsType  = objects.NewType("hamt_items", []*objects.Type{objects.ObjectType()})
)

HamtKeysType, HamtValuesType, HamtItemsType wrap the three iterator shapes CPython exposes through _PyHamt_NewIterKeys etc. They are runtime-private so we register only the bare type name.

CPython: Python/hamt.c:2680 _PyHamtKeys_Type / 2723 _PyHamtValues_Type / 2766 _PyHamtItems_Type

var HamtType = objects.NewType("hamt", []*objects.Type{objects.ObjectType()})

HamtType is the runtime type for Hamt objects. The runtime never exposes Hamt to Python directly; the type exists so Hamt satisfies objects.Object.

CPython: Python/hamt.c:2814 _PyHamt_Type

Types

type Hamt

type Hamt struct {
	objects.Header
	// contains filtered or unexported fields
}

Hamt is the immutable persistent mapping. The zero value is invalid; use New() to construct an empty mapping.

CPython: Include/internal/pycore_hamt.h PyHamtObject

func New

func New() *Hamt

New returns a fresh empty Hamt. Each call returns a distinct header, but they all share the singleton empty bitmap as their root so the allocation is a single struct.

CPython: Python/hamt.c:2390 hamt_alloc / Python/hamt.c:_PyHamt_New

func (*Hamt) Assoc

func (h *Hamt) Assoc(key, val objects.Object) (*Hamt, error)

Assoc returns a new Hamt that has key bound to val. If key already maps to val (identity-equal value object) the receiver is returned unchanged.

CPython: Python/hamt.c:2209 _PyHamt_Assoc

func (*Hamt) Eq

func (h *Hamt) Eq(other *Hamt) (bool, error)

Eq reports whether two Hamts hold the same key/value pairs. It short-circuits on identity and on size mismatch, then walks the receiver in tree order and looks each key up in `other`.

CPython: Python/hamt.c:2320 _PyHamt_Eq

func (*Hamt) Find

func (h *Hamt) Find(key objects.Object) (objects.Object, bool, error)

Find returns the value bound to key. ok==false reports a missing key without an error; err is non-nil only on hashing or comparison failures.

CPython: Python/hamt.c:2303 _PyHamt_Find

func (*Hamt) Iter

func (h *Hamt) Iter() *Iter

Iter returns a new iterator positioned at the start of the tree.

CPython: Python/hamt.c:2066 hamt_iterator_init

func (*Hamt) Len

func (h *Hamt) Len() int

Len returns the number of key/value pairs.

CPython: Python/hamt.c:2384 _PyHamt_Len

func (*Hamt) Without

func (h *Hamt) Without(key objects.Object) (*Hamt, bool, error)

Without returns a new Hamt with key removed and ok==true. If the key is absent, the receiver is returned unchanged with ok==false.

CPython: Python/hamt.c:2246 _PyHamt_Without

type Iter

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

Iter walks a Hamt in tree order. It is safe to call Iter multiple times on the same Hamt; each call returns a fresh iterator.

func (*Iter) Next

func (it *Iter) Next() (key, val objects.Object, ok bool, err error)

Next yields the next (key, val) pair. ok==false signals I_END. err is non-nil only on hashing/comparison failure during iteration (none today, but plumbed for parity with CPython).

CPython: Python/hamt.c:2182 hamt_iterator_next