aboutsummaryrefslogtreecommitdiff
path: root/internal
diff options
context:
space:
mode:
Diffstat (limited to 'internal')
-rw-r--r--internal/btree/btree.go6
-rw-r--r--internal/hash/hash.go83
-rw-r--r--internal/hash/hash_func.go9
-rw-r--r--internal/hash/hash_func_test.go28
-rw-r--r--internal/hash/hash_test.go26
-rw-r--r--internal/hash/testdata/aliases.dbbin0 -> 65536 bytes
-rw-r--r--internal/recno/rec.go1
7 files changed, 153 insertions, 0 deletions
diff --git a/internal/btree/btree.go b/internal/btree/btree.go
new file mode 100644
index 0000000..0681aa0
--- /dev/null
+++ b/internal/btree/btree.go
@@ -0,0 +1,6 @@
+package btree
+
+const (
+ btreeMagic = 0x053162
+ btreeVersion = 3
+)
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
--- /dev/null
+++ b/internal/hash/testdata/aliases.db
Binary files differ
diff --git a/internal/recno/rec.go b/internal/recno/rec.go
new file mode 100644
index 0000000..57f331a
--- /dev/null
+++ b/internal/recno/rec.go
@@ -0,0 +1 @@
+package recno