Merge pull request #41 from Bytom/dev

[bytom/vapor.git] / vendor / github.com / btcsuite / btcd / blockchain / chainview.go

// Copyright (c) 2017 The btcsuite developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.

package blockchain

import (
        "sync"
)

// approxNodesPerWeek is an approximation of the number of new blocks there are
// in a week on average.
const approxNodesPerWeek = 6 * 24 * 7

// log2FloorMasks defines the masks to use when quickly calculating
// floor(log2(x)) in a constant log2(32) = 5 steps, where x is a uint32, using
// shifts.  They are derived from (2^(2^x) - 1) * (2^(2^x)), for x in 4..0.
var log2FloorMasks = []uint32{0xffff0000, 0xff00, 0xf0, 0xc, 0x2}

// fastLog2Floor calculates and returns floor(log2(x)) in a constant 5 steps.
func fastLog2Floor(n uint32) uint8 {
        rv := uint8(0)
        exponent := uint8(16)
        for i := 0; i < 5; i++ {
                if n&log2FloorMasks[i] != 0 {
                        rv += exponent
                        n >>= exponent
                }
                exponent >>= 1
        }
        return rv
}

// chainView provides a flat view of a specific branch of the block chain from
// its tip back to the genesis block and provides various convenience functions
// for comparing chains.
//
// For example, assume a block chain with a side chain as depicted below:
//   genesis -> 1 -> 2 -> 3 -> 4  -> 5 ->  6  -> 7  -> 8
//                         \-> 4a -> 5a -> 6a
//
// The chain view for the branch ending in 6a consists of:
//   genesis -> 1 -> 2 -> 3 -> 4a -> 5a -> 6a
type chainView struct {
        mtx   sync.Mutex
        nodes []*blockNode
}

// newChainView returns a new chain view for the given tip block node.  Passing
// nil as the tip will result in a chain view that is not initialized.  The tip
// can be updated at any time via the setTip function.
func newChainView(tip *blockNode) *chainView {
        // The mutex is intentionally not held since this is a constructor.
        var c chainView
        c.setTip(tip)
        return &c
}

// genesis returns the genesis block for the chain view.  This only differs from
// the exported version in that it is up to the caller to ensure the lock is
// held.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) genesis() *blockNode {
        if len(c.nodes) == 0 {
                return nil
        }

        return c.nodes[0]
}

// Genesis returns the genesis block for the chain view.
//
// This function is safe for concurrent access.
func (c *chainView) Genesis() *blockNode {
        c.mtx.Lock()
        genesis := c.genesis()
        c.mtx.Unlock()
        return genesis
}

// tip returns the current tip block node for the chain view.  It will return
// nil if there is no tip.  This only differs from the exported version in that
// it is up to the caller to ensure the lock is held.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) tip() *blockNode {
        if len(c.nodes) == 0 {
                return nil
        }

        return c.nodes[len(c.nodes)-1]
}

// Tip returns the current tip block node for the chain view.  It will return
// nil if there is no tip.
//
// This function is safe for concurrent access.
func (c *chainView) Tip() *blockNode {
        c.mtx.Lock()
        tip := c.tip()
        c.mtx.Unlock()
        return tip
}

// setTip sets the chain view to use the provided block node as the current tip
// and ensures the view is consistent by populating it with the nodes obtained
// by walking backwards all the way to genesis block as necessary.  Further
// calls will only perform the minimum work needed, so switching between chain
// tips is efficient.  This only differs from the exported version in that it is
// up to the caller to ensure the lock is held.
//
// This function MUST be called with the view mutex locked (for writes).
func (c *chainView) setTip(node *blockNode) {
        if node == nil {
                // Keep the backing array around for potential future use.
                c.nodes = c.nodes[:0]
                return
        }

        // Create or resize the slice that will hold the block nodes to the
        // provided tip height.  When creating the slice, it is created with
        // some additional capacity for the underlying array as append would do
        // in order to reduce overhead when extending the chain later.  As long
        // as the underlying array already has enough capacity, simply expand or
        // contract the slice accordingly.  The additional capacity is chosen
        // such that the array should only have to be extended about once a
        // week.
        needed := node.height + 1
        if int32(cap(c.nodes)) < needed {
                nodes := make([]*blockNode, needed, needed+approxNodesPerWeek)
                copy(nodes, c.nodes)
                c.nodes = nodes
        } else {
                prevLen := int32(len(c.nodes))
                c.nodes = c.nodes[0:needed]
                for i := prevLen; i < needed; i++ {
                        c.nodes[i] = nil
                }
        }

        for node != nil && c.nodes[node.height] != node {
                c.nodes[node.height] = node
                node = node.parent
        }
}

