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.
diff --git a/openbsc/tests/bsc-nat-trie/Makefile.am b/openbsc/tests/bsc-nat-trie/Makefile.am
new file mode 100644
index 0000000..355ed64
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/Makefile.am
@@ -0,0 +1,18 @@
+AM_CPPFLAGS = $(all_includes) -I$(top_srcdir)/include
+AM_CFLAGS=-Wall -ggdb3 $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOSCCP_CFLAGS) $(LIBOSMOABIS_CFLAGS) $(COVERAGE_CFLAGS)
+AM_LDFLAGS = $(COVERAGE_LDFLAGS)
+
+EXTRA_DIST = bsc_nat_trie_test.ok prefixes.csv
+
+noinst_PROGRAMS = bsc_nat_trie_test
+
+bsc_nat_trie_test_SOURCES = bsc_nat_trie_test.c \
+ $(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
+bsc_nat_trie_test_LDADD = $(top_builddir)/src/libbsc/libbsc.a \
+ $(top_srcdir)/src/libctrl/libctrl.a \
+ $(top_srcdir)/src/libmgcp/libmgcp.a \
+ $(top_srcdir)/src/libtrau/libtrau.a \
+ $(top_srcdir)/src/libcommon/libcommon.a \
+ $(LIBOSMOCORE_LIBS) $(LIBOSMOGSM_LIBS) -lrt \
+ $(LIBOSMOSCCP_LIBS) $(LIBOSMOVTY_LIBS) \
+ $(LIBOSMOABIS_LIBS)