12199391122

Committed 06 Dec 2024 01:10PM UTC coverage: 49.807% (-9.1%) from 58.933%

Build # 12199391122

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #9337 from Guayaba221/patch-1

chore: fix typo in ruby.md

Run Details

100137 of 201051 relevant lines covered (49.81%)

2.07 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.7

/routing/heap.go

package routing

import (
        "container/heap"

        "github.com/lightningnetwork/lnd/lnwire"
        "github.com/lightningnetwork/lnd/routing/route"
)

// nodeWithDist is a helper struct that couples the distance from the current
// source to a node with a pointer to the node itself.
type nodeWithDist struct {
        // dist is the distance to this node from the source node in our
        // current context.
        dist int64

        // node is the vertex itself. This can be used to explore all the
        // outgoing edges (channels) emanating from a node.
        node route.Vertex

        // netAmountReceived is the amount that should be received by this node.
        // Either as final payment to the final node or as an intermediate
        // amount that includes also the fees for subsequent hops. This node's
        // inbound fee is already subtracted from the htlc amount - if
        // applicable.
        netAmountReceived lnwire.MilliSatoshi

        // outboundFee is the fee that this node charges on the outgoing
        // channel.
        outboundFee lnwire.MilliSatoshi

        // incomingCltv is the expected absolute expiry height for the incoming
        // htlc of this node. This value should already include the final cltv
        // delta.
        incomingCltv int32

        // probability is the probability that from this node onward the route
        // is successful.
        probability float64

        // weight is the cost of the route from this node to the destination.
        // Includes the routing fees and a virtual cost factor to account for
        // time locks.
        weight int64

        // nextHop is the edge this route comes from.
        nextHop *unifiedEdge

        // routingInfoSize is the total size requirement for the payloads field
        // in the onion packet from this hop towards the final destination.
        routingInfoSize uint64
}

// distanceHeap is a min-distance heap that's used within our path finding
// algorithm to keep track of the "closest" node to our source node.
type distanceHeap struct {
        nodes []*nodeWithDist

        // pubkeyIndices maps public keys of nodes to their respective index in
        // the heap. This is used as a way to avoid db lookups by using heap.Fix
        // instead of having duplicate entries on the heap.
        pubkeyIndices map[route.Vertex]int
}

// newDistanceHeap initializes a new distance heap. This is required because
// we must initialize the pubkeyIndices map for path-finding optimizations.
func newDistanceHeap(numNodes int) distanceHeap {
        distHeap := distanceHeap{
                pubkeyIndices: make(map[route.Vertex]int, numNodes),
                nodes:         make([]*nodeWithDist, 0, numNodes),
        }

        return distHeap
}

// Len returns the number of nodes in the priority queue.
//
// NOTE: This is part of the heap.Interface implementation.
func (d *distanceHeap) Len() int { return len(d.nodes) }

// Less returns whether the item in the priority queue with index i should sort
// before the item with index j.
//
// NOTE: This is part of the heap.Interface implementation.
func (d *distanceHeap) Less(i, j int) bool {
        // If distances are equal, tie break on probability.
        if d.nodes[i].dist == d.nodes[j].dist {
                return d.nodes[i].probability > d.nodes[j].probability
        }

        return d.nodes[i].dist < d.nodes[j].dist
}

// Swap swaps the nodes at the passed indices in the priority queue.
//
// NOTE: This is part of the heap.Interface implementation.
func (d *distanceHeap) Swap(i, j int) {
        d.nodes[i], d.nodes[j] = d.nodes[j], d.nodes[i]
        d.pubkeyIndices[d.nodes[i].node] = i
        d.pubkeyIndices[d.nodes[j].node] = j
}

// Push pushes the passed item onto the priority queue.
//
// NOTE: This is part of the heap.Interface implementation.
func (d *distanceHeap) Push(x interface{}) {
        n := x.(*nodeWithDist)
        d.nodes = append(d.nodes, n)
        d.pubkeyIndices[n.node] = len(d.nodes) - 1
}

// Pop removes the highest priority item (according to Less) from the priority
// queue and returns it.
//
// NOTE: This is part of the heap.Interface implementation.
func (d *distanceHeap) Pop() interface{} {
        n := len(d.nodes)
        x := d.nodes[n-1]
        d.nodes[n-1] = nil
        d.nodes = d.nodes[0 : n-1]
        delete(d.pubkeyIndices, x.node)
        return x
}

// PushOrFix attempts to adjust the position of a given node in the heap.
// If the vertex already exists in the heap, then we must call heap.Fix to
// modify its position and reorder the heap. If the vertex does not already
// exist in the heap, then it is pushed onto the heap. Otherwise, we will end
// up performing more db lookups on the same node in the pathfinding algorithm.
func (d *distanceHeap) PushOrFix(dist *nodeWithDist) {
        index, ok := d.pubkeyIndices[dist.node]
        if !ok {
                heap.Push(d, dist)
                return
        }

        // Change the value at the specified index.
        d.nodes[index] = dist

        // Call heap.Fix to reorder the heap.
        heap.Fix(d, index)
}

