tools/go-cuckoo
1
0
Fork 0
Code Issues 1 Pull Requests 1 Actions Releases 4 Wiki Activity

Compare commits

base: tools/go-cuckoo:docs/interface-congruency-analysis
Branches Tags
tools/go-cuckoo:main tools/go-cuckoo:docs/interface-congruency-analysis tools/go-cuckoo:ci/one-sentence-per-line tools/go-cuckoo:feat/pr-template
tools/go-cuckoo:v0.3.0 tools/go-cuckoo:v0.2.0 tools/go-cuckoo:v0.1.0 tools/go-cuckoo:v0.0.1
..
compare: tools/go-cuckoo:2eeff25efdd407fc3e29574ebe873cd67371cb21
Branches Tags
tools/go-cuckoo:main tools/go-cuckoo:docs/interface-congruency-analysis tools/go-cuckoo:ci/one-sentence-per-line tools/go-cuckoo:feat/pr-template
tools/go-cuckoo:v0.3.0 tools/go-cuckoo:v0.2.0 tools/go-cuckoo:v0.1.0 tools/go-cuckoo:v0.0.1

4 Commits
docs/interface-congruency-analysis .. 2eeff25efd

Author SHA1 Message Date
mvhutz 2eeff25efd Merge remote-tracking branch 'origin' into refactor/name-bucket-slot-table 2026-04-13 20:54:09 -04:00
mvhutz 6a5b40c097 docs: replaced instances of "bucket" with "table" 
- Removed instances of `growthFactor`, as it is unexported.
- Typo in `HashTable.String()`.
 2026-04-13 20:49:33 -04:00
mvhutz 395a3560c7 refactor: constructors, update docs 
- NewCustomTable -> NewCustom
- NewTableBy -> NewBy
- NewTable -> New
 2026-04-04 12:27:53 +02:00
