commit f8416810aad4cba6f622c6b3f9352abdd54cd01e
author Paul Jakma <paul@quagga.net> Tue Apr 13 22:42:33 2010 +0100
committer Paul Jakma <paul@quagga.net> Wed Dec 08 17:06:12 2010 +0000
tree 7ca0d68cd44ea6c0b4d838f6526b3ccadcb836f9
parent d358344759d85a965bbd767f4a994695f99b842e

lib: Fix bug in prefix trie lookup

* lib/table.c: (route_node_match) fix overshoot that was causing this
  function to go 1 bit too far and thus reading past end of prefix.
  (route_node_lookup) be defensive - don't assume others will clean up
  leaves when removing info.

lib/table.c

diff --git a/lib/table.c b/lib/table.c
index 04df3af..e40e670 100644
--- a/lib/table.c
+++ b/lib/table.c
@@ -209,6 +209,10 @@
     {
       if (node->info)
 	matched = node;
+      
+      if (node->p.prefixlen == p->prefixlen)
+        break;
+      
       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
     }
 
@@ -260,8 +264,8 @@
   while (node && node->p.prefixlen <= p->prefixlen && 
 	 prefix_match (&node->p, p))
     {
-      if (node->p.prefixlen == p->prefixlen && node->info)
-	return route_lock_node (node);
+      if (node->p.prefixlen == p->prefixlen)
+        return node->info ? route_lock_node (node) : NULL;
 
       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
     }
@@ -283,10 +287,8 @@
 	 prefix_match (&node->p, p))
     {
       if (node->p.prefixlen == p->prefixlen)
-	{
-	  route_lock_node (node);
-	  return node;
-	}
+        return route_lock_node (node);
+      
       match = node;
       node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
     }