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