From 75e6d810edd3026b60fb3ca7b759236e555c2d0d Mon Sep 17 00:00:00 2001
From: "Jason A. Donenfeld" <Jason@zx2c4.com>
Date: Wed, 10 Feb 2021 18:19:11 +0100
Subject: device: use container/list instead of open coding it

This linked list implementation is awful, but maybe Go 2 will help
eventually, and at least we're not open coding the hlist any more.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 device/allowedips.go | 41 ++++++++++++++---------------------------
 1 file changed, 14 insertions(+), 27 deletions(-)

(limited to 'device/allowedips.go')

diff --git a/device/allowedips.go b/device/allowedips.go
index cb6df0a..b6f096a 100644
--- a/device/allowedips.go
+++ b/device/allowedips.go
@@ -6,6 +6,7 @@
 package device
 
 import (
+	"container/list"
 	"errors"
 	"math/bits"
 	"net"
@@ -14,14 +15,13 @@ import (
 )
 
 type trieEntry struct {
-	child             [2]*trieEntry
-	peer              *Peer
-	bits              net.IP
-	cidr              uint
-	bit_at_byte       uint
-	bit_at_shift      uint
-	nextEntryForPeer  *trieEntry
-	pprevEntryForPeer **trieEntry
+	child        [2]*trieEntry
+	peer         *Peer
+	bits         net.IP
+	cidr         uint
+	bit_at_byte  uint
+	bit_at_shift uint
+	perPeerElem  *list.Element
 }
 
 func isLittleEndian() bool {
@@ -69,28 +69,14 @@ func commonBits(ip1 net.IP, ip2 net.IP) uint {
 }
 
 func (node *trieEntry) addToPeerEntries() {
-	p := node.peer
-	first := p.firstTrieEntry
-	node.nextEntryForPeer = first
-	if first != nil {
-		first.pprevEntryForPeer = &node.nextEntryForPeer
-	}
-	p.firstTrieEntry = node
-	node.pprevEntryForPeer = &p.firstTrieEntry
+	node.perPeerElem = node.peer.trieEntries.PushBack(node)
 }
 
 func (node *trieEntry) removeFromPeerEntries() {
-	if node.pprevEntryForPeer == nil {
-		return
-	}
-	next := node.nextEntryForPeer
-	pprev := node.pprevEntryForPeer
-	*pprev = next
-	if next != nil {
-		next.pprevEntryForPeer = pprev
+	if node.perPeerElem != nil {
+		node.peer.trieEntries.Remove(node.perPeerElem)
+		node.perPeerElem = nil
 	}
-	node.nextEntryForPeer = nil
-	node.pprevEntryForPeer = nil
 }
 
 func (node *trieEntry) removeByPeer(p *Peer) *trieEntry {
@@ -226,7 +212,8 @@ func (table *AllowedIPs) EntriesForPeer(peer *Peer, cb func(ip net.IP, cidr uint
 	table.mutex.RLock()
 	defer table.mutex.RUnlock()
 
-	for node := peer.firstTrieEntry; node != nil; node = node.nextEntryForPeer {
+	for elem := peer.trieEntries.Front(); elem != nil; elem = elem.Next() {
+		node := elem.Value.(*trieEntry)
 		if !cb(node.bits, node.cidr) {
 			return
 		}
-- 
cgit v1.2.3