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/testsuite.at b/openbsc/tests/testsuite.at
index ea3fa1c..148b3d3 100644
--- a/openbsc/tests/testsuite.at
+++ b/openbsc/tests/testsuite.at
@@ -48,6 +48,14 @@
AT_CHECK([$abs_top_builddir/tests/smpp/smpp_test], [], [expout], [experr])
AT_CLEANUP
+AT_SETUP([bsc-nat-trie])
+AT_KEYWORDS([bsc-nat-trie])
+AT_CHECK([test "$enable_nat_test" != no || exit 77])
+cp $abs_srcdir/bsc-nat-trie/prefixes.csv .
+cat $abs_srcdir/bsc-nat-trie/bsc_nat_trie_test.ok > expout
+AT_CHECK([$abs_top_builddir/tests/bsc-nat-trie/bsc_nat_trie_test], [], [expout], [ignore])
+AT_CLEANUP
+
AT_SETUP([si])
AT_KEYWORDS([si])
cat $abs_srcdir/si/si_test.ok > expout