network: Optimise _subnet function

This function used to create a network list which always
had exactly two elements. Since splitting a network in half
always returns two parts, we can simply return them as a
pointer.

This improves returning the network tree by about 17%.

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

diff --git a/src/loc/network.h b/src/loc/network.h
index 4b7410c48bdb9567050f5892a8b8a0ec5473a222..d67ec54a47d7e07d334c7b2fb3bbfa54dc7a77d5 100644 (file)
--- a/src/loc/network.h
+++ b/src/loc/network.h
@@ -62,7 +62,7 @@ int loc_network_gt(struct loc_network* self, struct loc_network* other);
 int loc_network_overlaps(struct loc_network* self, struct loc_network* other);
 int loc_network_is_subnet(struct loc_network* self, struct loc_network* other);
 int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other);
-struct loc_network_list* loc_network_subnets(struct loc_network* network);
+int loc_network_subnets(struct loc_network* network, struct loc_network** subnet1, struct loc_network** subnet2);
 struct loc_network_list* loc_network_exclude(
                struct loc_network* self, struct loc_network* other);
 struct loc_network_list* loc_network_exclude_list(

diff --git a/src/network.c b/src/network.c
index 3271272a5def8f1daae11a4a23240fd87b863ed1..ff9c1eb9373ef70e3eb760e39c9b41903f87a6de 100644 (file)
--- a/src/network.c
+++ b/src/network.c
@@ -507,66 +507,91 @@ LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_net
        return loc_network_is_subnet(other, self);
 }
 
-LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
-       struct loc_network_list* list;
+LOC_EXPORT int loc_network_subnets(struct loc_network* network,
+               struct loc_network** subnet1, struct loc_network** subnet2) {
+       int r;
+       *subnet1 = NULL;
+       *subnet2 = NULL;
 
        // New prefix length
        unsigned int prefix = network->prefix + 1;
 
        // Check if the new prefix is valid
        if (valid_prefix(&network->first_address, prefix))
-               return NULL;
-
-       // Create a new list with the result
-       int r = loc_network_list_new(network->ctx, &list);
-       if (r) {
-               ERROR(network->ctx, "Could not create network list: %d\n", r);
-               return NULL;
-       }
-
-       struct loc_network* subnet1 = NULL;
-       struct loc_network* subnet2 = NULL;
+               return -1;
 
        // Create the first half of the network
-       r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
+       r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
        if (r)
-               goto ERROR;
+               return r;
 
        // The next subnet starts after the first one
-       struct in6_addr first_address = address_increment(&subnet1->last_address);
+       struct in6_addr first_address = address_increment(&(*subnet1)->last_address);
 
        // Create the second half of the network
-       r = loc_network_new(network->ctx, &subnet2, &first_address, prefix);
-       if (r)
-               goto ERROR;
-
-       // Push the both onto the stack (in reverse order)
-       r = loc_network_list_push(list, subnet2);
+       r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
        if (r)
-               goto ERROR;
-
-       r = loc_network_list_push(list, subnet1);
-       if (r)
-               goto ERROR;
+               return r;
 
        // Copy country code
        const char* country_code = loc_network_get_country_code(network);
        if (country_code) {
-               loc_network_set_country_code(subnet1, country_code);
-               loc_network_set_country_code(subnet2, country_code);
+               loc_network_set_country_code(*subnet1, country_code);
+               loc_network_set_country_code(*subnet2, country_code);
        }
 
        // Copy ASN
        uint32_t asn = loc_network_get_asn(network);
        if (asn) {
-               loc_network_set_asn(subnet1, asn);
-               loc_network_set_asn(subnet2, asn);
+               loc_network_set_asn(*subnet1, asn);
+               loc_network_set_asn(*subnet2, asn);
        }
 
-       loc_network_unref(subnet1);
-       loc_network_unref(subnet2);
+       return 0;
+}
 
