VOL-2957 - Improved time complexity of portUpdated.
From O(n^2) to O(n*log(n)).
Change-Id: I90c4f7a88077cd1168eff632690f760d7931901c
diff --git a/rw_core/core/device/logical_agent.go b/rw_core/core/device/logical_agent.go
index 6236d81..c872da9 100644
--- a/rw_core/core/device/logical_agent.go
+++ b/rw_core/core/device/logical_agent.go
@@ -1707,48 +1707,34 @@
}
// diff go over two lists of logical ports and return what's new, what's changed and what's removed.
-func diff(oldList, newList []*voltha.LogicalPort) (newPorts, changedPorts, deletedPorts []*voltha.LogicalPort) {
- newPorts = make([]*voltha.LogicalPort, 0)
- changedPorts = make([]*voltha.LogicalPort, 0)
- deletedPorts = make([]*voltha.LogicalPort, 0)
- for _, o := range oldList {
- found := false
- for _, n := range newList {
- if o.Id == n.Id {
- found = true
- break
- }
- }
- if !found {
- deletedPorts = append(deletedPorts, o)
- }
- }
+func diff(oldList, newList []*voltha.LogicalPort) (newPorts, changedPorts, deletedPorts map[string]*voltha.LogicalPort) {
+ newPorts = make(map[string]*voltha.LogicalPort, len(newList))
+ changedPorts = make(map[string]*voltha.LogicalPort, len(oldList))
+ deletedPorts = make(map[string]*voltha.LogicalPort, len(oldList))
+
for _, n := range newList {
- found := false
- changed := false
- for _, o := range oldList {
- if o.Id == n.Id {
- changed = !proto.Equal(o, n)
- found = true
- break
+ newPorts[n.Id] = n
+ }
+
+ for _, o := range oldList {
+ if n, have := newPorts[o.Id]; have {
+ delete(newPorts, o.Id) // not new
+ if !proto.Equal(n, o) {
+ changedPorts[n.Id] = n // changed
}
- }
- if !found {
- newPorts = append(newPorts, n)
- }
- if changed {
- changedPorts = append(changedPorts, n)
+ } else {
+ deletedPorts[o.Id] = o // deleted
}
}
- return
+
+ return newPorts, changedPorts, deletedPorts
}
-// portUpdated is invoked when a port is updated on the logical device. Until
-// the POST_ADD notification is fixed, we will use the logical device to
-// update that data.
-func (agent *LogicalAgent) portUpdated(oldPorts, newPorts []*voltha.LogicalPort) interface{} {
+// portUpdated is invoked when a port is updated on the logical device
+func (agent *LogicalAgent) portUpdated(prevPorts, currPorts []*voltha.LogicalPort) interface{} {
// Get the difference between the two list
- newPorts, changedPorts, deletedPorts := diff(oldPorts, newPorts)
+ newPorts, changedPorts, deletedPorts := diff(prevPorts, currPorts)
+
// Send the port change events to the OF controller
for _, newP := range newPorts {
go agent.ldeviceMgr.eventCallbacks.SendChangeEvent(agent.logicalDeviceID,
diff --git a/rw_core/core/device/logical_agent_test.go b/rw_core/core/device/logical_agent_test.go
index 3c3b2b0..8a00a9e 100644
--- a/rw_core/core/device/logical_agent_test.go
+++ b/rw_core/core/device/logical_agent_test.go
@@ -162,8 +162,8 @@
assert.Equal(t, 2, len(newPorts))
assert.Equal(t, 0, len(changedPorts))
assert.Equal(t, 0, len(deletedPorts))
- assert.Equal(t, updatedLogicalPorts[0], newPorts[0])
- assert.Equal(t, updatedLogicalPorts[1], newPorts[1])
+ assert.Equal(t, updatedLogicalPorts[0], newPorts[updatedLogicalPorts[0].Id])
+ assert.Equal(t, updatedLogicalPorts[1], newPorts[updatedLogicalPorts[1].Id])
}
func TestLogicalDeviceAgent_diff_delete(t *testing.T) {
@@ -186,7 +186,7 @@
assert.Equal(t, 0, len(newPorts))
assert.Equal(t, 0, len(changedPorts))
assert.Equal(t, 1, len(deletedPorts))
- assert.Equal(t, currentLogicalPorts[0], deletedPorts[0])
+ assert.Equal(t, currentLogicalPorts[0], deletedPorts[currentLogicalPorts[0].Id])
}
func TestLogicalDeviceAgent_diff_changed(t *testing.T) {
@@ -270,8 +270,8 @@
assert.Equal(t, 0, len(newPorts))
assert.Equal(t, 2, len(changedPorts))
assert.Equal(t, 0, len(deletedPorts))
- assert.Equal(t, updatedLogicalPorts[0], changedPorts[0])
- assert.Equal(t, updatedLogicalPorts[1], changedPorts[1])
+ assert.Equal(t, updatedLogicalPorts[0], changedPorts[updatedLogicalPorts[0].Id])
+ assert.Equal(t, updatedLogicalPorts[1], changedPorts[updatedLogicalPorts[1].Id])
}
func TestLogicalDeviceAgent_diff_mix(t *testing.T) {
@@ -355,9 +355,9 @@
assert.Equal(t, 1, len(newPorts))
assert.Equal(t, 2, len(changedPorts))
assert.Equal(t, 1, len(deletedPorts))
- assert.Equal(t, updatedLogicalPorts[0], changedPorts[0])
- assert.Equal(t, updatedLogicalPorts[1], changedPorts[1])
- assert.Equal(t, currentLogicalPorts[2], deletedPorts[0])
+ assert.Equal(t, updatedLogicalPorts[0], changedPorts[updatedLogicalPorts[0].Id])
+ assert.Equal(t, updatedLogicalPorts[1], changedPorts[updatedLogicalPorts[1].Id])
+ assert.Equal(t, currentLogicalPorts[2], deletedPorts[currentLogicalPorts[2].Id])
}
type LDATest struct {