protocol/state/blockindex.go

   1 package state
   2
   3 import (
   4         "errors"
   5         "sort"
   6         "sync"
   7
   8         "github.com/vapor/common"
   9         "github.com/vapor/consensus"
  10         "github.com/vapor/protocol/bc"
  11         "github.com/vapor/protocol/bc/types"
  12 )
  13
  14 // approxNodesPerDay is an approximation of the number of new blocks there are
  15 // in a day on average.
  16 const approxNodesPerDay = 24 * 24
  17
  18 // BlockNode represents a block within the block chain and is primarily used to
  19 // aid in selecting the best chain to be the main chain.
  20 type BlockNode struct {
  21         Parent *BlockNode // parent is the parent block for this node.
  22         Hash   bc.Hash    // hash of the block.
  23
  24         Version                uint64
  25         Height                 uint64
  26         Timestamp              uint64
  27         TransactionsMerkleRoot bc.Hash
  28         TransactionStatusHash  bc.Hash
  29 }
  30
  31 func NewBlockNode(bh *types.BlockHeader, parent *BlockNode) (*BlockNode, error) {
  32         if bh.Height != 0 && parent == nil {
  33                 return nil, errors.New("parent node can not be nil")
  34         }
  35
  36         node := &BlockNode{
  37                 Parent:                 parent,
  38                 Hash:                   bh.Hash(),
  39                 Version:                bh.Version,
  40                 Height:                 bh.Height,
  41                 Timestamp:              bh.Timestamp,
  42                 TransactionsMerkleRoot: bh.TransactionsMerkleRoot,
  43                 TransactionStatusHash:  bh.TransactionStatusHash,
  44         }
  45         return node, nil
  46 }
  47
  48 // blockHeader convert a node to the header struct
  49 func (node *BlockNode) BlockHeader() *types.BlockHeader {
  50         previousBlockHash := bc.Hash{}
  51         if node.Parent != nil {
  52                 previousBlockHash = node.Parent.Hash
  53         }
  54         return &types.BlockHeader{
  55                 Version:           node.Version,
  56                 Height:            node.Height,
  57                 PreviousBlockHash: previousBlockHash,
  58                 Timestamp:         node.Timestamp,
  59                 BlockCommitment: types.BlockCommitment{
  60                         TransactionsMerkleRoot: node.TransactionsMerkleRoot,
  61                         TransactionStatusHash:  node.TransactionStatusHash,
  62                 },
  63         }
  64 }
  65
  66 func (node *BlockNode) CalcPastMedianTime() uint64 {
  67         timestamps := []uint64{}
  68         iterNode := node
  69         for i := 0; i < consensus.MedianTimeBlocks && iterNode != nil; i++ {
  70                 timestamps = append(timestamps, iterNode.Timestamp)
  71                 iterNode = iterNode.Parent
  72         }
  73
  74         sort.Sort(common.TimeSorter(timestamps))
  75         return timestamps[len(timestamps)/2]
  76 }
  77
  78 // BlockIndex is the struct for help chain trace block chain as tree
  79 type BlockIndex struct {
  80         sync.RWMutex
  81
  82         index     map[bc.Hash]*BlockNode
  83         mainChain []*BlockNode
  84 }
  85
  86 // NewBlockIndex will create a empty BlockIndex
  87 func NewBlockIndex() *BlockIndex {
  88         return &BlockIndex{
  89                 index:     make(map[bc.Hash]*BlockNode),
  90                 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
  91         }
  92 }
  93
  94 // AddNode will add node to the index map
  95 func (bi *BlockIndex) AddNode(node *BlockNode) {
  96         bi.Lock()
  97         bi.index[node.Hash] = node
  98         bi.Unlock()
  99 }
 100
 101 // GetNode will search node from the index map
 102 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
 103         bi.RLock()
 104         defer bi.RUnlock()
 105         return bi.index[*hash]
 106 }
 107
 108 func (bi *BlockIndex) BestNode() *BlockNode {
 109         bi.RLock()
 110         defer bi.RUnlock()
 111         return bi.mainChain[len(bi.mainChain)-1]
 112 }
 113
 114 // BlockExist check does the block existed in blockIndex
 115 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
 116         bi.RLock()
 117         _, ok := bi.index[*hash]
 118         bi.RUnlock()
 119         return ok
 120 }
 121
 122 // TODO: THIS FUNCTION MIGHT BE DELETED
 123 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
 124         bi.RLock()
 125         defer bi.RUnlock()
 126
 127         node, ok := bi.index[hash]
 128         if !ok {
 129                 return false
 130         }
 131         return bi.nodeByHeight(node.Height) == node
 132 }
 133
 134 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
 135         if height >= uint64(len(bi.mainChain)) {
 136                 return nil
 137         }
 138         return bi.mainChain[height]
 139 }
 140
 141 // NodeByHeight returns the block node at the specified height.
 142 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
 143         bi.RLock()
 144         defer bi.RUnlock()
 145         return bi.nodeByHeight(height)
 146 }
 147
 148 // SetMainChain will set the the mainChain array
 149 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
 150         bi.Lock()
 151         defer bi.Unlock()
 152
 153         needed := node.Height + 1
 154         if uint64(cap(bi.mainChain)) < needed {
 155                 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
 156                 copy(nodes, bi.mainChain)
 157                 bi.mainChain = nodes
 158         } else {
 159                 i := uint64(len(bi.mainChain))
 160                 bi.mainChain = bi.mainChain[0:needed]
 161                 for ; i < needed; i++ {
 162                         bi.mainChain[i] = nil
 163                 }
 164         }
 165
 166         for node != nil && bi.mainChain[node.Height] != node {
 167                 bi.mainChain[node.Height] = node
 168                 node = node.Parent
 169         }
 170 }