+++ /dev/null
-// Copyright (c) 2015-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 (
- "math/big"
- "sort"
- "sync"
- "time"
-
- "github.com/btcsuite/btcd/chaincfg"
- "github.com/btcsuite/btcd/chaincfg/chainhash"
- "github.com/btcsuite/btcd/database"
- "github.com/btcsuite/btcd/wire"
-)
-
-// blockNode represents a block within the block chain and is primarily used to
-// aid in selecting the best chain to be the main chain. The main chain is
-// stored into the block database.
-type blockNode struct {
- // NOTE: Additions, deletions, or modifications to the order of the
- // definitions in this struct should not be changed without considering
- // how it affects alignment on 64-bit platforms. The current order is
- // specifically crafted to result in minimal padding. There will be
- // hundreds of thousands of these in memory, so a few extra bytes of
- // padding adds up.
-
- // parent is the parent block for this node.
- parent *blockNode
-
- // hash is the double sha 256 of the block.
- hash chainhash.Hash
-
- // workSum is the total amount of work in the chain up to and including
- // this node.
- workSum *big.Int
-
- // height is the position in the block chain.
- height int32
-
- // Some fields from block headers to aid in best chain selection and
- // reconstructing headers from memory. These must be treated as
- // immutable and are intentionally ordered to avoid padding on 64-bit
- // platforms.
- version int32
- bits uint32
- nonce uint32
- timestamp int64
- merkleRoot chainhash.Hash
-}
-
-// initBlockNode initializes a block node from the given header and height. The
-// node is completely disconnected from the chain and the workSum value is just
-// the work for the passed block. The work sum must be updated accordingly when
-// the node is inserted into a chain.
-//
-// This function is NOT safe for concurrent access. It must only be called when
-// initially creating a node.
-func initBlockNode(node *blockNode, blockHeader *wire.BlockHeader, height int32) {
- *node = blockNode{
- hash: blockHeader.BlockHash(),
- workSum: CalcWork(blockHeader.Bits),
- height: height,
- version: blockHeader.Version,
- bits: blockHeader.Bits,
- nonce: blockHeader.Nonce,
- timestamp: blockHeader.Timestamp.Unix(),
- merkleRoot: blockHeader.MerkleRoot,
- }
-}
-
-// newBlockNode returns a new block node for the given block header. It is
-// completely disconnected from the chain and the workSum value is just the work
-// for the passed block. The work sum must be updated accordingly when the node
-// is inserted into a chain.
-func newBlockNode(blockHeader *wire.BlockHeader, height int32) *blockNode {
- var node blockNode
- initBlockNode(&node, blockHeader, height)
- return &node
-}
-
-// Header constructs a block header from the node and returns it.
-//
-// This function is safe for concurrent access.
-func (node *blockNode) Header() wire.BlockHeader {
- // No lock is needed because all accessed fields are immutable.
- prevHash := zeroHash
- if node.parent != nil {
- prevHash = &node.parent.hash
- }
- return wire.BlockHeader{
- Version: node.version,
- PrevBlock: *prevHash,
- MerkleRoot: node.merkleRoot,
- Timestamp: time.Unix(node.timestamp, 0),
- Bits: node.bits,
- Nonce: node.nonce,
- }
-}
-
-// Ancestor returns the ancestor block node at the provided height by following
-// the chain backwards from this node. The returned block will be nil when a
-// height is requested that is after the height of the passed node or is less
-// than zero.
-//
-// This function is safe for concurrent access.
-func (node *blockNode) Ancestor(height int32) *blockNode {
- if height < 0 || height > node.height {
- return nil
- }
-
- n := node
- for ; n != nil && n.height != height; n = n.parent {
- // Intentionally left blank
- }
-
- return n
-}
-
-// RelativeAncestor returns the ancestor block node a relative 'distance' blocks
-// before this node. This is equivalent to calling Ancestor with the node's
-// height minus provided distance.
-//
-// This function is safe for concurrent access.
-func (node *blockNode) RelativeAncestor(distance int32) *blockNode {
- return node.Ancestor(node.height - distance)
-}
-
-// CalcPastMedianTime calculates the median time of the previous few blocks
-// prior to, and including, the block node.
-//
-// This function is safe for concurrent access.
-func (node *blockNode) CalcPastMedianTime() time.Time {
- // Create a slice of the previous few block timestamps used to calculate
- // the median per the number defined by the constant medianTimeBlocks.
- timestamps := make([]int64, medianTimeBlocks)
- numNodes := 0
- iterNode := node
- for i := 0; i < medianTimeBlocks && iterNode != nil; i++ {
- timestamps[i] = iterNode.timestamp
- numNodes++
-
- iterNode = iterNode.parent
- }
-
- // Prune the slice to the actual number of available timestamps which
- // will be fewer than desired near the beginning of the block chain
- // and sort them.
- timestamps = timestamps[:numNodes]
- sort.Sort(timeSorter(timestamps))
-
- // NOTE: The consensus rules incorrectly calculate the median for even
- // numbers of blocks. A true median averages the middle two elements
- // for a set with an even number of elements in it. Since the constant
- // for the previous number of blocks to be used is odd, this is only an
- // issue for a few blocks near the beginning of the chain. I suspect
- // this is an optimization even though the result is slightly wrong for
- // a few of the first blocks since after the first few blocks, there
- // will always be an odd number of blocks in the set per the constant.
- //
- // This code follows suit to ensure the same rules are used, however, be
- // aware that should the medianTimeBlocks constant ever be changed to an
- // even number, this code will be wrong.
- medianTimestamp := timestamps[numNodes/2]
- return time.Unix(medianTimestamp, 0)
-}
-
-// blockIndex provides facilities for keeping track of an in-memory index of the
-// block chain. Although the name block chain suggests a single chain of
-// blocks, it is actually a tree-shaped structure where any node can have
-// multiple children. However, there can only be one active branch which does
-// indeed form a chain from the tip all the way back to the genesis block.
-type blockIndex struct {
- // The following fields are set when the instance is created and can't
- // be changed afterwards, so there is no need to protect them with a
- // separate mutex.
- db database.DB
- chainParams *chaincfg.Params
-
- sync.RWMutex
- index map[chainhash.Hash]*blockNode
-}
-
-// newBlockIndex returns a new empty instance of a block index. The index will
-// be dynamically populated as block nodes are loaded from the database and
-// manually added.
-func newBlockIndex(db database.DB, chainParams *chaincfg.Params) *blockIndex {
- return &blockIndex{
- db: db,
- chainParams: chainParams,
- index: make(map[chainhash.Hash]*blockNode),
- }
-}
-
-// HaveBlock returns whether or not the block index contains the provided hash.
-//
-// This function is safe for concurrent access.
-func (bi *blockIndex) HaveBlock(hash *chainhash.Hash) bool {
- bi.RLock()
- _, hasBlock := bi.index[*hash]
- bi.RUnlock()
- return hasBlock
-}
-
-// LookupNode returns the block node identified by the provided hash. It will
-// return nil if there is no entry for the hash.
-//
-// This function is safe for concurrent access.
-func (bi *blockIndex) LookupNode(hash *chainhash.Hash) *blockNode {
- bi.RLock()
- node := bi.index[*hash]
- bi.RUnlock()
- return node
-}
-
-// AddNode adds the provided node to the block index. Duplicate entries are not
-// checked so it is up to caller to avoid adding them.
-//
-// This function is safe for concurrent access.
-func (bi *blockIndex) AddNode(node *blockNode) {
- bi.Lock()
- bi.index[node.hash] = node
- bi.Unlock()
-}
-
-// RemoveNode removes the provided node from the block index. There is no check
-// whether another node in the index depends on this one, so it is up to caller
-// to avoid that situation.
-//
-// This function is safe for concurrent access.
-func (bi *blockIndex) RemoveNode(node *blockNode) {
- bi.Lock()
- delete(bi.index, node.hash)
- bi.Unlock()
-}
OSDN Git Service
