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
|
package bolt
import (
"bytes"
"sort"
)
type Cursor struct {
transaction *Transaction
root pgid
stack []elem
}
// elem represents a node on a page that's on the cursor's stack.
type elem struct {
page *page
index uint16
}
// First moves the cursor to the first item in the bucket and returns its key and data.
func (c *Cursor) First() ([]byte, []byte) {
// TODO: Traverse to the first key.
return nil, nil
}
// Move the cursor to the next key/value.
func (c *Cursor) Next() ([]byte, []byte) {
return nil, nil
}
// Get positions the cursor at a specific key and returns the its value.
func (c *Cursor) Get(key []byte) []byte {
// Start from root page and traverse to correct page.
c.stack = c.stack[:0]
c.search(key, c.transaction.page(c.root))
p, index := c.top()
// If the cursor is pointing to the end of page then return nil.
if index == p.count {
return nil
}
// If our target node isn't the same key as what's passed in then return nil.
if !bytes.Equal(key, c.node().key()) {
return nil
}
return c.node().value()
}
func (c *Cursor) search(key []byte, p *page) {
if (p.flags & (p_branch | p_leaf)) == 0 {
panic("invalid page type: " + p.typ())
}
e := elem{page: p}
c.stack = append(c.stack, e)
// If we're on a leaf page then find the specific node.
if (p.flags & p_leaf) != 0 {
c.nsearch(key, p)
return
}
// Binary search for the correct range.
inodes := p.branchPageElements()
var exact bool
index := sort.Search(int(p.count), func(i int) bool {
// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
ret := bytes.Compare(inodes[i].key(), key)
if ret == 0 {
exact = true
}
return ret != -1
})
if !exact && index > 0 {
index--
}
e.index = uint16(index)
// Recursively search to the next page.
c.search(key, c.transaction.page(inodes[e.index].pgid))
}
// nsearch searches a leaf node for the index of the node that matches key.
func (c *Cursor) nsearch(key []byte, p *page) {
e := &c.stack[len(c.stack)-1]
// Binary search for the correct leaf node index.
inodes := p.leafPageElements()
index := sort.Search(int(p.count), func(i int) bool {
return bytes.Compare(inodes[i].key(), key) != -1
})
e.index = uint16(index)
}
// top returns the page and leaf node that the cursor is currently pointing at.
func (c *Cursor) top() (*page, uint16) {
elem := c.stack[len(c.stack)-1]
return elem.page, elem.index
}
// page returns the page that the cursor is currently pointing at.
func (c *Cursor) page() *page {
return c.stack[len(c.stack)-1].page
}
// node returns the leaf node that the cursor is currently positioned on.
func (c *Cursor) node() *leafPageElement {
elem := c.stack[len(c.stack)-1]
return elem.page.leafPageElement(elem.index)
}
|
