diff options
author | Holger Hans Peter Freyther <zecke@selfish.org> | 2013-06-14 19:10:28 +0200 |
---|---|---|
committer | Holger Hans Peter Freyther <holger@moiji-mobile.com> | 2013-07-31 16:36:40 +0200 |
commit | 85d3b34ed2c3b627fca50c82abe426b7239b62a3 (patch) | |
tree | 3e00c4841a917432e504d2d1ba7ac6b9fd3bc258 /openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c | |
parent | b718ad397e9edc9311d960a93feb6bc3a5bbb2a7 (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/tests/bsc-nat-trie/bsc_nat_trie_test.c')
-rw-r--r-- | openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c new file mode 100644 index 000000000..4b4df2faf --- /dev/null +++ b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c @@ -0,0 +1,87 @@ +/* + * (C) 2013 by On-Waves + * (C) 2013 by Holger Hans Peter Freyther <zecke@selfish.org> + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + */ + +#include <openbsc/nat_rewrite_trie.h> +#include <openbsc/debug.h> + +#include <osmocom/core/application.h> +#include <osmocom/core/backtrace.h> +#include <osmocom/core/talloc.h> +#include <osmocom/core/utils.h> + +#include <string.h> + +int main(int argc, char **argv) +{ + struct nat_rewrite *trie; + + osmo_init_logging(&log_info); + + printf("Testing the trie\n"); + + trie = nat_rewrite_parse(NULL, "prefixes.csv"); + OSMO_ASSERT(trie); + + /* verify that it has been parsed */ + OSMO_ASSERT(trie->prefixes == 17); + printf("Dumping the internal trie\n"); + nat_rewrite_dump(trie); + + /* now do the matching... */ + OSMO_ASSERT(!nat_rewrite_lookup(trie, "")); + OSMO_ASSERT(!nat_rewrite_lookup(trie, "2")); + + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1")->rewrite, "1") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12")->rewrite, "2") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123")->rewrite, "3") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234")->rewrite, "4") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345")->rewrite, "5") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456")->rewrite, "6") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567")->rewrite, "7") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678")->rewrite, "8") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456789")->rewrite, "9") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567890")->rewrite, "10") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "13")->rewrite, "11") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "14")->rewrite, "12") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "15")->rewrite, "13") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "16")->rewrite, "14") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "823455")->rewrite, "15") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "82")->rewrite, "16") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "+49123445")->rewrite, "17") == 0); + + /* match a prefix */ + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "121")->rewrite, "2") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1292323")->rewrite, "2") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901")->rewrite, "10") == 0); + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "160")->rewrite, "14") == 0); + + OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901123452123123")->rewrite, "10") == 0); + + /* invalid input */ + OSMO_ASSERT(!nat_rewrite_lookup(trie, "12abc")); + + talloc_free(trie); + + trie = nat_rewrite_parse(NULL, "does_not_exist.csv"); + OSMO_ASSERT(!trie); + + printf("Done with the tests.\n"); + return 0; +} |