From 65f780cdcff14da4c3214fe9ed597c3f8629c923 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Wed, 16 Jan 2019 01:07:38 +0100 Subject: add log2 --- internal/hash/hash.go | 6 +++++- internal/hash/hash_func.go | 6 +++++- internal/hash/hash_log2.go | 9 +++++++++ internal/hash/hash_log2_test.go | 37 +++++++++++++++++++++++++++++++++++++ 4 files changed, 56 insertions(+), 2 deletions(-) create mode 100644 internal/hash/hash_log2.go create mode 100644 internal/hash/hash_log2_test.go diff --git a/internal/hash/hash.go b/internal/hash/hash.go index 4a718be..8662817 100644 --- a/internal/hash/hash.go +++ b/internal/hash/hash.go @@ -9,10 +9,14 @@ const ( type Hash struct { file *os.File + hash func([]byte) uint32 } func New(file *os.File) *Hash { - return &Hash{file: file} + return &Hash{ + file: file, + hash: defaultHash, + } } func (h *Hash) Close() error { diff --git a/internal/hash/hash_func.go b/internal/hash/hash_func.go index 853412b..41c4fd5 100644 --- a/internal/hash/hash_func.go +++ b/internal/hash/hash_func.go @@ -1,9 +1,13 @@ package hash +// defaultHash is Chris Torek's hash function func defaultHash(key []byte) uint32 { var h uint32 for _, v := range key { - h = (h << 5) + h + uint32(v) + h = hash4b(h, v) } return h } + +func hash4a(h uint32, v byte) uint32 { return (h << 5) - h + uint32(v) } +func hash4b(h uint32, v byte) uint32 { return (h << 5) + h + uint32(v) } diff --git a/internal/hash/hash_log2.go b/internal/hash/hash_log2.go new file mode 100644 index 0000000..5e30f17 --- /dev/null +++ b/internal/hash/hash_log2.go @@ -0,0 +1,9 @@ +package hash + +func log2(num uint32) uint32 { + var i uint32 + for limit := uint32(1); limit < num; limit <<= 1 { + i++ + } + return i +} diff --git a/internal/hash/hash_log2_test.go b/internal/hash/hash_log2_test.go new file mode 100644 index 0000000..f4c8bf3 --- /dev/null +++ b/internal/hash/hash_log2_test.go @@ -0,0 +1,37 @@ +package hash + +import ( + "fmt" + "testing" +) + +func TestLog2(t *testing.T) { + testCases := []struct { + n, res uint32 + }{ + {0, 0}, + {1, 0}, + {2, 1}, + {3, 2}, + {4, 2}, + {8, 3}, + {9, 4}, + {128, 7}, + {129, 8}, + {1024, 10}, + } + for _, tc := range testCases { + t.Run(fmt.Sprintf("log2(%v)=%v", tc.n, tc.res), func(t *testing.T) { + res := log2(tc.n) + if res != tc.res { + t.Errorf("got %v; want %v", res, tc.res) + } + }) + } +} + +func BenchmarkLog2(b *testing.B) { + for i := 0; i < b.N; i++ { + log2(1024) + } +} -- cgit v1.2.3