table: implement adj-in table use routing table structures

rib and adj-in use the same data strcutures. Needs more clean up.

Signed-off-by: FUJITA Tomonori <fujita.tomonori@gmail.com>

4 files changed, 88 insertions, 80 deletions

diff --git a/internal/pkg/table/adj.go b/internal/pkg/table/adj.go
index d434c938..4b9d7c5f 100644
--- a/internal/pkg/table/adj.go
+++ b/internal/pkg/table/adj.go
@@ -23,16 +23,16 @@ import (
 
 type AdjRib struct {
 	accepted map[bgp.RouteFamily]int
-	table    map[bgp.RouteFamily]map[string]*Path
+	table    map[bgp.RouteFamily]*Table
 }
 
 func NewAdjRib(rfList []bgp.RouteFamily) *AdjRib {
-	table := make(map[bgp.RouteFamily]map[string]*Path)
-	for _, rf := range rfList {
-		table[rf] = make(map[string]*Path)
+	m := make(map[bgp.RouteFamily]*Table)
+	for _, f := range rfList {
+		m[f] = NewTable(f)
 	}
 	return &AdjRib{
-		table:    table,
+		table:    m,
 		accepted: make(map[bgp.RouteFamily]int),
 	}
 }
@@ -43,57 +43,84 @@ func (adj *AdjRib) Update(pathList []*Path) {
 			continue
 		}
 		rf := path.GetRouteFamily()
-		key := fmt.Sprintf("%d:%s", path.GetNlri().PathIdentifier(), path.getPrefix())
+		t := adj.table[path.GetRouteFamily()]
+		d := t.getOrCreateDest(path.GetNlri(), 0)
+		var old *Path
+		idx := -1
+		for i, p := range d.knownPathList {
+			if p.GetNlri().PathIdentifier() == path.GetNlri().PathIdentifier() {
+				idx = i
+				break
+			}
+		}
+		if idx != -1 {
+			old = d.knownPathList[idx]
+		}
 
-		old, found := adj.table[rf][key]
 		if path.IsWithdraw {
-			if found {
-				delete(adj.table[rf], key)
+			if idx != -1 {
+				d.knownPathList = append(d.knownPathList[:idx], d.knownPathList[idx+1:]...)
+				if len(d.knownPathList) == 0 {
+					t.deleteDest(d)
+				}
 				if !old.IsAsLooped() {
 					adj.accepted[rf]--
 				}
 			}
 			path.SetDropped(true)
 		} else {
-			if found {
+			if idx != -1 {
 				if old.IsAsLooped() && !path.IsAsLooped() {
 					adj.accepted[rf]++
 				} else if !old.IsAsLooped() && path.IsAsLooped() {
 					adj.accepted[rf]--
 				}
+				if old.Equal(path) {
+					path.setTimestamp(old.GetTimestamp())
+				}
+				d.knownPathList[idx] = path
 			} else {
+				d.knownPathList = append(d.knownPathList, path)
 				if !path.IsAsLooped() {
 					adj.accepted[rf]++
 				}
 			}
-			if found && old.Equal(path) {
-				path.setTimestamp(old.GetTimestamp())
+		}
+	}
+}
+
+func (adj *AdjRib) walk(families []bgp.RouteFamily, fn func(*Destination) bool) {
+	for _, f := range families {
+		if t, ok := adj.table[f]; ok {
+			for _, d := range t.destinations {
+				if fn(d) {
+					return
+				}
 			}
-			adj.table[rf][key] = path
 		}
 	}
 }
 
 func (adj *AdjRib) PathList(rfList []bgp.RouteFamily, accepted bool) []*Path {
 	pathList := make([]*Path, 0, adj.Count(rfList))
-	for _, rf := range rfList {
-		for _, rr := range adj.table[rf] {
-			if accepted && rr.IsAsLooped() {
+	adj.walk(rfList, func(d *Destination) bool {
+		for _, p := range d.knownPathList {
+			if accepted && p.IsAsLooped() {
 				continue
 			}
-			pathList = append(pathList, rr)
+			pathList = append(pathList, p)
 		}
-	}
+		return false
+	})
 	return pathList
 }
 
 func (adj *AdjRib) Count(rfList []bgp.RouteFamily) int {
 	count := 0
-	for _, rf := range rfList {
-		if table, ok := adj.table[rf]; ok {
-			count += len(table)
-		}
-	}
+	adj.walk(rfList, func(d *Destination) bool {
+		count += len(d.knownPathList)
+		return false
+	})
 	return count
 }
 
@@ -109,77 +136,58 @@ func (adj *AdjRib) Accepted(rfList []bgp.RouteFamily) int {
 
 func (adj *AdjRib) Drop(rfList []bgp.RouteFamily) []*Path {
 	l := make([]*Path, 0, adj.Count(rfList))
-	for _, rf := range rfList {
-		if _, ok := adj.table[rf]; ok {
-			for _, p := range adj.table[rf] {
-				w := p.Clone(true)
-				w.SetDropped(true)
-				l = append(l, w)
-			}
-			adj.table[rf] = make(map[string]*Path)
-			adj.accepted[rf] = 0
+	adj.walk(rfList, func(d *Destination) bool {
+		for _, p := range d.knownPathList {
+			w := p.Clone(true)
+			w.SetDropped(true)
+			l = append(l, w)
 		}
+		return false
+	})
+	for _, rf := range rfList {
+		adj.table[rf] = NewTable(rf)
+		adj.accepted[rf] = 0
 	}
 	return l
 }
 
 func (adj *AdjRib) DropStale(rfList []bgp.RouteFamily) []*Path {
 	pathList := make([]*Path, 0, adj.Count(rfList))
-	for _, rf := range rfList {
-		if table, ok := adj.table[rf]; ok {
-			for k, p := range table {
-				if p.IsStale() {
-					delete(table, k)
-					if !p.IsAsLooped() {
-						adj.accepted[rf]--
-					}
-					w := p.Clone(true)
-					w.SetDropped(true)
-					pathList = append(pathList, w)
-				}
+	adj.walk(rfList, func(d *Destination) bool {
+		for _, p := range d.knownPathList {
+			if p.IsStale() {
+				w := p.Clone(true)
+				w.SetDropped(true)
+				pathList = append(pathList, w)
 			}
 		}
-	}
+		return false
+	})
+	adj.Update(pathList)
 	return pathList
 }
 
 func (adj *AdjRib) StaleAll(rfList []bgp.RouteFamily) []*Path {
-	pathList := make([]*Path, 0)
-	for _, rf := range rfList {
-		if table, ok := adj.table[rf]; ok {
-			l := make([]*Path, 0, len(table))
-			for k, p := range table {
-				n := p.Clone(false)
-				n.MarkStale(true)
-				table[k] = n
-				l = append(l, n)
-			}
-			if len(l) > 0 {
-				pathList = append(pathList, l...)
-			}
+	pathList := make([]*Path, 0, adj.Count(rfList))
+	adj.walk(rfList, func(d *Destination) bool {
+		for i, p := range d.knownPathList {
+			n := p.Clone(false)
+			n.MarkStale(true)
+			d.knownPathList[i] = n
+			pathList = append(pathList, n)
 		}
-	}
+		return false
+	})
 	return pathList
 }
 
 func (adj *AdjRib) Select(family bgp.RouteFamily, accepted bool, option ...TableSelectOption) (*Table, error) {
-	m := make(map[string][]*Path)
-	pl := adj.PathList([]bgp.RouteFamily{family}, accepted)
-	for _, path := range pl {
-		key := path.GetNlri().String()
-		if _, y := m[key]; y {
-			m[key] = append(m[key], path)
-		} else {
-			m[key] = []*Path{path}
-		}
-	}
-	d := make([]*Destination, 0, len(pl))
-	for _, l := range m {
-		d = append(d, NewDestination(l[0].GetNlri(), 0, l...))
+	t, ok := adj.table[family]
+	if !ok {
+		t = NewTable((family))
 	}
-	tbl := NewTable(family, d...)
 	option = append(option, TableSelectOption{adj: true})
-	return tbl.Select(option...)
+	return t.Select(option...)
 }
 
 func (adj *AdjRib) TableInfo(family bgp.RouteFamily) (*TableInfo, error) {
diff --git a/internal/pkg/table/adj_test.go b/internal/pkg/table/adj_test.go
index ac4fc5a0..d4c892cf 100644
--- a/internal/pkg/table/adj_test.go
+++ b/internal/pkg/table/adj_test.go
@@ -39,14 +39,14 @@ func TestStaleAll(t *testing.T) {
 
 	adj := NewAdjRib(families)
 	adj.Update([]*Path{p1, p2})
-	assert.Equal(t, len(adj.table[family]), 2)
+	assert.Equal(t, adj.Count([]bgp.RouteFamily{family}), 2)
 
 	adj.StaleAll(families)
 
-	for _, p := range adj.table[family] {
+	for _, p := range adj.PathList([]bgp.RouteFamily{family}, false) {
 		assert.True(t, p.IsStale())
 	}
 
 	adj.DropStale(families)
-	assert.Equal(t, len(adj.table[family]), 0)
+	assert.Equal(t, adj.Count([]bgp.RouteFamily{family}), 0)
 }
diff --git a/internal/pkg/table/table.go b/internal/pkg/table/table.go
index f6ed2444..40eab0f7 100644
--- a/internal/pkg/table/table.go
+++ b/internal/pkg/table/table.go
@@ -175,7 +175,7 @@ func (t *Table) validatePath(path *Path) {
 	}
 }
 
-func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
+func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface, size int) *Destination {
 	dest := t.GetDestination(nlri)
 	// If destination for given prefix does not exist we create it.
 	if dest == nil {
@@ -183,7 +183,7 @@ func (t *Table) getOrCreateDest(nlri bgp.AddrPrefixInterface) *Destination {
 			"Topic": "Table",
 			"Nlri":  nlri,
 		}).Debugf("create Destination")
-		dest = NewDestination(nlri, 64)
+		dest = NewDestination(nlri, size)
 		t.setDestination(dest)
 	}
 	return dest
diff --git a/internal/pkg/table/table_manager.go b/internal/pkg/table/table_manager.go
index 55436369..aa0cd0fc 100644
--- a/internal/pkg/table/table_manager.go
+++ b/internal/pkg/table/table_manager.go
@@ -182,7 +182,7 @@ func (manager *TableManager) DeleteVrf(name string) ([]*Path, error) {
 func (tm *TableManager) update(newPath *Path) *Update {
 	t := tm.Tables[newPath.GetRouteFamily()]
 	t.validatePath(newPath)
-	dst := t.getOrCreateDest(newPath.GetNlri())
+	dst := t.getOrCreateDest(newPath.GetNlri(), 64)
 	u := dst.Calculate(newPath)
 	if len(dst.knownPathList) == 0 {
 		t.deleteDest(dst)