aboutsummaryrefslogtreecommitdiffstats
path: root/src/trie_rand_test.go
diff options
context:
space:
mode:
authorMathias Hall-Andersen <mathias@hall-andersen.dk>2017-06-02 17:58:46 +0200
committerMathias Hall-Andersen <mathias@hall-andersen.dk>2017-06-02 17:58:46 +0200
commita377bcaed7e97dba2ef953e995abb5272396dc2f (patch)
tree58ac6b437fcdbf9c05f7eac77d23573f2447548f /src/trie_rand_test.go
parentInital implementation of trie (diff)
downloadwireguard-go-a377bcaed7e97dba2ef953e995abb5272396dc2f.tar.xz
wireguard-go-a377bcaed7e97dba2ef953e995abb5272396dc2f.zip
Added random test for trie
Diffstat (limited to '')
-rw-r--r--src/trie_rand_test.go120
1 files changed, 120 insertions, 0 deletions
diff --git a/src/trie_rand_test.go b/src/trie_rand_test.go
new file mode 100644
index 0000000..f8b860c
--- /dev/null
+++ b/src/trie_rand_test.go
@@ -0,0 +1,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)
+ }
+ }
+}