device: remove recursion from insertion and connect parent pointers

This makes the insertion algorithm a bit more efficient, while also now
taking on the additional task of connecting up parent pointers. This
will be handy in the following commit.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

1 files changed, 12 insertions, 11 deletions

diff --git a/device/allowedips_test.go b/device/allowedips_test.go
index 8dc8438..cbd32cc 100644
--- a/device/allowedips_test.go
+++ b/device/allowedips_test.go
@@ -42,6 +42,7 @@ func TestCommonBits(t *testing.T) {
 func benchmarkTrie(peerNumber int, addressNumber int, addressLength int, b *testing.B) {
 	var trie *trieEntry
 	var peers []*Peer
+	root := parentIndirection{&trie, 2}
 
 	rand.Seed(1)
 
@@ -56,7 +57,7 @@ func benchmarkTrie(peerNumber int, addressNumber int, addressLength int, b *test
 		rand.Read(addr[:])
 		cidr := uint8(rand.Uint32() % (AddressLength * 8))
 		index := rand.Int() % peerNumber
-		trie = trie.insert(addr[:], cidr, peers[index])
+		root.insert(addr[:], cidr, peers[index])
 	}
 
 	for n := 0; n < b.N; n++ {
@@ -94,21 +95,21 @@ func TestTrieIPv4(t *testing.T) {
 	g := &Peer{}
 	h := &Peer{}
 
-	var trie *trieEntry
+	var allowedIPs AllowedIPs
 
 	insert := func(peer *Peer, a, b, c, d byte, cidr uint8) {
-		trie = trie.insert([]byte{a, b, c, d}, cidr, peer)
+		allowedIPs.Insert([]byte{a, b, c, d}, cidr, peer)
 	}
 
 	assertEQ := func(peer *Peer, a, b, c, d byte) {
-		p := trie.lookup([]byte{a, b, c, d})
+		p := allowedIPs.LookupIPv4([]byte{a, b, c, d})
 		if p != peer {
 			t.Error("Assert EQ failed")
 		}
 	}
 
 	assertNEQ := func(peer *Peer, a, b, c, d byte) {
-		p := trie.lookup([]byte{a, b, c, d})
+		p := allowedIPs.LookupIPv4([]byte{a, b, c, d})
 		if p == peer {
 			t.Error("Assert NEQ failed")
 		}
@@ -150,7 +151,7 @@ func TestTrieIPv4(t *testing.T) {
 	assertEQ(a, 192, 0, 0, 0)
 	assertEQ(a, 255, 0, 0, 0)
 
-	trie = trie.removeByPeer(a)
+	allowedIPs.RemoveByPeer(a)
 
 	assertNEQ(a, 1, 0, 0, 0)
 	assertNEQ(a, 64, 0, 0, 0)
@@ -158,12 +159,12 @@ func TestTrieIPv4(t *testing.T) {
 	assertNEQ(a, 192, 0, 0, 0)
 	assertNEQ(a, 255, 0, 0, 0)
 
-	trie = nil
+	allowedIPs = AllowedIPs{}
 
 	insert(a, 192, 168, 0, 0, 16)
 	insert(a, 192, 168, 0, 0, 24)
 
-	trie = trie.removeByPeer(a)
+	allowedIPs.RemoveByPeer(a)
 
 	assertNEQ(a, 192, 168, 0, 1)
 }
@@ -181,7 +182,7 @@ func TestTrieIPv6(t *testing.T) {
 	g := &Peer{}
 	h := &Peer{}
 
-	var trie *trieEntry
+	var allowedIPs AllowedIPs
 
 	expand := func(a uint32) []byte {
 		var out [4]byte
@@ -198,7 +199,7 @@ func TestTrieIPv6(t *testing.T) {
 		addr = append(addr, expand(b)...)
 		addr = append(addr, expand(c)...)
 		addr = append(addr, expand(d)...)
-		trie = trie.insert(addr, cidr, peer)
+		allowedIPs.Insert(addr, cidr, peer)
 	}
 
 	assertEQ := func(peer *Peer, a, b, c, d uint32) {
@@ -207,7 +208,7 @@ func TestTrieIPv6(t *testing.T) {
 		addr = append(addr, expand(b)...)
 		addr = append(addr, expand(c)...)
 		addr = append(addr, expand(d)...)
-		p := trie.lookup(addr)
+		p := allowedIPs.LookupIPv6(addr)
 		if p != peer {
 			t.Error("Assert EQ failed")
 		}