1	package routing
2
3	import (
4	"container/heap"
5
6	"github.com/lightningnetwork/lnd/lnwire"
7	"github.com/lightningnetwork/lnd/routing/route"
8	)
9
10	// nodeWithDist is a helper struct that couples the distance from the current
11	// source to a node with a pointer to the node itself.
12	type nodeWithDist struct {
13	// dist is the distance to this node from the source node in our
14	// current context.
15	dist int64
16
17	// node is the vertex itself. This can be used to explore all the
18	// outgoing edges (channels) emanating from a node.
19	node route.Vertex
20
21	// netAmountReceived is the amount that should be received by this node.
22	// Either as final payment to the final node or as an intermediate
23	// amount that includes also the fees for subsequent hops. This node's
24	// inbound fee is already subtracted from the htlc amount - if
25	// applicable.
26	netAmountReceived lnwire.MilliSatoshi
27
28	// outboundFee is the fee that this node charges on the outgoing
29	// channel.
30	outboundFee lnwire.MilliSatoshi
31
32	// incomingCltv is the expected absolute expiry height for the incoming
33	// htlc of this node. This value should already include the final cltv
34	// delta.
35	incomingCltv int32
36
37	// probability is the probability that from this node onward the route
38	// is successful.
39	probability float64
40
41	// weight is the cost of the route from this node to the destination.
42	// Includes the routing fees and a virtual cost factor to account for
43	// time locks.
44	weight int64
45
46	// nextHop is the edge this route comes from.
47	nextHop *unifiedEdge
48
49	// routingInfoSize is the total size requirement for the payloads field
50	// in the onion packet from this hop towards the final destination.
51	routingInfoSize uint64
52	}
53
54	// distanceHeap is a min-distance heap that's used within our path finding
55	// algorithm to keep track of the "closest" node to our source node.
56	type distanceHeap struct {
57	nodes []*nodeWithDist
58
59	// pubkeyIndices maps public keys of nodes to their respective index in
60	// the heap. This is used as a way to avoid db lookups by using heap.Fix
61	// instead of having duplicate entries on the heap.
62	pubkeyIndices map[route.Vertex]int
63	}
64
65	// newDistanceHeap initializes a new distance heap. This is required because
66	// we must initialize the pubkeyIndices map for path-finding optimizations.
67	func newDistanceHeap(numNodes int) distanceHeap {	4✔
68	distHeap := distanceHeap{	4✔
69	pubkeyIndices: make(map[route.Vertex]int, numNodes),	4✔
70	nodes: make([]*nodeWithDist, 0, numNodes),	4✔
71	}	4✔
72		4✔
73	return distHeap	4✔
74	}	4✔
75
76	// Len returns the number of nodes in the priority queue.
77	//
78	// NOTE: This is part of the heap.Interface implementation.
79	func (d *distanceHeap) Len() int { return len(d.nodes) }	4✔
80
81	// Less returns whether the item in the priority queue with index i should sort
82	// before the item with index j.
83	//
84	// NOTE: This is part of the heap.Interface implementation.
85	func (d *distanceHeap) Less(i, j int) bool {	4✔
86	// If distances are equal, tie break on probability.	4✔
87	if d.nodes[i].dist == d.nodes[j].dist {	8✔
88	return d.nodes[i].probability > d.nodes[j].probability	4✔
89	}	4✔
90
91	return d.nodes[i].dist < d.nodes[j].dist	4✔
92	}
93
94	// Swap swaps the nodes at the passed indices in the priority queue.
95	//
96	// NOTE: This is part of the heap.Interface implementation.
97	func (d *distanceHeap) Swap(i, j int) {	4✔
98	d.nodes[i], d.nodes[j] = d.nodes[j], d.nodes[i]	4✔
99	d.pubkeyIndices[d.nodes[i].node] = i	4✔
100	d.pubkeyIndices[d.nodes[j].node] = j	4✔
101	}	4✔
102
103	// Push pushes the passed item onto the priority queue.
104	//
105	// NOTE: This is part of the heap.Interface implementation.
106	func (d *distanceHeap) Push(x interface{}) {	4✔
107	n := x.(*nodeWithDist)	4✔
108	d.nodes = append(d.nodes, n)	4✔
109	d.pubkeyIndices[n.node] = len(d.nodes) - 1	4✔
110	}	4✔
111
112	// Pop removes the highest priority item (according to Less) from the priority
113	// queue and returns it.
114	//
115	// NOTE: This is part of the heap.Interface implementation.
116	func (d *distanceHeap) Pop() interface{} {	4✔
117	n := len(d.nodes)	4✔
118	x := d.nodes[n-1]	4✔
119	d.nodes[n-1] = nil	4✔
120	d.nodes = d.nodes[0 : n-1]	4✔
121	delete(d.pubkeyIndices, x.node)	4✔
122	return x	4✔
123	}	4✔
124
125	// PushOrFix attempts to adjust the position of a given node in the heap.
126	// If the vertex already exists in the heap, then we must call heap.Fix to
127	// modify its position and reorder the heap. If the vertex does not already
128	// exist in the heap, then it is pushed onto the heap. Otherwise, we will end
129	// up performing more db lookups on the same node in the pathfinding algorithm.
130	func (d distanceHeap) PushOrFix(dist nodeWithDist) {	4✔
131	index, ok := d.pubkeyIndices[dist.node]	4✔
132	if !ok {	8✔
133	heap.Push(d, dist)	4✔
134	return	4✔
135	}	4✔
136
137	// Change the value at the specified index.
138	d.nodes[index] = dist	×
139		×
140	// Call heap.Fix to reorder the heap.	×
141	heap.Fix(d, index)	×
142	}

lightningnetwork / lnd / 12199391122

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous