-
Notifications
You must be signed in to change notification settings - Fork 36
/
Copy pathsorting.go
64 lines (55 loc) · 1.68 KB
/
sorting.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package kbucket
import (
"container/list"
"sort"
"github.com/libp2p/go-libp2p/core/peer"
)
// A helper struct to sort peers by their distance to the local node
type peerDistance struct {
p peer.ID
distance ID
}
// peerDistanceSorter implements sort.Interface to sort peers by xor distance
type peerDistanceSorter struct {
peers []peerDistance
target ID
}
func (pds *peerDistanceSorter) Len() int { return len(pds.peers) }
func (pds *peerDistanceSorter) Swap(a, b int) {
pds.peers[a], pds.peers[b] = pds.peers[b], pds.peers[a]
}
func (pds *peerDistanceSorter) Less(a, b int) bool {
return pds.peers[a].distance.less(pds.peers[b].distance)
}
// Append the peer.ID to the sorter's slice. It may no longer be sorted.
func (pds *peerDistanceSorter) appendPeer(p peer.ID, pDhtId ID) {
pds.peers = append(pds.peers, peerDistance{
p: p,
distance: xor(pds.target, pDhtId),
})
}
// Append the peer.ID values in the list to the sorter's slice. It may no longer be sorted.
func (pds *peerDistanceSorter) appendPeersFromList(l *list.List) {
for e := l.Front(); e != nil; e = e.Next() {
pds.appendPeer(e.Value.(*PeerInfo).Id, e.Value.(*PeerInfo).dhtId)
}
}
func (pds *peerDistanceSorter) sort() {
sort.Sort(pds)
}
// SortClosestPeers Sort the given peers by their ascending distance from the target. A new slice is returned.
func SortClosestPeers(peers []peer.ID, target ID) []peer.ID {
sorter := peerDistanceSorter{
peers: make([]peerDistance, 0, len(peers)),
target: target,
}
for _, p := range peers {
sorter.appendPeer(p, ConvertPeerID(p))
}
sorter.sort()
out := make([]peer.ID, 0, sorter.Len())
for _, p := range sorter.peers {
out = append(out, p.p)
}
return out
}