pespin has uploaded this change for review. (
https://gerrit.osmocom.org/c/libosmo-sigtran/+/42112?usp=email )
Change subject: ss7_as: Optimize ss7_as_asp_assoc_find()
......................................................................
ss7_as: Optimize ss7_as_asp_assoc_find()
Look for counterpart on the object with the shortest list, ie. convert
from O(N) to O(min(N,M)).
This way eg. if we have 100 ASPs on 1 AS, lookup time becomes O(1).
Same if we have eg. 1 ASP serving 100 AS.
Change-Id: I139aede15af6b6a77d19e6fcf6b6abe8ed6599a6
---
M src/ss7_as.c
1 file changed, 14 insertions(+), 2 deletions(-)
git pull ssh://gerrit.osmocom.org:29418/libosmo-sigtran
refs/changes/12/42112/1
diff --git a/src/ss7_as.c b/src/ss7_as.c
index a0c3cf0..35c85f7 100644
--- a/src/ss7_as.c
+++ b/src/ss7_as.c
@@ -241,8 +241,20 @@
const struct osmo_ss7_asp
*asp)
{
struct ss7_as_asp_assoc *assoc;
- llist_for_each_entry(assoc, &as->assoc_asp_list, as_entry) {
- if (assoc->asp == asp)
+ OSMO_ASSERT(as);
+ OSMO_ASSERT(asp);
+
+ /* Optimization: Look for counterpart on the object with the shortest
list: */
+ if (as->num_assoc_asps <= asp->num_assoc_as) {
+ llist_for_each_entry(assoc, &as->assoc_asp_list, as_entry) {
+ if (assoc->asp == asp)
+ return assoc;
+ }
+ return NULL;
+ }
+
+ llist_for_each_entry(assoc, &asp->assoc_as_list, asp_entry) {
+ if (assoc->as == as)
return assoc;
}
return NULL;
--
To view, visit https://gerrit.osmocom.org/c/libosmo-sigtran/+/42112?usp=email
To unsubscribe, or for help writing mail filters, visit
https://gerrit.osmocom.org/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: libosmo-sigtran
Gerrit-Branch: master
Gerrit-Change-Id: I139aede15af6b6a77d19e6fcf6b6abe8ed6599a6
Gerrit-Change-Number: 42112
Gerrit-PatchSet: 1
Gerrit-Owner: pespin <[email protected]>
