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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
package main
import (
"math/rand"
"sort"
"testing"
)
const (
NumberOfPeers = 100
NumberOfAddresses = 250
NumberOfTests = 10000
)
type SlowRouter []*Trie
func (r SlowRouter) Len() int {
return len(r)
}
func (r SlowRouter) Less(i, j int) bool {
return r[i].cidr > r[j].cidr
}
func (r SlowRouter) Swap(i, j int) {
r[i], r[j] = r[j], r[i]
}
func (r SlowRouter) Insert(addr []byte, cidr uint, peer *Peer) SlowRouter {
for _, t := range r {
if t.cidr == cidr && commonBits(t.bits, addr) >= cidr {
t.peer = peer
t.bits = addr
return r
}
}
r = append(r, &Trie{
cidr: cidr,
bits: addr,
peer: peer,
})
sort.Sort(r)
return r
}
func (r SlowRouter) Lookup(addr []byte) *Peer {
for _, t := range r {
common := commonBits(t.bits, addr)
if common >= t.cidr {
return t.peer
}
}
return nil
}
func TestTrieRandomIPv4(t *testing.T) {
var trie *Trie
var slow SlowRouter
var peers []*Peer
rand.Seed(1)
const AddressLength = 4
for n := 0; n < NumberOfPeers; n += 1 {
peers = append(peers, &Peer{})
}
for n := 0; n < NumberOfAddresses; n += 1 {
var addr [AddressLength]byte
rand.Read(addr[:])
cidr := uint(rand.Uint32() % (AddressLength * 8))
index := rand.Int() % NumberOfPeers
trie = trie.Insert(addr[:], cidr, peers[index])
slow = slow.Insert(addr[:], cidr, peers[index])
}
for n := 0; n < NumberOfTests; n += 1 {
var addr [AddressLength]byte
rand.Read(addr[:])
peer1 := slow.Lookup(addr[:])
peer2 := trie.Lookup(addr[:])
if peer1 != peer2 {
t.Error("Trie did not match niave implementation, for:", addr)
}
}
}
func TestTrieRandomIPv6(t *testing.T) {
var trie *Trie
var slow SlowRouter
var peers []*Peer
rand.Seed(1)
const AddressLength = 16
for n := 0; n < NumberOfPeers; n += 1 {
peers = append(peers, &Peer{})
}
for n := 0; n < NumberOfAddresses; n += 1 {
var addr [AddressLength]byte
rand.Read(addr[:])
cidr := uint(rand.Uint32() % (AddressLength * 8))
index := rand.Int() % NumberOfPeers
trie = trie.Insert(addr[:], cidr, peers[index])
slow = slow.Insert(addr[:], cidr, peers[index])
}
for n := 0; n < NumberOfTests; n += 1 {
var addr [AddressLength]byte
rand.Read(addr[:])
peer1 := slow.Lookup(addr[:])
peer2 := trie.Lookup(addr[:])
if peer1 != peer2 {
t.Error("Trie did not match niave implementation, for:", addr)
}
}
}
|
