[VOL-5486] Fix deprecated versions
Change-Id: I3e03ea246020547ae75fa92ce8cf5cbba7e8f3bb
Signed-off-by: Abhay Kumar <abhay.kumar@radisys.com>
diff --git a/vendor/go.etcd.io/bbolt/bucket.go b/vendor/go.etcd.io/bbolt/bucket.go
new file mode 100644
index 0000000..6371ace
--- /dev/null
+++ b/vendor/go.etcd.io/bbolt/bucket.go
@@ -0,0 +1,1005 @@
+package bbolt
+
+import (
+ "bytes"
+ "fmt"
+ "unsafe"
+
+ "go.etcd.io/bbolt/errors"
+ "go.etcd.io/bbolt/internal/common"
+)
+
+const (
+ // MaxKeySize is the maximum length of a key, in bytes.
+ MaxKeySize = 32768
+
+ // MaxValueSize is the maximum length of a value, in bytes.
+ MaxValueSize = (1 << 31) - 2
+)
+
+const (
+ minFillPercent = 0.1
+ maxFillPercent = 1.0
+)
+
+// DefaultFillPercent is the percentage that split pages are filled.
+// This value can be changed by setting Bucket.FillPercent.
+const DefaultFillPercent = 0.5
+
+// Bucket represents a collection of key/value pairs inside the database.
+type Bucket struct {
+ *common.InBucket
+ tx *Tx // the associated transaction
+ buckets map[string]*Bucket // subbucket cache
+ page *common.Page // inline page reference
+ rootNode *node // materialized node for the root page.
+ nodes map[common.Pgid]*node // node cache
+
+ // Sets the threshold for filling nodes when they split. By default,
+ // the bucket will fill to 50% but it can be useful to increase this
+ // amount if you know that your write workloads are mostly append-only.
+ //
+ // This is non-persisted across transactions so it must be set in every Tx.
+ FillPercent float64
+}
+
+// newBucket returns a new bucket associated with a transaction.
+func newBucket(tx *Tx) Bucket {
+ var b = Bucket{tx: tx, FillPercent: DefaultFillPercent}
+ if tx.writable {
+ b.buckets = make(map[string]*Bucket)
+ b.nodes = make(map[common.Pgid]*node)
+ }
+ return b
+}
+
+// Tx returns the tx of the bucket.
+func (b *Bucket) Tx() *Tx {
+ return b.tx
+}
+
+// Root returns the root of the bucket.
+func (b *Bucket) Root() common.Pgid {
+ return b.RootPage()
+}
+
+// Writable returns whether the bucket is writable.
+func (b *Bucket) Writable() bool {
+ return b.tx.writable
+}
+
+// Cursor creates a cursor associated with the bucket.
+// The cursor is only valid as long as the transaction is open.
+// Do not use a cursor after the transaction is closed.
+func (b *Bucket) Cursor() *Cursor {
+ // Update transaction statistics.
+ b.tx.stats.IncCursorCount(1)
+
+ // Allocate and return a cursor.
+ return &Cursor{
+ bucket: b,
+ stack: make([]elemRef, 0),
+ }
+}
+
+// Bucket retrieves a nested bucket by name.
+// Returns nil if the bucket does not exist.
+// The bucket instance is only valid for the lifetime of the transaction.
+func (b *Bucket) Bucket(name []byte) *Bucket {
+ if b.buckets != nil {
+ if child := b.buckets[string(name)]; child != nil {
+ return child
+ }
+ }
+
+ // Move cursor to key.
+ c := b.Cursor()
+ k, v, flags := c.seek(name)
+
+ // Return nil if the key doesn't exist or it is not a bucket.
+ if !bytes.Equal(name, k) || (flags&common.BucketLeafFlag) == 0 {
+ return nil
+ }
+
+ // Otherwise create a bucket and cache it.
+ var child = b.openBucket(v)
+ if b.buckets != nil {
+ b.buckets[string(name)] = child
+ }
+
+ return child
+}
+
+// Helper method that re-interprets a sub-bucket value
+// from a parent into a Bucket
+func (b *Bucket) openBucket(value []byte) *Bucket {
+ var child = newBucket(b.tx)
+
+ // Unaligned access requires a copy to be made.
+ const unalignedMask = unsafe.Alignof(struct {
+ common.InBucket
+ common.Page
+ }{}) - 1
+ unaligned := uintptr(unsafe.Pointer(&value[0]))&unalignedMask != 0
+ if unaligned {
+ value = cloneBytes(value)
+ }
+
+ // If this is a writable transaction then we need to copy the bucket entry.
+ // Read-only transactions can point directly at the mmap entry.
+ if b.tx.writable && !unaligned {
+ child.InBucket = &common.InBucket{}
+ *child.InBucket = *(*common.InBucket)(unsafe.Pointer(&value[0]))
+ } else {
+ child.InBucket = (*common.InBucket)(unsafe.Pointer(&value[0]))
+ }
+
+ // Save a reference to the inline page if the bucket is inline.
+ if child.RootPage() == 0 {
+ child.page = (*common.Page)(unsafe.Pointer(&value[common.BucketHeaderSize]))
+ }
+
+ return &child
+}
+
+// CreateBucket creates a new bucket at the given key and returns the new bucket.
+// Returns an error if the key already exists, if the bucket name is blank, or if the bucket name is too long.
+// The bucket instance is only valid for the lifetime of the transaction.
+func (b *Bucket) CreateBucket(key []byte) (rb *Bucket, err error) {
+ if lg := b.tx.db.Logger(); lg != discardLogger {
+ lg.Debugf("Creating bucket %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Creating bucket %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Creating bucket %q successfully", key)
+ }
+ }()
+ }
+ if b.tx.db == nil {
+ return nil, errors.ErrTxClosed
+ } else if !b.tx.writable {
+ return nil, errors.ErrTxNotWritable
+ } else if len(key) == 0 {
+ return nil, errors.ErrBucketNameRequired
+ }
+
+ // Insert into node.
+ // Tip: Use a new variable `newKey` instead of reusing the existing `key` to prevent
+ // it from being marked as leaking, and accordingly cannot be allocated on stack.
+ newKey := cloneBytes(key)
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, _, flags := c.seek(newKey)
+
+ // Return an error if there is an existing key.
+ if bytes.Equal(newKey, k) {
+ if (flags & common.BucketLeafFlag) != 0 {
+ return nil, errors.ErrBucketExists
+ }
+ return nil, errors.ErrIncompatibleValue
+ }
+
+ // Create empty, inline bucket.
+ var bucket = Bucket{
+ InBucket: &common.InBucket{},
+ rootNode: &node{isLeaf: true},
+ FillPercent: DefaultFillPercent,
+ }
+ var value = bucket.write()
+
+ c.node().put(newKey, newKey, value, 0, common.BucketLeafFlag)
+
+ // Since subbuckets are not allowed on inline buckets, we need to
+ // dereference the inline page, if it exists. This will cause the bucket
+ // to be treated as a regular, non-inline bucket for the rest of the tx.
+ b.page = nil
+
+ return b.Bucket(newKey), nil
+}
+
+// CreateBucketIfNotExists creates a new bucket if it doesn't already exist and returns a reference to it.
+// Returns an error if the bucket name is blank, or if the bucket name is too long.
+// The bucket instance is only valid for the lifetime of the transaction.
+func (b *Bucket) CreateBucketIfNotExists(key []byte) (rb *Bucket, err error) {
+ if lg := b.tx.db.Logger(); lg != discardLogger {
+ lg.Debugf("Creating bucket if not exist %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Creating bucket if not exist %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Creating bucket if not exist %q successfully", key)
+ }
+ }()
+ }
+
+ if b.tx.db == nil {
+ return nil, errors.ErrTxClosed
+ } else if !b.tx.writable {
+ return nil, errors.ErrTxNotWritable
+ } else if len(key) == 0 {
+ return nil, errors.ErrBucketNameRequired
+ }
+
+ // Insert into node.
+ // Tip: Use a new variable `newKey` instead of reusing the existing `key` to prevent
+ // it from being marked as leaking, and accordingly cannot be allocated on stack.
+ newKey := cloneBytes(key)
+
+ if b.buckets != nil {
+ if child := b.buckets[string(newKey)]; child != nil {
+ return child, nil
+ }
+ }
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, v, flags := c.seek(newKey)
+
+ // Return an error if there is an existing non-bucket key.
+ if bytes.Equal(newKey, k) {
+ if (flags & common.BucketLeafFlag) != 0 {
+ var child = b.openBucket(v)
+ if b.buckets != nil {
+ b.buckets[string(newKey)] = child
+ }
+
+ return child, nil
+ }
+ return nil, errors.ErrIncompatibleValue
+ }
+
+ // Create empty, inline bucket.
+ var bucket = Bucket{
+ InBucket: &common.InBucket{},
+ rootNode: &node{isLeaf: true},
+ FillPercent: DefaultFillPercent,
+ }
+ var value = bucket.write()
+
+ c.node().put(newKey, newKey, value, 0, common.BucketLeafFlag)
+
+ // Since subbuckets are not allowed on inline buckets, we need to
+ // dereference the inline page, if it exists. This will cause the bucket
+ // to be treated as a regular, non-inline bucket for the rest of the tx.
+ b.page = nil
+
+ return b.Bucket(newKey), nil
+}
+
+// DeleteBucket deletes a bucket at the given key.
+// Returns an error if the bucket does not exist, or if the key represents a non-bucket value.
+func (b *Bucket) DeleteBucket(key []byte) (err error) {
+ if lg := b.tx.db.Logger(); lg != discardLogger {
+ lg.Debugf("Deleting bucket %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Deleting bucket %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Deleting bucket %q successfully", key)
+ }
+ }()
+ }
+
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ } else if !b.Writable() {
+ return errors.ErrTxNotWritable
+ }
+
+ newKey := cloneBytes(key)
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, _, flags := c.seek(newKey)
+
+ // Return an error if bucket doesn't exist or is not a bucket.
+ if !bytes.Equal(newKey, k) {
+ return errors.ErrBucketNotFound
+ } else if (flags & common.BucketLeafFlag) == 0 {
+ return errors.ErrIncompatibleValue
+ }
+
+ // Recursively delete all child buckets.
+ child := b.Bucket(newKey)
+ err = child.ForEachBucket(func(k []byte) error {
+ if err := child.DeleteBucket(k); err != nil {
+ return fmt.Errorf("delete bucket: %s", err)
+ }
+ return nil
+ })
+ if err != nil {
+ return err
+ }
+
+ // Remove cached copy.
+ delete(b.buckets, string(newKey))
+
+ // Release all bucket pages to freelist.
+ child.nodes = nil
+ child.rootNode = nil
+ child.free()
+
+ // Delete the node if we have a matching key.
+ c.node().del(newKey)
+
+ return nil
+}
+
+// MoveBucket moves a sub-bucket from the source bucket to the destination bucket.
+// Returns an error if
+// 1. the sub-bucket cannot be found in the source bucket;
+// 2. or the key already exists in the destination bucket;
+// 3. or the key represents a non-bucket value;
+// 4. the source and destination buckets are the same.
+func (b *Bucket) MoveBucket(key []byte, dstBucket *Bucket) (err error) {
+ lg := b.tx.db.Logger()
+ if lg != discardLogger {
+ lg.Debugf("Moving bucket %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Moving bucket %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Moving bucket %q successfully", key)
+ }
+ }()
+ }
+
+ if b.tx.db == nil || dstBucket.tx.db == nil {
+ return errors.ErrTxClosed
+ } else if !b.Writable() || !dstBucket.Writable() {
+ return errors.ErrTxNotWritable
+ }
+
+ if b.tx.db.Path() != dstBucket.tx.db.Path() || b.tx != dstBucket.tx {
+ lg.Errorf("The source and target buckets are not in the same db file, source bucket in %s and target bucket in %s", b.tx.db.Path(), dstBucket.tx.db.Path())
+ return errors.ErrDifferentDB
+ }
+
+ newKey := cloneBytes(key)
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, v, flags := c.seek(newKey)
+
+ // Return an error if bucket doesn't exist or is not a bucket.
+ if !bytes.Equal(newKey, k) {
+ return errors.ErrBucketNotFound
+ } else if (flags & common.BucketLeafFlag) == 0 {
+ lg.Errorf("An incompatible key %s exists in the source bucket", newKey)
+ return errors.ErrIncompatibleValue
+ }
+
+ // Do nothing (return true directly) if the source bucket and the
+ // destination bucket are actually the same bucket.
+ if b == dstBucket || (b.RootPage() == dstBucket.RootPage() && b.RootPage() != 0) {
+ lg.Errorf("The source bucket (%s) and the target bucket (%s) are the same bucket", b, dstBucket)
+ return errors.ErrSameBuckets
+ }
+
+ // check whether the key already exists in the destination bucket
+ curDst := dstBucket.Cursor()
+ k, _, flags = curDst.seek(newKey)
+
+ // Return an error if there is an existing key in the destination bucket.
+ if bytes.Equal(newKey, k) {
+ if (flags & common.BucketLeafFlag) != 0 {
+ return errors.ErrBucketExists
+ }
+ lg.Errorf("An incompatible key %s exists in the target bucket", newKey)
+ return errors.ErrIncompatibleValue
+ }
+
+ // remove the sub-bucket from the source bucket
+ delete(b.buckets, string(newKey))
+ c.node().del(newKey)
+
+ // add te sub-bucket to the destination bucket
+ newValue := cloneBytes(v)
+ curDst.node().put(newKey, newKey, newValue, 0, common.BucketLeafFlag)
+
+ return nil
+}
+
+// Inspect returns the structure of the bucket.
+func (b *Bucket) Inspect() BucketStructure {
+ return b.recursivelyInspect([]byte("root"))
+}
+
+func (b *Bucket) recursivelyInspect(name []byte) BucketStructure {
+ bs := BucketStructure{Name: string(name)}
+
+ keyN := 0
+ c := b.Cursor()
+ for k, _, flags := c.first(); k != nil; k, _, flags = c.next() {
+ if flags&common.BucketLeafFlag != 0 {
+ childBucket := b.Bucket(k)
+ childBS := childBucket.recursivelyInspect(k)
+ bs.Children = append(bs.Children, childBS)
+ } else {
+ keyN++
+ }
+ }
+ bs.KeyN = keyN
+
+ return bs
+}
+
+// Get retrieves the value for a key in the bucket.
+// Returns a nil value if the key does not exist or if the key is a nested bucket.
+// The returned value is only valid for the life of the transaction.
+// The returned memory is owned by bbolt and must never be modified; writing to this memory might corrupt the database.
+func (b *Bucket) Get(key []byte) []byte {
+ k, v, flags := b.Cursor().seek(key)
+
+ // Return nil if this is a bucket.
+ if (flags & common.BucketLeafFlag) != 0 {
+ return nil
+ }
+
+ // If our target node isn't the same key as what's passed in then return nil.
+ if !bytes.Equal(key, k) {
+ return nil
+ }
+ return v
+}
+
+// Put sets the value for a key in the bucket.
+// If the key exist then its previous value will be overwritten.
+// Supplied value must remain valid for the life of the transaction.
+// Returns an error if the bucket was created from a read-only transaction, if the key is blank, if the key is too large, or if the value is too large.
+func (b *Bucket) Put(key []byte, value []byte) (err error) {
+ if lg := b.tx.db.Logger(); lg != discardLogger {
+ lg.Debugf("Putting key %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Putting key %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Putting key %q successfully", key)
+ }
+ }()
+ }
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ } else if !b.Writable() {
+ return errors.ErrTxNotWritable
+ } else if len(key) == 0 {
+ return errors.ErrKeyRequired
+ } else if len(key) > MaxKeySize {
+ return errors.ErrKeyTooLarge
+ } else if int64(len(value)) > MaxValueSize {
+ return errors.ErrValueTooLarge
+ }
+
+ // Insert into node.
+ // Tip: Use a new variable `newKey` instead of reusing the existing `key` to prevent
+ // it from being marked as leaking, and accordingly cannot be allocated on stack.
+ newKey := cloneBytes(key)
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, _, flags := c.seek(newKey)
+
+ // Return an error if there is an existing key with a bucket value.
+ if bytes.Equal(newKey, k) && (flags&common.BucketLeafFlag) != 0 {
+ return errors.ErrIncompatibleValue
+ }
+
+ // gofail: var beforeBucketPut struct{}
+
+ c.node().put(newKey, newKey, value, 0, 0)
+
+ return nil
+}
+
+// Delete removes a key from the bucket.
+// If the key does not exist then nothing is done and a nil error is returned.
+// Returns an error if the bucket was created from a read-only transaction.
+func (b *Bucket) Delete(key []byte) (err error) {
+ if lg := b.tx.db.Logger(); lg != discardLogger {
+ lg.Debugf("Deleting key %q", key)
+ defer func() {
+ if err != nil {
+ lg.Errorf("Deleting key %q failed: %v", key, err)
+ } else {
+ lg.Debugf("Deleting key %q successfully", key)
+ }
+ }()
+ }
+
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ } else if !b.Writable() {
+ return errors.ErrTxNotWritable
+ }
+
+ // Move cursor to correct position.
+ c := b.Cursor()
+ k, _, flags := c.seek(key)
+
+ // Return nil if the key doesn't exist.
+ if !bytes.Equal(key, k) {
+ return nil
+ }
+
+ // Return an error if there is already existing bucket value.
+ if (flags & common.BucketLeafFlag) != 0 {
+ return errors.ErrIncompatibleValue
+ }
+
+ // Delete the node if we have a matching key.
+ c.node().del(key)
+
+ return nil
+}
+
+// Sequence returns the current integer for the bucket without incrementing it.
+func (b *Bucket) Sequence() uint64 {
+ return b.InSequence()
+}
+
+// SetSequence updates the sequence number for the bucket.
+func (b *Bucket) SetSequence(v uint64) error {
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ } else if !b.Writable() {
+ return errors.ErrTxNotWritable
+ }
+
+ // Materialize the root node if it hasn't been already so that the
+ // bucket will be saved during commit.
+ if b.rootNode == nil {
+ _ = b.node(b.RootPage(), nil)
+ }
+
+ // Set the sequence.
+ b.SetInSequence(v)
+ return nil
+}
+
+// NextSequence returns an autoincrementing integer for the bucket.
+func (b *Bucket) NextSequence() (uint64, error) {
+ if b.tx.db == nil {
+ return 0, errors.ErrTxClosed
+ } else if !b.Writable() {
+ return 0, errors.ErrTxNotWritable
+ }
+
+ // Materialize the root node if it hasn't been already so that the
+ // bucket will be saved during commit.
+ if b.rootNode == nil {
+ _ = b.node(b.RootPage(), nil)
+ }
+
+ // Increment and return the sequence.
+ b.IncSequence()
+ return b.Sequence(), nil
+}
+
+// ForEach executes a function for each key/value pair in a bucket.
+// Because ForEach uses a Cursor, the iteration over keys is in lexicographical order.
+// If the provided function returns an error then the iteration is stopped and
+// the error is returned to the caller. The provided function must not modify
+// the bucket; this will result in undefined behavior.
+func (b *Bucket) ForEach(fn func(k, v []byte) error) error {
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ }
+ c := b.Cursor()
+ for k, v := c.First(); k != nil; k, v = c.Next() {
+ if err := fn(k, v); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+func (b *Bucket) ForEachBucket(fn func(k []byte) error) error {
+ if b.tx.db == nil {
+ return errors.ErrTxClosed
+ }
+ c := b.Cursor()
+ for k, _, flags := c.first(); k != nil; k, _, flags = c.next() {
+ if flags&common.BucketLeafFlag != 0 {
+ if err := fn(k); err != nil {
+ return err
+ }
+ }
+ }
+ return nil
+}
+
+// Stats returns stats on a bucket.
+func (b *Bucket) Stats() BucketStats {
+ var s, subStats BucketStats
+ pageSize := b.tx.db.pageSize
+ s.BucketN += 1
+ if b.RootPage() == 0 {
+ s.InlineBucketN += 1
+ }
+ b.forEachPage(func(p *common.Page, depth int, pgstack []common.Pgid) {
+ if p.IsLeafPage() {
+ s.KeyN += int(p.Count())
+
+ // used totals the used bytes for the page
+ used := common.PageHeaderSize
+
+ if p.Count() != 0 {
+ // If page has any elements, add all element headers.
+ used += common.LeafPageElementSize * uintptr(p.Count()-1)
+
+ // Add all element key, value sizes.
+ // The computation takes advantage of the fact that the position
+ // of the last element's key/value equals to the total of the sizes
+ // of all previous elements' keys and values.
+ // It also includes the last element's header.
+ lastElement := p.LeafPageElement(p.Count() - 1)
+ used += uintptr(lastElement.Pos() + lastElement.Ksize() + lastElement.Vsize())
+ }
+
+ if b.RootPage() == 0 {
+ // For inlined bucket just update the inline stats
+ s.InlineBucketInuse += int(used)
+ } else {
+ // For non-inlined bucket update all the leaf stats
+ s.LeafPageN++
+ s.LeafInuse += int(used)
+ s.LeafOverflowN += int(p.Overflow())
+
+ // Collect stats from sub-buckets.
+ // Do that by iterating over all element headers
+ // looking for the ones with the bucketLeafFlag.
+ for i := uint16(0); i < p.Count(); i++ {
+ e := p.LeafPageElement(i)
+ if (e.Flags() & common.BucketLeafFlag) != 0 {
+ // For any bucket element, open the element value
+ // and recursively call Stats on the contained bucket.
+ subStats.Add(b.openBucket(e.Value()).Stats())
+ }
+ }
+ }
+ } else if p.IsBranchPage() {
+ s.BranchPageN++
+ lastElement := p.BranchPageElement(p.Count() - 1)
+
+ // used totals the used bytes for the page
+ // Add header and all element headers.
+ used := common.PageHeaderSize + (common.BranchPageElementSize * uintptr(p.Count()-1))
+
+ // Add size of all keys and values.
+ // Again, use the fact that last element's position equals to
+ // the total of key, value sizes of all previous elements.
+ used += uintptr(lastElement.Pos() + lastElement.Ksize())
+ s.BranchInuse += int(used)
+ s.BranchOverflowN += int(p.Overflow())
+ }
+
+ // Keep track of maximum page depth.
+ if depth+1 > s.Depth {
+ s.Depth = depth + 1
+ }
+ })
+
+ // Alloc stats can be computed from page counts and pageSize.
+ s.BranchAlloc = (s.BranchPageN + s.BranchOverflowN) * pageSize
+ s.LeafAlloc = (s.LeafPageN + s.LeafOverflowN) * pageSize
+
+ // Add the max depth of sub-buckets to get total nested depth.
+ s.Depth += subStats.Depth
+ // Add the stats for all sub-buckets
+ s.Add(subStats)
+ return s
+}
+
+// forEachPage iterates over every page in a bucket, including inline pages.
+func (b *Bucket) forEachPage(fn func(*common.Page, int, []common.Pgid)) {
+ // If we have an inline page then just use that.
+ if b.page != nil {
+ fn(b.page, 0, []common.Pgid{b.RootPage()})
+ return
+ }
+
+ // Otherwise traverse the page hierarchy.
+ b.tx.forEachPage(b.RootPage(), fn)
+}
+
+// forEachPageNode iterates over every page (or node) in a bucket.
+// This also includes inline pages.
+func (b *Bucket) forEachPageNode(fn func(*common.Page, *node, int)) {
+ // If we have an inline page or root node then just use that.
+ if b.page != nil {
+ fn(b.page, nil, 0)
+ return
+ }
+ b._forEachPageNode(b.RootPage(), 0, fn)
+}
+
+func (b *Bucket) _forEachPageNode(pgId common.Pgid, depth int, fn func(*common.Page, *node, int)) {
+ var p, n = b.pageNode(pgId)
+
+ // Execute function.
+ fn(p, n, depth)
+
+ // Recursively loop over children.
+ if p != nil {
+ if p.IsBranchPage() {
+ for i := 0; i < int(p.Count()); i++ {
+ elem := p.BranchPageElement(uint16(i))
+ b._forEachPageNode(elem.Pgid(), depth+1, fn)
+ }
+ }
+ } else {
+ if !n.isLeaf {
+ for _, inode := range n.inodes {
+ b._forEachPageNode(inode.Pgid(), depth+1, fn)
+ }
+ }
+ }
+}
+
+// spill writes all the nodes for this bucket to dirty pages.
+func (b *Bucket) spill() error {
+ // Spill all child buckets first.
+ for name, child := range b.buckets {
+ // If the child bucket is small enough and it has no child buckets then
+ // write it inline into the parent bucket's page. Otherwise spill it
+ // like a normal bucket and make the parent value a pointer to the page.
+ var value []byte
+ if child.inlineable() {
+ child.free()
+ value = child.write()
+ } else {
+ if err := child.spill(); err != nil {
+ return err
+ }
+
+ // Update the child bucket header in this bucket.
+ value = make([]byte, unsafe.Sizeof(common.InBucket{}))
+ var bucket = (*common.InBucket)(unsafe.Pointer(&value[0]))
+ *bucket = *child.InBucket
+ }
+
+ // Skip writing the bucket if there are no materialized nodes.
+ if child.rootNode == nil {
+ continue
+ }
+
+ // Update parent node.
+ var c = b.Cursor()
+ k, _, flags := c.seek([]byte(name))
+ if !bytes.Equal([]byte(name), k) {
+ panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
+ }
+ if flags&common.BucketLeafFlag == 0 {
+ panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
+ }
+ c.node().put([]byte(name), []byte(name), value, 0, common.BucketLeafFlag)
+ }
+
+ // Ignore if there's not a materialized root node.
+ if b.rootNode == nil {
+ return nil
+ }
+
+ // Spill nodes.
+ if err := b.rootNode.spill(); err != nil {
+ return err
+ }
+ b.rootNode = b.rootNode.root()
+
+ // Update the root node for this bucket.
+ if b.rootNode.pgid >= b.tx.meta.Pgid() {
+ panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.Pgid()))
+ }
+ b.SetRootPage(b.rootNode.pgid)
+
+ return nil
+}
+
+// inlineable returns true if a bucket is small enough to be written inline
+// and if it contains no subbuckets. Otherwise, returns false.
+func (b *Bucket) inlineable() bool {
+ var n = b.rootNode
+
+ // Bucket must only contain a single leaf node.
+ if n == nil || !n.isLeaf {
+ return false
+ }
+
+ // Bucket is not inlineable if it contains subbuckets or if it goes beyond
+ // our threshold for inline bucket size.
+ var size = common.PageHeaderSize
+ for _, inode := range n.inodes {
+ size += common.LeafPageElementSize + uintptr(len(inode.Key())) + uintptr(len(inode.Value()))
+
+ if inode.Flags()&common.BucketLeafFlag != 0 {
+ return false
+ } else if size > b.maxInlineBucketSize() {
+ return false
+ }
+ }
+
+ return true
+}
+
+// Returns the maximum total size of a bucket to make it a candidate for inlining.
+func (b *Bucket) maxInlineBucketSize() uintptr {
+ return uintptr(b.tx.db.pageSize / 4)
+}
+
+// write allocates and writes a bucket to a byte slice.
+func (b *Bucket) write() []byte {
+ // Allocate the appropriate size.
+ var n = b.rootNode
+ var value = make([]byte, common.BucketHeaderSize+n.size())
+
+ // Write a bucket header.
+ var bucket = (*common.InBucket)(unsafe.Pointer(&value[0]))
+ *bucket = *b.InBucket
+
+ // Convert byte slice to a fake page and write the root node.
+ var p = (*common.Page)(unsafe.Pointer(&value[common.BucketHeaderSize]))
+ n.write(p)
+
+ return value
+}
+
+// rebalance attempts to balance all nodes.
+func (b *Bucket) rebalance() {
+ for _, n := range b.nodes {
+ n.rebalance()
+ }
+ for _, child := range b.buckets {
+ child.rebalance()
+ }
+}
+
+// node creates a node from a page and associates it with a given parent.
+func (b *Bucket) node(pgId common.Pgid, parent *node) *node {
+ common.Assert(b.nodes != nil, "nodes map expected")
+
+ // Retrieve node if it's already been created.
+ if n := b.nodes[pgId]; n != nil {
+ return n
+ }
+
+ // Otherwise create a node and cache it.
+ n := &node{bucket: b, parent: parent}
+ if parent == nil {
+ b.rootNode = n
+ } else {
+ parent.children = append(parent.children, n)
+ }
+
+ // Use the inline page if this is an inline bucket.
+ var p = b.page
+ if p == nil {
+ p = b.tx.page(pgId)
+ } else {
+ // if p isn't nil, then it's an inline bucket.
+ // The pgId must be 0 in this case.
+ common.Verify(func() {
+ common.Assert(pgId == 0, "The page ID (%d) isn't 0 for an inline bucket", pgId)
+ })
+ }
+
+ // Read the page into the node and cache it.
+ n.read(p)
+ b.nodes[pgId] = n
+
+ // Update statistics.
+ b.tx.stats.IncNodeCount(1)
+
+ return n
+}
+
+// free recursively frees all pages in the bucket.
+func (b *Bucket) free() {
+ if b.RootPage() == 0 {
+ return
+ }
+
+ var tx = b.tx
+ b.forEachPageNode(func(p *common.Page, n *node, _ int) {
+ if p != nil {
+ tx.db.freelist.Free(tx.meta.Txid(), p)
+ } else {
+ n.free()
+ }
+ })
+ b.SetRootPage(0)
+}
+
+// dereference removes all references to the old mmap.
+func (b *Bucket) dereference() {
+ if b.rootNode != nil {
+ b.rootNode.root().dereference()
+ }
+
+ for _, child := range b.buckets {
+ child.dereference()
+ }
+}
+
+// pageNode returns the in-memory node, if it exists.
+// Otherwise, returns the underlying page.
+func (b *Bucket) pageNode(id common.Pgid) (*common.Page, *node) {
+ // Inline buckets have a fake page embedded in their value so treat them
+ // differently. We'll return the rootNode (if available) or the fake page.
+ if b.RootPage() == 0 {
+ if id != 0 {
+ panic(fmt.Sprintf("inline bucket non-zero page access(2): %d != 0", id))
+ }
+ if b.rootNode != nil {
+ return nil, b.rootNode
+ }
+ return b.page, nil
+ }
+
+ // Check the node cache for non-inline buckets.
+ if b.nodes != nil {
+ if n := b.nodes[id]; n != nil {
+ return nil, n
+ }
+ }
+
+ // Finally lookup the page from the transaction if no node is materialized.
+ return b.tx.page(id), nil
+}
+
+// BucketStats records statistics about resources used by a bucket.
+type BucketStats struct {
+ // Page count statistics.
+ BranchPageN int // number of logical branch pages
+ BranchOverflowN int // number of physical branch overflow pages
+ LeafPageN int // number of logical leaf pages
+ LeafOverflowN int // number of physical leaf overflow pages
+
+ // Tree statistics.
+ KeyN int // number of keys/value pairs
+ Depth int // number of levels in B+tree
+
+ // Page size utilization.
+ BranchAlloc int // bytes allocated for physical branch pages
+ BranchInuse int // bytes actually used for branch data
+ LeafAlloc int // bytes allocated for physical leaf pages
+ LeafInuse int // bytes actually used for leaf data
+
+ // Bucket statistics
+ BucketN int // total number of buckets including the top bucket
+ InlineBucketN int // total number on inlined buckets
+ InlineBucketInuse int // bytes used for inlined buckets (also accounted for in LeafInuse)
+}
+
+func (s *BucketStats) Add(other BucketStats) {
+ s.BranchPageN += other.BranchPageN
+ s.BranchOverflowN += other.BranchOverflowN
+ s.LeafPageN += other.LeafPageN
+ s.LeafOverflowN += other.LeafOverflowN
+ s.KeyN += other.KeyN
+ if s.Depth < other.Depth {
+ s.Depth = other.Depth
+ }
+ s.BranchAlloc += other.BranchAlloc
+ s.BranchInuse += other.BranchInuse
+ s.LeafAlloc += other.LeafAlloc
+ s.LeafInuse += other.LeafInuse
+
+ s.BucketN += other.BucketN
+ s.InlineBucketN += other.InlineBucketN
+ s.InlineBucketInuse += other.InlineBucketInuse
+}
+
+// cloneBytes returns a copy of a given slice.
+func cloneBytes(v []byte) []byte {
+ var clone = make([]byte, len(v))
+ copy(clone, v)
+ return clone
+}
+
+type BucketStructure struct {
+ Name string `json:"name"` // name of the bucket
+ KeyN int `json:"keyN"` // number of key/value pairs
+ Children []BucketStructure `json:"buckets,omitempty"` // child buckets
+}