sync.go

// Copyright 2015 The go-ethereum Authors
// This file is part of the go-ethereum library.
//
// The go-ethereum library is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// The go-ethereum library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.

package trie

import (
	"github.com/ethereum/go-ethereum/common"
)

type requestQueue struct {
	req  []common.Hash
	sent int
}

func (self *requestQueue) add(req common.Hash) {
	self.req = append(self.req, req)
}

func (self *requestQueue) get(max int) []common.Hash {
	rem := len(self.req) - self.sent
	cnt := max
	if rem < max {
		cnt = rem
	}
	ret := self.req[self.sent : self.sent+cnt]
	self.sent += cnt
	if self.sent > 100 {
		self.req = self.req[self.sent:]
		self.sent = 0
	}
	return ret
}

type nodeReq struct {
	nodeRef            *node // hash node is replaced with actual node when received
	hash               common.Hash
	rlp                []byte
	parent             *nodeReq
	depth, reqChildCnt int
}

type TrieSync struct {
	db       Database
	trie     *Trie
	rqList   [65]requestQueue
	maxDepth int
	reqs     map[common.Hash]*nodeReq
}

func NewTrieSync(root common.Hash, db Database) *TrieSync {
    ts := &TrieSync{
        db:   db,
        trie: &Trie{db: db},
        reqs: make(map[common.Hash]*nodeReq),
    }
    ts.trie.root = hashNode(root.Bytes())
	req := &nodeReq{
		nodeRef: &ts.trie.root,
		hash:    root,
	}
	ts.addReq(req)
	return ts
}

func (self *TrieSync) addReq(req *nodeReq) {
	if req.depth > 64 {
		panic(nil)
	}
	self.rqList[req.depth].add(req.hash)
	if self.maxDepth < req.depth {
		self.maxDepth = req.depth
	}
	self.reqs[req.hash] = req
}

func (self *TrieSync) GetHashes(max int) []common.Hash {
	res := []common.Hash{}
	for (self.maxDepth >= 0) && (len(res) < max) {
		r := self.rqList[self.maxDepth].get(max - len(res))
		if len(r) == 0 {
			self.maxDepth--
		} else {
			res = append(res, r...)
		}
	}
	return res
}

type RawNodeData struct {
	hash common.Hash
	rlp  []byte
}

func (self *TrieSync) ProcessNodes(nodes []RawNodeData) {
	for _, nd := range nodes {
		nr := self.reqs[nd.hash]
		if nr == nil {
			continue
		}
		node := mustDecodeNode(nd.hash[:], nd.rlp)
		*nr.nodeRef = node
		nr.rlp = nd.rlp
		crs := self.createChildReqs(nr)
		nr.reqChildCnt = len(crs)
		if nr.reqChildCnt == 0 {
			self.subTreeFinished(nr)
		}
		for _, cr := range crs {
			self.addReq(cr)
		}
	}
}

func (self *TrieSync) createChildReqs(nr *nodeReq) []*nodeReq {
	tn := *nr.nodeRef
	var cnodes [](*node)
	var cdepth int
	switch n := tn.(type) {
	case shortNode:
		cnodes = [](*node){&n.Val}
		cdepth = nr.depth + len(n.Key)
	case fullNode:
		for i := 0; i < 16; i++ {
			if n[i] != nil {
				cnodes = append(cnodes, &n[i])
			}
		}
		cdepth = nr.depth + 1
	default:
		panic(nil)
	}

	var reqs []*nodeReq
	for _, cn := range cnodes {
		hash, ishash := (*cn).(hashNode)
		if ishash {
			nn := self.trie.resolveHash(hash)
			if nn != nil {
				ishash = false
				*cn = nn
			}
		}
		if ishash { // node not found in db, subtree is missing or incomplete
			req := &nodeReq{
				nodeRef: cn,
				hash:    common.BytesToHash(hash),
				parent:  nr,
				depth:   cdepth,
			}
			reqs = append(reqs, req)
		}
	}
	return reqs
}

func (self *TrieSync) subTreeFinished(nr *nodeReq) {
	// write node to disk
	self.db.Put(nr.hash[:], nr.rlp)
	// check if parent is finished too
	self.reqs[nr.hash] = nil
	pr := nr.parent
	if pr != nil {
		pr.reqChildCnt--
		if pr.reqChildCnt == 0 {
			self.subTreeFinished(pr)
		}
	}
}