Beginning work on UAPI and routing table

1 files changed, 154 insertions, 0 deletions

diff --git a/src/trie.go b/src/trie.go
new file mode 100644
index 0000000..7fd7c5f
--- /dev/null
+++ b/src/trie.go
@@ -0,0 +1,154 @@
+package main
+
+import "fmt"
+
+/* Syncronization must be done seperatly
+ *
+ */
+
+type Trie struct {
+	cidr  uint
+	child [2]*Trie
+	bits  []byte
+	peer  *Peer
+
+	// Index of "branching" bit
+	// bit_at_shift
+	bit_at_byte  uint
+	bit_at_shift uint
+}
+
+/* Finds length of matching prefix
+ * Maybe there is a faster way
+ *
+ * Assumption: len(s1) == len(s2)
+ */
+func commonBits(s1 []byte, s2 []byte) uint {
+	var i uint
+	size := uint(len(s1))
+	for i = 0; i < size; i += 1 {
+		v := s1[i] ^ s2[i]
+		if v != 0 {
+			v >>= 1
+			if v == 0 {
+				return i*8 + 7
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 6
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 5
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 4
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 3
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 2
+			}
+
+			v >>= 1
+			if v == 0 {
+				return i*8 + 1
+			}
+			return i * 8
+		}
+	}
+	return i * 8
+}
+
+func (node *Trie) RemovePeer(p *Peer) *Trie {
+	if node == nil {
+		return node
+	}
+
+	// Walk recursivly
+
+	node.child[0] = node.child[0].RemovePeer(p)
+	node.child[1] = node.child[1].RemovePeer(p)
+
+	if node.peer != p {
+		return node
+	}
+
+	// Remove peer & merge
+
+	node.peer = nil
+	if node.child[0] == nil {
+		return node.child[1]
+	}
+	return node.child[0]
+}
+
+func (node *Trie) Insert(key []byte, cidr uint, peer *Peer) *Trie {
+	if node == nil {
+		return &Trie{
+			bits:         key,
+			peer:         peer,
+			cidr:         cidr,
+			bit_at_byte:  cidr / 8,
+			bit_at_shift: 7 - (cidr % 8),
+		}
+	}
+
+	// Traverse deeper
+
+	common := commonBits(node.bits, key)
+	if node.cidr <= cidr && common >= node.cidr {
+		// Check if match the t.bits[:t.cidr] exactly
+		if node.cidr == cidr {
+			node.peer = peer
+			return node
+		}
+
+		// Go to child
+		bit := (key[node.bit_at_byte] >> node.bit_at_shift) & 1
+		node.child[bit] = node.child[bit].Insert(key, cidr, peer)
+		return node
+	}
+
+	// Split node
+
+	fmt.Println("new", common)
+
+	newNode := &Trie{
+		bits:         key,
+		peer:         peer,
+		cidr:         cidr,
+		bit_at_byte:  cidr / 8,
+		bit_at_shift: 7 - (cidr % 8),
+	}
+
+	cidr = min(cidr, common)
+	node.cidr = cidr
+	node.bit_at_byte = cidr / 8
+	node.bit_at_shift = 7 - (cidr % 8)
+
+	// bval := node.bits[node.bit_at_byte] >> node.bit_at_shift // todo : remember index
+	// Work in progress
+	node.child[0] = newNode
+	node.child[1] = newNode
+
+	return node
+}
+
+func (t *Trie) Lookup(key []byte) *Peer {
+	if t == nil {
+		return nil
+	}
+
+	return nil
+
+}