From 7550eb651c14a35c42d3aedb11daa49e6fc2f63e Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 15 Jan 2019 23:40:19 +0100 Subject: adjust interface --- internal/hash/hash.go | 83 ++++++++++++++++++++++++++++++++++++++ internal/hash/hash_func.go | 9 +++++ internal/hash/hash_func_test.go | 28 +++++++++++++ internal/hash/hash_test.go | 26 ++++++++++++ internal/hash/testdata/aliases.db | Bin 0 -> 65536 bytes 5 files changed, 146 insertions(+) create mode 100644 internal/hash/hash.go create mode 100644 internal/hash/hash_func.go create mode 100644 internal/hash/hash_func_test.go create mode 100644 internal/hash/hash_test.go create mode 100644 internal/hash/testdata/aliases.db (limited to 'internal/hash') diff --git a/internal/hash/hash.go b/internal/hash/hash.go new file mode 100644 index 0000000..c159e78 --- /dev/null +++ b/internal/hash/hash.go @@ -0,0 +1,83 @@ +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 +} + +const ( + hashMagic = 0x061561 + hashVersion = 2 +) diff --git a/internal/hash/hash_func.go b/internal/hash/hash_func.go new file mode 100644 index 0000000..853412b --- /dev/null +++ b/internal/hash/hash_func.go @@ -0,0 +1,9 @@ +package hash + +func defaultHash(key []byte) uint32 { + var h uint32 + for _, v := range key { + h = (h << 5) + h + uint32(v) + } + return h +} diff --git a/internal/hash/hash_func_test.go b/internal/hash/hash_func_test.go new file mode 100644 index 0000000..5ce39b4 --- /dev/null +++ b/internal/hash/hash_func_test.go @@ -0,0 +1,28 @@ +package hash + +import "testing" + +func TestDefaultHash(t *testing.T) { + testCases := []struct { + key string + hash uint32 + }{ + {"", 0}, + {"A", 65}, + {"AA", 2210}, + {"AAA", 72995}, + {"AAAA", 2408900}, + {"AAAAA", 79493765}, + {"AAAAAA", 2623294310}, + {"AAAAAAA", 669366375}, + {"AAAAAAAA", 614253960}, + } + for _, tc := range testCases { + t.Run(tc.key, func(t *testing.T) { + x := defaultHash([]byte(tc.key)) + if x != tc.hash { + t.Errorf("got %v, want %v", x, tc.hash) + } + }) + } +} diff --git a/internal/hash/hash_test.go b/internal/hash/hash_test.go new file mode 100644 index 0000000..0526146 --- /dev/null +++ b/internal/hash/hash_test.go @@ -0,0 +1,26 @@ +package hash + +import ( + "encoding/binary" + "os" + "testing" +) + +func TestOpen(t *testing.T) { + fd, err := os.Open("testdata/aliases.db") + if err != nil { + t.Fatal(err) + } + defer fd.Close() + var hdr HashHdr + if err := binary.Read(fd, binary.BigEndian, &hdr); err != nil { + t.Fatal(err) + } + if hdr.Magic != hashMagic { + t.Errorf("got %x, want %x", hdr.Magic, hashMagic) + } + if hdr.Version != hashVersion { + t.Errorf("got %x, want %x", hdr.Version, hashVersion) + } + t.Logf("%+v", hdr) +} diff --git a/internal/hash/testdata/aliases.db b/internal/hash/testdata/aliases.db new file mode 100644 index 0000000..0fb69a5 Binary files /dev/null and b/internal/hash/testdata/aliases.db differ -- cgit v1.2.3