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/nat_rewrite_trie.h | 44 ++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 openbsc/include/openbsc/nat_rewrite_trie.h (limited to 'openbsc/include/openbsc/nat_rewrite_trie.h') diff --git a/openbsc/include/openbsc/nat_rewrite_trie.h b/openbsc/include/openbsc/nat_rewrite_trie.h new file mode 100644 index 000000000..4445c3e09 --- /dev/null +++ b/openbsc/include/openbsc/nat_rewrite_trie.h @@ -0,0 +1,44 @@ +/* + * (C) 2013 by On-Waves + * (C) 2013 by Holger Hans Peter Freyther + * 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 . + * + */ +#ifndef NAT_REWRITE_FILE_H +#define NAT_REWRITE_FILE_H + +#include + +struct nat_rewrite_rule { + /* For digits 0-9 and + */ + struct nat_rewrite_rule *rules[11]; + + char empty; + char prefix[14]; + char rewrite[4]; +}; + +struct nat_rewrite { + struct nat_rewrite_rule rule; + size_t prefixes; +}; + + +struct nat_rewrite *nat_rewrite_parse(void *ctx, const char *filename); +struct nat_rewrite_rule *nat_rewrite_lookup(struct nat_rewrite *, const char *prefix); +void nat_rewrite_dump(struct nat_rewrite *rewr); + +#endif -- cgit v1.2.3