cursor.go

Documentation: go.etcd.io/bbolt

     1  package bbolt
     2  
     3  import (
     4  	"bytes"
     5  	"fmt"
     6  	"sort"
     7  )
     8  
     9  // Cursor represents an iterator that can traverse over all key/value pairs in a bucket
    10  // in lexicographical order.
    11  // Cursors see nested buckets with value == nil.
    12  // Cursors can be obtained from a transaction and are valid as long as the transaction is open.
    13  //
    14  // Keys and values returned from the cursor are only valid for the life of the transaction.
    15  //
    16  // Changing data while traversing with a cursor may cause it to be invalidated
    17  // and return unexpected keys and/or values. You must reposition your cursor
    18  // after mutating data.
    19  type Cursor struct {
    20  	bucket *Bucket
    21  	stack  []elemRef
    22  }
    23  
    24  // Bucket returns the bucket that this cursor was created from.
    25  func (c *Cursor) Bucket() *Bucket {
    26  	return c.bucket
    27  }
    28  
    29  // First moves the cursor to the first item in the bucket and returns its key and value.
    30  // If the bucket is empty then a nil key and value are returned.
    31  // The returned key and value are only valid for the life of the transaction.
    32  func (c *Cursor) First() (key []byte, value []byte) {
    33  	_assert(c.bucket.tx.db != nil, "tx closed")
    34  	k, v, flags := c.first()
    35  	if (flags & uint32(bucketLeafFlag)) != 0 {
    36  		return k, nil
    37  	}
    38  	return k, v
    39  }
    40  
    41  func (c *Cursor) first() (key []byte, value []byte, flags uint32) {
    42  	c.stack = c.stack[:0]
    43  	p, n := c.bucket.pageNode(c.bucket.root)
    44  	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
    45  	c.goToFirstElementOnTheStack()
    46  
    47  	// If we land on an empty page then move to the next value.
    48  	// https://github.com/boltdb/bolt/issues/450
    49  	if c.stack[len(c.stack)-1].count() == 0 {
    50  		c.next()
    51  	}
    52  
    53  	k, v, flags := c.keyValue()
    54  	if (flags & uint32(bucketLeafFlag)) != 0 {
    55  		return k, nil, flags
    56  	}
    57  	return k, v, flags
    58  }
    59  
    60  // Last moves the cursor to the last item in the bucket and returns its key and value.
    61  // If the bucket is empty then a nil key and value are returned.
    62  // The returned key and value are only valid for the life of the transaction.
    63  func (c *Cursor) Last() (key []byte, value []byte) {
    64  	_assert(c.bucket.tx.db != nil, "tx closed")
    65  	c.stack = c.stack[:0]
    66  	p, n := c.bucket.pageNode(c.bucket.root)
    67  	ref := elemRef{page: p, node: n}
    68  	ref.index = ref.count() - 1
    69  	c.stack = append(c.stack, ref)
    70  	c.last()
    71  
    72  	// If this is an empty page (calling Delete may result in empty pages)
    73  	// we call prev to find the last page that is not empty
    74  	for len(c.stack) > 0 && c.stack[len(c.stack)-1].count() == 0 {
    75  		c.prev()
    76  	}
    77  
    78  	if len(c.stack) == 0 {
    79  		return nil, nil
    80  	}
    81  
    82  	k, v, flags := c.keyValue()
    83  	if (flags & uint32(bucketLeafFlag)) != 0 {
    84  		return k, nil
    85  	}
    86  	return k, v
    87  }
    88  
    89  // Next moves the cursor to the next item in the bucket and returns its key and value.
    90  // If the cursor is at the end of the bucket then a nil key and value are returned.
    91  // The returned key and value are only valid for the life of the transaction.
    92  func (c *Cursor) Next() (key []byte, value []byte) {
    93  	_assert(c.bucket.tx.db != nil, "tx closed")
    94  	k, v, flags := c.next()
    95  	if (flags & uint32(bucketLeafFlag)) != 0 {
    96  		return k, nil
    97  	}
    98  	return k, v
    99  }
   100  
   101  // Prev moves the cursor to the previous item in the bucket and returns its key and value.
   102  // If the cursor is at the beginning of the bucket then a nil key and value are returned.
   103  // The returned key and value are only valid for the life of the transaction.
   104  func (c *Cursor) Prev() (key []byte, value []byte) {
   105  	_assert(c.bucket.tx.db != nil, "tx closed")
   106  	k, v, flags := c.prev()
   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 using a b-tree search 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.
   117  func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
   118  	_assert(c.bucket.tx.db != nil, "tx closed")
   119  
   120  	k, v, flags := c.seek(seek)
   121  
   122  	// If we ended up after the last element of a page then move to the next one.
   123  	if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() {
   124  		k, v, flags = c.next()
   125  	}
   126  
   127  	if k == nil {
   128  		return nil, nil
   129  	} else if (flags & uint32(bucketLeafFlag)) != 0 {
   130  		return k, nil
   131  	}
   132  	return k, v
   133  }
   134  
   135  // Delete removes the current key/value under the cursor from the bucket.
   136  // Delete fails if current key/value is a bucket or if the transaction is not writable.
   137  func (c *Cursor) Delete() error {
   138  	if c.bucket.tx.db == nil {
   139  		return ErrTxClosed
   140  	} else if !c.bucket.Writable() {
   141  		return ErrTxNotWritable
   142  	}
   143  
   144  	key, _, flags := c.keyValue()
   145  	// Return an error if current value is a bucket.
   146  	if (flags & bucketLeafFlag) != 0 {
   147  		return ErrIncompatibleValue
   148  	}
   149  	c.node().del(key)
   150  
   151  	return nil
   152  }
   153  
   154  // seek moves the cursor to a given key and returns it.
   155  // If the key does not exist then the next key is used.
   156  func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
   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.
   166  func (c *Cursor) goToFirstElementOnTheStack() {
   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.
   187  func (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.
   212  func (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.goToFirstElementOnTheStack()
   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  // prev moves the cursor to the previous item in the bucket and returns its key and value.
   247  // If the cursor is at the beginning of the bucket then a nil key and value are returned.
   248  func (c *Cursor) prev() (key []byte, value []byte, flags uint32) {
   249  	// Attempt to move back one element until we're successful.
   250  	// Move up the stack as we hit the beginning of each page in our stack.
   251  	for i := len(c.stack) - 1; i >= 0; i-- {
   252  		elem := &c.stack[i]
   253  		if elem.index > 0 {
   254  			elem.index--
   255  			break
   256  		}
   257  		c.stack = c.stack[:i]
   258  	}
   259  
   260  	// If we've hit the end then return nil.
   261  	if len(c.stack) == 0 {
   262  		return nil, nil, 0
   263  	}
   264  
   265  	// Move down the stack to find the last element of the last leaf under this branch.
   266  	c.last()
   267  	return c.keyValue()
   268  }
   269  
   270  // search recursively performs a binary search against a given page/node until it finds a given key.
   271  func (c *Cursor) search(key []byte, pgId pgid) {
   272  	p, n := c.bucket.pageNode(pgId)
   273  	if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
   274  		panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
   275  	}
   276  	e := elemRef{page: p, node: n}
   277  	c.stack = append(c.stack, e)
   278  
   279  	// If we're on a leaf page/node then find the specific node.
   280  	if e.isLeaf() {
   281  		c.nsearch(key)
   282  		return
   283  	}
   284  
   285  	if n != nil {
   286  		c.searchNode(key, n)
   287  		return
   288  	}
   289  	c.searchPage(key, p)
   290  }
   291  
   292  func (c *Cursor) searchNode(key []byte, n *node) {
   293  	var exact bool
   294  	index := sort.Search(len(n.inodes), func(i int) bool {
   295  		// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
   296  		// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
   297  		ret := bytes.Compare(n.inodes[i].key, key)
   298  		if ret == 0 {
   299  			exact = true
   300  		}
   301  		return ret != -1
   302  	})
   303  	if !exact && index > 0 {
   304  		index--
   305  	}
   306  	c.stack[len(c.stack)-1].index = index
   307  
   308  	// Recursively search to the next page.
   309  	c.search(key, n.inodes[index].pgid)
   310  }
   311  
   312  func (c *Cursor) searchPage(key []byte, p *page) {
   313  	// Binary search for the correct range.
   314  	inodes := p.branchPageElements()
   315  
   316  	var exact bool
   317  	index := sort.Search(int(p.count), func(i int) bool {
   318  		// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
   319  		// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
   320  		ret := bytes.Compare(inodes[i].key(), key)
   321  		if ret == 0 {
   322  			exact = true
   323  		}
   324  		return ret != -1
   325  	})
   326  	if !exact && index > 0 {
   327  		index--
   328  	}
   329  	c.stack[len(c.stack)-1].index = index
   330  
   331  	// Recursively search to the next page.
   332  	c.search(key, inodes[index].pgid)
   333  }
   334  
   335  // nsearch searches the leaf node on the top of the stack for a key.
   336  func (c *Cursor) nsearch(key []byte) {
   337  	e := &c.stack[len(c.stack)-1]
   338  	p, n := e.page, e.node
   339  
   340  	// If we have a node then search its inodes.
   341  	if n != nil {
   342  		index := sort.Search(len(n.inodes), func(i int) bool {
   343  			return bytes.Compare(n.inodes[i].key, key) != -1
   344  		})
   345  		e.index = index
   346  		return
   347  	}
   348  
   349  	// If we have a page then search its leaf elements.
   350  	inodes := p.leafPageElements()
   351  	index := sort.Search(int(p.count), func(i int) bool {
   352  		return bytes.Compare(inodes[i].key(), key) != -1
   353  	})
   354  	e.index = index
   355  }
   356  
   357  // keyValue returns the key and value of the current leaf element.
   358  func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
   359  	ref := &c.stack[len(c.stack)-1]
   360  
   361  	// If the cursor is pointing to the end of page/node then return nil.
   362  	if ref.count() == 0 || ref.index >= ref.count() {
   363  		return nil, nil, 0
   364  	}
   365  
   366  	// Retrieve value from node.
   367  	if ref.node != nil {
   368  		inode := &ref.node.inodes[ref.index]
   369  		return inode.key, inode.value, inode.flags
   370  	}
   371  
   372  	// Or retrieve value from page.
   373  	elem := ref.page.leafPageElement(uint16(ref.index))
   374  	return elem.key(), elem.value(), elem.flags
   375  }
   376  
   377  // node returns the node that the cursor is currently positioned on.
   378  func (c *Cursor) node() *node {
   379  	_assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")
   380  
   381  	// If the top of the stack is a leaf node then just return it.
   382  	if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
   383  		return ref.node
   384  	}
   385  
   386  	// Start from root and traverse down the hierarchy.
   387  	var n = c.stack[0].node
   388  	if n == nil {
   389  		n = c.bucket.node(c.stack[0].page.id, nil)
   390  	}
   391  	for _, ref := range c.stack[:len(c.stack)-1] {
   392  		_assert(!n.isLeaf, "expected branch node")
   393  		n = n.childAt(ref.index)
   394  	}
   395  	_assert(n.isLeaf, "expected leaf node")
   396  	return n
   397  }
   398  
   399  // elemRef represents a reference to an element on a given page/node.
   400  type elemRef struct {
   401  	page  *page
   402  	node  *node
   403  	index int
   404  }
   405  
   406  // isLeaf returns whether the ref is pointing at a leaf page/node.
   407  func (r *elemRef) isLeaf() bool {
   408  	if r.node != nil {
   409  		return r.node.isLeaf
   410  	}
   411  	return (r.page.flags & leafPageFlag) != 0
   412  }
   413  
   414  // count returns the number of inodes or page elements.
   415  func (r *elemRef) count() int {
   416  	if r.node != nil {
   417  		return len(r.node.inodes)
   418  	}
   419  	return int(r.page.count)
   420  }
   421
View as plain text