1package bolt 2 3import ( 4 "bytes" 5 "fmt" 6 "sort" 7) 8 9// Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order. 10// Cursors see nested buckets with value == nil. 11// Cursors can be obtained from a transaction and are valid as long as the transaction is open. 12// 13// Keys and values returned from the cursor are only valid for the life of the transaction. 14// 15// Changing data while traversing with a cursor may cause it to be invalidated 16// and return unexpected keys and/or values. You must reposition your cursor 17// after mutating data. 18type Cursor struct { 19 bucket *Bucket 20 stack []elemRef 21} 22 23// Bucket returns the bucket that this cursor was created from. 24func (c *Cursor) Bucket() *Bucket { 25 return c.bucket 26} 27 28// First moves the cursor to the first item in the bucket and returns its key and value. 29// If the bucket is empty then a nil key and value are returned. 30// The returned key and value are only valid for the life of the transaction. 31func (c *Cursor) First() (key []byte, value []byte) { 32 _assert(c.bucket.tx.db != nil, "tx closed") 33 c.stack = c.stack[:0] 34 p, n := c.bucket.pageNode(c.bucket.root) 35 c.stack = append(c.stack, elemRef{page: p, node: n, index: 0}) 36 c.first() 37 38 // If we land on an empty page then move to the next value. 39 // https://github.com/boltdb/bolt/issues/450 40 if c.stack[len(c.stack)-1].count() == 0 { 41 c.next() 42 } 43 44 k, v, flags := c.keyValue() 45 if (flags & uint32(bucketLeafFlag)) != 0 { 46 return k, nil 47 } 48 return k, v 49 50} 51 52// Last moves the cursor to the last item in the bucket and returns its key and value. 53// If the bucket is empty then a nil key and value are returned. 54// The returned key and value are only valid for the life of the transaction. 55func (c *Cursor) Last() (key []byte, value []byte) { 56 _assert(c.bucket.tx.db != nil, "tx closed") 57 c.stack = c.stack[:0] 58 p, n := c.bucket.pageNode(c.bucket.root) 59 ref := elemRef{page: p, node: n} 60 ref.index = ref.count() - 1 61 c.stack = append(c.stack, ref) 62 c.last() 63 k, v, flags := c.keyValue() 64 if (flags & uint32(bucketLeafFlag)) != 0 { 65 return k, nil 66 } 67 return k, v 68} 69 70// Next moves the cursor to the next item in the bucket and returns its key and value. 71// If the cursor is at the end of the bucket then a nil key and value are returned. 72// The returned key and value are only valid for the life of the transaction. 73func (c *Cursor) Next() (key []byte, value []byte) { 74 _assert(c.bucket.tx.db != nil, "tx closed") 75 k, v, flags := c.next() 76 if (flags & uint32(bucketLeafFlag)) != 0 { 77 return k, nil 78 } 79 return k, v 80} 81 82// Prev moves the cursor to the previous item in the bucket and returns its key and value. 83// If the cursor is at the beginning of the bucket then a nil key and value are returned. 84// The returned key and value are only valid for the life of the transaction. 85func (c *Cursor) Prev() (key []byte, value []byte) { 86 _assert(c.bucket.tx.db != nil, "tx closed") 87 88 // Attempt to move back one element until we're successful. 89 // Move up the stack as we hit the beginning of each page in our stack. 90 for i := len(c.stack) - 1; i >= 0; i-- { 91 elem := &c.stack[i] 92 if elem.index > 0 { 93 elem.index-- 94 break 95 } 96 c.stack = c.stack[:i] 97 } 98 99 // If we've hit the end then return nil. 100 if len(c.stack) == 0 { 101 return nil, nil 102 } 103 104 // Move down the stack to find the last element of the last leaf under this branch. 105 c.last() 106 k, v, flags := c.keyValue() 107 if (flags & uint32(bucketLeafFlag)) != 0 { 108 return k, nil 109 } 110 return k, v 111} 112 113// Seek moves the cursor to a given key and returns it. 114// If the key does not exist then the next key is used. If no keys 115// follow, a nil key is returned. 116// The returned key and value are only valid for the life of the transaction. 117func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) { 118 k, v, flags := c.seek(seek) 119 120 // If we ended up after the last element of a page then move to the next one. 121 if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() { 122 k, v, flags = c.next() 123 } 124 125 if k == nil { 126 return nil, nil 127 } else if (flags & uint32(bucketLeafFlag)) != 0 { 128 return k, nil 129 } 130 return k, v 131} 132 133// Delete removes the current key/value under the cursor from the bucket. 134// Delete fails if current key/value is a bucket or if the transaction is not writable. 135func (c *Cursor) Delete() error { 136 if c.bucket.tx.db == nil { 137 return ErrTxClosed 138 } else if !c.bucket.Writable() { 139 return ErrTxNotWritable 140 } 141 142 key, _, flags := c.keyValue() 143 // Return an error if current value is a bucket. 144 if (flags & bucketLeafFlag) != 0 { 145 return ErrIncompatibleValue 146 } 147 c.node().del(key) 148 149 return nil 150} 151 152// seek moves the cursor to a given key and returns it. 153// If the key does not exist then the next key is used. 154func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) { 155 _assert(c.bucket.tx.db != nil, "tx closed") 156 157 // Start from root page/node and traverse to correct page. 158 c.stack = c.stack[:0] 159 c.search(seek, c.bucket.root) 160 ref := &c.stack[len(c.stack)-1] 161 162 // If the cursor is pointing to the end of page/node then return nil. 163 if ref.index >= ref.count() { 164 return nil, nil, 0 165 } 166 167 // If this is a bucket then return a nil value. 168 return c.keyValue() 169} 170 171// first moves the cursor to the first leaf element under the last page in the stack. 172func (c *Cursor) first() { 173 for { 174 // Exit when we hit a leaf page. 175 var ref = &c.stack[len(c.stack)-1] 176 if ref.isLeaf() { 177 break 178 } 179 180 // Keep adding pages pointing to the first element to the stack. 181 var pgid pgid 182 if ref.node != nil { 183 pgid = ref.node.inodes[ref.index].pgid 184 } else { 185 pgid = ref.page.branchPageElement(uint16(ref.index)).pgid 186 } 187 p, n := c.bucket.pageNode(pgid) 188 c.stack = append(c.stack, elemRef{page: p, node: n, index: 0}) 189 } 190} 191 192// last moves the cursor to the last leaf element under the last page in the stack. 193func (c *Cursor) last() { 194 for { 195 // Exit when we hit a leaf page. 196 ref := &c.stack[len(c.stack)-1] 197 if ref.isLeaf() { 198 break 199 } 200 201 // Keep adding pages pointing to the last element in the stack. 202 var pgid pgid 203 if ref.node != nil { 204 pgid = ref.node.inodes[ref.index].pgid 205 } else { 206 pgid = ref.page.branchPageElement(uint16(ref.index)).pgid 207 } 208 p, n := c.bucket.pageNode(pgid) 209 210 var nextRef = elemRef{page: p, node: n} 211 nextRef.index = nextRef.count() - 1 212 c.stack = append(c.stack, nextRef) 213 } 214} 215 216// next moves to the next leaf element and returns the key and value. 217// If the cursor is at the last leaf element then it stays there and returns nil. 218func (c *Cursor) next() (key []byte, value []byte, flags uint32) { 219 for { 220 // Attempt to move over one element until we're successful. 221 // Move up the stack as we hit the end of each page in our stack. 222 var i int 223 for i = len(c.stack) - 1; i >= 0; i-- { 224 elem := &c.stack[i] 225 if elem.index < elem.count()-1 { 226 elem.index++ 227 break 228 } 229 } 230 231 // If we've hit the root page then stop and return. This will leave the 232 // cursor on the last element of the last page. 233 if i == -1 { 234 return nil, nil, 0 235 } 236 237 // Otherwise start from where we left off in the stack and find the 238 // first element of the first leaf page. 239 c.stack = c.stack[:i+1] 240 c.first() 241 242 // If this is an empty page then restart and move back up the stack. 243 // https://github.com/boltdb/bolt/issues/450 244 if c.stack[len(c.stack)-1].count() == 0 { 245 continue 246 } 247 248 return c.keyValue() 249 } 250} 251 252// search recursively performs a binary search against a given page/node until it finds a given key. 253func (c *Cursor) search(key []byte, pgid pgid) { 254 p, n := c.bucket.pageNode(pgid) 255 if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 { 256 panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags)) 257 } 258 e := elemRef{page: p, node: n} 259 c.stack = append(c.stack, e) 260 261 // If we're on a leaf page/node then find the specific node. 262 if e.isLeaf() { 263 c.nsearch(key) 264 return 265 } 266 267 if n != nil { 268 c.searchNode(key, n) 269 return 270 } 271 c.searchPage(key, p) 272} 273 274func (c *Cursor) searchNode(key []byte, n *node) { 275 var exact bool 276 index := sort.Search(len(n.inodes), func(i int) bool { 277 // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now. 278 // sort.Search() finds the lowest index where f() != -1 but we need the highest index. 279 ret := bytes.Compare(n.inodes[i].key, key) 280 if ret == 0 { 281 exact = true 282 } 283 return ret != -1 284 }) 285 if !exact && index > 0 { 286 index-- 287 } 288 c.stack[len(c.stack)-1].index = index 289 290 // Recursively search to the next page. 291 c.search(key, n.inodes[index].pgid) 292} 293 294func (c *Cursor) searchPage(key []byte, p *page) { 295 // Binary search for the correct range. 296 inodes := p.branchPageElements() 297 298 var exact bool 299 index := sort.Search(int(p.count), func(i int) bool { 300 // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now. 301 // sort.Search() finds the lowest index where f() != -1 but we need the highest index. 302 ret := bytes.Compare(inodes[i].key(), key) 303 if ret == 0 { 304 exact = true 305 } 306 return ret != -1 307 }) 308 if !exact && index > 0 { 309 index-- 310 } 311 c.stack[len(c.stack)-1].index = index 312 313 // Recursively search to the next page. 314 c.search(key, inodes[index].pgid) 315} 316 317// nsearch searches the leaf node on the top of the stack for a key. 318func (c *Cursor) nsearch(key []byte) { 319 e := &c.stack[len(c.stack)-1] 320 p, n := e.page, e.node 321 322 // If we have a node then search its inodes. 323 if n != nil { 324 index := sort.Search(len(n.inodes), func(i int) bool { 325 return bytes.Compare(n.inodes[i].key, key) != -1 326 }) 327 e.index = index 328 return 329 } 330 331 // If we have a page then search its leaf elements. 332 inodes := p.leafPageElements() 333 index := sort.Search(int(p.count), func(i int) bool { 334 return bytes.Compare(inodes[i].key(), key) != -1 335 }) 336 e.index = index 337} 338 339// keyValue returns the key and value of the current leaf element. 340func (c *Cursor) keyValue() ([]byte, []byte, uint32) { 341 ref := &c.stack[len(c.stack)-1] 342 if ref.count() == 0 || ref.index >= ref.count() { 343 return nil, nil, 0 344 } 345 346 // Retrieve value from node. 347 if ref.node != nil { 348 inode := &ref.node.inodes[ref.index] 349 return inode.key, inode.value, inode.flags 350 } 351 352 // Or retrieve value from page. 353 elem := ref.page.leafPageElement(uint16(ref.index)) 354 return elem.key(), elem.value(), elem.flags 355} 356 357// node returns the node that the cursor is currently positioned on. 358func (c *Cursor) node() *node { 359 _assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack") 360 361 // If the top of the stack is a leaf node then just return it. 362 if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() { 363 return ref.node 364 } 365 366 // Start from root and traverse down the hierarchy. 367 var n = c.stack[0].node 368 if n == nil { 369 n = c.bucket.node(c.stack[0].page.id, nil) 370 } 371 for _, ref := range c.stack[:len(c.stack)-1] { 372 _assert(!n.isLeaf, "expected branch node") 373 n = n.childAt(int(ref.index)) 374 } 375 _assert(n.isLeaf, "expected leaf node") 376 return n 377} 378 379// elemRef represents a reference to an element on a given page/node. 380type elemRef struct { 381 page *page 382 node *node 383 index int 384} 385 386// isLeaf returns whether the ref is pointing at a leaf page/node. 387func (r *elemRef) isLeaf() bool { 388 if r.node != nil { 389 return r.node.isLeaf 390 } 391 return (r.page.flags & leafPageFlag) != 0 392} 393 394// count returns the number of inodes or page elements. 395func (r *elemRef) count() int { 396 if r.node != nil { 397 return len(r.node.inodes) 398 } 399 return int(r.page.count) 400} 401