vendor/go.etcd.io/bbolt/cursor.go - voltha-lib-go - Gitiles

 package bbolt

 import (
 	"bytes"
 	"fmt"
 	"sort"
 )

 // Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.
 // Cursors see nested buckets with value == nil.
 // Cursors can be obtained from a transaction and are valid as long as the transaction is open.
 //
 // Keys and values returned from the cursor are only valid for the life of the transaction.
 //
 // Changing data while traversing with a cursor may cause it to be invalidated
 // and return unexpected keys and/or values. You must reposition your cursor
 // after mutating data.
 type Cursor struct {
 	bucket *Bucket
 	stack  []elemRef
 }

 // Bucket returns the bucket that this cursor was created from.
 func (c *Cursor) Bucket() *Bucket {
 	return c.bucket
 }

 // First moves the cursor to the first item in the bucket and returns its key and value.
 // If the bucket is empty then a nil key and value are returned.
 // The returned key and value are only valid for the life of the transaction.
 func (c *Cursor) First() (key []byte, value []byte) {
 	_assert(c.bucket.tx.db != nil, "tx closed")
 	c.stack = c.stack[:0]
 	p, n := c.bucket.pageNode(c.bucket.root)
 	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 	c.first()

 	// If we land on an empty page then move to the next value.
 	// https://github.com/boltdb/bolt/issues/450
 	if c.stack[len(c.stack)-1].count() == 0 {
 		c.next()
 	}

 	k, v, flags := c.keyValue()
 	if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
 	}
 	return k, v

 }

 // Last moves the cursor to the last item in the bucket and returns its key and value.
 // If the bucket is empty then a nil key and value are returned.
 // The returned key and value are only valid for the life of the transaction.
 func (c *Cursor) Last() (key []byte, value []byte) {
 	_assert(c.bucket.tx.db != nil, "tx closed")
 	c.stack = c.stack[:0]
 	p, n := c.bucket.pageNode(c.bucket.root)
 	ref := elemRef{page: p, node: n}
 	ref.index = ref.count() - 1
 	c.stack = append(c.stack, ref)
 	c.last()
 	k, v, flags := c.keyValue()
 	if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
 	}
 	return k, v
 }

 // Next moves the cursor to the next item in the bucket and returns its key and value.
 // If the cursor is at the end of the bucket then a nil key and value are returned.
 // The returned key and value are only valid for the life of the transaction.
 func (c *Cursor) Next() (key []byte, value []byte) {
 	_assert(c.bucket.tx.db != nil, "tx closed")
 	k, v, flags := c.next()
 	if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
 	}
 	return k, v
 }

 // Prev moves the cursor to the previous item in the bucket and returns its key and value.
 // If the cursor is at the beginning of the bucket then a nil key and value are returned.
 // The returned key and value are only valid for the life of the transaction.
 func (c *Cursor) Prev() (key []byte, value []byte) {
 	_assert(c.bucket.tx.db != nil, "tx closed")

 	// Attempt to move back one element until we're successful.
 	// Move up the stack as we hit the beginning of each page in our stack.
 	for i := len(c.stack) - 1; i >= 0; i-- {
 		elem := &c.stack[i]
 		if elem.index > 0 {
 			elem.index--
 			break
 		}
 		c.stack = c.stack[:i]
 	}

 	// If we've hit the end then return nil.
 	if len(c.stack) == 0 {
 		return nil, nil
 	}

 	// Move down the stack to find the last element of the last leaf under this branch.
 	c.last()
 	k, v, flags := c.keyValue()
 	if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
 	}
 	return k, v
 }

 // Seek moves the cursor to a given key and returns it.
 // If the key does not exist then the next key is used. If no keys
 // follow, a nil key is returned.
 // The returned key and value are only valid for the life of the transaction.
 func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
 	k, v, flags := c.seek(seek)

 	// If we ended up after the last element of a page then move to the next one.
 	if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() {
 		k, v, flags = c.next()
 	}

 	if k == nil {
 		return nil, nil
 	} else if (flags & uint32(bucketLeafFlag)) != 0 {
 		return k, nil
 	}
 	return k, v
 }

 // Delete removes the current key/value under the cursor from the bucket.
 // Delete fails if current key/value is a bucket or if the transaction is not writable.
 func (c *Cursor) Delete() error {
 	if c.bucket.tx.db == nil {
 		return ErrTxClosed
 	} else if !c.bucket.Writable() {
 		return ErrTxNotWritable
 	}

 	key, _, flags := c.keyValue()
 	// Return an error if current value is a bucket.
 	if (flags & bucketLeafFlag) != 0 {
 		return ErrIncompatibleValue
 	}
 	c.node().del(key)

 	return nil
 }

 // seek moves the cursor to a given key and returns it.
 // If the key does not exist then the next key is used.
 func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
 	_assert(c.bucket.tx.db != nil, "tx closed")

 	// Start from root page/node and traverse to correct page.
 	c.stack = c.stack[:0]
 	c.search(seek, c.bucket.root)

 	// If this is a bucket then return a nil value.
 	return c.keyValue()
 }

 // first moves the cursor to the first leaf element under the last page in the stack.
 func (c *Cursor) first() {
 	for {
 		// Exit when we hit a leaf page.
 		var ref = &c.stack[len(c.stack)-1]
 		if ref.isLeaf() {
 			break
 		}

 		// Keep adding pages pointing to the first element to the stack.
 		var pgid pgid
 		if ref.node != nil {
 			pgid = ref.node.inodes[ref.index].pgid
 		} else {
 			pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
 		}
 		p, n := c.bucket.pageNode(pgid)
 		c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
 	}
 }

 // last moves the cursor to the last leaf element under the last page in the stack.
 func (c *Cursor) last() {
 	for {
 		// Exit when we hit a leaf page.
 		ref := &c.stack[len(c.stack)-1]
 		if ref.isLeaf() {
 			break
 		}

 		// Keep adding pages pointing to the last element in the stack.
 		var pgid pgid
 		if ref.node != nil {
 			pgid = ref.node.inodes[ref.index].pgid
 		} else {
 			pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
 		}
 		p, n := c.bucket.pageNode(pgid)

 		var nextRef = elemRef{page: p, node: n}
 		nextRef.index = nextRef.count() - 1
 		c.stack = append(c.stack, nextRef)
 	}
 }

 // next moves to the next leaf element and returns the key and value.
 // If the cursor is at the last leaf element then it stays there and returns nil.
 func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
 	for {
 		// Attempt to move over one element until we're successful.
 		// Move up the stack as we hit the end of each page in our stack.
 		var i int
 		for i = len(c.stack) - 1; i >= 0; i-- {
 			elem := &c.stack[i]
 			if elem.index < elem.count()-1 {
 				elem.index++
 				break
 			}
 		}

 		// If we've hit the root page then stop and return. This will leave the
 		// cursor on the last element of the last page.
 		if i == -1 {
 			return nil, nil, 0
 		}

 		// Otherwise start from where we left off in the stack and find the
 		// first element of the first leaf page.
 		c.stack = c.stack[:i+1]
 		c.first()

 		// If this is an empty page then restart and move back up the stack.
 		// https://github.com/boltdb/bolt/issues/450
 		if c.stack[len(c.stack)-1].count() == 0 {
 			continue
 		}

 		return c.keyValue()
 	}
 }

 // search recursively performs a binary search against a given page/node until it finds a given key.
 func (c *Cursor) search(key []byte, pgid pgid) {
 	p, n := c.bucket.pageNode(pgid)
 	if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
 		panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
 	}
 	e := elemRef{page: p, node: n}
 	c.stack = append(c.stack, e)

 	// If we're on a leaf page/node then find the specific node.
 	if e.isLeaf() {
 		c.nsearch(key)
 		return
 	}

 	if n != nil {
 		c.searchNode(key, n)
 		return
 	}
 	c.searchPage(key, p)
 }

 func (c *Cursor) searchNode(key []byte, n *node) {
 	var exact bool
 	index := sort.Search(len(n.inodes), func(i int) bool {
 		// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
 		// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
 		ret := bytes.Compare(n.inodes[i].key, key)
 		if ret == 0 {
 			exact = true
 		}
 		return ret != -1
 	})
 	if !exact && index > 0 {
 		index--
 	}
 	c.stack[len(c.stack)-1].index = index

 	// Recursively search to the next page.
 	c.search(key, n.inodes[index].pgid)
 }

 func (c *Cursor) searchPage(key []byte, p *page) {
 	// Binary search for the correct range.
 	inodes := p.branchPageElements()

 	var exact bool
 	index := sort.Search(int(p.count), func(i int) bool {
 		// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
 		// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
 		ret := bytes.Compare(inodes[i].key(), key)
 		if ret == 0 {
 			exact = true
 		}
 		return ret != -1
 	})
 	if !exact && index > 0 {
 		index--
 	}
 	c.stack[len(c.stack)-1].index = index

 	// Recursively search to the next page.
 	c.search(key, inodes[index].pgid)
 }

 // nsearch searches the leaf node on the top of the stack for a key.
 func (c *Cursor) nsearch(key []byte) {
 	e := &c.stack[len(c.stack)-1]
 	p, n := e.page, e.node

 	// If we have a node then search its inodes.
 	if n != nil {
 		index := sort.Search(len(n.inodes), func(i int) bool {
 			return bytes.Compare(n.inodes[i].key, key) != -1
 		})
 		e.index = index
 		return
 	}

 	// If we have a page then search its leaf elements.
 	inodes := p.leafPageElements()
 	index := sort.Search(int(p.count), func(i int) bool {
 		return bytes.Compare(inodes[i].key(), key) != -1
 	})
 	e.index = index
 }

 // keyValue returns the key and value of the current leaf element.
 func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
 	ref := &c.stack[len(c.stack)-1]

 	// If the cursor is pointing to the end of page/node then return nil.
 	if ref.count() == 0 || ref.index >= ref.count() {
 		return nil, nil, 0
 	}

 	// Retrieve value from node.
 	if ref.node != nil {
 		inode := &ref.node.inodes[ref.index]
 		return inode.key, inode.value, inode.flags
 	}

 	// Or retrieve value from page.
 	elem := ref.page.leafPageElement(uint16(ref.index))
 	return elem.key(), elem.value(), elem.flags
 }

 // node returns the node that the cursor is currently positioned on.
 func (c *Cursor) node() *node {
 	_assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")

 	// If the top of the stack is a leaf node then just return it.
 	if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
 		return ref.node
 	}

 	// Start from root and traverse down the hierarchy.
 	var n = c.stack[0].node
 	if n == nil {
 		n = c.bucket.node(c.stack[0].page.id, nil)
 	}
 	for _, ref := range c.stack[:len(c.stack)-1] {
 		_assert(!n.isLeaf, "expected branch node")
 		n = n.childAt(int(ref.index))
 	}
 	_assert(n.isLeaf, "expected leaf node")
 	return n
 }

 // elemRef represents a reference to an element on a given page/node.
 type elemRef struct {
 	page  *page
 	node  *node
 	index int
 }

 // isLeaf returns whether the ref is pointing at a leaf page/node.
 func (r *elemRef) isLeaf() bool {
 	if r.node != nil {
 		return r.node.isLeaf
 	}
 	return (r.page.flags & leafPageFlag) != 0
 }

 // count returns the number of inodes or page elements.
 func (r *elemRef) count() int {
 	if r.node != nil {
 		return len(r.node.inodes)
 	}
 	return int(r.page.count)
 }
	package bbolt

	import (
	"bytes"
	"fmt"
	"sort"
	)

	// Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.
	// Cursors see nested buckets with value == nil.
	// Cursors can be obtained from a transaction and are valid as long as the transaction is open.
	//
	// Keys and values returned from the cursor are only valid for the life of the transaction.
	//
	// Changing data while traversing with a cursor may cause it to be invalidated
	// and return unexpected keys and/or values. You must reposition your cursor
	// after mutating data.
	type Cursor struct {
	bucket *Bucket
	stack []elemRef
	}

	// Bucket returns the bucket that this cursor was created from.
	func (c Cursor) Bucket() Bucket {
	return c.bucket
	}

	// First moves the cursor to the first item in the bucket and returns its key and value.
	// If the bucket is empty then a nil key and value are returned.
	// The returned key and value are only valid for the life of the transaction.
	func (c *Cursor) First() (key []byte, value []byte) {
	_assert(c.bucket.tx.db != nil, "tx closed")
	c.stack = c.stack[:0]
	p, n := c.bucket.pageNode(c.bucket.root)
	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
	c.first()

	// If we land on an empty page then move to the next value.
	// https://github.com/boltdb/bolt/issues/450
	if c.stack[len(c.stack)-1].count() == 0 {
	c.next()
	}

	k, v, flags := c.keyValue()
	if (flags & uint32(bucketLeafFlag)) != 0 {
	return k, nil
	}
	return k, v

	}

	// Last moves the cursor to the last item in the bucket and returns its key and value.
	// If the bucket is empty then a nil key and value are returned.
	// The returned key and value are only valid for the life of the transaction.
	func (c *Cursor) Last() (key []byte, value []byte) {
	_assert(c.bucket.tx.db != nil, "tx closed")
	c.stack = c.stack[:0]
	p, n := c.bucket.pageNode(c.bucket.root)
	ref := elemRef{page: p, node: n}
	ref.index = ref.count() - 1
	c.stack = append(c.stack, ref)
	c.last()
	k, v, flags := c.keyValue()
	if (flags & uint32(bucketLeafFlag)) != 0 {
	return k, nil
	}
	return k, v
	}

	// Next moves the cursor to the next item in the bucket and returns its key and value.
	// If the cursor is at the end of the bucket then a nil key and value are returned.
	// The returned key and value are only valid for the life of the transaction.
	func (c *Cursor) Next() (key []byte, value []byte) {
	_assert(c.bucket.tx.db != nil, "tx closed")
	k, v, flags := c.next()
	if (flags & uint32(bucketLeafFlag)) != 0 {
	return k, nil
	}
	return k, v
	}

	// Prev moves the cursor to the previous item in the bucket and returns its key and value.
	// If the cursor is at the beginning of the bucket then a nil key and value are returned.
	// The returned key and value are only valid for the life of the transaction.
	func (c *Cursor) Prev() (key []byte, value []byte) {
	_assert(c.bucket.tx.db != nil, "tx closed")

	// Attempt to move back one element until we're successful.
	// Move up the stack as we hit the beginning of each page in our stack.
	for i := len(c.stack) - 1; i >= 0; i-- {
	elem := &c.stack[i]
	if elem.index > 0 {
	elem.index--
	break
	}
	c.stack = c.stack[:i]
	}

	// If we've hit the end then return nil.
	if len(c.stack) == 0 {
	return nil, nil
	}

	// Move down the stack to find the last element of the last leaf under this branch.
	c.last()
	k, v, flags := c.keyValue()
	if (flags & uint32(bucketLeafFlag)) != 0 {
	return k, nil
	}
	return k, v
	}

	// Seek moves the cursor to a given key and returns it.
	// If the key does not exist then the next key is used. If no keys
	// follow, a nil key is returned.
	// The returned key and value are only valid for the life of the transaction.
	func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
	k, v, flags := c.seek(seek)

	// If we ended up after the last element of a page then move to the next one.
	if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() {
	k, v, flags = c.next()
	}

	if k == nil {
	return nil, nil
	} else if (flags & uint32(bucketLeafFlag)) != 0 {
	return k, nil
	}
	return k, v
	}

	// Delete removes the current key/value under the cursor from the bucket.
	// Delete fails if current key/value is a bucket or if the transaction is not writable.
	func (c *Cursor) Delete() error {
	if c.bucket.tx.db == nil {
	return ErrTxClosed
	} else if !c.bucket.Writable() {
	return ErrTxNotWritable
	}

	key, _, flags := c.keyValue()
	// Return an error if current value is a bucket.
	if (flags & bucketLeafFlag) != 0 {
	return ErrIncompatibleValue
	}
	c.node().del(key)

	return nil
	}

	// seek moves the cursor to a given key and returns it.
	// If the key does not exist then the next key is used.
	func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
	_assert(c.bucket.tx.db != nil, "tx closed")

	// Start from root page/node and traverse to correct page.
	c.stack = c.stack[:0]
	c.search(seek, c.bucket.root)

	// If this is a bucket then return a nil value.
	return c.keyValue()
	}

	// first moves the cursor to the first leaf element under the last page in the stack.
	func (c *Cursor) first() {
	for {
	// Exit when we hit a leaf page.
	var ref = &c.stack[len(c.stack)-1]
	if ref.isLeaf() {
	break
	}

	// Keep adding pages pointing to the first element to the stack.
	var pgid pgid
	if ref.node != nil {
	pgid = ref.node.inodes[ref.index].pgid
	} else {
	pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
	}
	p, n := c.bucket.pageNode(pgid)
	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
	}
	}

	// last moves the cursor to the last leaf element under the last page in the stack.
	func (c *Cursor) last() {
	for {
	// Exit when we hit a leaf page.
	ref := &c.stack[len(c.stack)-1]
	if ref.isLeaf() {
	break
	}

	// Keep adding pages pointing to the last element in the stack.
	var pgid pgid
	if ref.node != nil {
	pgid = ref.node.inodes[ref.index].pgid
	} else {
	pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
	}
	p, n := c.bucket.pageNode(pgid)

	var nextRef = elemRef{page: p, node: n}
	nextRef.index = nextRef.count() - 1
	c.stack = append(c.stack, nextRef)
	}
	}

	// next moves to the next leaf element and returns the key and value.
	// If the cursor is at the last leaf element then it stays there and returns nil.
	func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
	for {
	// Attempt to move over one element until we're successful.
	// Move up the stack as we hit the end of each page in our stack.
	var i int
	for i = len(c.stack) - 1; i >= 0; i-- {
	elem := &c.stack[i]
	if elem.index < elem.count()-1 {
	elem.index++
	break
	}
	}

	// If we've hit the root page then stop and return. This will leave the
	// cursor on the last element of the last page.
	if i == -1 {
	return nil, nil, 0
	}

	// Otherwise start from where we left off in the stack and find the
	// first element of the first leaf page.
	c.stack = c.stack[:i+1]
	c.first()

	// If this is an empty page then restart and move back up the stack.
	// https://github.com/boltdb/bolt/issues/450
	if c.stack[len(c.stack)-1].count() == 0 {
	continue
	}

	return c.keyValue()
	}
	}

	// search recursively performs a binary search against a given page/node until it finds a given key.
	func (c *Cursor) search(key []byte, pgid pgid) {
	p, n := c.bucket.pageNode(pgid)
	if p != nil && (p.flags&(branchPageFlag\|leafPageFlag)) == 0 {
	panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
	}
	e := elemRef{page: p, node: n}
	c.stack = append(c.stack, e)

	// If we're on a leaf page/node then find the specific node.
	if e.isLeaf() {
	c.nsearch(key)
	return
	}

	if n != nil {
	c.searchNode(key, n)
	return
	}
	c.searchPage(key, p)
	}

	func (c Cursor) searchNode(key []byte, n node) {
	var exact bool
	index := sort.Search(len(n.inodes), func(i int) bool {
	// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
	// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
	ret := bytes.Compare(n.inodes[i].key, key)
	if ret == 0 {
	exact = true
	}
	return ret != -1
	})
	if !exact && index > 0 {
	index--
	}
	c.stack[len(c.stack)-1].index = index

	// Recursively search to the next page.
	c.search(key, n.inodes[index].pgid)
	}

	func (c Cursor) searchPage(key []byte, p page) {
	// Binary search for the correct range.
	inodes := p.branchPageElements()

	var exact bool
	index := sort.Search(int(p.count), func(i int) bool {
	// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
	// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
	ret := bytes.Compare(inodes[i].key(), key)
	if ret == 0 {
	exact = true
	}
	return ret != -1
	})
	if !exact && index > 0 {
	index--
	}
	c.stack[len(c.stack)-1].index = index

	// Recursively search to the next page.
	c.search(key, inodes[index].pgid)
	}

	// nsearch searches the leaf node on the top of the stack for a key.
	func (c *Cursor) nsearch(key []byte) {
	e := &c.stack[len(c.stack)-1]
	p, n := e.page, e.node

	// If we have a node then search its inodes.
	if n != nil {
	index := sort.Search(len(n.inodes), func(i int) bool {
	return bytes.Compare(n.inodes[i].key, key) != -1
	})
	e.index = index
	return
	}

	// If we have a page then search its leaf elements.
	inodes := p.leafPageElements()
	index := sort.Search(int(p.count), func(i int) bool {
	return bytes.Compare(inodes[i].key(), key) != -1
	})
	e.index = index
	}

	// keyValue returns the key and value of the current leaf element.
	func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
	ref := &c.stack[len(c.stack)-1]

	// If the cursor is pointing to the end of page/node then return nil.
	if ref.count() == 0 \|\| ref.index >= ref.count() {
	return nil, nil, 0
	}

	// Retrieve value from node.
	if ref.node != nil {
	inode := &ref.node.inodes[ref.index]
	return inode.key, inode.value, inode.flags
	}

	// Or retrieve value from page.
	elem := ref.page.leafPageElement(uint16(ref.index))
	return elem.key(), elem.value(), elem.flags
	}

	// node returns the node that the cursor is currently positioned on.
	func (c Cursor) node() node {
	_assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")

	// If the top of the stack is a leaf node then just return it.
	if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
	return ref.node
	}

	// Start from root and traverse down the hierarchy.
	var n = c.stack[0].node
	if n == nil {
	n = c.bucket.node(c.stack[0].page.id, nil)
	}
	for _, ref := range c.stack[:len(c.stack)-1] {
	_assert(!n.isLeaf, "expected branch node")
	n = n.childAt(int(ref.index))
	}
	_assert(n.isLeaf, "expected leaf node")
	return n
	}

	// elemRef represents a reference to an element on a given page/node.
	type elemRef struct {
	page *page
	node *node
	index int
	}

	// isLeaf returns whether the ref is pointing at a leaf page/node.
	func (r *elemRef) isLeaf() bool {
	if r.node != nil {
	return r.node.isLeaf
	}
	return (r.page.flags & leafPageFlag) != 0
	}

	// count returns the number of inodes or page elements.
	func (r *elemRef) count() int {
	if r.node != nil {
	return len(r.node.inodes)
	}
	return int(r.page.count)
	}