// SetTip sets the chain view to use the provided block node as the current tip
// and ensures the view is consistent by populating it with the nodes obtained
// by walking backwards all the way to genesis block as necessary.  Further
// calls will only perform the minimum work needed, so switching between chain
// tips is efficient.
//
// This function is safe for concurrent access.
func (c *chainView) SetTip(node *blockNode) {
        c.mtx.Lock()
        c.setTip(node)
        c.mtx.Unlock()
}

// height returns the height of the tip of the chain view.  It will return -1 if
// there is no tip (which only happens if the chain view has not been
// initialized).  This only differs from the exported version in that it is up
// to the caller to ensure the lock is held.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) height() int32 {
        return int32(len(c.nodes) - 1)
}

// Height returns the height of the tip of the chain view.  It will return -1 if
// there is no tip (which only happens if the chain view has not been
// initialized).
//
// This function is safe for concurrent access.
func (c *chainView) Height() int32 {
        c.mtx.Lock()
        height := c.height()
        c.mtx.Unlock()
        return height
}

// nodeByHeight returns the block node at the specified height.  Nil will be
// returned if the height does not exist.  This only differs from the exported
// version in that it is up to the caller to ensure the lock is held.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) nodeByHeight(height int32) *blockNode {
        if height < 0 || height >= int32(len(c.nodes)) {
                return nil
        }

        return c.nodes[height]
}

// NodeByHeight returns the block node at the specified height.  Nil will be
// returned if the height does not exist.
//
// This function is safe for concurrent access.
func (c *chainView) NodeByHeight(height int32) *blockNode {
        c.mtx.Lock()
        node := c.nodeByHeight(height)
        c.mtx.Unlock()
        return node
}

// Equals returns whether or not two chain views are the same.  Uninitialized
// views (tip set to nil) are considered equal.
//
// This function is safe for concurrent access.
func (c *chainView) Equals(other *chainView) bool {
        c.mtx.Lock()
        other.mtx.Lock()
        equals := len(c.nodes) == len(other.nodes) && c.tip() == other.tip()
        other.mtx.Unlock()
        c.mtx.Unlock()
        return equals
}

// contains returns whether or not the chain view contains the passed block
// node.  This only differs from the exported version in that it is up to the
// caller to ensure the lock is held.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) contains(node *blockNode) bool {
        return c.nodeByHeight(node.height) == node
}

// Contains returns whether or not the chain view contains the passed block
// node.
//
// This function is safe for concurrent access.
func (c *chainView) Contains(node *blockNode) bool {
        c.mtx.Lock()
        contains := c.contains(node)
        c.mtx.Unlock()
        return contains
}

// next returns the successor to the provided node for the chain view.  It will
// return nil if there is no successor or the provided node is not part of the
// view.  This only differs from the exported version in that it is up to the
// caller to ensure the lock is held.
//
// See the comment on the exported function for more details.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) next(node *blockNode) *blockNode {
        if node == nil || !c.contains(node) {
                return nil
        }

        return c.nodeByHeight(node.height + 1)
}

// Next returns the successor to the provided node for the chain view.  It will
// return nil if there is no successfor or the provided node is not part of the
// view.
//
// For example, assume a block chain with a side chain as depicted below:
//   genesis -> 1 -> 2 -> 3 -> 4  -> 5 ->  6  -> 7  -> 8
//                         \-> 4a -> 5a -> 6a
//
// Further, assume the view is for the longer chain depicted above.  That is to
// say it consists of:
//   genesis -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
//
// Invoking this function with block node 5 would return block node 6 while
// invoking it with block node 5a would return nil since that node is not part
// of the view.
//
// This function is safe for concurrent access.
func (c *chainView) Next(node *blockNode) *blockNode {
        c.mtx.Lock()
        next := c.next(node)
        c.mtx.Unlock()
        return next
}

