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         BlockWitness           *common.BitMap
  28         TransactionsMerkleRoot bc.Hash
  29         TransactionStatusHash  bc.Hash
  30 }
  31
  32 func NewBlockNode(bh *types.BlockHeader, parent *BlockNode) (*BlockNode, error) {
  33         if bh.Height != 0 && parent == nil {
  34                 return nil, errors.New("parent node can not be nil")
  35         }
  36
  37         node := &BlockNode{
  38                 Parent:                 parent,
  39                 Hash:                   bh.Hash(),
  40                 Version:                bh.Version,
  41                 Height:                 bh.Height,
  42                 Timestamp:              bh.Timestamp,
  43                 TransactionsMerkleRoot: bh.TransactionsMerkleRoot,
  44                 TransactionStatusHash:  bh.TransactionStatusHash,
  45         }
  46
  47         node.BlockWitness = common.NewBitMap(uint32(len(bh.Witness)))
  48         for i, witness := range bh.Witness {
  49                 if len(witness) != 0 {
  50                         if err := node.BlockWitness.Set(uint32(i)); err != nil {
  51                                 return nil, err
  52                         }
  53                 }
  54         }
  55         return node, nil
  56 }
  57
  58 // blockHeader convert a node to the header struct
  59 func (node *BlockNode) BlockHeader() *types.BlockHeader {
  60         previousBlockHash := bc.Hash{}
  61         if node.Parent != nil {
  62                 previousBlockHash = node.Parent.Hash
  63         }
  64         return &types.BlockHeader{
  65                 Version:           node.Version,
  66                 Height:            node.Height,
  67                 PreviousBlockHash: previousBlockHash,
  68                 Timestamp:         node.Timestamp,
  69                 BlockCommitment: types.BlockCommitment{
  70                         TransactionsMerkleRoot: node.TransactionsMerkleRoot,
  71                         TransactionStatusHash:  node.TransactionStatusHash,
  72                 },
  73         }
  74 }
  75
  76 func (node *BlockNode) CalcPastMedianTime() uint64 {
  77         timestamps := []uint64{}
  78         iterNode := node
  79         for i := 0; i < consensus.MedianTimeBlocks && iterNode != nil; i++ {
  80                 timestamps = append(timestamps, iterNode.Timestamp)
  81                 iterNode = iterNode.Parent
  82         }
  83
  84         sort.Sort(common.TimeSorter(timestamps))
  85         return timestamps[len(timestamps)/2]
  86 }
  87
  88 // BlockIndex is the struct for help chain trace block chain as tree
  89 type BlockIndex struct {
  90         sync.RWMutex
  91
  92         index       map[bc.Hash]*BlockNode
  93         heightIndex map[uint64][]*BlockNode
  94         mainChain   []*BlockNode
  95 }
  96
  97 // NewBlockIndex will create a empty BlockIndex
  98 func NewBlockIndex() *BlockIndex {
  99         return &BlockIndex{
 100                 index:     make(map[bc.Hash]*BlockNode),
 101                 heightIndex: make(map[uint64][]*BlockNode),
 102                 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
 103         }
 104 }
 105
 106 // AddNode will add node to the index map
 107 func (bi *BlockIndex) AddNode(node *BlockNode) {
 108         bi.Lock()
 109         bi.index[node.Hash] = node
 110         bi.heightIndex[node.Height] = append(bi.heightIndex[node.Height], node)
 111         bi.Unlock()
 112 }
 113
 114 // GetNode will search node from the index map
 115 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
 116         bi.RLock()
 117         defer bi.RUnlock()
 118         return bi.index[*hash]
 119 }
 120
 121 // NodeByHeightInSameChain return the node of specified height
 122 // And the node satisfies the same chain as the node that specifies the hash
 123 // Height of the block of the specified node hash must greater than height parameter
 124 func (bi *BlockIndex) NodeByHeightInSameChain(nodeHash *bc.Hash, height uint64) *BlockNode {
 125         bi.RLock()
 126         defer bi.RUnlock()
 127
 128         blockNode := bi.index[*nodeHash]
 129         prevBlockNode := blockNode
 130         for prevBlockNode != nil && prevBlockNode.Height != height {
 131                 if prevBlockNode.Height < height {
 132                         return nil
 133                 }
 134                 prevBlockNode = bi.index[prevBlockNode.Parent.Hash]
 135         }
 136         return prevBlockNode
 137 }
 138
 139 func (bi *BlockIndex) BestNode() *BlockNode {
 140         bi.RLock()
 141         defer bi.RUnlock()
 142         return bi.mainChain[len(bi.mainChain)-1]
 143 }
 144
 145 // BlockExist check does the block existed in blockIndex
 146 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
 147         bi.RLock()
 148         _, ok := bi.index[*hash]
 149         bi.RUnlock()
 150         return ok
 151 }
 152
 153 // TODO: THIS FUNCTION MIGHT BE DELETED
 154 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
 155         bi.RLock()
 156         defer bi.RUnlock()
 157
 158         node, ok := bi.index[hash]
 159         if !ok {
 160                 return false
 161         }
 162         return bi.nodeByHeight(node.Height) == node
 163 }
 164
 165 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
 166         if height >= uint64(len(bi.mainChain)) {
 167                 return nil
 168         }
 169         return bi.mainChain[height]
 170 }
 171
 172 // NodeByHeight returns the block node at the specified height.
 173 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
 174         bi.RLock()
 175         defer bi.RUnlock()
 176         return bi.nodeByHeight(height)
 177 }
 178
 179 // NodesByHeight return all block nodes at the specified height.
 180 func (bi *BlockIndex) NodesByHeight(height uint64) []*BlockNode {
 181         bi.RLock()
 182         defer bi.RUnlock()
 183         return bi.heightIndex[height]
 184 }
 185
 186 // SetMainChain will set the the mainChain array
 187 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
 188         bi.Lock()
 189         defer bi.Unlock()
 190
 191         needed := node.Height + 1
 192         if uint64(cap(bi.mainChain)) < needed {
 193                 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
 194                 copy(nodes, bi.mainChain)
 195                 bi.mainChain = nodes
 196         } else {
 197                 i := uint64(len(bi.mainChain))
 198                 bi.mainChain = bi.mainChain[0:needed]
 199                 for ; i < needed; i++ {
 200                         bi.mainChain[i] = nil
 201                 }
 202         }
 203
 204         for node != nil && bi.mainChain[node.Height] != node {
 205                 bi.mainChain[node.Height] = node
 206                 node = node.Parent
 207         }
 208 }