hashtable

Documentation

Overview

Package hashtable is the gopy port of cpython/Python/hashtable.c. It implements _Py_hashtable_t, the generic open-chained hash table the runtime uses for tracemalloc, the type method cache, the .pyc rdep tracker, and similar internal indexes. It is *not* the Python dict.

The layout matches CPython byte-for-byte: a power-of-two bucket array of singly-linked entry chains, with rehash-on-load thresholds at HASHTABLE_HIGH (50%) and HASHTABLE_LOW (10%).

CPython: Python/hashtable.c

Index

• func CompareDirect(a, b any) bool
• func HashPointer(p unsafe.Pointer) uint64
• type CompareFunc
• type DestroyFunc
• type Entry
• type HashFunc
• type Table
  • func New(hash HashFunc, cmp CompareFunc) *Table
  • func NewFull(hash HashFunc, cmp CompareFunc, keyDtor, valDtor DestroyFunc) *Table
  • func (t *Table) Clear()
  • func (t *Table) Destroy()
  • func (t *Table) Foreach(fn func(*Entry) error) error
  • func (t *Table) Get(key any) (any, bool)
  • func (t *Table) Len() int
  • func (t *Table) Set(key, val any)
  • func (t *Table) Size() int
  • func (t *Table) Steal(key any) (any, bool)

Functions

func CompareDirect

func CompareDirect(a, b any) bool

CompareDirect mirrors _Py_hashtable_compare_direct: pointer equality. Used with HashPointer for tables keyed on raw addresses.

CPython: Python/hashtable.c:100 _Py_hashtable_compare_direct

func HashPointer

func HashPointer(p unsafe.Pointer) uint64

HashPointer mirrors _Py_hashtable_hash_ptr: cast the address to a uintptr and rotate so low alignment bits do not crowd the bucket.

CPython: Python/hashtable.c:93 _Py_hashtable_hash_ptr

Types

type CompareFunc

type CompareFunc func(a, b any) bool

CompareFunc returns true when a and b are the same key. Mirrors _Py_hashtable_compare_func (which returns int).

CPython: Include/internal/pycore_hashtable.h:46 _Py_hashtable_compare_func

type DestroyFunc

type DestroyFunc func(value any)

DestroyFunc runs at entry teardown. Mirrors _Py_hashtable_destroy_func.

CPython: Include/internal/pycore_hashtable.h:47 _Py_hashtable_destroy_func

type Entry

type Entry struct {
	Key     any
	Value   any
	KeyHash uint64
	// contains filtered or unexported fields
}

Entry is one (key, value) record in the table. next links to the rest of the bucket chain. CPython embeds an _Py_slist_item_t at offset 0; we use a plain pointer because Go's GC tracks it.

CPython: Include/internal/pycore_hashtable.h:28 _Py_hashtable_entry_t

type HashFunc

type HashFunc func(key any) uint64

HashFunc returns the 64-bit hash of key. Mirrors _Py_hashtable_hash_func.

CPython: Include/internal/pycore_hashtable.h:45 _Py_hashtable_hash_func

type Table

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

Table is the runtime hash table. nentries and nbuckets are kept in step with the buckets slice. The function pointers cannot be nil after construction; New / NewFull install defaults if the caller passes nil for the optional ones.

CPython: Include/internal/pycore_hashtable.h:60 _Py_hashtable_t

func New

func New(hash HashFunc, cmp CompareFunc) *Table

New builds a table with default destructors and the default allocator. Mirrors _Py_hashtable_new.

CPython: Python/hashtable.c:370 _Py_hashtable_new

func NewFull

func NewFull(hash HashFunc, cmp CompareFunc, keyDtor, valDtor DestroyFunc) *Table

NewFull builds a table with optional key / value destructors. Pass nil for either dtor to skip teardown work for that side. Mirrors _Py_hashtable_new_full; the allocator argument is dropped because Go's runtime owns memory.

CPython: Python/hashtable.c:323 _Py_hashtable_new_full

func (*Table) Clear

func (t *Table) Clear()

Clear removes every entry, invoking the destructors, and shrinks the bucket array back toward the minimum.

CPython: Python/hashtable.c:392 _Py_hashtable_clear

func (*Table) Destroy

func (t *Table) Destroy()

Destroy tears down every entry (running destructors) and drops the bucket array. The table value is unusable after Destroy returns.

CPython: Python/hashtable.c:411 _Py_hashtable_destroy

func (*Table) Foreach

func (t *Table) Foreach(fn func(*Entry) error) error

Foreach calls fn on every entry. Returning a non-nil error from fn stops iteration and propagates the error. Bucket order matches CPython.

CPython: Python/hashtable.c:268 _Py_hashtable_foreach

func (*Table) Get

func (t *Table) Get(key any) (any, bool)

Get returns the value for key. found==false means key is not in the table.

CPython: Python/hashtable.c:255 _Py_hashtable_get

func (*Table) Len

func (t *Table) Len() int

Len returns the number of entries.

CPython: Python/hashtable.c:133 _Py_hashtable_len

func (*Table) Set

func (t *Table) Set(key, val any)

Set inserts or replaces key. CPython asserts the key is absent (the C version is "set or die"); we mirror by replacing in place when an entry already exists, which keeps the surface usable from Go without breaking the byte-for-byte shape of the rehash logic.

CPython: Python/hashtable.c:217 _Py_hashtable_set

func (*Table) Size

func (t *Table) Size() int

Size returns the rough memory footprint of the table in bytes, matching _Py_hashtable_size's accounting (table header plus bucket array plus entries).

CPython: Python/hashtable.c:121 _Py_hashtable_size

func (*Table) Steal

func (t *Table) Steal(key any) (any, bool)

Steal removes key and returns its value without invoking the destructor. found==false leaves the table unchanged.

CPython: Python/hashtable.c:182 _Py_hashtable_steal