-       return list;
+static int __loc_network_exclude(struct loc_network* network,
+               struct loc_network* other, struct loc_network_list* list) {
+       struct loc_network* subnet1 = NULL;
+       struct loc_network* subnet2 = NULL;
+
+       int r = loc_network_subnets(network, &subnet1, &subnet2);
+       if (r)
+               goto ERROR;
+
+       if (loc_network_eq(other, subnet1)) {
+               r = loc_network_list_push(list, subnet2);
+               if (r)
+                       goto ERROR;
+
+       } else if (loc_network_eq(other, subnet2)) {
+               r = loc_network_list_push(list, subnet1);
+               if (r)
+                       goto ERROR;
+
+       } else  if (loc_network_is_subnet_of(other, subnet1)) {
+               r = loc_network_list_push(list, subnet2);
+               if (r)
+                       goto ERROR;
+
+               r = __loc_network_exclude(subnet1, other, list);
+               if (r)
+                       goto ERROR;
+
+       } else if (loc_network_is_subnet_of(other, subnet2)) {
+               r = loc_network_list_push(list, subnet1);
+               if (r)
+                       goto ERROR;
+
+               r = __loc_network_exclude(subnet2, other, list);
+               if (r)
+                       goto ERROR;
+
+       } else {
+               ERROR(network->ctx, "We should never get here\n");
+               r = 1;
+               goto ERROR;
+       }
 
 ERROR:
        if (subnet1)
@@ -575,10 +600,7 @@ ERROR:
        if (subnet2)
                loc_network_unref(subnet2);
 
-       if (list)
-               loc_network_list_unref(list);
-
-       return NULL;
+       return r;
 }
 
 LOC_EXPORT struct loc_network_list* loc_network_exclude(
@@ -623,67 +645,15 @@ LOC_EXPORT struct loc_network_list* loc_network_exclude(
                return NULL;
        }
 
-       struct loc_network_list* subnets = loc_network_subnets(self);
-
-       struct loc_network* subnet1 = NULL;
-       struct loc_network* subnet2 = NULL;
-
-       while (subnets) {
-               // Fetch both subnets
-               subnet1 = loc_network_list_get(subnets, 0);
-               subnet2 = loc_network_list_get(subnets, 1);
-
-               // Free list
-               loc_network_list_unref(subnets);
-               subnets = NULL;
-
-               if (loc_network_eq(other, subnet1)) {
-                       r = loc_network_list_push(list, subnet2);
-                       if (r)
-                               goto ERROR;
-
-               } else if (loc_network_eq(other, subnet2)) {
-                       r = loc_network_list_push(list, subnet1);
-                       if (r)
-                               goto ERROR;
-
-               } else  if (loc_network_is_subnet_of(other, subnet1)) {
-                       r = loc_network_list_push(list, subnet2);
-                       if (r)
-                               goto ERROR;
-
-                       subnets = loc_network_subnets(subnet1);
-
-               } else if (loc_network_is_subnet_of(other, subnet2)) {
-                       r = loc_network_list_push(list, subnet1);
-                       if (r)
-                               goto ERROR;
-
-                       subnets = loc_network_subnets(subnet2);
-
-               } else {
-                       ERROR(self->ctx, "We should never get here\n");
-                       goto ERROR;
-               }
+       r = __loc_network_exclude(self, other, list);
+       if (r) {
+               loc_network_list_unref(list);
 
-               loc_network_unref(subnet1);
-               loc_network_unref(subnet2);
+               return NULL;
        }
 
        // Return the result
        return list;
-
-ERROR:
-       if (subnet1)
-               loc_network_unref(subnet1);
-
-       if (subnet2)
-               loc_network_unref(subnet2);
-
-       if (list)
-               loc_network_list_unref(list);
-
-       return NULL;
 }
 
 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(

diff --git a/src/test-network.c b/src/test-network.c
index 7c902241a91f2b88765af7b3276ca68185d9cc31..79c29679edb3e2fdc820cb4c35cb731b099ffca6 100644 (file)
--- a/src/test-network.c
+++ b/src/test-network.c
@@ -138,47 +138,48 @@ int main(int argc, char** argv) {
        }
 
        // Check subnet function
-       err = loc_network_is_subnet_of(network1, network2);
-       if (err != 0) {
+       err = loc_network_is_subnet(network1, network2);
+       if (!err) {
                fprintf(stderr, "Subnet check 1 failed: %d\n", err);
                exit(EXIT_FAILURE);
        }
 
-       err = loc_network_is_subnet_of(network2, network1);
-       if (err != 1) {
+       err = loc_network_is_subnet(network2, network1);
+       if (err) {
                fprintf(stderr, "Subnet check 2 failed: %d\n", err);
                exit(EXIT_FAILURE);
        }
 
-       // Make list of subnets
-       struct loc_network_list* subnets = loc_network_subnets(network1);
-       if (!subnets) {
-               fprintf(stderr, "Could not find subnets of network\n");
+       // Make subnets
+       struct loc_network* subnet1 = NULL;
+       struct loc_network* subnet2 = NULL;
+
+       err  = loc_network_subnets(network1, &subnet1, &subnet2);
+       if (err || !subnet1 || !subnet2) {
+               fprintf(stderr, "Could not find subnets of network: %d\n", err);
                exit(EXIT_FAILURE);
        }
 
-       loc_network_list_dump(subnets);
-
-       while (!loc_network_list_empty(subnets)) {
-               struct loc_network* subnet = loc_network_list_pop(subnets);
-               if (!subnet) {
-                       fprintf(stderr, "Received an empty subnet\n");
-                       exit(EXIT_FAILURE);
-               }
+       char* s = loc_network_str(subnet1);
+       printf("Received subnet1 = %s\n", s);
+       free(s);
 
-               char* s = loc_network_str(subnet);
-               printf("Received subnet %s\n", s);
-               free(s);
+       s = loc_network_str(subnet2);
+       printf("Received subnet2 = %s\n", s);
+       free(s);
 
-               if (!loc_network_is_subnet_of(subnet, network1)) {
-                       fprintf(stderr, "Not a subnet\n");
-                       exit(EXIT_FAILURE);
-               }
+       if (!loc_network_is_subnet(network1, subnet1)) {
+               fprintf(stderr, "Subnet1 is not a subnet\n");
+               exit(EXIT_FAILURE);
+       }
 
-               loc_network_unref(subnet);
+       if (!loc_network_is_subnet(network1, subnet2)) {
+               fprintf(stderr, "Subnet2 is not a subnet\n");
+               exit(EXIT_FAILURE);
        }
 
-       loc_network_list_unref(subnets);
+       loc_network_unref(subnet1);
+       loc_network_unref(subnet2);
 
        struct loc_network_list* excluded = loc_network_exclude(network1, network2);
        if (!excluded) {