pespin has submitted this change. (
https://gerrit.osmocom.org/c/libosmo-sigtran/+/42112?usp=email )
(
3 is the latest approved patch-set.
No files were changed between the latest approved patch-set and the submitted
one.
)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(-)
Approvals:
Jenkins Builder: Verified
pespin: Looks good to me, approved
osmith: Looks good to me, but someone else must approve
laforge: Looks good to me, but someone else must approve
diff --git a/src/ss7_as.c b/src/ss7_as.c
index e22fc6c..1cc212f 100644
--- a/src/ss7_as.c
+++ b/src/ss7_as.c
@@ -243,8 +243,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: merged
Gerrit-Project: libosmo-sigtran
Gerrit-Branch: master
Gerrit-Change-Id: I139aede15af6b6a77d19e6fcf6b6abe8ed6599a6
Gerrit-Change-Number: 42112
Gerrit-PatchSet: 5
Gerrit-Owner: pespin <[email protected]>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: laforge <[email protected]>
Gerrit-Reviewer: osmith <[email protected]>
Gerrit-Reviewer: pespin <[email protected]>
