1package bbolt
2
3import (
4	"fmt"
5	"os"
6	"sort"
7	"unsafe"
8)
9
10const pageHeaderSize = unsafe.Sizeof(page{})
11
12const minKeysPerPage = 2
13
14const branchPageElementSize = unsafe.Sizeof(branchPageElement{})
15const leafPageElementSize = unsafe.Sizeof(leafPageElement{})
16
17const (
18	branchPageFlag   = 0x01
19	leafPageFlag     = 0x02
20	metaPageFlag     = 0x04
21	freelistPageFlag = 0x10
22)
23
24const (
25	bucketLeafFlag = 0x01
26)
27
28type pgid uint64
29
30type page struct {
31	id       pgid
32	flags    uint16
33	count    uint16
34	overflow uint32
35}
36
37// typ returns a human readable page type string used for debugging.
38func (p *page) typ() string {
39	if (p.flags & branchPageFlag) != 0 {
40		return "branch"
41	} else if (p.flags & leafPageFlag) != 0 {
42		return "leaf"
43	} else if (p.flags & metaPageFlag) != 0 {
44		return "meta"
45	} else if (p.flags & freelistPageFlag) != 0 {
46		return "freelist"
47	}
48	return fmt.Sprintf("unknown<%02x>", p.flags)
49}
50
51// meta returns a pointer to the metadata section of the page.
52func (p *page) meta() *meta {
53	return (*meta)(unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p)))
54}
55
56// leafPageElement retrieves the leaf node by index
57func (p *page) leafPageElement(index uint16) *leafPageElement {
58	return (*leafPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
59		leafPageElementSize, int(index)))
60}
61
62// leafPageElements retrieves a list of leaf nodes.
63func (p *page) leafPageElements() []leafPageElement {
64	if p.count == 0 {
65		return nil
66	}
67	var elems []leafPageElement
68	data := unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p))
69	unsafeSlice(unsafe.Pointer(&elems), data, int(p.count))
70	return elems
71}
72
73// branchPageElement retrieves the branch node by index
74func (p *page) branchPageElement(index uint16) *branchPageElement {
75	return (*branchPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
76		unsafe.Sizeof(branchPageElement{}), int(index)))
77}
78
79// branchPageElements retrieves a list of branch nodes.
80func (p *page) branchPageElements() []branchPageElement {
81	if p.count == 0 {
82		return nil
83	}
84	var elems []branchPageElement
85	data := unsafeAdd(unsafe.Pointer(p), unsafe.Sizeof(*p))
86	unsafeSlice(unsafe.Pointer(&elems), data, int(p.count))
87	return elems
88}
89
90// dump writes n bytes of the page to STDERR as hex output.
91func (p *page) hexdump(n int) {
92	buf := unsafeByteSlice(unsafe.Pointer(p), 0, 0, n)
93	fmt.Fprintf(os.Stderr, "%x\n", buf)
94}
95
96type pages []*page
97
98func (s pages) Len() int           { return len(s) }
99func (s pages) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
100func (s pages) Less(i, j int) bool { return s[i].id < s[j].id }
101
102// branchPageElement represents a node on a branch page.
103type branchPageElement struct {
104	pos   uint32
105	ksize uint32
106	pgid  pgid
107}
108
109// key returns a byte slice of the node key.
110func (n *branchPageElement) key() []byte {
111	return unsafeByteSlice(unsafe.Pointer(n), 0, int(n.pos), int(n.pos)+int(n.ksize))
112}
113
114// leafPageElement represents a node on a leaf page.
115type leafPageElement struct {
116	flags uint32
117	pos   uint32
118	ksize uint32
119	vsize uint32
120}
121
122// key returns a byte slice of the node key.
123func (n *leafPageElement) key() []byte {
124	i := int(n.pos)
125	j := i + int(n.ksize)
126	return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
127}
128
129// value returns a byte slice of the node value.
130func (n *leafPageElement) value() []byte {
131	i := int(n.pos) + int(n.ksize)
132	j := i + int(n.vsize)
133	return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
134}
135
136// PageInfo represents human readable information about a page.
137type PageInfo struct {
138	ID            int
139	Type          string
140	Count         int
141	OverflowCount int
142}
143
144type pgids []pgid
145
146func (s pgids) Len() int           { return len(s) }
147func (s pgids) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
148func (s pgids) Less(i, j int) bool { return s[i] < s[j] }
149
150// merge returns the sorted union of a and b.
151func (a pgids) merge(b pgids) pgids {
152	// Return the opposite slice if one is nil.
153	if len(a) == 0 {
154		return b
155	}
156	if len(b) == 0 {
157		return a
158	}
159	merged := make(pgids, len(a)+len(b))
160	mergepgids(merged, a, b)
161	return merged
162}
163
164// mergepgids copies the sorted union of a and b into dst.
165// If dst is too small, it panics.
166func mergepgids(dst, a, b pgids) {
167	if len(dst) < len(a)+len(b) {
168		panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
169	}
170	// Copy in the opposite slice if one is nil.
171	if len(a) == 0 {
172		copy(dst, b)
173		return
174	}
175	if len(b) == 0 {
176		copy(dst, a)
177		return
178	}
179
180	// Merged will hold all elements from both lists.
181	merged := dst[:0]
182
183	// Assign lead to the slice with a lower starting value, follow to the higher value.
184	lead, follow := a, b
185	if b[0] < a[0] {
186		lead, follow = b, a
187	}
188
189	// Continue while there are elements in the lead.
190	for len(lead) > 0 {
191		// Merge largest prefix of lead that is ahead of follow[0].
192		n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
193		merged = append(merged, lead[:n]...)
194		if n >= len(lead) {
195			break
196		}
197
198		// Swap lead and follow.
199		lead, follow = follow, lead[n:]
200	}
201
202	// Append what's left in follow.
203	_ = append(merged, follow...)
204}
205