speedup lookups by avoiding heap allocations

New_Prefix2 takes a second argument which allows us to
use a static or stack variable to avoid hitting the heap.
This results in speedups for places where we previously
allocated and freed a prefix:

--------------------------- 8< ------------------------
require "rpatricia"
require "benchmark"
nr = 1000000
addr = "127.1.1.1"
p = Patricia.new
p.add "127.0.0.0/8"
res = Benchmark.measure do
  nr.times { p.include?(addr) }
end
p res
--------------------------- 8< ------------------------
            user     system      total        real
before  0.470000   0.000000   0.470000 (  0.467902)
 after  0.330000   0.000000   0.330000 (  0.328538)

3 files changed, 26 insertions, 38 deletions

diff --git a/ext/rpatricia/patricia.c b/ext/rpatricia/patricia.c
index 44cc01c..9913a3f 100644
--- a/ext/rpatricia/patricia.c
+++ b/ext/rpatricia/patricia.c
@@ -148,9 +148,8 @@ New_Prefix (int family, void *dest, int bitlen)
 /* ascii2prefix
  */
 prefix_t *
-ascii2prefix(char *string)
+ascii2prefix(char *string, prefix_t *prefix)
 {
-    prefix_t *prefix;
     long bitlen;
     size_t maxbitlen;
     void *dest;
@@ -185,10 +184,10 @@ ascii2prefix(char *string)
     if (result != 1)
         return NULL;
 
-    return New_Prefix2(family, &addr, bitlen, NULL);
+    return New_Prefix2(family, &addr, bitlen, prefix);
 }
 
-prefix_t *
+static prefix_t *
 Ref_Prefix (prefix_t * prefix)
 {
     if (prefix == NULL)
@@ -201,7 +200,7 @@ Ref_Prefix (prefix_t * prefix)
     return (prefix);
 }
 
-void 
+static void
 Deref_Prefix (prefix_t * prefix)
 {
     if (prefix == NULL)
diff --git a/ext/rpatricia/patricia.h b/ext/rpatricia/patricia.h
index f4abffd..4bde733 100644
--- a/ext/rpatricia/patricia.h
+++ b/ext/rpatricia/patricia.h
@@ -86,7 +86,7 @@ void patricia_process (patricia_tree_t *patricia, void_fn_t func);
 /* { from demo.c */
 
 prefix_t *
-ascii2prefix (char *string);
+ascii2prefix (char *string, prefix_t *prefix);
 
 /* } */
 
diff --git a/ext/rpatricia/rpatricia.c b/ext/rpatricia/rpatricia.c
index 4132c32..066f82e 100644
--- a/ext/rpatricia/rpatricia.c
+++ b/ext/rpatricia/rpatricia.c
@@ -43,24 +43,18 @@ wrap_node(patricia_node_t *orig)
   return Data_Wrap_Struct(cNode, p_node_mark, -1, node);
 }
 
-static prefix_t *
-my_ascii2prefix(patricia_tree_t *tree, VALUE str)
+static void
+my_ascii2prefix(patricia_tree_t *tree, VALUE str, prefix_t *prefix)
 {
   char *cstr = StringValuePtr(str);
-  prefix_t *prefix = ascii2prefix(cstr);
+  prefix_t *ok = ascii2prefix(cstr, prefix);
 
-  if (!prefix)
+  if (!ok)
     rb_raise(rb_eArgError, "invalid prefix: %s", cstr);
 
-  if (prefix->bitlen > tree->maxbits) {
-    unsigned bitlen = prefix->bitlen;
-
-    Deref_Prefix(prefix);
+  if (prefix->bitlen > tree->maxbits)
     rb_raise(rb_eArgError, "prefix length (%u) larger than maxbits (%u)",
-             bitlen, tree->maxbits);
-  }
-
-  return prefix;
+             prefix->bitlen, tree->maxbits);
 }
 
 static VALUE
@@ -69,15 +63,14 @@ p_add (int argc, VALUE *argv, VALUE self)
   VALUE user_data;
   patricia_tree_t *tree;
   patricia_node_t *node;
-  prefix_t *prefix;
+  prefix_t prefix;
 
   if (argc > 2 || argc < 1) 
     return Qnil;
 
   Data_Get_Struct(self, patricia_tree_t, tree);
-  prefix = my_ascii2prefix(tree, argv[0]);
-  node = patricia_lookup(tree, prefix);
-  Deref_Prefix(prefix);
+  my_ascii2prefix(tree, argv[0], &prefix);
+  node = patricia_lookup(tree, &prefix);
 
   if (argc == 2) {
     user_data = argv[1];
@@ -99,12 +92,11 @@ p_remove (VALUE self, VALUE r_key)
 {
   patricia_tree_t *tree;
   patricia_node_t *node;
-  prefix_t *prefix;
+  prefix_t prefix;
 
   Data_Get_Struct(self, patricia_tree_t, tree);
-  prefix = my_ascii2prefix(tree, r_key);
-  node = patricia_search_exact(tree, prefix);
-  Deref_Prefix (prefix);
+  my_ascii2prefix(tree, r_key, &prefix);
+  node = patricia_search_exact(tree, &prefix);
 
   if (node) {
     patricia_remove (tree, node);
@@ -119,12 +111,11 @@ p_match (VALUE self, VALUE r_key)
 {
   patricia_tree_t *tree;
   patricia_node_t *node;
-  prefix_t *prefix;
+  prefix_t prefix;
   
   Data_Get_Struct(self, patricia_tree_t, tree);
-  prefix = my_ascii2prefix(tree, r_key);
-  node = patricia_search_best(tree, prefix);
-  Deref_Prefix (prefix);
+  my_ascii2prefix(tree, r_key, &prefix);
+  node = patricia_search_best(tree, &prefix);
 
   return node ? wrap_node(node) : Qnil;
 }
@@ -134,12 +125,11 @@ p_include (VALUE self, VALUE r_key)
 {
   patricia_tree_t *tree;
   patricia_node_t *node;
-  prefix_t *prefix;
+  prefix_t prefix;
 
   Data_Get_Struct(self, patricia_tree_t, tree);
-  prefix = my_ascii2prefix(tree, r_key);
-  node = patricia_search_best(tree, prefix);
-  Deref_Prefix (prefix);
+  my_ascii2prefix(tree, r_key, &prefix);
+  node = patricia_search_best(tree, &prefix);
 
   return node ? Qtrue : Qfalse;
 }
@@ -149,12 +139,11 @@ p_match_exact (VALUE self, VALUE r_key)
 {
   patricia_tree_t *tree;
   patricia_node_t *node;
-  prefix_t *prefix;
+  prefix_t prefix;
 
   Data_Get_Struct(self, patricia_tree_t, tree);
-  prefix = my_ascii2prefix(tree, r_key);
-  node = patricia_search_exact(tree, prefix);
-  Deref_Prefix (prefix);
+  my_ascii2prefix(tree, r_key, &prefix);
+  node = patricia_search_exact(tree, &prefix);
 
   return node ? wrap_node(node) : Qnil;
 }