From 3dbb460b6a9f82c159f6cc9beaa64eb9f7782256 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Wed, 16 Jan 2019 02:01:09 +0100 Subject: rename --- internal/hash/def.go | 78 +++++++++++++++++++++++++++++++++++++++++ internal/hash/func.go | 13 +++++++ internal/hash/func_test.go | 44 +++++++++++++++++++++++ internal/hash/hash_def.go | 78 ----------------------------------------- internal/hash/hash_func.go | 13 ------- internal/hash/hash_func_test.go | 44 ----------------------- internal/hash/hash_log2.go | 9 ----- internal/hash/hash_log2_test.go | 42 ---------------------- internal/hash/log2.go | 9 +++++ internal/hash/log2_test.go | 42 ++++++++++++++++++++++ 10 files changed, 186 insertions(+), 186 deletions(-) create mode 100644 internal/hash/def.go create mode 100644 internal/hash/func.go create mode 100644 internal/hash/func_test.go delete mode 100644 internal/hash/hash_def.go delete mode 100644 internal/hash/hash_func.go delete mode 100644 internal/hash/hash_func_test.go delete mode 100644 internal/hash/hash_log2.go delete mode 100644 internal/hash/hash_log2_test.go create mode 100644 internal/hash/log2.go create mode 100644 internal/hash/log2_test.go diff --git a/internal/hash/def.go b/internal/hash/def.go new file mode 100644 index 0000000..f84edeb --- /dev/null +++ b/internal/hash/def.go @@ -0,0 +1,78 @@ +package hash + +type Action int + +// Operations +const ( + HashGet Action = iota + HashPut + HashPutNew + HashDelete + HashFirst + HashNext +) + +const ( + BufMod = 1 << iota + BufDisk + BufBucket + BufPin +) + +type BufHead struct { + Prev *BufHead // LRU links + Next *BufHead // LRU links + Ovrlf *BufHead // Overflow page buffer header + Addr uint32 // Address of this page + Page []byte // Actual page data + Flags byte +} + +type Segment *BufHead + +// HTab is memroy resident data structure +type HTab struct { + Hdr HashHdr // Header + NSegs int // Number of allocated segments + ExSegs int // Number of extra allocated + Hash func(interface{}, int64) uint32 // Hash function + Flags int // Flag values + FP int // File pointer + TmpBuf []byte // Temprory Buffer for BIG data + TmpKey []byte // Temprory Buffer for BIG keys + CPage BufHead // Currrent page + CBucket int // Current bucket + Err int // Error Number -- for DBM compatibility + NewFile int // Indicates if fd is backing store or not + SaveFile int // Indicates whether we need to flush file at exit + Mapp [nCached]uint32 // Pointers to page maps + NMaps int // Initial number of bitmaps + NBufs int // Number of buffers left to allocate + BufHead BufHead // Header of buffer lru list + Dir Segment // Hash Bucket directory +} + +const nCached = 32 // number of bit maps and spare points + +// HashHdr holds hash table invormation +type HashHdr struct { + Magic int32 // Magic NO for hash tables + Version int32 // Version ID + LOrder uint32 // Byte Order + BSize int32 // Bucket/Page Size + BShift int32 // Bucket shift + DSize int32 // Directory Size + SSize int32 // Segment Size + SShift int32 // Segment shift + OvflPoint int32 // Where overflow pages are being allocated + LastFreed int32 // Last overflow page freed + MaxBucket int32 // ID of Maximum bucket in use + HighMask int32 // Mask to modulo into entire table + LowMask int32 // Mask to modulo into lower half of table + FFactor int32 // Fill factor + NKeys int32 // Number of keys in hash table + HdrPages int32 // Size of table header + HCharkey int32 // value of hash(CHARKEY) + Spares [nCached]int32 // spare pages for overflow + Bitmaps [nCached]uint16 // address of overflow page bitmaps +} diff --git a/internal/hash/func.go b/internal/hash/func.go new file mode 100644 index 0000000..41c4fd5 --- /dev/null +++ b/internal/hash/func.go @@ -0,0 +1,13 @@ +package hash + +// defaultHash is Chris Torek's hash function +func defaultHash(key []byte) uint32 { + var h uint32 + for _, v := range key { + 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/func_test.go b/internal/hash/func_test.go new file mode 100644 index 0000000..458b306 --- /dev/null +++ b/internal/hash/func_test.go @@ -0,0 +1,44 @@ +package hash + +import "testing" + +func TestDefaultHash(t *testing.T) { + testCases := []struct { + key string + want uint32 + }{ + {"", 0}, + {"A", 65}, + {"AA", 2210}, + {"AAA", 72995}, + {"AAAA", 2408900}, + {"AAAAA", 79493765}, + {"AAAAAA", 2623294310}, + {"AAAAAAA", 669366375}, + {"AAAAAAAA", 614253960}, + {"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 3607767976}, + } + for _, tc := range testCases { + t.Run(tc.key, func(t *testing.T) { + got := defaultHash([]byte(tc.key)) + if got != tc.want { + t.Errorf("got %v, want %v", got, tc.want) + } + }) + } +} + +func BenchmarkDefaultHash(b *testing.B) { + benchCases := []string{ + "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", + "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG", + } + for _, bc := range benchCases { + b.Run(bc, func(b *testing.B) { + key := []byte(bc) + for i := 0; i < b.N; i++ { + defaultHash(key) + } + }) + } +} diff --git a/internal/hash/hash_def.go b/internal/hash/hash_def.go deleted file mode 100644 index f84edeb..0000000 --- a/internal/hash/hash_def.go +++ /dev/null @@ -1,78 +0,0 @@ -package hash - -type Action int - -// Operations -const ( - HashGet Action = iota - HashPut - HashPutNew - HashDelete - HashFirst - HashNext -) - -const ( - BufMod = 1 << iota - BufDisk - BufBucket - BufPin -) - -type BufHead struct { - Prev *BufHead // LRU links - Next *BufHead // LRU links - Ovrlf *BufHead // Overflow page buffer header - Addr uint32 // Address of this page - Page []byte // Actual page data - Flags byte -} - -type Segment *BufHead - -// HTab is memroy resident data structure -type HTab struct { - Hdr HashHdr // Header - NSegs int // Number of allocated segments - ExSegs int // Number of extra allocated - Hash func(interface{}, int64) uint32 // Hash function - Flags int // Flag values - FP int // File pointer - TmpBuf []byte // Temprory Buffer for BIG data - TmpKey []byte // Temprory Buffer for BIG keys - CPage BufHead // Currrent page - CBucket int // Current bucket - Err int // Error Number -- for DBM compatibility - NewFile int // Indicates if fd is backing store or not - SaveFile int // Indicates whether we need to flush file at exit - Mapp [nCached]uint32 // Pointers to page maps - NMaps int // Initial number of bitmaps - NBufs int // Number of buffers left to allocate - BufHead BufHead // Header of buffer lru list - Dir Segment // Hash Bucket directory -} - -const nCached = 32 // number of bit maps and spare points - -// HashHdr holds hash table invormation -type HashHdr struct { - Magic int32 // Magic NO for hash tables - Version int32 // Version ID - LOrder uint32 // Byte Order - BSize int32 // Bucket/Page Size - BShift int32 // Bucket shift - DSize int32 // Directory Size - SSize int32 // Segment Size - SShift int32 // Segment shift - OvflPoint int32 // Where overflow pages are being allocated - LastFreed int32 // Last overflow page freed - MaxBucket int32 // ID of Maximum bucket in use - HighMask int32 // Mask to modulo into entire table - LowMask int32 // Mask to modulo into lower half of table - FFactor int32 // Fill factor - NKeys int32 // Number of keys in hash table - HdrPages int32 // Size of table header - HCharkey int32 // value of hash(CHARKEY) - Spares [nCached]int32 // spare pages for overflow - Bitmaps [nCached]uint16 // address of overflow page bitmaps -} diff --git a/internal/hash/hash_func.go b/internal/hash/hash_func.go deleted file mode 100644 index 41c4fd5..0000000 --- a/internal/hash/hash_func.go +++ /dev/null @@ -1,13 +0,0 @@ -package hash - -// defaultHash is Chris Torek's hash function -func defaultHash(key []byte) uint32 { - var h uint32 - for _, v := range key { - 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_func_test.go b/internal/hash/hash_func_test.go deleted file mode 100644 index 458b306..0000000 --- a/internal/hash/hash_func_test.go +++ /dev/null @@ -1,44 +0,0 @@ -package hash - -import "testing" - -func TestDefaultHash(t *testing.T) { - testCases := []struct { - key string - want uint32 - }{ - {"", 0}, - {"A", 65}, - {"AA", 2210}, - {"AAA", 72995}, - {"AAAA", 2408900}, - {"AAAAA", 79493765}, - {"AAAAAA", 2623294310}, - {"AAAAAAA", 669366375}, - {"AAAAAAAA", 614253960}, - {"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 3607767976}, - } - for _, tc := range testCases { - t.Run(tc.key, func(t *testing.T) { - got := defaultHash([]byte(tc.key)) - if got != tc.want { - t.Errorf("got %v, want %v", got, tc.want) - } - }) - } -} - -func BenchmarkDefaultHash(b *testing.B) { - benchCases := []string{ - "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", - "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG", - } - for _, bc := range benchCases { - b.Run(bc, func(b *testing.B) { - key := []byte(bc) - for i := 0; i < b.N; i++ { - defaultHash(key) - } - }) - } -} diff --git a/internal/hash/hash_log2.go b/internal/hash/hash_log2.go deleted file mode 100644 index 5e30f17..0000000 --- a/internal/hash/hash_log2.go +++ /dev/null @@ -1,9 +0,0 @@ -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 deleted file mode 100644 index c58e213..0000000 --- a/internal/hash/hash_log2_test.go +++ /dev/null @@ -1,42 +0,0 @@ -package hash - -import ( - "fmt" - "testing" -) - -func TestLog2(t *testing.T) { - testCases := []struct { - num, want 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.num, tc.want), func(t *testing.T) { - got := log2(tc.num) - if got != tc.want { - t.Errorf("got %v, want %v", got, tc.want) - } - }) - } -} - -func BenchmarkLog2(b *testing.B) { - benchCases := []uint32{1, 1024} - for _, bc := range benchCases { - b.Run(fmt.Sprintf("log(%v)", bc), func(b *testing.B) { - for i := 0; i < b.N; i++ { - log2(1024) - } - }) - } -} diff --git a/internal/hash/log2.go b/internal/hash/log2.go new file mode 100644 index 0000000..5e30f17 --- /dev/null +++ b/internal/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/log2_test.go b/internal/hash/log2_test.go new file mode 100644 index 0000000..c58e213 --- /dev/null +++ b/internal/hash/log2_test.go @@ -0,0 +1,42 @@ +package hash + +import ( + "fmt" + "testing" +) + +func TestLog2(t *testing.T) { + testCases := []struct { + num, want 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.num, tc.want), func(t *testing.T) { + got := log2(tc.num) + if got != tc.want { + t.Errorf("got %v, want %v", got, tc.want) + } + }) + } +} + +func BenchmarkLog2(b *testing.B) { + benchCases := []uint32{1, 1024} + for _, bc := range benchCases { + b.Run(fmt.Sprintf("log(%v)", bc), func(b *testing.B) { + for i := 0; i < b.N; i++ { + log2(1024) + } + }) + } +} -- cgit v1.2.3