diff options
Diffstat (limited to 'search')
| -rw-r--r-- | search/hash.go | 9 | ||||
| -rw-r--r-- | search/search_test.go | 8 |
2 files changed, 16 insertions, 1 deletions
diff --git a/search/hash.go b/search/hash.go index 0b41b6b..7302d1a 100644 --- a/search/hash.go +++ b/search/hash.go @@ -26,7 +26,14 @@ func (h *Hash[K,V]) Size() int { } func (h *Hash[K,V]) hash(key K) int { - i := key + key*2 + key<<10 + key>>2 + // Mix the key in a full-width int64 rather than in K. K is any ds.Integer, + // so for a narrow type (e.g. int8) the "key<<10" term would shift past the + // type width and vanish to 0, destroying the intended high-bit mixing (and + // go vet rightly flags it). Widening to int64 first keeps the result + // identical for 64-bit int keys while making the mix well-defined for every + // integer width. + i := int64(key) + i = i + i*2 + i<<10 + i>>2 if i < 0 { i = -i } diff --git a/search/search_test.go b/search/search_test.go index 36ef4bf..b2c167a 100644 --- a/search/search_test.go +++ b/search/search_test.go @@ -45,7 +45,15 @@ func TestGoMap(t *testing.T) { } } +// shortMaxLength caps the largest input size exercised under `go test -short` +// (used by `make verify`, which runs under the race detector). The full range +// still runs in a plain `make test`. +const shortMaxLength int = 1000 + func test[K ds.Integer, V ds.Number](s Set[K,V], l int, t *testing.T) { + if testing.Short() && l > shortMaxLength { + t.Skipf("skipping size %d in -short mode", l) + } keys := ds.NewRandomArrayList[K](l, l) randoms := ds.NewRandomArrayList[V](l, -1) mapping := make(map[K]V, l) |