From: Michael Tremer <michael.tremer@ipfire.org>
Date: Tue, 30 Jan 2018 23:29:52 +0000 (+0000)
Subject: database: Walk down into the tree as much as possible first
X-Git-Tag: 0.9.0~83
X-Git-Url: http://git.ipfire.org/?p=people%2Fms%2Flibloc.git;a=commitdiff_plain;h=9086d2b1db0eb01996dda2a4b50a058cb190e1c9;ds=sidebyside

database: Walk down into the tree as much as possible first

Instead of stopping when we find the largest network that
matches, we will have to go as deep as we can and then
check all networks on the way from the bottom up.

Signed-off-by: Michael Tremer <michael.tremer@ipfire.org>
---

diff --git a/src/database.c b/src/database.c
index 7c8ea89..ec8aae9 100644
--- a/src/database.c
+++ b/src/database.c
@@ -527,13 +527,6 @@ static int __loc_database_lookup(struct loc_database* db, const struct in6_addr*
 	int r;
 	off_t node_index;
 
-	// If the node is a leaf node, we end here
-	if (__loc_database_node_is_leaf(node)) {
-		r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
-		if (r <= 0)
-			return r;
-	}
-
 	// Follow the path
 	int bit = in6_addr_get_bit(address, level);
 	in6_addr_set_bit(network_address, level, bit);
@@ -543,27 +536,32 @@ static int __loc_database_lookup(struct loc_database* db, const struct in6_addr*
 	else
 		node_index = be32toh(node->one);
 
-	// If we point back to root, the path ends here
-	if (node_index == 0) {
-		DEBUG(db->ctx, "Tree ends here\n");
-		return 1;
-	}
+	// If the node index is zero, the tree ends here
+	// and we cannot descend any further
+	if (node_index > 0) {
+		// Check boundaries
+		if ((size_t)node_index >= db->network_nodes_count)
+			return -EINVAL;
 
-	// Check boundaries
-	if ((size_t)node_index >= db->network_nodes_count)
-		return -EINVAL;
+		// Move on to the next node
+		r = __loc_database_lookup(db, address, network, network_address,
+			db->network_nodes_v0 + node_index, level + 1);
 
-	// Move on to the next node
-	r = __loc_database_lookup(db, address, network, network_address,
-		db->network_nodes_v0 + node_index, level + 1);
+		// End here if a result was found
+		if (r == 0)
+			return r;
 
-	// End here if a result was found
-	if (r == 0)
-		return r;
+		// Raise any errors
+		else if (r < 0)
+			return r;
+	}
 
-	// Raise any errors
-	else if (r < 0)
-		return r;
+	// If this node has a leaf, we will check if it matches
+	if (__loc_database_node_is_leaf(node)) {
+		r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
+		if (r <= 0)
+			return r;
+	}
 
 	DEBUG(db->ctx, "Could not find an exact match at %u\n", level);