From 85d3b34ed2c3b627fca50c82abe426b7239b62a3 Mon Sep 17 00:00:00 2001 From: Holger Hans Peter Freyther Date: Fri, 14 Jun 2013 19:10:28 +0200 Subject: 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. --- openbsc/include/openbsc/Makefile.am | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'openbsc/include/openbsc/Makefile.am') diff --git a/openbsc/include/openbsc/Makefile.am b/openbsc/include/openbsc/Makefile.am index 93b30bb0c..6ba6d1b97 100644 --- a/openbsc/include/openbsc/Makefile.am +++ b/openbsc/include/openbsc/Makefile.am @@ -13,7 +13,7 @@ noinst_HEADERS = abis_nm.h abis_rsl.h db.h gsm_04_08.h gsm_data.h \ osmo_bsc_rf.h osmo_bsc.h network_listen.h bsc_nat_sccp.h \ osmo_msc_data.h osmo_bsc_grace.h sms_queue.h abis_om2000.h \ bss.h gsm_data_shared.h control_cmd.h ipaccess.h mncc_int.h \ - arfcn_range_encode.h + arfcn_range_encode.h nat_rewrite_trie.h openbsc_HEADERS = gsm_04_08.h meas_rep.h bsc_api.h openbscdir = $(includedir)/openbsc -- cgit v1.2.3