From b4e2d9e440a4eb6d3091a7c586d2e55b69ec968a Mon Sep 17 00:00:00 2001 From: FUJITA Tomonori Date: Fri, 25 Oct 2019 20:33:59 +0900 Subject: table: replace radix with crit-bit algo for longer-prefixes search faster and less memory usage. Now go-radix has gone. Signed-off-by: FUJITA Tomonori --- internal/pkg/table/table.go | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'internal/pkg/table/table.go') diff --git a/internal/pkg/table/table.go b/internal/pkg/table/table.go index 40eab0f7..bfcf2059 100644 --- a/internal/pkg/table/table.go +++ b/internal/pkg/table/table.go @@ -22,7 +22,7 @@ import ( "strings" "unsafe" - "github.com/armon/go-radix" + "github.com/k-sone/critbitgo" "github.com/osrg/gobgp/pkg/packet/bgp" log "github.com/sirupsen/logrus" ) @@ -212,14 +212,13 @@ func (t *Table) GetLongerPrefixDestinations(key string) ([]*Destination, error) if err != nil { return nil, err } - k := CidrToRadixkey(prefix.String()) - r := radix.New() + r := critbitgo.NewNet() for _, dst := range t.GetDestinations() { - r.Insert(AddrToRadixkey(dst.nlri), dst) + r.Add(nlriToIPNet(dst.nlri), dst) } - r.WalkPrefix(k, func(s string, v interface{}) bool { + r.WalkPrefix(prefix, func(_ *net.IPNet, v interface{}) bool { results = append(results, v.(*Destination)) - return false + return true }) default: for _, dst := range t.GetDestinations() { -- cgit v1.2.3