// findFork returns the final common block between the provided node and the
// the chain view.  It will return nil if there is no common block.  This only
// differs from the exported version in that it is up to the caller to ensure
// the lock is held.
//
// See the exported FindFork comments for more details.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) findFork(node *blockNode) *blockNode {
        // No fork point for node that doesn't exist.
        if node == nil {
                return nil
        }

        // When the height of the passed node is higher than the height of the
        // tip of the current chain view, walk backwards through the nodes of
        // the other chain until the heights match (or there or no more nodes in
        // which case there is no common node between the two).
        //
        // NOTE: This isn't strictly necessary as the following section will
        // find the node as well, however, it is more efficient to avoid the
        // contains check since it is already known that the common node can't
        // possibly be past the end of the current chain view.  It also allows
        // this code to take advantage of any potential future optimizations to
        // the Ancestor function such as using an O(log n) skip list.
        chainHeight := c.height()
        if node.height > chainHeight {
                node = node.Ancestor(chainHeight)
        }

        // Walk the other chain backwards as long as the current one does not
        // contain the node or there are no more nodes in which case there is no
        // common node between the two.
        for node != nil && !c.contains(node) {
                node = node.parent
        }

        return node
}

// FindFork returns the final common block between the provided node and the
// the chain view.  It will return nil if there is no common block.
//
// For example, assume a block chain with a side chain as depicted below:
//   genesis -> 1 -> 2 -> ... -> 5 -> 6  -> 7  -> 8
//                                \-> 6a -> 7a
//
// Further, assume the view is for the longer chain depicted above.  That is to
// say it consists of:
//   genesis -> 1 -> 2 -> ... -> 5 -> 6 -> 7 -> 8.
//
// Invoking this function with block node 7a would return block node 5 while
// invoking it with block node 7 would return itself since it is already part of
// the branch formed by the view.
//
// This function is safe for concurrent access.
func (c *chainView) FindFork(node *blockNode) *blockNode {
        c.mtx.Lock()
        fork := c.findFork(node)
        c.mtx.Unlock()
        return fork
}

// blockLocator returns a block locator for the passed block node.  The passed
// node can be nil in which case the block locator for the current tip
// associated with the view will be returned.  This only differs from the
// exported version in that it is up to the caller to ensure the lock is held.
//
// See the exported BlockLocator function comments for more details.
//
// This function MUST be called with the view mutex locked (for reads).
func (c *chainView) blockLocator(node *blockNode) BlockLocator {
        // Use the current tip if requested.
        if node == nil {
                node = c.tip()
        }
        if node == nil {
                return nil
        }

        // Calculate the max number of entries that will ultimately be in the
        // block locator.  See the description of the algorithm for how these
        // numbers are derived.
        var maxEntries uint8
        if node.height <= 12 {
                maxEntries = uint8(node.height) + 1
        } else {
                // Requested hash itself + previous 10 entries + genesis block.
                // Then floor(log2(height-10)) entries for the skip portion.
                adjustedHeight := uint32(node.height) - 10
                maxEntries = 12 + fastLog2Floor(adjustedHeight)
        }
        locator := make(BlockLocator, 0, maxEntries)

        step := int32(1)
        for node != nil {
                locator = append(locator, &node.hash)

                // Nothing more to add once the genesis block has been added.
                if node.height == 0 {
                        break
                }

                // Calculate height of previous node to include ensuring the
                // final node is the genesis block.
                height := node.height - step
                if height < 0 {
                        height = 0
                }

                // When the node is in the current chain view, all of its
                // ancestors must be too, so use a much faster O(1) lookup in
                // that case.  Otherwise, fall back to walking backwards through
                // the nodes of the other chain to the correct ancestor.
                if c.contains(node) {
                        node = c.nodes[height]
                } else {
                        node = node.Ancestor(height)
                }

                // Once 11 entries have been included, start doubling the
                // distance between included hashes.
                if len(locator) > 10 {
                        step *= 2
                }
        }

        return locator
}

// BlockLocator returns a block locator for the passed block node.  The passed
// node can be nil in which case the block locator for the current tip
// associated with the view will be returned.
//
// See the BlockLocator type for details on the algorithm used to create a block
// locator.
//
// This function is safe for concurrent access.
func (c *chainView) BlockLocator(node *blockNode) BlockLocator {
        c.mtx.Lock()
        locator := c.blockLocator(node)
        c.mtx.Unlock()
        return locator
}