diff options
| author | Pau Espin Pedrol <pespin@sysmocom.de> | 2023-03-10 17:33:54 +0100 |
|---|---|---|
| committer | Pau Espin Pedrol <pespin@sysmocom.de> | 2023-03-10 17:56:42 +0100 |
| commit | 253c45307efc0e763b4458dd2420d9861f458d29 (patch) | |
| tree | 09a7cf3a9b7d0f9b4885f699865d742bb8f1edd4 /src/sccp_internal.h | |
| parent | a19cf68c65c4a69e46f9a82c78d979c9ae0353cb (diff) | |
Implement sccp_instance->connections as rbtree
As a result we move from:
INSERT=O(1) SEARCH=O(n) REMOVE=O(1)
to:
INSERT=O(log(N)) SEARCH=O(log(N)) REMOVE=O(log(N))
So we get rid of O(n) complexity every time we need to find a conn
object based on conn_id. When a big number of SCCP conns is handled,
this saves a lot of CPU time every time a conn needs to be looked up,
for instance each time a message is received.
For instance, given 1500 SCCP conns, searching is ~10 steps while it
took 1500 steps beforehand.
Morever, since when creating a new conn_id the code looks if it exists
prior to it, that means in practice inserting used to took O(n), while
now it takes O(log(N)).
Change-Id: I28ac67038207e2fad89ea291629cec5b2f912461
Diffstat (limited to 'src/sccp_internal.h')
| -rw-r--r-- | src/sccp_internal.h | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/src/sccp_internal.h b/src/sccp_internal.h index 23b3ef3..bfdca34 100644 --- a/src/sccp_internal.h +++ b/src/sccp_internal.h @@ -2,6 +2,8 @@ #include <osmocom/core/fsm.h> #include <osmocom/core/prim.h> +#include <osmocom/core/linuxlist.h> +#include <osmocom/core/linuxrbtree.h> #include <osmocom/sigtran/sccp_sap.h> #include <osmocom/sigtran/osmo_ss7.h> #include <osmocom/sigtran/protocol/mtp.h> @@ -42,8 +44,8 @@ static inline const char *osmo_sccp_timer_description(enum osmo_sccp_timer val) struct osmo_sccp_instance { /* entry in global list of ss7 instances */ struct llist_head list; - /* list of 'struct sccp_connection' in this instance */ - struct llist_head connections; + /* rbtree root of 'struct sccp_connection' in this instance */ + struct rb_root connections; /* list of SCCP users in this instance */ struct llist_head users; /* routing context to be used in all outbound messages */ |