network: Fix walking through the tree in order

[people/ms/libloc.git] / src / network.c

diff --git a/src/network.c b/src/network.c
index 11b68dd18291376ceb64964a904299aee956a316..296a354d2e9986f969224350b67e923381ac9985 100644 (file)
--- a/src/network.c
+++ b/src/network.c
@@ -37,32 +37,81 @@ struct loc_network {
        uint32_t asn;
 };
 
+static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
+       // The prefix cannot be larger than 128 bits
+       if (prefix > 128)
+               return 1;
+
+       // And the prefix cannot be zero
+       if (prefix == 0)
+               return 1;
+
+       // For IPv4-mapped addresses the prefix has to be 96 or lager
+       if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
+               return 1;
+
+       return 0;
+}
+
+static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
+       struct in6_addr bitmask;
+
+       for (unsigned int i = 0; i < 16; i++)
+               bitmask.s6_addr[i] = 0;
+
+       for (unsigned int i = prefix, j = 0; i > 0; i -= 8, j++) {
+               if (i >= 8)
+                       bitmask.s6_addr[j] = 0xff;
+               else
+                       bitmask.s6_addr[j] = 0xff << (8 - i);
+       }
+
+       return bitmask;
+}
+
+static struct in6_addr make_start_address(struct in6_addr* address, unsigned int prefix) {
+       struct in6_addr a;
+       struct in6_addr bitmask = prefix_to_bitmask(prefix);
+
+       // Perform bitwise AND
+       for (unsigned int i = 0; i < 4; i++)
+               a.s6_addr32[i] = address->s6_addr32[i] & bitmask.s6_addr32[i];
+
+       return a;
+}
+
 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
-               struct in6_addr start_address, unsigned int prefix) {
+               struct in6_addr address, unsigned int prefix) {
        // Address cannot be unspecified
-       if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
+       if (IN6_IS_ADDR_UNSPECIFIED(&address)) {
                DEBUG(ctx, "Start address is unspecified\n");
                return -EINVAL;
        }
 
        // Address cannot be loopback
-       if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
+       if (IN6_IS_ADDR_LOOPBACK(&address)) {
                DEBUG(ctx, "Start address is loopback address\n");
                return -EINVAL;
        }
 
        // Address cannot be link-local
-       if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
+       if (IN6_IS_ADDR_LINKLOCAL(&address)) {
                DEBUG(ctx, "Start address cannot be link-local\n");
                return -EINVAL;
        }
 
        // Address cannot be site-local
-       if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
+       if (IN6_IS_ADDR_SITELOCAL(&address)) {
                DEBUG(ctx, "Start address cannot be site-local\n");
                return -EINVAL;
        }
 
+       // Validate the prefix
+       if (valid_prefix(&address, prefix) != 0) {
+               DEBUG(ctx, "Invalid prefix: %u\n", prefix);
+               return -EINVAL;
+       }
+
        struct loc_network* n = calloc(1, sizeof(*n));
        if (!n)
                return -ENOMEM;
@@ -70,7 +119,8 @@ LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network
        n->ctx = loc_ref(ctx);
        n->refcount = 1;
 
-       n->start_address = start_address;
+       // Store the first address in the network
+       n->start_address = make_start_address(&address, prefix);
        n->prefix = prefix;
 
        DEBUG(n->ctx, "Network allocated at %p\n", n);
@@ -119,7 +169,9 @@ static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_add
 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
                const char* address_string) {
        struct in6_addr start_address;
+       unsigned int prefix = 0;
        char* prefix_string;
+       int r = 1;
 
        // Make a copy of the string to work on it
        char* buffer = strdup(address_string);
@@ -128,11 +180,20 @@ LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_netwo
        // Split address and prefix
        address_string = strsep(&prefix_string, "/");
 
-       // Convert prefix to integer
-       unsigned int prefix = strtol(prefix_string, NULL, 10);
+       // Did we find a prefix?
+       if (prefix_string) {
+               // Convert prefix to integer
+               prefix = strtol(prefix_string, NULL, 10);
+
+               if (prefix) {
+                       // Parse the address
+                       r = parse_address(ctx, address_string, &start_address);
 
-       // Parse the address
-       int r = parse_address(ctx, address_string, &start_address);
+                       // Map the prefix to IPv6 if needed
+                       if (IN6_IS_ADDR_V4MAPPED(&start_address))
+                               prefix += 96;
+               }
+       }
 
        // Free temporary buffer
        free(buffer);
@@ -192,6 +253,8 @@ LOC_EXPORT char* loc_network_str(struct loc_network* network) {
        if (!string)
                return NULL;
 
+       unsigned int prefix = network->prefix;
+
        int family = loc_network_address_family(network);
        switch (family) {
                case AF_INET6:
@@ -200,6 +263,7 @@ LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 
                case AF_INET:
                        r = format_ipv4_address(network, string, length);
+                       prefix -= 96;
                        break;
 
                default:
@@ -215,7 +279,7 @@ LOC_EXPORT char* loc_network_str(struct loc_network* network) {
        }
 
        // Append prefix
-       sprintf(string + strlen(string), "/%u", network->prefix);
+       sprintf(string + strlen(string), "/%u", prefix);
 
        return string;
 }
@@ -247,7 +311,7 @@ LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 }
 
 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
-       dbobj->prefix = htobe16(network->prefix);
+       dbobj->prefix = network->prefix;
 
        // Add country code
        for (unsigned int i = 0; i < 2; i++) {
@@ -305,9 +369,9 @@ static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_networ
        struct loc_network_tree_node** n;
 
        if (path)
-               n = &node->one;
-       else
                n = &node->zero;
+       else
+               n = &node->one;
 
        // If the desired node doesn't exist, yet, we will create it
        if (*n == NULL) {
@@ -405,7 +469,7 @@ LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tr
        return NULL;
 }
 
-int __loc_network_tree_dump(struct loc_network* network, void* data) {
+static int __loc_network_tree_dump(struct loc_network* network, void* data) {
        DEBUG(network->ctx, "Dumping network at %p\n", network);
 
        char* s = loc_network_str(network);
@@ -463,3 +527,19 @@ LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree)
 
        return counter;
 }
+
+static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
+       size_t counter = 1;
+
+       if (node->zero)
+               counter += __loc_network_tree_count_nodes(node->zero);
+
+       if (node->one)
+               counter += __loc_network_tree_count_nodes(node->one);
+
+       return counter;
+}
+
+LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
+       return __loc_network_tree_count_nodes(tree->root);
+}