diff options
| author | Holger Hans Peter Freyther <zecke@selfish.org> | 2013-06-14 19:10:28 +0200 |
|---|---|---|
| committer | Holger Hans Peter Freyther <holger@moiji-mobile.com> | 2013-07-31 16:36:40 +0200 |
| commit | 85d3b34ed2c3b627fca50c82abe426b7239b62a3 (patch) | |
| tree | 3e00c4841a917432e504d2d1ba7ac6b9fd3bc258 /openbsc/src/osmo-bsc_nat/Makefile.am | |
| parent | b718ad397e9edc9311d960a93feb6bc3a5bbb2a7 (diff) | |
nat: Introduce a prefix lookup tree (trie) for number rewriting
* It is a trie. The max depth of the trie is the length of the
longest prefix. The lookup is O(lookuped_prefix), but as the prefix
length is limited, the lookup time is constant.
* Each node can hold the entire prefix, has place for the rewrite
rule with up to three digits.
* A trie with 20k entries will take about 3MB ram.
* Filling the trie 100 times takes ~800ms on my i7 laptop
* 10.000.000 lookups take 315ms.. (for the same prefix).
* 93/99 lines are tested, 6/6 functions are tested, 49 of 54 branches
are tested. Only memory allocation failures are not covered
* A late addition is to handle the '+' sign and to increase the number
of chars in the rewrite prefix. The timing/line coverage has not
been updated after this change.
Diffstat (limited to 'openbsc/src/osmo-bsc_nat/Makefile.am')
| -rw-r--r-- | openbsc/src/osmo-bsc_nat/Makefile.am | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/openbsc/src/osmo-bsc_nat/Makefile.am b/openbsc/src/osmo-bsc_nat/Makefile.am index e2ba551a0..aae6d6966 100644 --- a/openbsc/src/osmo-bsc_nat/Makefile.am +++ b/openbsc/src/osmo-bsc_nat/Makefile.am @@ -7,7 +7,7 @@ bin_PROGRAMS = osmo-bsc_nat osmo_bsc_nat_SOURCES = bsc_filter.c bsc_mgcp_utils.c bsc_nat.c bsc_nat_utils.c \ bsc_nat_vty.c bsc_sccp.c bsc_ussd.c bsc_nat_ctrl.c \ - bsc_nat_rewrite.c bsc_nat_filter.c + bsc_nat_rewrite.c bsc_nat_filter.c bsc_nat_rewrite_trie.c osmo_bsc_nat_LDADD = $(top_builddir)/src/libcommon/libcommon.a \ $(top_builddir)/src/libmgcp/libmgcp.a \ $(top_builddir)/src/libbsc/libbsc.a \ |