tree 3e00c4841a917432e504d2d1ba7ac6b9fd3bc258
parent b718ad397e9edc9311d960a93feb6bc3a5bbb2a7
author Holger Hans Peter Freyther <zecke@selfish.org> 1371229828 +0200
committer Holger Hans Peter Freyther <holger@moiji-mobile.com> 1375281400 +0200

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.