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
|
package bolt
import (
"bytes"
"sort"
)
type Cursor struct {
transaction *Transaction
root pgid
stack []pageElementRef
}
// 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.element().key()) {
return nil
}
return c.element().value()
}
func (c *Cursor) search(key []byte, p *page) {
if (p.flags & (p_branch | p_leaf)) == 0 {
panic("invalid page type: " + p.typ())
}
e := pageElementRef{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--
}
c.stack[len(c.stack)-1].index = uint16(index)
// Recursively search to the next page.
c.search(key, c.transaction.page(inodes[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) {
ptr := c.stack[len(c.stack)-1]
return ptr.page, ptr.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
}
// element returns the leaf element that the cursor is currently positioned on.
func (c *Cursor) element() *leafPageElement {
ref := c.stack[len(c.stack)-1]
return ref.page.leafPageElement(ref.index)
}
// node returns the node that the cursor is currently positioned on.
func (c *Cursor) node(t *RWTransaction) *node {
if len(c.stack) == 0 {
return nil
}
// Start from root and traverse down the hierarchy.
n := t.node(c.stack[0].page.id, nil)
for _, ref := range c.stack[:len(c.stack)-1] {
_assert(!n.isLeaf, "expected branch node")
_assert(ref.page.id == n.pgid, "node/page mismatch a: %d != %d", ref.page.id, n.childAt(int(ref.index)).pgid)
n = n.childAt(int(ref.index))
}
_assert(n.isLeaf, "expected leaf node")
_assert(n.pgid == c.stack[len(c.stack)-1].page.id, "node/page mismatch b: %d != %d", n.pgid, c.stack[len(c.stack)-1].page.id)
return n
}
|
