aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2019-01-16 01:07:38 +0100
committerDimitri Sokolyuk <demon@dim13.org>2019-01-16 01:07:38 +0100
commit65f780cdcff14da4c3214fe9ed597c3f8629c923 (patch)
tree322cc9a23c331a84f765f3694d09c7a5a7dc8206
parent75dcd2d3f84836e7a362f8b2027093838439ee57 (diff)
add log2
-rw-r--r--internal/hash/hash.go6
-rw-r--r--internal/hash/hash_func.go6
-rw-r--r--internal/hash/hash_log2.go9
-rw-r--r--internal/hash/hash_log2_test.go37
4 files changed, 56 insertions, 2 deletions
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)
+ }
+}