8 "github.com/vapor/common"
9 "github.com/vapor/consensus"
10 "github.com/vapor/protocol/bc"
11 "github.com/vapor/protocol/bc/types"
14 // approxNodesPerDay is an approximation of the number of new blocks there are
15 // in a day on average.
16 const approxNodesPerDay = 24 * 24
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.
27 BlockWitness *common.BitMap
28 TransactionsMerkleRoot bc.Hash
29 TransactionStatusHash bc.Hash
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")
42 Timestamp: bh.Timestamp,
43 TransactionsMerkleRoot: bh.TransactionsMerkleRoot,
44 TransactionStatusHash: bh.TransactionStatusHash,
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 {
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
64 return &types.BlockHeader{
65 Version: node.Version,
67 PreviousBlockHash: previousBlockHash,
68 Timestamp: node.Timestamp,
69 BlockCommitment: types.BlockCommitment{
70 TransactionsMerkleRoot: node.TransactionsMerkleRoot,
71 TransactionStatusHash: node.TransactionStatusHash,
76 func (node *BlockNode) CalcPastMedianTime() uint64 {
77 timestamps := []uint64{}
79 for i := 0; i < consensus.MedianTimeBlocks && iterNode != nil; i++ {
80 timestamps = append(timestamps, iterNode.Timestamp)
81 iterNode = iterNode.Parent
84 sort.Sort(common.TimeSorter(timestamps))
85 return timestamps[len(timestamps)/2]
88 // GetParent return the node of specified height
89 // And the node satisfies the same chain as current node
90 // Height of current node must greater than height parameter
91 func (node *BlockNode) GetParent(height uint64) *BlockNode {
93 for prevBlockNode != nil && prevBlockNode.Height != height {
94 if prevBlockNode.Height < height {
97 prevBlockNode = prevBlockNode.Parent
102 // BlockIndex is the struct for help chain trace block chain as tree
103 type BlockIndex struct {
106 index map[bc.Hash]*BlockNode
107 heightIndex map[uint64][]*BlockNode
108 mainChain []*BlockNode
111 // NewBlockIndex will create a empty BlockIndex
112 func NewBlockIndex() *BlockIndex {
114 index: make(map[bc.Hash]*BlockNode),
115 heightIndex: make(map[uint64][]*BlockNode),
116 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
120 // AddNode will add node to the index map
121 func (bi *BlockIndex) AddNode(node *BlockNode) {
123 bi.index[node.Hash] = node
124 bi.heightIndex[node.Height] = append(bi.heightIndex[node.Height], node)
128 // GetNode will search node from the index map
129 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
132 return bi.index[*hash]
135 func (bi *BlockIndex) BestNode() *BlockNode {
138 return bi.mainChain[len(bi.mainChain)-1]
141 // BlockExist check does the block existed in blockIndex
142 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
144 _, ok := bi.index[*hash]
149 // TODO: THIS FUNCTION MIGHT BE DELETED
150 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
154 node, ok := bi.index[hash]
158 return bi.nodeByHeight(node.Height) == node
161 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
162 if height >= uint64(len(bi.mainChain)) {
165 return bi.mainChain[height]
168 // NodeByHeight returns the block node at the specified height.
169 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
172 return bi.nodeByHeight(height)
175 // NodesByHeight return all block nodes at the specified height.
176 func (bi *BlockIndex) NodesByHeight(height uint64) []*BlockNode {
179 return bi.heightIndex[height]
182 // SetMainChain will set the the mainChain array
183 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
187 needed := node.Height + 1
188 if uint64(cap(bi.mainChain)) < needed {
189 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
190 copy(nodes, bi.mainChain)
193 i := uint64(len(bi.mainChain))
194 bi.mainChain = bi.mainChain[0:needed]
195 for ; i < needed; i++ {
196 bi.mainChain[i] = nil
200 for node != nil && bi.mainChain[node.Height] != node {
201 bi.mainChain[node.Height] = node