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.
diff --git a/openbsc/include/openbsc/nat_rewrite_trie.h b/openbsc/include/openbsc/nat_rewrite_trie.h
new file mode 100644
index 0000000..4445c3e
--- /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 <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/>.
+ *
+ */
+#ifndef NAT_REWRITE_FILE_H
+#define NAT_REWRITE_FILE_H
+
+#include <osmocom/core/linuxrbtree.h>
+
+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