-
Notifications
You must be signed in to change notification settings - Fork 0
/
disk_file.go
98 lines (91 loc) · 2.09 KB
/
disk_file.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package lsmt
import (
"bytes"
"encoding/gob"
"fmt"
"log"
"io"
"strconv"
)
const (
maxFileLen = 1024
indexSparseRatio = 3
)
type DiskFile struct {
index *TreeNode
data io.ReadSeeker
size int
buf bytes.Buffer
}
func (d DiskFile) Empty() bool {
return d.size == 0
}
func NewDiskFile(elems []Element) DiskFile {
d := DiskFile{size: len(elems)}
var indexElems []Element
var enc *gob.Encoder
for i, e := range elems {
if i % indexSparseRatio == 0 {
// Create sparse index.
idx := Element{Key: e.Key, Value: fmt.Sprintf("%d", d.buf.Len())}
log.Printf("created sparse index element %v", idx)
indexElems = append(indexElems, idx)
enc = gob.NewEncoder(&d.buf)
}
enc.Encode(e)
}
d.index = NewTree(indexElems)
return d
}
func (d DiskFile) Search(key string) (Element, error) {
canErr := fmt.Errorf("key %s not found in disk file", key)
if d.Empty() {
return Element{}, canErr
}
var si, ei int
start, err := JustSmallerOrEqual(d.index, key)
if err != nil {
// Key smaller than all.
return Element{}, canErr
}
si, _ = strconv.Atoi(start.Value)
end, err := JustLarger(d.index, key)
if err != nil {
// Key larger than all or equal to the last one.
ei = d.buf.Len()
} else {
ei, _ = strconv.Atoi(end.Value)
}
log.Printf("searching in range [%d,%d)]", si, ei)
buf := bytes.NewBuffer(d.buf.Bytes()[si:ei])
dec := gob.NewDecoder(buf)
for {
var e Element
if err := dec.Decode(&e); err != nil {
log.Printf("got err: %v", err)
break
}
if e.Key == key {
return e, nil
}
}
return Element{}, canErr
}
func (d DiskFile) AllElements() []Element {
indexElems := Traverse(d.index)
var elems []Element
var dec *gob.Decoder
for i, idx := range indexElems {
start, _ := strconv.Atoi(idx.Value)
end := d.buf.Len()
if i < len(indexElems)-1 {
end, _ = strconv.Atoi(indexElems[i+1].Value)
}
dec = gob.NewDecoder(bytes.NewBuffer(d.buf.Bytes()[start:end]))
var e Element
for dec.Decode(&e)==nil {
elems = append(elems, e)
}
}
return elems
}