Skip to content

Instantly share code, notes, and snippets.

@mgraczyk

mgraczyk/perlin4.go

Created Jun 28, 2018
Embed
What would you like to do?
// Searches for suitable parent transactions for a new transaction.
func (n *Node) SelectParents() []string {
// [OT] The lock could be held for less time with BFS
mutex.RLock()
defer mutex.RUnlock()
var eligibleParents []*Transaction
// [OT] Search every historical transaction.
for _, tx := range n.Transactions {
if n.IsStronglyPreferred(tx) {
// [OT] Figure 19, line 2
if len(n.Conflicts[tx.Body.Utxo].Transactions) == 1 ||
n.Confidence(tx) > 0 {
eligibleParents = append(eligibleParents, tx)
}
}
}
// [OT] Parents are strings rather than typed transactions.
var parents []string
// [OT] Figure 19, line 3
// Parents are defined as tx's whose children are not eligible parents
// themselves.
for _, x := range eligibleParents {
var children []*Transaction
// [OT] This is O(n^2) in the number of transactions...
// Could be avoided by storing the graph in topological order, or
// including child pointers.
// Get all children of the candidate parent.
for _, tx := range n.Transactions {
for _, parentId := range tx.Body.GetParents() {
if parentId == x.Id {
children = append(children, tx)
}
}
}
// [OT] Does golang not have a set()?
// eligible := set(children).intersect(eligibleParents).length == 0
eligible := true
// Check if the child is an eligible parent himself.
for _, y := range eligibleParents {
for _, child := range children {
if y.Id == child.Id {
eligible = false
break
}
}
}
if eligible {
parents = append(parents, x.Id)
}
}
// [OT] No sampling here or up the stack.
return parents
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.