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
|
package bolt
import (
"bytes"
"sort"
"unsafe"
)
// leaf represents an in-memory, deserialized leaf page.
type leaf struct {
pgid pgid
parent *branch
items leafItems
}
// size returns the size of the leaf after serialization.
func (l *leaf) size() int {
var size int = pageHeaderSize
for _, item := range l.items {
size += lnodeSize + len(item.key) + len(item.value)
}
return size
}
// put inserts or replaces a key on a leaf page.
func (l *leaf) put(key []byte, value []byte) {
// Find insertion index.
index := sort.Search(len(l.items), func(i int) bool { return bytes.Compare(l.items[i].key, key) != -1 })
// If there is no existing key then add a new item.
if index == len(l.items) {
l.items = append(l.items, leafItem{})
} else if len(l.items) == 0 || !bytes.Equal(l.items[index].key, key) {
l.items = append(l.items, leafItem{})
copy(l.items[index+1:], l.items[index:])
}
l.items[index].key = key
l.items[index].value = value
}
// read initializes the item data from an on-disk page.
func (l *leaf) read(p *page) {
l.pgid = p.id
l.items = make(leafItems, int(p.count))
lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&p.ptr))
for i := 0; i < int(p.count); i++ {
lnode := &lnodes[i]
item := &l.items[i]
item.key = lnode.key()
item.value = lnode.value()
}
}
// write writes the items onto one or more leaf pages.
func (l *leaf) write(p *page) {
// Initialize page.
p.flags |= p_leaf
p.count = uint16(len(l.items))
// Loop over each item and write it to the page.
lnodes := (*[maxNodesPerPage]lnode)(unsafe.Pointer(&p.ptr))
b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[lnodeSize*len(l.items):]
for index, item := range l.items {
// Write node.
lnode := &lnodes[index]
lnode.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(lnode)))
lnode.ksize = uint32(len(item.key))
lnode.vsize = uint32(len(item.value))
// Write data to the end of the page.
copy(b[0:], item.key)
b = b[len(item.key):]
copy(b[0:], item.value)
b = b[len(item.value):]
}
}
// split divides up the noes in the page into appropriately sized groups.
func (l *leaf) split(pageSize int) []*leaf {
// Ignore the split if the page doesn't have at least enough nodes for
// multiple pages or if the data can fit on a single page.
if len(l.items) <= (minKeysPerPage*2) || l.size() < pageSize {
return []*leaf{l}
}
// Set fill threshold to 50%.
threshold := pageSize / 2
// Otherwise group into smaller pages and target a given fill size.
size := 0
current := &leaf{}
leafs := make([]*leaf, 0)
for index, item := range l.items {
nodeSize := lnodeSize + len(item.key) + len(item.value)
if len(current.items) >= minKeysPerPage && index < len(l.items)-minKeysPerPage && size+nodeSize > threshold {
size = pageHeaderSize
leafs = append(leafs, current)
current = &leaf{}
}
size += nodeSize
current.items = append(current.items, item)
}
leafs = append(leafs, current)
return leafs
}
type leafItems []leafItem
type leafItem struct {
key []byte
value []byte
}
func (s leafItems) Len() int { return len(s) }
func (s leafItems) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s leafItems) Less(i, j int) bool { return bytes.Compare(s[i].key, s[j].key) == -1 }
|
