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.

1 files changed, 44 insertions, 0 deletions

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 <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