path: root/openbsc/.gitignore
diff options
authorHolger Hans Peter Freyther <zecke@selfish.org>2013-06-14 19:10:28 +0200
committerHolger Hans Peter Freyther <holger@moiji-mobile.com>2013-07-31 16:36:40 +0200
commit85d3b34ed2c3b627fca50c82abe426b7239b62a3 (patch)
tree3e00c4841a917432e504d2d1ba7ac6b9fd3bc258 /openbsc/.gitignore
parentb718ad397e9edc9311d960a93feb6bc3a5bbb2a7 (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/.gitignore')
1 files changed, 1 insertions, 0 deletions
diff --git a/openbsc/.gitignore b/openbsc/.gitignore
index 3743f6951..79222f751 100644
--- a/openbsc/.gitignore
+++ b/openbsc/.gitignore
@@ -50,6 +50,7 @@ src/osmo-bsc_nat/osmo-bsc_nat