mvhutz 2fd9da973b refactor: bucket -> table, Table -> HashTable 2026-04-04 12:22:42 +02:00
18 changed files with 366 additions and 2315 deletions
Expand all files Collapse all files
.gitea/workflows/ci.yml
+9 -2
View File
@@ -32,8 +32,9 @@ jobs:
- name: Check go mod tidy - name: Check go mod tidy
run: go mod tidy && git diff --exit-code go.mod go.sum run: go mod tidy && git diff --exit-code go.mod go.sum
- name: Run linter - uses: golangci/golangci-lint-action@v7
run: make lint-go with:
version: latest
lint-makefile: lint-makefile:
name: Makefile Lint name: Makefile Lint
@@ -45,6 +46,9 @@ jobs:
with: with:
go-version-file: go.mod go-version-file: go.mod
- name: Install gremlins
run: go install github.com/checkmake/checkmake/cmd/checkmake@latest
- name: Run mutation tests - name: Run mutation tests
run: make lint-makefile run: make lint-makefile
@@ -92,5 +96,8 @@ jobs:
with: with:
go-version-file: go.mod go-version-file: go.mod
- name: Install gremlins
run: go install github.com/go-gremlins/gremlins/cmd/gremlins@latest
- name: Run mutation tests - name: Run mutation tests
run: make test-mutation run: make test-mutation
.golangci.yml
-3
View File
@@ -114,9 +114,6 @@ linters:
# Reports uses of functions with replacement inside the testing package. # Reports uses of functions with replacement inside the testing package.
- usetesting - usetesting
# Reports mixed receiver types in structs/interfaces.
- recvcheck
settings: settings:
revive: revive:
rules: rules:
Makefile
+9 -5
View File
@@ -4,13 +4,17 @@ help: ## Show this help
@grep -E '^[a-zA-Z_-]+:.*##' $(MAKEFILE_LIST) | awk -F ':.*## ' '{printf " %-15s %s\n", $$1, $$2}' @grep -E '^[a-zA-Z_-]+:.*##' $(MAKEFILE_LIST) | awk -F ':.*## ' '{printf " %-15s %s\n", $$1, $$2}'
install: ## Install dev tools install: ## Install dev tools
go mod download go install github.com/golangci/golangci-lint/cmd/golangci-lint@latest
go install github.com/checkmake/checkmake/cmd/checkmake@latest
go install github.com/go-gremlins/gremlins/cmd/gremlins@latest
go install golang.org/x/tools/cmd/godoc@latest
go install golang.org/x/vuln/cmd/govulncheck@latest
test-unit: ## Run unit tests with coverage test-unit: ## Run unit tests with coverage
go test ./... -cover -v go test ./... -cover -v
test-mutation: ## Run mutation tests with gremlins test-mutation: ## Run mutation tests with gremlins
go tool gremlins unleash gremlins unleash
FUZZ_TIME ?= 30 FUZZ_TIME ?= 30
@@ -23,10 +27,10 @@ test-fuzz: ## Run all fuzz tests for 30s each
test: test-unit test-mutation test-fuzz ## Run all tests test: test-unit test-mutation test-fuzz ## Run all tests
lint-go: ## Lint Go code lint-go: ## Lint Go code
go tool golangci-lint run ./... golangci-lint run ./...
lint-makefile: ## Lint the Makefile lint-makefile: ## Lint the Makefile
go tool checkmake Makefile checkmake Makefile
lint-markdown: ## Lint Markdown files lint-markdown: ## Lint Markdown files
docker run --rm -v $(CURDIR):/workdir davidanson/markdownlint-cli2 "**/*.md" docker run --rm -v $(CURDIR):/workdir davidanson/markdownlint-cli2 "**/*.md"
@@ -35,7 +39,7 @@ lint: lint-go lint-makefile lint-markdown ## Lint all code
docs: ## Serve godoc locally docs: ## Serve godoc locally
@echo ">>> Visit: http://localhost:6060/pkg/$$(go list -m)" @echo ">>> Visit: http://localhost:6060/pkg/$$(go list -m)"
go tool godoc -http=:6060 godoc -http=:6060
clean: ## Clean build and test caches clean: ## Clean build and test caches
go clean -cache -testcache go clean -cache -testcache
compare.go
+2 -2
View File
@@ -1,11 +1,11 @@
package cuckoo package cuckoo
// An EqualFunc determines whethers two keys are 'equal'. Keys that are 'equal' // An EqualFunc determines whethers two keys are 'equal'. Keys that are 'equal'
// are teated as the same by the [Table]. A good EqualFunc is pure, // are teated as the same by the [HashTable]. A good EqualFunc is pure,
// deterministic, and fast. By default, [New] uses [DefaultEqualFunc]. // deterministic, and fast. By default, [New] uses [DefaultEqualFunc].
// //
// This function MUST NOT return true if the [Hash] digest of two keys // This function MUST NOT return true if the [Hash] digest of two keys
// are different: the [Table] will not work. // are different: the [HashTable] will not work.
type EqualFunc[K any] = func(a, b K) bool type EqualFunc[K any] = func(a, b K) bool
// DefaultEqualFunc compares two keys by strict equality. Returns true if the // DefaultEqualFunc compares two keys by strict equality. Returns true if the
cuckoo_fuzz_test.go
+6 -7
View File
@@ -68,22 +68,21 @@ func FuzzInsertLookup(f *testing.F) {
for _, step := range scenario.steps { for _, step := range scenario.steps {
if step.drop { if step.drop {
ok := actual.Drop(step.key) err := actual.Drop(step.key)
_, has := expected[step.key] assert.NoError(err)
assert.Equal(ok, has)
delete(expected, step.key) delete(expected, step.key)
_, ok = actual.Get(step.key) _, err = actual.Get(step.key)
assert.False(ok) assert.Error(err)
} else { } else {
err := actual.Put(step.key, step.value) err := actual.Put(step.key, step.value)
assert.NoError(err) assert.NoError(err)
expected[step.key] = step.value expected[step.key] = step.value
found, ok := actual.Get(step.key) found, err := actual.Get(step.key)
assert.True(ok) assert.NoError(err)
assert.Equal(step.value, found) assert.Equal(step.value, found)
} }
cuckoo_test.go
+11 -10
View File
@@ -108,12 +108,12 @@ func TestGetMany(t *testing.T) {
} }
for i := range 2_000 { for i := range 2_000 {
value, ok := table.Get(i) value, err := table.Get(i)
if i < 1_000 { if i < 1_000 {
assert.True(ok) assert.NoError(err)
assert.Equal(value, true) assert.Equal(value, true)
} else { } else {
assert.False(ok) assert.Error(err)
} }
} }
} }
@@ -124,9 +124,9 @@ func TestDropExistingItem(t *testing.T) {
table := cuckoo.New[int, bool]() table := cuckoo.New[int, bool]()
(table.Put(key, value)) (table.Put(key, value))
had := table.Drop(key) err := table.Drop(key)
assert.True(had) assert.NoError(err)
assert.Equal(0, table.Size()) assert.Equal(0, table.Size())
assert.False(table.Has(key)) assert.False(table.Has(key))
} }
@@ -136,9 +136,9 @@ func TestDropNoItem(t *testing.T) {
key := 0 key := 0
table := cuckoo.New[int, bool]() table := cuckoo.New[int, bool]()
had := table.Drop(key) err := table.Drop(key)
assert.False(had) assert.NoError(err)
assert.Equal(0, table.Size()) assert.Equal(0, table.Size())
assert.False(table.Has(key)) assert.False(table.Has(key))
} }
@@ -152,9 +152,10 @@ func TestDropItemCapacity(t *testing.T) {
) )
startingCapacity := table.TotalCapacity() startingCapacity := table.TotalCapacity()
table.Drop(key) err := table.Drop(key)
endingCapacity := table.TotalCapacity() endingCapacity := table.TotalCapacity()
assert.NoError(err)
assert.Equal(0, table.Size()) assert.Equal(0, table.Size())
assert.Equal(uint64(128), startingCapacity) assert.Equal(uint64(128), startingCapacity)
assert.Equal(uint64(64), endingCapacity) assert.Equal(uint64(64), endingCapacity)
@@ -202,9 +203,9 @@ func TestDropResizeCapacity(t *testing.T) {
err1 := table.Put(0, true) err1 := table.Put(0, true)
err2 := table.Put(1, true) err2 := table.Put(1, true)
table.Drop(1) err3 := table.Drop(1)
assert.NoError(errors.Join(err1, err2)) assert.NoError(errors.Join(err1, err2, err3))
assert.Equal(uint64(20), table.TotalCapacity()) assert.Equal(uint64(20), table.TotalCapacity())
} }
doc.go
-3
View File
@@ -5,8 +5,5 @@
// a table with any key type using [NewCustom]. Custom [Hash] functions and // a table with any key type using [NewCustom]. Custom [Hash] functions and
// key comparison are also supported. // key comparison are also supported.
// //
// NOTE: The [Table] is a look-up structure, and not a source of truth. If
// [ErrBadHash] occurs, the data cannot be restored.
//
// See more: https://en.wikipedia.org/wiki/Cuckoo_hashing // See more: https://en.wikipedia.org/wiki/Cuckoo_hashing
package cuckoo package cuckoo
doc_example_test.go
+5 -5
View File
@@ -14,19 +14,19 @@ func Example_basic() {
fmt.Println("Put error:", err) fmt.Println("Put error:", err)
} }
if item, ok := table.Get(1); !ok { if item, err := table.Get(1); err != nil {
fmt.Println("Not Found 1!") fmt.Println("Error:", err)
} else { } else {
fmt.Println("Found 1:", item) fmt.Println("Found 1:", item)
} }
if item, ok := table.Get(0); !ok { if item, err := table.Get(0); err != nil {
fmt.Println("Not Found 0!") fmt.Println("Error:", err)
} else { } else {
fmt.Println("Found 0:", item) fmt.Println("Found 0:", item)
} }
// Output: // Output:
// Found 1: Hello, World! // Found 1: Hello, World!
// Not Found 0! // Error: key '0' not found
} }
docs/adr/000_template.md
-15
View File
@@ -1,15 +0,0 @@
# Title
**Status**: <!-- Proposed, accepted, rejected, etc... -->
## Context
<!-- What is the issue that we're seeing that is motivating this decision or change? -->
## Decision
<!-- What is the change that we're proposing and/or doing? -->
## Consequences
<!-- What becomes easier or more difficult to do because of this change? -->
docs/adr/001_design_principles.md
-44
View File
@@ -1,44 +0,0 @@
# Adopt Congruent and Familiar Design For `go-cuckoo`
**Status**: Proposed
## Context
I built `go-cuckoo`'s API interface without design intent.
Up until now, I paid more attention implementing the underlying functionality of the cuckoo hashing.
With the fundamentals of the algorithm built, I should revisit the interface.
The goal of this project was to create an implementation of cuckoo hashing, while adhering to Go's idioms, and being as usable as possible.
While the implementation does work, it lacks direction.
## Decision
To resolve this, I'm enforcing two new principles onto the contract of `go-cuckoo`:
- **Congruency**:
A `go-cuckoo` table should have the same core functionality as Go's built-in map.
- **Familiarity**:
A `go-cuckoo` table should behave similarly to Go's standard map, so users will intuitively know how to use it.
In effect, its users will carry less cognitive load.
These principles should _guide_ the public interface of `go-cuckoo`.
Neither should be treated absolutely, though.
The behavior of `go-cuckoo` is distinct from `map`.
Do not equate them.
## Consequences
1. The repository should support both design principles.
- [ ] Update the `README.md` and `doc.go` to reflect these principles.
- [ ] Update the contributing guide and pull request template to require these principles are met.
2. The repository should contain a living document, describing the interface differences between `go-cuckoo` and `map`.
I should prioritize limiting any incongruencies.
- [ ] Produce the first draft to uncover any current incongruencies.
- [ ] Link the document to the `README.md`.
3. Analyze the familiarity of `go-cuckoo`'s current interface.
Unlike the analysis of congruency, this should be a one time document.
Familiarity is implicit to users, and does not need to be referenced.
But, any rationale should be documented in commit messages, or future ADRs.
- [ ] Produce the analysis document.
- [ ] Resolve any issues found.
go.mod
+1 -227
View File
@@ -4,225 +4,7 @@ go 1.25.6
require github.com/stretchr/testify v1.11.1 require github.com/stretchr/testify v1.11.1
require ( require github.com/kr/pretty v0.3.1 // indirect
4d63.com/gocheckcompilerdirectives v1.3.0 // indirect
4d63.com/gochecknoglobals v0.2.2 // indirect
charm.land/lipgloss/v2 v2.0.3 // indirect
codeberg.org/chavacava/garif v0.2.0 // indirect
codeberg.org/polyfloyd/go-errorlint v1.9.0 // indirect
dev.gaijin.team/go/exhaustruct/v4 v4.0.0 // indirect
dev.gaijin.team/go/golib v0.6.0 // indirect
github.com/4meepo/tagalign v1.4.3 // indirect
github.com/Abirdcfly/dupword v0.1.7 // indirect
github.com/AdminBenni/iota-mixing v1.0.0 // indirect
github.com/AlwxSin/noinlineerr v1.0.5 // indirect
github.com/Antonboom/errname v1.1.1 // indirect
github.com/Antonboom/nilnil v1.1.1 // indirect
github.com/Antonboom/testifylint v1.6.4 // indirect
github.com/BurntSushi/toml v1.6.0 // indirect
github.com/ClickHouse/clickhouse-go-linter v1.2.0 // indirect
github.com/Djarvur/go-err113 v0.1.1 // indirect
github.com/MakeNowJust/heredoc v1.0.0 // indirect
github.com/Masterminds/semver/v3 v3.5.0 // indirect
github.com/MirrexOne/unqueryvet v1.5.4 // indirect
github.com/OpenPeeDeeP/depguard/v2 v2.2.1 // indirect
github.com/alecthomas/chroma/v2 v2.24.1 // indirect
github.com/alecthomas/go-check-sumtype v0.3.1 // indirect
github.com/alexkohler/nakedret/v2 v2.0.6 // indirect
github.com/alexkohler/prealloc v1.1.0 // indirect
github.com/alfatraining/structtag v1.0.0 // indirect
github.com/alingse/asasalint v0.0.11 // indirect
github.com/alingse/nilnesserr v0.2.0 // indirect
github.com/ashanbrown/forbidigo/v2 v2.3.1 // indirect
github.com/ashanbrown/makezero/v2 v2.2.1 // indirect
github.com/beorn7/perks v1.0.1 // indirect
github.com/bkielbasa/cyclop v1.2.3 // indirect
github.com/blizzy78/varnamelen v0.8.0 // indirect
github.com/bluekeyes/go-gitdiff v0.8.1 // indirect
github.com/bombsimon/wsl/v4 v4.7.0 // indirect
github.com/bombsimon/wsl/v5 v5.8.0 // indirect
github.com/breml/bidichk v0.3.3 // indirect
github.com/breml/errchkjson v0.4.1 // indirect
github.com/butuzov/ireturn v0.4.1 // indirect
github.com/butuzov/mirror v1.3.0 // indirect
github.com/catenacyber/perfsprint v0.10.1 // indirect
github.com/ccojocar/zxcvbn-go v1.0.4 // indirect
github.com/cespare/xxhash/v2 v2.3.0 // indirect
github.com/charithe/durationcheck v0.0.11 // indirect
github.com/charmbracelet/colorprofile v0.4.3 // indirect
github.com/charmbracelet/ultraviolet v0.0.0-20251205161215-1948445e3318 // indirect
github.com/charmbracelet/x/ansi v0.11.7 // indirect
github.com/charmbracelet/x/term v0.2.2 // indirect
github.com/charmbracelet/x/termios v0.1.1 // indirect
github.com/charmbracelet/x/windows v0.2.2 // indirect
github.com/checkmake/checkmake v0.3.2 // indirect
github.com/ckaznocha/intrange v0.3.1 // indirect
github.com/clipperhouse/displaywidth v0.11.0 // indirect
github.com/clipperhouse/uax29/v2 v2.7.0 // indirect
github.com/curioswitch/go-reassign v0.3.0 // indirect
github.com/daixiang0/gci v0.13.7 // indirect
github.com/dave/dst v0.27.3 // indirect
github.com/denis-tingaikin/go-header v0.5.0 // indirect
github.com/dlclark/regexp2 v1.12.0 // indirect
github.com/ettle/strcase v0.2.0 // indirect
github.com/fatih/color v1.19.0 // indirect
github.com/fatih/structtag v1.2.0 // indirect
github.com/firefart/nonamedreturns v1.0.6 // indirect
github.com/fsnotify/fsnotify v1.9.0 // indirect
github.com/fzipp/gocyclo v0.6.0 // indirect
github.com/ghostiam/protogetter v0.3.20 // indirect
github.com/go-critic/go-critic v0.14.3 // indirect
github.com/go-gremlins/gremlins v0.6.0 // indirect
github.com/go-ini/ini v1.67.0 // indirect
github.com/go-toolsmith/astcast v1.1.0 // indirect
github.com/go-toolsmith/astcopy v1.1.0 // indirect
github.com/go-toolsmith/astequal v1.2.0 // indirect
github.com/go-toolsmith/astfmt v1.1.0 // indirect
github.com/go-toolsmith/astp v1.1.0 // indirect
github.com/go-toolsmith/strparse v1.1.0 // indirect
github.com/go-toolsmith/typep v1.1.0 // indirect
github.com/go-viper/mapstructure/v2 v2.5.0 // indirect
github.com/go-xmlfmt/xmlfmt v1.1.3 // indirect
github.com/gobwas/glob v0.2.3 // indirect
github.com/godoc-lint/godoc-lint v0.11.2 // indirect
github.com/gofrs/flock v0.13.0 // indirect
github.com/golang/protobuf v1.5.3 // indirect
github.com/golangci/asciicheck v0.5.0 // indirect
github.com/golangci/dupl v0.0.0-20260401084720-c99c5cf5c202 // indirect
github.com/golangci/go-printf-func-name v0.1.1 // indirect
github.com/golangci/gofmt v0.0.0-20250106114630-d62b90e6713d // indirect
github.com/golangci/golangci-lint/v2 v2.12.2 // indirect
github.com/golangci/golines v0.15.0 // indirect
github.com/golangci/misspell v0.8.0 // indirect
github.com/golangci/plugin-module-register v0.1.2 // indirect
github.com/golangci/revgrep v0.8.0 // indirect
github.com/golangci/rowserrcheck v0.0.0-20260419091836-c5f79b8a11ba // indirect
github.com/golangci/swaggoswag v0.0.0-20250504205917-77f2aca3143e // indirect
github.com/golangci/unconvert v0.0.0-20250410112200-a129a6e6413e // indirect
github.com/google/go-cmp v0.7.0 // indirect
github.com/gordonklaus/ineffassign v0.2.0 // indirect
github.com/gostaticanalysis/analysisutil v0.7.1 // indirect
github.com/gostaticanalysis/comment v1.5.0 // indirect
github.com/gostaticanalysis/forcetypeassert v0.2.0 // indirect
github.com/gostaticanalysis/nilerr v0.1.2 // indirect
github.com/hako/durafmt v0.0.0-20210608085754-5c1018a4e16b // indirect
github.com/hashicorp/go-immutable-radix/v2 v2.1.0 // indirect
github.com/hashicorp/go-version v1.9.0 // indirect
github.com/hashicorp/golang-lru/v2 v2.0.7 // indirect
github.com/hexops/gotextdiff v1.0.3 // indirect
github.com/inconshreveable/mousetrap v1.1.0 // indirect
github.com/jgautheron/goconst v1.10.0 // indirect
github.com/jjti/go-spancheck v0.6.5 // indirect
github.com/julz/importas v0.2.0 // indirect
github.com/karamaru-alpha/copyloopvar v1.2.2 // indirect
github.com/kisielk/errcheck v1.10.0 // indirect
github.com/kkHAIKE/contextcheck v1.1.6 // indirect
github.com/kulti/thelper v0.7.1 // indirect
github.com/kunwardeep/paralleltest v1.0.15 // indirect
github.com/lasiar/canonicalheader v1.1.2 // indirect
github.com/ldez/exptostd v0.4.5 // indirect
github.com/ldez/gomoddirectives v0.8.0 // indirect
github.com/ldez/grignotin v0.10.1 // indirect
github.com/ldez/structtags v0.6.1 // indirect
github.com/ldez/tagliatelle v0.7.2 // indirect
github.com/ldez/usetesting v0.5.0 // indirect
github.com/leonklingele/grouper v1.1.2 // indirect
github.com/lucasb-eyer/go-colorful v1.4.0 // indirect
github.com/macabu/inamedparam v0.2.0 // indirect
github.com/manuelarte/embeddedstructfieldcheck v0.4.0 // indirect
github.com/manuelarte/funcorder v0.6.0 // indirect
github.com/maratori/testableexamples v1.0.1 // indirect
github.com/maratori/testpackage v1.1.2 // indirect
github.com/matoous/godox v1.1.0 // indirect
github.com/mattn/go-colorable v0.1.14 // indirect
github.com/mattn/go-isatty v0.0.20 // indirect
github.com/mattn/go-runewidth v0.0.23 // indirect
github.com/matttproud/golang_protobuf_extensions v1.0.1 // indirect
github.com/mgechev/revive v1.15.0 // indirect
github.com/mitchellh/go-homedir v1.1.0 // indirect
github.com/moricho/tparallel v0.3.2 // indirect
github.com/muesli/cancelreader v0.2.2 // indirect
github.com/nakabonne/nestif v0.3.1 // indirect
github.com/nishanths/exhaustive v0.12.0 // indirect
github.com/nishanths/predeclared v0.2.2 // indirect
github.com/nunnatsa/ginkgolinter v0.23.0 // indirect
github.com/olekukonko/cat v0.0.0-20250911104152-50322a0618f6 // indirect
github.com/olekukonko/errors v1.1.0 // indirect
github.com/olekukonko/ll v0.1.3 // indirect
github.com/olekukonko/tablewriter v1.1.2 // indirect
github.com/pelletier/go-toml/v2 v2.3.1 // indirect
github.com/prometheus/client_golang v1.12.1 // indirect
github.com/prometheus/client_model v0.2.0 // indirect
github.com/prometheus/common v0.32.1 // indirect
github.com/prometheus/procfs v0.7.3 // indirect
github.com/quasilyte/go-ruleguard v0.4.5 // indirect
github.com/quasilyte/go-ruleguard/dsl v0.3.23 // indirect
github.com/quasilyte/gogrep v0.5.0 // indirect
github.com/quasilyte/regex/syntax v0.0.0-20210819130434-b3f0c404a727 // indirect
github.com/quasilyte/stdinfo v0.0.0-20220114132959-f7386bf02567 // indirect
github.com/raeperd/recvcheck v0.2.0 // indirect
github.com/rivo/uniseg v0.4.7 // indirect
github.com/rogpeppe/go-internal v1.14.1 // indirect
github.com/ryancurrah/gomodguard v1.4.1 // indirect
github.com/ryancurrah/gomodguard/v2 v2.1.3 // indirect
github.com/ryanrolds/sqlclosecheck v0.6.0 // indirect
github.com/sagikazarmark/locafero v0.12.0 // indirect
github.com/sanposhiho/wastedassign/v2 v2.1.0 // indirect
github.com/santhosh-tekuri/jsonschema/v6 v6.0.2 // indirect
github.com/sashamelentyev/interfacebloat v1.1.0 // indirect
github.com/sashamelentyev/usestdlibvars v1.29.0 // indirect
github.com/securego/gosec/v2 v2.26.1 // indirect
github.com/sirupsen/logrus v1.9.4 // indirect
github.com/sivchari/containedctx v1.0.3 // indirect
github.com/sonatard/noctx v0.5.1 // indirect
github.com/sourcegraph/go-diff v0.8.0 // indirect
github.com/spf13/afero v1.15.0 // indirect
github.com/spf13/cast v1.10.0 // indirect
github.com/spf13/cobra v1.10.2 // indirect
github.com/spf13/pflag v1.0.10 // indirect
github.com/spf13/viper v1.21.0 // indirect
github.com/ssgreg/nlreturn/v2 v2.2.1 // indirect
github.com/stbenjam/no-sprintf-host-port v0.3.1 // indirect
github.com/stretchr/objx v0.5.2 // indirect
github.com/subosito/gotenv v1.6.0 // indirect
github.com/tetafro/godot v1.5.6 // indirect
github.com/timakin/bodyclose v0.0.0-20260129054331-73d1f95b84b4 // indirect
github.com/timonwong/loggercheck v0.11.0 // indirect
github.com/tomarrell/wrapcheck/v2 v2.12.0 // indirect
github.com/tommy-muehle/go-mnd/v2 v2.5.1 // indirect
github.com/ultraware/funlen v0.2.0 // indirect
github.com/ultraware/whitespace v0.2.0 // indirect
github.com/uudashr/gocognit v1.2.1 // indirect
github.com/uudashr/iface v1.4.2 // indirect
github.com/xen0n/gosmopolitan v1.3.0 // indirect
github.com/xo/terminfo v0.0.0-20220910002029-abceb7e1c41e // indirect
github.com/yagipy/maintidx v1.0.0 // indirect
github.com/yeya24/promlinter v0.3.0 // indirect
github.com/ykadowak/zerologlint v0.1.5 // indirect
github.com/yuin/goldmark v1.7.13 // indirect
gitlab.com/bosi/decorder v0.4.2 // indirect
go-simpler.org/musttag v0.14.0 // indirect
go-simpler.org/sloglint v0.12.0 // indirect
go.augendre.info/arangolint v0.4.0 // indirect
go.augendre.info/fatcontext v0.9.0 // indirect
go.uber.org/multierr v1.10.0 // indirect
go.uber.org/zap v1.27.0 // indirect
go.yaml.in/yaml/v3 v3.0.4 // indirect
golang.org/x/exp/typeparams v0.0.0-20260209203927-2842357ff358 // indirect
golang.org/x/mod v0.35.0 // indirect
golang.org/x/sync v0.20.0 // indirect
golang.org/x/sys v0.43.0 // indirect
golang.org/x/telemetry v0.0.0-20260421165255-392afab6f40e // indirect
golang.org/x/text v0.36.0 // indirect
golang.org/x/tools v0.44.0 // indirect
golang.org/x/tools/cmd/godoc v0.1.0-deprecated // indirect
golang.org/x/tools/godoc v0.1.0-deprecated // indirect
golang.org/x/vuln v1.3.0 // indirect
google.golang.org/protobuf v1.36.10 // indirect
honnef.co/go/tools v0.7.0 // indirect
mvdan.cc/gofumpt v0.9.2 // indirect
mvdan.cc/unparam v0.0.0-20251027182757-5beb8c8f8f15 // indirect
)
require ( require (
github.com/davecgh/go-spew v1.1.1 // indirect github.com/davecgh/go-spew v1.1.1 // indirect
@@ -230,11 +12,3 @@ require (
github.com/trailofbits/go-fuzz-utils v0.0.0-20260318143407-0907cafe7589 github.com/trailofbits/go-fuzz-utils v0.0.0-20260318143407-0907cafe7589
gopkg.in/yaml.v3 v3.0.1 // indirect gopkg.in/yaml.v3 v3.0.1 // indirect
) )
tool (
github.com/checkmake/checkmake/cmd/checkmake
github.com/go-gremlins/gremlins/cmd/gremlins
github.com/golangci/golangci-lint/v2/cmd/golangci-lint
golang.org/x/tools/cmd/godoc
golang.org/x/vuln/cmd/govulncheck
)
go.sum
+4 -984
View File
File diff suppressed because it is too large Load Diff
hash.go
+2 -2
View File
@@ -7,9 +7,9 @@ import (
// A Hash function maps any data to a fixed-length value (in this case, a // A Hash function maps any data to a fixed-length value (in this case, a
// [uint64]). // [uint64]).
// //
// It is used by the [Table] to evenly distribute values // It is used by the [HashTable] to evenly distribute values
// amongst its slots. A good hash function is uniform, [chaotic], and // amongst its slots. A good hash function is uniform, [chaotic], and
// deterministic. [Table] uses [NewDefaultHash] by default, which is built on // deterministic. [HashTable] uses [NewDefaultHash] by default, which is built on
// [maphash.Comparable]. // [maphash.Comparable].
// //
// [chaotic]: https://en.wikipedia.org/wiki/Avalanche_effect // [chaotic]: https://en.wikipedia.org/wiki/Avalanche_effect
hash_table.go
+246
View File
@@ -0,0 +1,246 @@
package cuckoo
import (
"errors"
"fmt"
"iter"
"math/bits"
"strings"
)
// ErrBadHash occurs when the hashes given to a [Table] cause too many key
// collisions. Try rebuilding the table using:
//
// 1. Different hash seeds. Equal seeds produce equal hash functions, which
// always cycle.
// 2. A different [Hash] algorithm.
var ErrBadHash = errors.New("bad hash")
// A HashTable which uses cuckoo hashing to resolve collision. Create
// one with [New]. Or if you want more granularity, use [NewBy] or
// [NewCustom].
type HashTable[K, V any] struct {
tableA, tableB table[K, V]
growthFactor uint64
minLoadFactor float64
}
// TotalCapacity returns the number of slots allocated for the [HashTable]. To get the
// number of slots filled, look at [HashTable.Size].
func (t *HashTable[K, V]) TotalCapacity() uint64 {
return t.tableA.capacity + t.tableB.capacity
}
// Size returns how many slots are filled in the [HashTable].
func (t *HashTable[K, V]) Size() int {
return int(t.tableA.size + t.tableB.size)
}
func log2(n uint64) (m int) {
return max(0, bits.Len64(n)-1)
}
func (t *HashTable[K, V]) maxEvictions() int {
return 3 * log2(t.TotalCapacity())
}
func (t *HashTable[K, V]) load() float64 {
// When there are no slots in the table, we still treat the load as 100%.
// Every slot in the table is full.
if t.TotalCapacity() == 0 {
return 1.0
}
return float64(t.Size()) / float64(t.TotalCapacity())
}
// resize clears all tables, changes the sizes of them to a specific capacity,
// and fills them back up again. It is a helper function for [HashTable.grow] and
// [HashTable.shrink]; use them instead.
func (t *HashTable[K, V]) resize(capacity uint64) error {
entries := make([]entry[K, V], 0, t.Size())
for k, v := range t.Entries() {
entries = append(entries, entry[K, V]{k, v})
}
t.tableA.resize(capacity)
t.tableB.resize(capacity)
for _, entry := range entries {
if err := t.Put(entry.key, entry.value); err != nil {
return err
}
}
return nil
}
// grow increases the table's capacity by the growth factor. If the
// capacity is 0, it increases it to 1.
func (t *HashTable[K, V]) grow() error {
var newCapacity uint64
if t.TotalCapacity() == 0 {
newCapacity = 1
} else {
newCapacity = t.tableA.capacity * t.growthFactor
}
return t.resize(newCapacity)
}
// shrink reduces the table's capacity by the growth factor. It may
// reduce it down to 0.
func (t *HashTable[K, V]) shrink() error {
return t.resize(t.tableA.capacity / t.growthFactor)
}
// Get fetches the value for a key in the [HashTable]. Returns an error if no value
// is found.
func (t *HashTable[K, V]) Get(key K) (value V, err error) {
if item, ok := t.tableA.get(key); ok {
return item, nil
}
if item, ok := t.tableB.get(key); ok {
return item, nil
}
return value, fmt.Errorf("key '%v' not found", key)
}
// Has returns true if a key has a value in the table.
func (t *HashTable[K, V]) Has(key K) (exists bool) {
_, err := t.Get(key)
return err == nil
}
// Put sets the value for a key. Returns error if its value cannot be set.
func (t *HashTable[K, V]) Put(key K, value V) (err error) {
if t.tableA.update(key, value) {
return nil
}
if t.tableB.update(key, value) {
return nil
}
entry, eviction := entry[K, V]{key, value}, false
for range t.maxEvictions() {
if entry, eviction = t.tableA.evict(entry); !eviction {
return nil
}
if entry, eviction = t.tableB.evict(entry); !eviction {
return nil
}
}
if t.load() < t.minLoadFactor {
return fmt.Errorf("hash functions produced a cycle at load %d/%d: %w", t.Size(), t.TotalCapacity(), ErrBadHash)
}
if err := t.grow(); err != nil {
return err
}
return t.Put(entry.key, entry.value)
}
// Drop removes a value for a key in the table. Returns an error if its value
// cannot be removed.
func (t *HashTable[K, V]) Drop(key K) (err error) {
t.tableA.drop(key)
t.tableB.drop(key)
if t.load() < t.minLoadFactor {
return t.shrink()
}
return nil
}
// Entries returns an unordered sequence of all key-value pairs in the table.
func (t *HashTable[K, V]) Entries() iter.Seq2[K, V] {
return func(yield func(K, V) bool) {
for _, slot := range t.tableA.slots {
if slot.occupied {
if !yield(slot.key, slot.value) {
return
}
}
}
for _, slot := range t.tableB.slots {
if slot.occupied {
if !yield(slot.key, slot.value) {
return
}
}
}
}
}
// String returns the entries of the table as a string in the format:
// "table[k1:v1 k2:v2 ...]".
func (t *HashTable[K, V]) String() string {
var sb strings.Builder
sb.WriteString("table[")
first := true
for k, v := range t.Entries() {
if !first {
sb.WriteString(" ")
}
fmt.Fprintf(&sb, "%v:%v", k, v)
first = false
}
sb.WriteString("]")
return sb.String()
}
// NewCustom creates a [HashTable] with custom [Hash] and [EqualFunc]
// functions, along with any [Option] the user provides.
func NewCustom[K, V any](hashA, hashB Hash[K], compare EqualFunc[K], options ...Option) *HashTable[K, V] {
settings := &settings{
growthFactor: DefaultGrowthFactor,
bucketSize: DefaultCapacity,
minLoadFactor: defaultMinimumLoad,
}
for _, option := range options {
option(settings)
}
return &HashTable[K, V]{
growthFactor: settings.growthFactor,
minLoadFactor: settings.minLoadFactor,
tableA: newTable[K, V](settings.bucketSize, hashA, compare),
tableB: newTable[K, V](settings.bucketSize, hashB, compare),
}
}
func pipe[X, Y, Z any](a func(X) Y, b func(Y) Z) func(X) Z {
return func(x X) Z { return b(a(x)) }
}
// NewBy creates a [HashTable] for any key type by using keyFunc to derive a
// comparable key. Two keys with the same derived key are treated as equal.
func NewBy[K, V any, C comparable](keyFunc func(K) C, options ...Option) *HashTable[K, V] {
return NewCustom[K, V](
pipe(keyFunc, NewDefaultHash[C]()),
pipe(keyFunc, NewDefaultHash[C]()),
func(a, b K) bool { return keyFunc(a) == keyFunc(b) },
options...,
)
}
// New creates a [HashTable] using the default [Hash] and [EqualFunc]. Use
// the [Option] functions to configure its behavior. Note that this constructor
// is only provided for comparable keys. For arbitrary keys, consider
// [NewBy] or [NewCustom].
func New[K comparable, V any](options ...Option) *HashTable[K, V] {
return NewCustom[K, V](NewDefaultHash[K](), NewDefaultHash[K](), DefaultEqualFunc[K], options...)
}
settings.go
+7 -12
View File
@@ -2,39 +2,34 @@ package cuckoo
import "fmt" import "fmt"
// DefaultCapacity is the initial capacity of a [Table]. It is inspired from // DefaultCapacity is the initial capacity of a [HashTable]. It is inspired from
// Java's [HashMap] implementation, which also uses 16. // Java's [HashMap] implementation, which also uses 16.
// //
// [HashMap]: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#HashMap-- // [HashMap]: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#HashMap--
const DefaultCapacity uint64 = 16 const DefaultCapacity uint64 = 16
// DefaultGrowthFactor is the standard resize multiplier for a [Table]. Most // DefaultGrowthFactor is the standard resize multiplier for a [HashTable]. Most
// implementations use 2. // implementations use 2.
const DefaultGrowthFactor uint64 = 2 const DefaultGrowthFactor uint64 = 2
// defaultMinimumLoad is the default lowest acceptable occupancy of a [Table]. // defaultMinimumLoad is the default lowest acceptable occupancy of a [HashTable].
// The higher the minimum load, the more likely that a [Table.Put] will not // The higher the minimum load, the more likely that a [HashTable.Put] will not
// succeed. The value of 5% is taken from [libcuckoo]. // succeed. The value of 5% is taken from [libcuckoo].
// //
// [libcuckoo]: https://github.com/efficient/libcuckoo/blob/656714705a055df2b7a605eb3c71586d9da1e119/libcuckoo/cuckoohash_config.hh#L21 // [libcuckoo]: https://github.com/efficient/libcuckoo/blob/656714705a055df2b7a605eb3c71586d9da1e119/libcuckoo/cuckoohash_config.hh#L21
const defaultMinimumLoad float64 = 0.05 const defaultMinimumLoad float64 = 0.05
// defaultGrowthLimit is the maximum number of times a [Table] can grow in a
// single [Table.Put], before the library infers it will lead to a stack
// overflow. The value of '64' was chosen arbirarily.
const defaultGrowthLimit uint64 = 64
type settings struct { type settings struct {
growthFactor uint64 growthFactor uint64
minLoadFactor float64 minLoadFactor float64
bucketSize uint64 bucketSize uint64
} }
// An Option modifies the settings of a [Table]. It is used in its constructors // An Option modifies the settings of a [HashTable]. It is used in its constructors
// like [New], for example. // like [New], for example.
type Option func(*settings) type Option func(*settings)
// Capacity modifies the starting capacity of each subtable of the [Table]. The // Capacity modifies the starting capacity of each table of the [HashTable]. The
// value must be non-negative. // value must be non-negative.
func Capacity(value int) Option { func Capacity(value int) Option {
if value < 0 { if value < 0 {
@@ -44,7 +39,7 @@ func Capacity(value int) Option {
return func(s *settings) { s.bucketSize = uint64(value) } return func(s *settings) { s.bucketSize = uint64(value) }
} }
// GrowthFactor controls how much the capacity of the [Table] multiplies when // GrowthFactor controls how much the capacity of the [HashTable] multiplies when
// it must resize. The value must be greater than 1. // it must resize. The value must be greater than 1.
func GrowthFactor(value int) Option { func GrowthFactor(value int) Option {
if value < 2 { if value < 2 {
subtable.go
-107
View File
@@ -1,107 +0,0 @@
package cuckoo
// An entry is a key-value pair.
type entry[K, V any] struct {
key K
value V
}
type slot[K, V any] struct {
entry[K, V]
occupied bool
}
type subtable[K, V any] struct {
hash Hash[K]
slots []slot[K, V]
capacity, size uint64
compare EqualFunc[K]
}
// location determines where in the subtable a certain key would be placed. If
// the capacity is 0, this will panic.
func (t *subtable[K, V]) location(key K) uint64 {
return t.hash(key) % t.capacity
}
func (t *subtable[K, V]) get(key K) (value V, found bool) {
if t.capacity == 0 {
return
}
slot := t.slots[t.location(key)]
return slot.value, slot.occupied && t.compare(slot.key, key)
}
func (t *subtable[K, V]) drop(key K) (occupied bool) {
if t.capacity == 0 {
return
}
slot := &t.slots[t.location(key)]
if slot.occupied && t.compare(slot.key, key) {
slot.occupied = false
t.size--
return true
}
return false
}
func (t *subtable[K, V]) resized(capacity uint64) *subtable[K, V] {
return &subtable[K, V]{
slots: make([]slot[K, V], capacity),
capacity: capacity,
hash: t.hash,
compare: t.compare,
}
}
func (t *subtable[K, V]) update(key K, value V) (updated bool) {
if t.capacity == 0 {
return
}
slot := &t.slots[t.location(key)]
if slot.occupied && t.compare(slot.key, key) {
slot.value = value
return true
}
return false
}
func (t *subtable[K, V]) insert(insertion entry[K, V]) (evicted entry[K, V], eviction bool) {
if t.capacity == 0 {
return insertion, true
}
slot := &t.slots[t.location(insertion.key)]
if !slot.occupied {
slot.entry = insertion
slot.occupied = true
t.size++
return
}
if t.compare(slot.key, insertion.key) {
slot.value = insertion.value
return
}
insertion, slot.entry = slot.entry, insertion
return insertion, true
}
func newSubtable[K, V any](capacity uint64, hash Hash[K], compare EqualFunc[K]) *subtable[K, V] {
return &subtable[K, V]{
hash: hash,
capacity: capacity,
compare: compare,
size: 0,
slots: make([]slot[K, V], capacity),
}
}
table.go
+66 -246
View File
@@ -1,283 +1,103 @@
package cuckoo package cuckoo
import ( type entry[K, V any] struct {
"errors" key K
"fmt" value V
"iter"
"math/bits"
"strings"
)
// ErrBadHash occurs when the hashes given to a [Table] cause too many key
// collisions. Discard the old table, rebuild it from your source data, and try:
//
// 1. Different hash seeds. Equal seeds produce equal hash functions, which
// always cycle.
// 2. A different [Hash] algorithm.
var ErrBadHash = errors.New("bad hash")
// A Table which uses cuckoo hashing to resolve collision. Create
// one with [New]. Or if you want more granularity, use [NewBy] or
// [NewCustom].
type Table[K, V any] struct {
tableA, tableB *subtable[K, V]
growthFactor uint64
minLoadFactor float64
} }
// TotalCapacity returns the number of slots allocated for the [Table]. To get the type slot[K, V any] struct {
// number of slots filled, look at [Table.Size]. entry[K, V]
func (t *Table[K, V]) TotalCapacity() uint64 { occupied bool
return t.tableA.capacity + t.tableB.capacity
} }
// Size returns how many slots are filled in the [Table]. type table[K, V any] struct {
func (t *Table[K, V]) Size() int { hash Hash[K]
return int(t.tableA.size + t.tableB.size) slots []slot[K, V]
capacity, size uint64
compare EqualFunc[K]
} }
func log2(n uint64) (m int) { // location determines where in the table a certain key would be placed. If the
return max(0, bits.Len64(n)-1) // capacity is 0, this will panic.
func (t table[K, V]) location(key K) uint64 {
return t.hash(key) % t.capacity
} }
func (t *Table[K, V]) maxEvictions() int { func (t table[K, V]) get(key K) (value V, found bool) {
return 3 * log2(t.TotalCapacity()) if t.capacity == 0 {
}
func (t *Table[K, V]) load() float64 {
// When there are no slots in the table, we still treat the load as 100%.
// Every slot in the table is full.
if t.TotalCapacity() == 0 {
return 1.0
}
return float64(t.Size()) / float64(t.TotalCapacity())
}
// insert attempts to put/update an entry in the table, without modifying the
// size of the table. Returns a displaced entry and 'homeless = true' if an
// entry could not be placed after exhausting evictions.
func (t *Table[K, V]) insert(entry entry[K, V]) (displaced entry[K, V], homeless bool) {
if t.tableA.update(entry.key, entry.value) {
return return
} }
if t.tableB.update(entry.key, entry.value) { slot := t.slots[t.location(key)]
return slot.value, slot.occupied && t.compare(slot.key, key)
}
func (t *table[K, V]) drop(key K) (occupied bool) {
if t.capacity == 0 {
return return
} }
for range t.maxEvictions() { slot := &t.slots[t.location(key)]
if entry, homeless = t.tableA.insert(entry); !homeless {
return
}
if entry, homeless = t.tableB.insert(entry); !homeless { if slot.occupied && t.compare(slot.key, key) {
return slot.occupied = false
} t.size--
}
return entry, true
}
// resized creates an empty copy of the table, with a new capacity for each
// bucket.
func (t *Table[K, V]) resized(capacity uint64) *Table[K, V] {
return &Table[K, V]{
growthFactor: t.growthFactor,
minLoadFactor: t.minLoadFactor,
tableA: t.tableA.resized(capacity),
tableB: t.tableB.resized(capacity),
}
}
// resize creates a new [Table.resized] with 'capacity', inserts all items into
// the array, and replaces the current table. It is a helper function for
// [Table.grow] and [Table.shrink]; use them instead.
func (t *Table[K, V]) resize(capacity uint64) bool {
updated := t.resized(capacity)
for k, v := range t.Entries() {
if _, failed := updated.insert(entry[K, V]{k, v}); failed {
return false
}
}
*t = *updated
return true return true
} }
// grow increases the table's capacity by the growth factor. If the return false
// capacity is 0, it increases it to 1.
func (t *Table[K, V]) grow() bool {
var newCapacity uint64
if t.TotalCapacity() == 0 {
newCapacity = 1
} else {
newCapacity = t.tableA.capacity * t.growthFactor
} }
return t.resize(newCapacity) func (t *table[K, V]) resize(capacity uint64) {
} t.slots = make([]slot[K, V], capacity)
t.capacity = capacity
// shrink reduces the table's capacity by the growth factor. It may t.size = 0
// reduce it down to 0.
func (t *Table[K, V]) shrink() bool {
return t.resize(t.tableA.capacity / t.growthFactor)
}
// Get fetches the value for a key in the [Table]. Matches the comma-ok pattern
// of a builtin map; see [Table.Find] for plain indexing.
func (t *Table[K, V]) Get(key K) (value V, ok bool) {
if item, ok := t.tableA.get(key); ok {
return item, true
}
if item, ok := t.tableB.get(key); ok {
return item, true
} }
func (t table[K, V]) update(key K, value V) (updated bool) {
if t.capacity == 0 {
return return
} }
// Find fetches the value of a key. Matches direct indexing of a builtin map; slot := &t.slots[t.location(key)]
// see [Table.Get] for a comma-ok pattern.
func (t *Table[K, V]) Find(key K) (value V) { if slot.occupied && t.compare(slot.key, key) {
value, _ = t.Get(key) slot.value = value
return true
}
return false
}
func (t *table[K, V]) evict(insertion entry[K, V]) (evicted entry[K, V], eviction bool) {
if t.capacity == 0 {
return insertion, true
}
slot := &t.slots[t.location(insertion.key)]
if !slot.occupied {
slot.entry = insertion
slot.occupied = true
t.size++
return return
} }
// Has returns true if a key has a value in the table. if t.compare(slot.key, insertion.key) {
func (t *Table[K, V]) Has(key K) (exists bool) { slot.value = insertion.value
_, exists = t.Get(key)
return return
} }
// Put sets the value for a key. If it cannot be set, an error is returned. insertion, slot.entry = slot.entry, insertion
func (t *Table[K, V]) Put(key K, value V) (err error) { return insertion, true
var (
entry = entry[K, V]{key, value}
homeless bool
)
for range defaultGrowthLimit {
if entry, homeless = t.insert(entry); !homeless {
return
} }
// Both this and the growth limit are necessary: this catches bad hashes func newTable[K, V any](capacity uint64, hash Hash[K], compare EqualFunc[K]) table[K, V] {
// early when the table is sparse, while the latter catches cases where return table[K, V]{
// growing never helps. hash: hash,
if t.load() < t.minLoadFactor { capacity: capacity,
return fmt.Errorf("hash functions produced a cycle at load %d/%d: %w", t.Size(), t.TotalCapacity(), ErrBadHash) compare: compare,
} size: 0,
slots: make([]slot[K, V], capacity),
// It is theoretically possible to have a table with a larger capacity
// that is valid. But this chance is astronomically small, so we ignore
// it in this implementation.
if grew := t.grow(); !grew {
return fmt.Errorf("could not redistribute entries into larger table: %w", ErrBadHash)
} }
} }
return fmt.Errorf("could not place entry after %d resizes: %w", defaultGrowthLimit, ErrBadHash)
}
// Drop removes a value for a key in the table. Returns whether the key had
// existed.
func (t *Table[K, V]) Drop(key K) bool {
occupied := t.tableA.drop(key) || t.tableB.drop(key)
if t.load() < t.minLoadFactor {
// The error is not handled here, because table-shrinking is an internal
// optimization.
t.shrink()
}
return occupied
}
// Entries returns an unordered sequence of all key-value pairs in the table.
func (t *Table[K, V]) Entries() iter.Seq2[K, V] {
return func(yield func(K, V) bool) {
for _, slot := range t.tableA.slots {
if slot.occupied {
if !yield(slot.key, slot.value) {
return
}
}
}
for _, slot := range t.tableB.slots {
if slot.occupied {
if !yield(slot.key, slot.value) {
return
}
}
}
}
}
// String returns the entries of the table as a string in the format:
// "table[k1:v1 k2:v2 ...]".
func (t *Table[K, V]) String() string {
var sb strings.Builder
sb.WriteString("table[")
first := true
for k, v := range t.Entries() {
if !first {
sb.WriteString(" ")
}
fmt.Fprintf(&sb, "%v:%v", k, v)
first = false
}
sb.WriteString("]")
return sb.String()
}
// NewCustom creates a [Table] with custom [Hash] and [EqualFunc]
// functions, along with any [Option] the user provides.
func NewCustom[K, V any](hashA, hashB Hash[K], compare EqualFunc[K], options ...Option) *Table[K, V] {
settings := &settings{
growthFactor: DefaultGrowthFactor,
bucketSize: DefaultCapacity,
minLoadFactor: defaultMinimumLoad,
}
for _, option := range options {
option(settings)
}
return &Table[K, V]{
growthFactor: settings.growthFactor,
minLoadFactor: settings.minLoadFactor,
tableA: newSubtable[K, V](settings.bucketSize, hashA, compare),
tableB: newSubtable[K, V](settings.bucketSize, hashB, compare),
}
}
func pipe[X, Y, Z any](a func(X) Y, b func(Y) Z) func(X) Z {
return func(x X) Z { return b(a(x)) }
}
// NewBy creates a [Table] for any key type by using keyFunc to derive a
// comparable key. Two keys with the same derived key are treated as equal.
func NewBy[K, V any, C comparable](keyFunc func(K) C, options ...Option) *Table[K, V] {
return NewCustom[K, V](
pipe(keyFunc, NewDefaultHash[C]()),
pipe(keyFunc, NewDefaultHash[C]()),
func(a, b K) bool { return keyFunc(a) == keyFunc(b) },
options...,
)
}
// New creates a [Table] using the default [Hash] and [EqualFunc]. Use
// the [Option] functions to configure its behavior. Note that this constructor
// is only provided for comparable keys. For arbitrary keys, consider
// [NewBy] or [NewCustom].
func New[K comparable, V any](options ...Option) *Table[K, V] {
return NewCustom[K, V](NewDefaultHash[K](), NewDefaultHash[K](), DefaultEqualFunc[K], options...)
}
wip/INTERFACE_ANALYSIS.md
-643
View File
@@ -1,643 +0,0 @@
# Designing an Idiomatic API Interface
- [Designing an Idiomatic API Interface](#designing-an-idiomatic-api-interface)
- [Current State](#current-state)
- [Interface of the Built-in Map](#interface-of-the-built-in-map)
- [Interface of `go-cuckoo`](#interface-of-go-cuckoo)
- [Determining Congruency](#determining-congruency)
- [Determining Familiarity](#determining-familiarity)
- [Target State](#target-state)
- [Solving Congruency](#solving-congruency)
We (the maintainers) built `go-cuckoo`'s API interface without design intent.
Up until now, we paid more attention implementing the underlying functionality of the cuckoo hashing.
With the fundamentals of the algorithm built, we should revisit the interface.
It should align closer to the following principles:
- **Congruency**
A `go-cuckoo` table should have the same core functionality as Go's built-in map.
- **Familiarity**
A `go-cuckoo` table should behave similarly to Go's standard map, so users will intuitively know how to use it.
In effect, its users will carry less cognitive load.
## Current State
### Interface of the Built-in Map
Listed below is every interface provided by Go to the built-in map object.
Also included, are the functions from the package `maps` in the standard library.
<details>
<summary>Interfaces</summary>
| # | Built-in Interface | Description |
| --- | ---------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------- |
| 1 | `m := make(map[K]V)` | Returns an empty map using the built-in `make()` function. |
| 2 | `m := make(map[K]V, hint)` | Returns an empty map using `make()`, with a capacity 'hint'. This hint is how many items the map expects to hold, _not_ a measure of how large it is. |
| 3 | `m := map[K]V{...}` | Returns a map, which may be filled with entries in the ellipsis (optional). |
| 4 | `var m map[K]V` | Defines an empty _variable_ that holds a map. This differs from #1 because `m` is uninitialized (nil) here. |
| 5 | `m[k] := v` | Assigns the value of `k` to `v`. |
| 6 | `v := m[k]` | Returns the value of `k` if it exists. Otherwise, `v` is uninitialized. |
| 7 | `v, ok := m[k]` | Similar to #6, except `ok` is equal to whether `v` is initialized. This is comma-ok notation. |
| 8 | `for k, v := range m` | Iterates over every key-value pair in `m`. The order is random. |
| 9 | `delete(m, k)` | Unassigns the value `k`. Returns no value. |
| 10 | `clear(m)` | Unassigns all keys in `m`. Returns no value. |
| 11 | `n := len(m)` | Returns the number of entries in `m`. If nil, `m` returns 0. |
| 12 | `m2 := maps.Clone(m)` | Returns a copy of `m`. |
| 13 | `maps.Copy(dst, src)` | Assigns every entry of `src` in `dst`. |
| 14 | `ok := maps.Equal(m1, m2)` | Returns true iff `m1` and `m2` the same entries. |
| 15 | `ok := maps.EqualFunc(m1, m2, fn)` | Like #14, but with a custom comparator for non-comparable values. |
| 16 | `maps.DeleteFunc(m, fn)` | Removes every entry in `m` which satisfies `fn`. Returns no value. |
| 17 | `it2 := maps.All(m)` | Returns an 2D iterator over every key-value pair. |
| 18 | `it := maps.Keys(m)` | Returns an iterator over every key. |
| 19 | `it := maps.Values(m)` | Returns an iterator over every value. There can be duplicates. |
| 20 | `m := maps.Collect(seq)` | Returns a map, with every entry defined in a 2D iterator over key-value pairs. |
| 21 | `maps.Insert(m, seq)` | Assigns to `m` all key-value pairs in 2D iterator `seq`. Returns no value. |
</details>
### Interface of `go-cuckoo`
On the other hand, here is the current contract for `go-cuckoo`.
<details>
<summary>Interfaces</summary>
| # | `go-cuckoo` Interface | Description |
| --- | -------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------- |
| 1 | `m := New(opts...)` | Creates a table using the default hash and equal function. The options configure its behavior. Confined to comparable keys. |
| 2 | `m := NewBy(keyFunc, opts...)` | Like #1, but allows any key type. A `keyFunc` is used to derive a comparable key. |
| 3 | `m := NewCustom(hashA, hashB, equalFunc, opts...)` | Like #1, but allows control over the hashes used to allow any key type. An `equalFunc` determines key equality. |
| 4 | `seq := m.Entries()` | Returns an unordered 2D iterator of all key-value pairs in the table. |
| 5 | `v := m.Find(k)` | Removes the value for `k`. Returns true if `k` existed. |
| 6 | `v, ok := m.Get(k)` | Returns the value for `k` in the table. Also, returns true if the `k` exists, otherwise false. When false, `v` is undefined. |
| 7 | `ok := m.Has(k)` | Returns true if `k` is in the table. |
| 8 | `err := m.Put(k, v)` | Sets value `v` for key `k`. Otherwise, returns error. |
| 9 | `n := m.Size()` | Returns the number of items in `m`. |
| 10 | `str := m.String()` | Returns `m` as a string in the format "table[k1:v1 k2:v2 ...]". |
| 11 | `cap := m.TotalCapacity()` | Returns how many slots `m` has allocated. |
| 12 | `ok := m.Drop(k)` | Removes `k` from the table. Returns whether the key had existed. |
</details>
### Determining Congruency
So, how does the core functionality compare?
Listed below is an analysis of every interface in Go's standard map.
Each is compared against what `go-cuckoo` offers, and categorized into the following groups:
- ✅ Covered: an analog exists.
- ⚠️ Partial: workaround available.
- ❌ Gap: no analog yet; addressed in [Target State](#solving-congruency).
Specifically, here we are checking for functionality.
Is there functionality that this offers which `go-cuckoo` does not?
We are checking accessibility, but not discoverability.
The latter will be considered later.
<details>
<summary>✅ <code>m := make(map[K]V)</code></summary>
The analog is `m := New()`.
</details>
<details>
<summary>⚠️ <code>m := make(map[K]V, hint)</code></summary>
This has no simple analog.
It is close to `m := New(Capacity(hint))`, but it assigns starting capacity, not expected size.
For the built-in map, these are two separate things.
- Capacity is an internal measure, used to optimize space/speed.
It is hidden from the user because it depends on the underlying implementation, which may change.
- Expected size requires the map must hold a number of items before resizing.
This is tangeable and agnostic to implementation, hence why it is given to the user.
In short, this interface defines expected size, but `Capacity()` defines capacity.
</details>
<details>
<summary>❌ <code>m := map[K]V{...}</code></summary>
This has no simple analog, the closest being:
```go
m := New[K, V]()
for k, v := range startingEntries {
m.Put(k, v)
}
```
It is idiomatic, but far less ergonomic.
</details>
<details>
<summary>✅ <code>var m map[K]V</code></summary>
The analog is `var m Table[K, V]`.
</details>
<details>
<summary>✅ <code>m[k] := v</code></summary>
The analog is `err := m.Put(k, v)`.
</details>
<details>
<summary>✅ <code>v := m[k]</code></summary>
The analog is `v := m.Find(k)`.
</details>
<details>
<summary>✅ <code>v, ok := m[k]</code></summary>
The analog is `v, ok := m.Get(k)`.
</details>
<details>
<summary>✅ <code>for k, v := range m</code></summary>
The analog is `for k, v := range m.Entries()`.
</details>
<details>
<summary>✅ <code>delete(m, k)</code></summary>
The analog is `ok := m.Drop(k)`.
</details>
<details>
<summary>❌ <code>clear(m)</code></summary>
There is no analog.
The easiest may to do this is to delete all items individually:
```go
for k := range m.Entries() {
m.Drop(k)
}
```
</details>
<details>
<summary>✅ <code>n := len(m)</code></summary>
The analog is `n := m.Size()`.
</details>
<details>
<summary>❌ <code>m2 := maps.Clone(m)</code></summary>
There is no analog.
The easiest way to do this currently is to make a new map, and manually add the items.
```go
m2 := cuckoo.Table[K, V]()
for k, v := range m.Entries() {
m2.Put(k, v)
}
```
This gets complicated by the various options available to the user.
Furthermore, any custom `EqualFunc`, `keyFunc` or `Hash` is not transferred.
</details>
<details>
<summary>❌ <code>maps.Copy(dst, src)</code></summary>
There is no analog.
The simplest way to do this is with a for-loop.
```go
for k, v := range src.Entries() {
dst.Put(k, v)
}
```
</details>
<details>
<summary>❌ <code>ok := maps.Equal(m1, m2)</code></summary>
There is no analog.
Users have to manually check the key-value pairs to determine equality.
</details>
<details>
<summary>❌ <code>ok := maps.EqualFunc(m1, m2, fn)</code></summary>
There is no analog.
Users have to manually check the key-value pairs to determine equality.
</details>
<details>
<summary>❌ <code>maps.DeleteFunc(m, fn)</code></summary>
There is no analog.
Users have to manually delete keys.
</details>
<details>
<summary>✅ <code>it2 := maps.All(m)</code></summary>
The analog is `it2 := m.Entries()`.
</details>
<details>
<summary>⚠️ <code>it := maps.Keys(m)</code></summary>
There is no simple analog.
A close neighbor is `it2 := m.Entries()`.
Users can use this in a for-loop, and pick out just the keys:
```go
for k := range m.Entries() {
// ...
}
```
</details>
<details>
<summary>⚠️ <code>it := maps.Values(m)</code></summary>
There is no simple analog.
A close neighbor is `it2 := m.Entries()`.
Users can use this in a for-loop, and pick out just the values:
```go
for _, v := range m.Entries() {
// ...
}
```
</details>
<details>
<summary>❌ <code>m := maps.Collect(seq)</code></summary>
There is no analog.
</details>
<details>
<summary>❌ <code>maps.Insert(m, seq)</code></summary>
There is no analog.
</details>
### Determining Familiarity
We can categorize all existing table functionality by each interface's familiarity:
- ✅ Idiomatic: is clear, intuitive, and easily understood.
- ❌ Non-idiomatic: is misleading; addressed in [Target State](#solving-congruency).
<details>
<summary>✅ <code>m := New(opts...)</code></summary>
Criteria:
Noun/adjective form — Go constructors use NewX where X is a noun or adjective, not a verb or past participle (NewReaderSize, not NewSized)
Names what the user provides — the suffix should hint at the distinguishing parameter (NewBufferString tells you it takes a string)
Progression is readable — the three names together should imply simple → intermediate → advanced
Not misleadingly generic — NewWith or NewConfig could mean anything
</details>
<details>
<summary><code>m := NewBy(keyFunc, opts...)</code></summary>
- Use `NewKeyed()`.
</details>
<details>
<summary><code>m := NewCustom(hashA, hashB, equalFunc, opts...)</code></summary>
- Use `NewHashed()`.
</details>
<details>
<summary>❌ <code>seq := m.Entries()</code></summary>
- Call it `All()`.
</details>
<details>
<summary><code>v := m.Find(k)</code></summary>
- Call it `m.Lookup()`. The name `m.Find` implies a search algorithm.
</details>
<details>
<summary><code>v, ok := m.Get(k)</code></summary>
</details>
<details>
<summary><code>ok := m.Has(k)</code></summary>
</details>
<details>
<summary>❌ <code>err := m.Put(k, v)</code></summary>
- Call it `Set()`.
- No built-in library consensus, but 3rd party packages prefer `Set()`.
</details>
<details>
<summary>❌ <code>n := m.Size()</code></summary>
- Call it `Len()`.
- Size is a Java idiom.
</details>
<details>
<summary>✅ <code>str := m.String()</code></summary>
</details>
<details>
<summary>❌ <code>cap := m.TotalCapacity()</code></summary>
- Remove. This is an implementation detail.
</details>
<details>
<summary>❌ <code>ok := m.Drop(k)</code></summary>
- Call it `Delete()`.
</details>
## Target State
### Solving Congruency
We should make the following changes to accomodate for congruency:
<details>
<summary><code>ok := maps.EqualFunc(m1, m2, fn)</code></summary>
We should implement a new function:
```go
func EqualFunc[K, V1, V2 any](t1 *Table[K, V1], t2 *Table[K, V2], eq func(V1, V2) bool) bool
```
This function is free, and not bound as a receiver function.
(It is called `cuckoo.Equal(t1, t2)`, not `t1.Equals(t2)`.)
The latter implies `t1` has authority, when in fact neither do.
We define equality as:
1. Neither table has a key the other doesn't.
2. Each key has the same value in each table.
Parameter `eq` determines this equality.
Custom `EqualFunc`'s complicate this, as they modulate key identity in tables.
If two tables may differ on whether two keys are different, this function might break.
So, we must assume that:
- Both tables have `EqualFunc`'s which 'agree' on the identity of the keys present in the tables.
Agreement is defined as: if two keys are distinct in one table, they are distinct in the other.
The name `EqualFunc` is already taken by `EqualFunc[K, V]`: an alias for `func(a, b K) bool`.
Inlining `EqualFunc[K, V]` would solve this problem.
We will move the documentation attached to it to `DefaultEqualFunc`.
</details>
<details>
<summary><code>ok := maps.Equal(m1, m2)</code></summary>
We should implement a new function, to conform with the standard library:
```go
func Equal[K any, V comparable](t1, t2 *Table[K, V]) bool
```
It uses the same equality check as in `EqualFunc`.
Once again, the function is free because it is symmetric.
</details>
<details>
<summary><code>maps.Insert(m, seq)</code></summary>
We should implement a new receiver for the table:
```go
func (t *Table[K, V]) Insert(seq iter.Seq2[K, V]) error
```
A receiver fits better even though `maps.Insert` is a free function, because copying it is asymmetric.
Map `dst` receives entries from map `src`.
It's only free because Go's standard map is built into the language, and so cannot have receivers.
In terms of naming, `t.Extend` is more accurate, and has precedent in [Python](docs.python.org/3/tutorial/datastructures.html#more-on-lists) and [Rust](https://doc.rust-lang.org/std/iter/trait.Extend.html).
When [adding iterator function](https://github.com/golang/go/issues/61900) to the `maps` package, the Go team chose to frame it as 'sources' and 'sinks'.
With this model, `maps.Insert` made more sense than `maps.Extend`.
Ultimately, `t.Insert()` is a better choice to be consistent with `maps`.
</details>
<details>
<summary><code>maps.Copy(dst, src)</code></summary>
We should implement a new receiver for the table:
```go
func (t *Table[K, V]) Copy(src *Table[K, V]) error
```
It's functionality should match that of `t.Insert()`.
A receiver fits better even though `maps.Copy` is a free function, 'copying' it is asymmetric: `dst` is writen into by `src`.
It is only free because Go's standard map is built into the language, and so cannot have receivers.
The name `t.Merge()` might be more accurate, but it does work because:
- `t.Copy()` matches Go's built-in `copy()`, and `io.Copy()`. The Go team used [the same logic](https://github.com/golang/go/discussions/47330#discussioncomment-1167799) to name `maps.Copy()`.
In this case, `t.Merge()` would be an outlier.
- `t.Merge()` implies some sort of conflict-resolution, when there is not.
It simply overwrites the values.
</details>
<details>
<summary><code>maps.DeleteFunc(m, fn)</code></summary>
We should implement a new receiver for the table:
```go
func (t *Table[K, V]) DeleteFunc(del func(K, V) bool)
```
It would have the same functionality as `maps.DeleteFunc`.
A free function could work here, but `t` has clear authority over `del`.
Other than being consistent with the `maps` package, `t.DeleteFunc` follows the Go convention of appending `Func` to higher-order equivalents of functions.
This trumps names like `t.DeleteIf`, which lend more to [Java](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#removeIf-java.util.function.Predicate-) or [C++](https://en.cppreference.com/cpp/algorithm/remove).
The word `Delete` is also convention, tying back to the built-in `delete()`.
</details>
<details>
<summary><code>m := maps.Collect(seq)</code></summary>
We should implement a new constructor.
```go
func Collect[K comparable, V any](seq iter.Seq2[K, V]) (*Table[K, V], error)
```
It would create a `New()` table, and insert all entries in `seq`.
This reveicer only supports the standard table constructor, with comparable keys.
It is tempting to add `CollectBy` or `CollectCustom` to support all table types, but doing so would pollute the public interface.
It would be just one more line to initialize the table and then call `t.Insert` directly:
```go
t := // ...
err := t.Insert(seq)
```
</details>
<details>
<summary><code>m := map[K]V{...}</code></summary>
We should make a new constructor, because entries are generic.
So, creating an option with inialized entries doesn't work.
With the previous additions, users have a few options.
If they want to use a `New()` table, `t.Collect` matches well:
```go
t, err := cuckoo.Collect(func(yield func(K, V) bool) {
yield(key1, val1)
yield(key2, val2)
})
```
For `NewCustom()` or `NewBy()` tables, users can call `t.Insert` after initialization:
```go
t := // ...
err := t.Insert(func(yield func(K, V) bool) {
yield(key1, val1)
yield(key2, val2)
})
```
It is one more line.
But, the alternative is polluting the public interface with corresponding `*WithEntries` constuctors.
</details>
<details>
<summary><code>m := make(map[K]V, hint)</code></summary>
We should add a new option:
```go
func ExpectedSize(n int) Option
```
When fed to a table, it will allocate enough space to hold `n` entries without a resize.
</details>
<details>
<summary><code>clear(m)</code></summary>
We should implement a new receiver:
```go
func (t *Table[K, V]) Clear()
```
It will remove all entries from the table.
</details>
<details>
<summary><code>m2 := maps.Clone(m)</code></summary>
We should implement a matching function:
```go
func (t *Table[K, V]) Clone() *Table[K, V]
```
Also, it will copy the hash, equality function, and options used in the table.
</details>
<details>
<summary><code>it := maps.Keys(m)</code></summary>
We should implement a matching function:
```go
func (t *Table[K, V]) Keys() iter.Seq[K]
```
It is tempting to just have `All()`, but it returns a `Seq2`, not a `Seq`.
There is no iterator adaptor between `Seq` and `Seq2`, and will not be for the foreseeable future.
This function, while it feels superfluous, is required.
</details>
<details>
<summary><code>it := maps.Values(m)</code></summary>
We should implement a matching function:
```go
func (t *Table[K, V]) Values() iter.Seq[V]
```
For the same reason we need `Keys()`, we also need `Values()`.
</details>