-
Notifications
You must be signed in to change notification settings - Fork 3
/
reader.go
154 lines (132 loc) · 3.27 KB
/
reader.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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package cdb64
import (
"bytes"
"io"
"os"
)
// Reader represents a thread-safe CDB database reader. To
// create a database, use Writer.
type Reader struct {
reader io.ReaderAt
header header
}
// Open opens an existing CDB database at the given path for reading.
func Open(path string) (*Reader, error) {
f, err := os.Open(path)
if err != nil {
return nil, err
}
r, err := NewReader(f)
if err != nil {
_ = f.Close()
return nil, err
}
return r, nil
}
// NewReader opens a new Reader.
func NewReader(r io.ReaderAt) (*Reader, error) {
// read header
buf := make([]byte, headerSize)
if _, err := r.ReadAt(buf, 0); err != nil {
return nil, err
}
// parse header
var h header
for i := 0; i < 256; i++ {
off := i * 16
h[i] = table{
offset: int64(binLE.Uint64(buf[off : off+8])),
length: int(binLE.Uint64(buf[off+8 : off+16])),
}
}
return &Reader{reader: r, header: h}, nil
}
// Get returns the value for a given key, or nil if it can't be found.
func (r *Reader) Get(key []byte) ([]byte, error) {
value, _, err := r.find(key, nil)
return value, err
}
// Batch creates a new batch operator. Please note that Batch instances are not
// thread-safe and must not be shared across goroutines.
func (r *Reader) Batch() *Batch {
return &Batch{reader: r}
}
// Iterator creates an Iterator that can be used to iterate the database.
func (r *Reader) Iterator() *Iterator {
return &Iterator{
reader: r,
off: headerSize,
maxOff: r.header[0].offset,
}
}
// Close closes the underlying reader.
func (r *Reader) Close() error {
if c, ok := r.reader.(io.Closer); ok {
return c.Close()
}
return nil
}
func (r *Reader) find(key, buf []byte) ([]byte, []byte, error) {
hash := hashKey(key)
table := r.header[hash&0xff]
if table.length == 0 {
return nil, buf, nil
}
// Probe the given hash table, starting at the given slot.
var value []byte
firstSlot := hashSlot(hash, table.length)
for slot := firstSlot; true; {
slotOffset := table.offset + int64(16*slot)
slotHash, offset, err := r.readTuple(slotOffset)
if err != nil {
return nil, buf, err
}
// An empty slot means the key doesn't exist.
if slotHash == 0 {
break
}
if slotHash == hash {
value, buf, err = r.valueAt(int64(offset), key, buf)
if err != nil {
return nil, buf, err
} else if value != nil {
return value, buf, nil
}
}
// advance to next slot
if slot = (slot + 1) % table.length; slot == firstSlot {
break
}
}
return nil, buf, nil
}
func (r *Reader) valueAt(offset int64, key, buf []byte) ([]byte, []byte, error) {
klen, vlen, err := r.readTuple(offset)
if err != nil {
return nil, buf, err
}
// We can compare key lengths before reading the key at all.
if int(klen) != len(key) {
return nil, buf, nil
}
if n := int(klen + vlen); n <= cap(buf) {
buf = buf[:n]
} else {
buf = make([]byte, n)
}
if _, err := r.reader.ReadAt(buf, offset+16); err != nil {
return nil, buf, err
}
// If they keys don't match, this isn't it.
if !bytes.Equal(buf[:klen], key) {
return nil, buf, nil
}
return buf[klen:], buf, nil
}
func (r *Reader) readTuple(offset int64) (uint64, uint64, error) {
buf := make([]byte, 16)
if _, err := r.reader.ReadAt(buf, offset); err != nil {
return 0, 0, err
}
return binLE.Uint64(buf[:8]), binLE.Uint64(buf[8:]), nil
}