blob: 3000aced6c4c1d38661f54f415c466440f66e987 [file] [log] [blame]
khenaidooab1f7bd2019-11-14 14:00:27 -05001package bbolt
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
161 // If this is a bucket then return a nil value.
162 return c.keyValue()
163}
164
165// first moves the cursor to the first leaf element under the last page in the stack.
166func (c *Cursor) first() {
167 for {
168 // Exit when we hit a leaf page.
169 var ref = &c.stack[len(c.stack)-1]
170 if ref.isLeaf() {
171 break
172 }
173
174 // Keep adding pages pointing to the first element to the stack.
175 var pgid pgid
176 if ref.node != nil {
177 pgid = ref.node.inodes[ref.index].pgid
178 } else {
179 pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
180 }
181 p, n := c.bucket.pageNode(pgid)
182 c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
183 }
184}
185
186// last moves the cursor to the last leaf element under the last page in the stack.
187func (c *Cursor) last() {
188 for {
189 // Exit when we hit a leaf page.
190 ref := &c.stack[len(c.stack)-1]
191 if ref.isLeaf() {
192 break
193 }
194
195 // Keep adding pages pointing to the last element in the stack.
196 var pgid pgid
197 if ref.node != nil {
198 pgid = ref.node.inodes[ref.index].pgid
199 } else {
200 pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
201 }
202 p, n := c.bucket.pageNode(pgid)
203
204 var nextRef = elemRef{page: p, node: n}
205 nextRef.index = nextRef.count() - 1
206 c.stack = append(c.stack, nextRef)
207 }
208}
209
210// next moves to the next leaf element and returns the key and value.
211// If the cursor is at the last leaf element then it stays there and returns nil.
212func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
213 for {
214 // Attempt to move over one element until we're successful.
215 // Move up the stack as we hit the end of each page in our stack.
216 var i int
217 for i = len(c.stack) - 1; i >= 0; i-- {
218 elem := &c.stack[i]
219 if elem.index < elem.count()-1 {
220 elem.index++
221 break
222 }
223 }
224
225 // If we've hit the root page then stop and return. This will leave the
226 // cursor on the last element of the last page.
227 if i == -1 {
228 return nil, nil, 0
229 }
230
231 // Otherwise start from where we left off in the stack and find the
232 // first element of the first leaf page.
233 c.stack = c.stack[:i+1]
234 c.first()
235
236 // If this is an empty page then restart and move back up the stack.
237 // https://github.com/boltdb/bolt/issues/450
238 if c.stack[len(c.stack)-1].count() == 0 {
239 continue
240 }
241
242 return c.keyValue()
243 }
244}
245
246// search recursively performs a binary search against a given page/node until it finds a given key.
247func (c *Cursor) search(key []byte, pgid pgid) {
248 p, n := c.bucket.pageNode(pgid)
249 if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
250 panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
251 }
252 e := elemRef{page: p, node: n}
253 c.stack = append(c.stack, e)
254
255 // If we're on a leaf page/node then find the specific node.
256 if e.isLeaf() {
257 c.nsearch(key)
258 return
259 }
260
261 if n != nil {
262 c.searchNode(key, n)
263 return
264 }
265 c.searchPage(key, p)
266}
267
268func (c *Cursor) searchNode(key []byte, n *node) {
269 var exact bool
270 index := sort.Search(len(n.inodes), func(i int) bool {
271 // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
272 // sort.Search() finds the lowest index where f() != -1 but we need the highest index.
273 ret := bytes.Compare(n.inodes[i].key, key)
274 if ret == 0 {
275 exact = true
276 }
277 return ret != -1
278 })
279 if !exact && index > 0 {
280 index--
281 }
282 c.stack[len(c.stack)-1].index = index
283
284 // Recursively search to the next page.
285 c.search(key, n.inodes[index].pgid)
286}
287
288func (c *Cursor) searchPage(key []byte, p *page) {
289 // Binary search for the correct range.
290 inodes := p.branchPageElements()
291
292 var exact bool
293 index := sort.Search(int(p.count), func(i int) bool {
294 // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
295 // sort.Search() finds the lowest index where f() != -1 but we need the highest index.
296 ret := bytes.Compare(inodes[i].key(), key)
297 if ret == 0 {
298 exact = true
299 }
300 return ret != -1
301 })
302 if !exact && index > 0 {
303 index--
304 }
305 c.stack[len(c.stack)-1].index = index
306
307 // Recursively search to the next page.
308 c.search(key, inodes[index].pgid)
309}
310
311// nsearch searches the leaf node on the top of the stack for a key.
312func (c *Cursor) nsearch(key []byte) {
313 e := &c.stack[len(c.stack)-1]
314 p, n := e.page, e.node
315
316 // If we have a node then search its inodes.
317 if n != nil {
318 index := sort.Search(len(n.inodes), func(i int) bool {
319 return bytes.Compare(n.inodes[i].key, key) != -1
320 })
321 e.index = index
322 return
323 }
324
325 // If we have a page then search its leaf elements.
326 inodes := p.leafPageElements()
327 index := sort.Search(int(p.count), func(i int) bool {
328 return bytes.Compare(inodes[i].key(), key) != -1
329 })
330 e.index = index
331}
332
333// keyValue returns the key and value of the current leaf element.
334func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
335 ref := &c.stack[len(c.stack)-1]
336
337 // If the cursor is pointing to the end of page/node then return nil.
338 if ref.count() == 0 || ref.index >= ref.count() {
339 return nil, nil, 0
340 }
341
342 // Retrieve value from node.
343 if ref.node != nil {
344 inode := &ref.node.inodes[ref.index]
345 return inode.key, inode.value, inode.flags
346 }
347
348 // Or retrieve value from page.
349 elem := ref.page.leafPageElement(uint16(ref.index))
350 return elem.key(), elem.value(), elem.flags
351}
352
353// node returns the node that the cursor is currently positioned on.
354func (c *Cursor) node() *node {
355 _assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")
356
357 // If the top of the stack is a leaf node then just return it.
358 if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
359 return ref.node
360 }
361
362 // Start from root and traverse down the hierarchy.
363 var n = c.stack[0].node
364 if n == nil {
365 n = c.bucket.node(c.stack[0].page.id, nil)
366 }
367 for _, ref := range c.stack[:len(c.stack)-1] {
368 _assert(!n.isLeaf, "expected branch node")
369 n = n.childAt(int(ref.index))
370 }
371 _assert(n.isLeaf, "expected leaf node")
372 return n
373}
374
375// elemRef represents a reference to an element on a given page/node.
376type elemRef struct {
377 page *page
378 node *node
379 index int
380}
381
382// isLeaf returns whether the ref is pointing at a leaf page/node.
383func (r *elemRef) isLeaf() bool {
384 if r.node != nil {
385 return r.node.isLeaf
386 }
387 return (r.page.flags & leafPageFlag) != 0
388}
389
390// count returns the number of inodes or page elements.
391func (r *elemRef) count() int {
392 if r.node != nil {
393 return len(r.node.inodes)
394 }
395 return int(r.page.count)
396}