Implement new path-compressed radix trie.

- The performance benefit over the old algorithm is about 10 times.
- Memory usage is significantly lower as well.
- Now radix trie can accept any IPv4/IPv6 values

1 files changed, 18 insertions, 0 deletions

diff --git a/src/libutil/radix.h b/src/libutil/radix.h
index 5b014355e..3ecb52eba 100644
--- a/src/libutil/radix.h
+++ b/src/libutil/radix.h
@@ -9,6 +9,13 @@
 
 typedef struct radix_node_s radix_node_t;
 typedef struct radix_tree_s radix_tree_t;
+typedef struct radix_tree_compressed radix_compressed_t;
+
+enum radix_insert_type {
+	RADIX_INSERT,
+	RADIX_ADD,
+	RADIX_REPLACE
+};
 
 typedef gboolean (*radix_tree_traverse_func)(guint32 key, guint32 mask,
 	uintptr_t value, void *user_data);
@@ -86,4 +93,15 @@ void radix32tree_traverse (radix_tree_t *tree,
  */
 void radix_tree_free (radix_tree_t *tree);
 
+uintptr_t
+radix_insert_compressed (radix_compressed_t * tree,
+	guint8 *key, gsize keylen,
+	gsize masklen,
+	uintptr_t value);
+
+uintptr_t radix_find_compressed (radix_compressed_t * tree, guint8 *key,
+		gsize keylen);
+
+radix_compressed_t *radix_tree_create_compressed (void);
+
 #endif