network: Add functions to break network into subnets

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

diff --git a/src/libloc.sym b/src/libloc.sym
index a5641c6bacdc466314cbd47c74a85276df0ae88f..fcb9ea5c9a4960bb8cad7b0b27e7a45ed83dbb47 100644 (file)
--- a/src/libloc.sym
+++ b/src/libloc.sym
@@ -80,6 +80,8 @@ global:
 
        # Network
        loc_network_address_family;
+       loc_network_eq;
+       loc_network_exclude;
        loc_network_format_first_address;
        loc_network_format_last_address;
        loc_network_get_asn;
@@ -96,6 +98,7 @@ global:
        loc_network_set_country_code;
        loc_network_set_flag;
        loc_network_str;
+       loc_network_subnets;
        loc_network_unref;
 
        # Network List
@@ -107,7 +110,9 @@ global:
        loc_network_list_pop;
        loc_network_list_push;
        loc_network_list_ref;
+       loc_network_list_reverse;
        loc_network_list_size;
+       loc_network_list_sort;
        loc_network_list_unref;
 
        # Writer

diff --git a/src/loc/network.h b/src/loc/network.h
index 44c50a426e946cba95c9688eb270ee15a1371386..4e51a6299527410f9b41810e55f280dbea086b66 100644 (file)
--- a/src/loc/network.h
+++ b/src/loc/network.h
@@ -54,7 +54,11 @@ int loc_network_has_flag(struct loc_network* network, uint32_t flag);
 int loc_network_set_flag(struct loc_network* network, uint32_t flag);
 int loc_network_match_flag(struct loc_network* network, uint32_t flag);
 
+int loc_network_eq(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);
+struct loc_network_list* loc_network_exclude(
+               struct loc_network* self, struct loc_network* other);
 
 // List
 struct loc_network_list;
@@ -68,6 +72,8 @@ void loc_network_list_dump(struct loc_network_list* list);
 struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index);
 int loc_network_list_push(struct loc_network_list* list, struct loc_network* network);
 struct loc_network* loc_network_list_pop(struct loc_network_list* list);
+void loc_network_list_sort(struct loc_network_list* list);
+void loc_network_list_reverse(struct loc_network_list* list);
 
 #ifdef LIBLOC_PRIVATE
 

diff --git a/src/network.c b/src/network.c
index 097740694b4165cba922407a903b8f86d4d48858..6c08070830c9aa36cf5adecc3b5b59969d68cc58 100644 (file)
--- a/src/network.c
+++ b/src/network.c
@@ -97,6 +97,21 @@ static struct in6_addr make_last_address(const struct in6_addr* address, const s
        return a;
 }
 
+static struct in6_addr address_increment(const struct in6_addr* address) {
+       struct in6_addr a = *address;
+
+       for (int octet = 15; octet >= 0; octet--) {
+               if (a.s6_addr[octet] < 255) {
+                       a.s6_addr[octet]++;
+                       break;
+               } else {
+                       a.s6_addr[octet] = 0;
+               }
+       }
+
+       return a;
+}
+
 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
                struct in6_addr* address, unsigned int prefix) {
        // Address cannot be unspecified
@@ -405,6 +420,69 @@ LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag
        return loc_network_has_flag(network, flag);
 }
 
+LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
+#ifdef ENABLE_DEBUG
+       char* n1 = loc_network_str(self);
+       char* n2 = loc_network_str(other);
+
+       DEBUG(self->ctx, "Is %s equal to %s?\n", n1, n2);
+
+       free(n1);
+       free(n2);
+#endif
+
+       // Family must be the same
+       if (self->family != other->family) {
+               DEBUG(self->ctx, "  Family mismatch\n");
+
+               return 0;
+       }
+
+       // The start address must be the same
+       if (in6_addr_cmp(&self->first_address, &other->first_address) != 0) {
+               DEBUG(self->ctx, "  Address mismatch\n");
+
+               return 0;
+       }
+
+       // The prefix length must be the same
+       if (self->prefix != other->prefix) {
+               DEBUG(self->ctx, "  Prefix mismatch\n");
+               return 0;
+       }
+
+       DEBUG(self->ctx, "  Yes!\n");
+
+       return 1;
+}
+
+static int loc_network_gt(struct loc_network* self, struct loc_network* other) {
+       // Families must match
+       if (self->family != other->family)
+               return -1;
+
+       int r = in6_addr_cmp(&self->first_address, &other->first_address);
+
+       switch (r) {
+               // Smaller
+               case -1:
+                       return 0;
+
+               // Larger
+               case 1:
+                       return 1;
+
+               default:
+                       break;
+       }
+
+       if (self->prefix > other->prefix)
+               return 1;
+
+       // Dunno
+       return 0;
+}
+
 LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
        // If the start address of the other network is smaller than this network,
        // it cannot be a subnet.
@@ -419,6 +497,175 @@ LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_net
        return 1;
 }
 
+LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
+       struct loc_network_list* list;
+
+       // 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;
+
+       // Create the first half of the network
+       r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
+       if (r)
+               goto ERROR;
+
+       // The next subnet starts after the first one
+       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);
+       if (r)
+               goto ERROR;
+
+       r = loc_network_list_push(list, subnet1);
+       if (r)
+               goto ERROR;
+
+       loc_network_unref(subnet1);
+       loc_network_unref(subnet2);
+
+       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(
+               struct loc_network* self, struct loc_network* other) {
+       struct loc_network_list* list;
+
+#ifdef ENABLE_DEBUG
+       char* n1 = loc_network_str(self);
+       char* n2 = loc_network_str(other);
+
+       DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
+
+       free(n1);
+       free(n2);
+#endif
+
+       // Family must match
+       if (self->family != other->family) {
+               DEBUG(self->ctx, "Family mismatch\n");
+
+               return NULL;
+       }
+
+       // Other must be a subnet of self
+       if (!loc_network_is_subnet_of(other, self)) {
+               DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
+
+               return NULL;
+       }
+
+       // We cannot perform this operation if both networks equal
+       if (loc_network_eq(self, other)) {
+               DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
+
+               return NULL;
+       }
+
+       // Create a new list with the result
+       int r = loc_network_list_new(self->ctx, &list);
+       if (r) {
+               ERROR(self->ctx, "Could not create network list: %d\n", r);
+               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;
+               }
+
+               loc_network_unref(subnet1);
+               loc_network_unref(subnet2);
+       }
+
+#ifdef ENABLE_DEBUG
+       loc_network_list_dump(list);
+#endif
+
+       // 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 int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
        // Add country code
        loc_country_code_copy(dbobj->country_code, network->country_code);
@@ -854,5 +1101,46 @@ LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* lis
        if (loc_network_list_empty(list))
                return NULL;
 
-       return list->list[list->size--];
+       return list->list[--list->size];
+}
+
+static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
+       // Do nothing for invalid indices
+       if (i1 >= list->size || i2 >= list->size)
+               return;
+
+       DEBUG(list->ctx, "Swapping %u with %u\n", i1, i2);
+
+       struct loc_network* network1 = list->list[i1];
+       struct loc_network* network2 = list->list[i2];
+
+       list->list[i1] = network2;
+       list->list[i2] = network1;
+}
+
+LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
+       unsigned int i = 0;
+       unsigned int j = list->size - 1;
+
+       while (i < j) {
+               loc_network_list_swap(list, i++, j--);
+       }
+}
+
+LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
+       unsigned int n = list->size;
+       int swapped;
+
+       do {
+               swapped = 0;
+
+               for (unsigned int i = 1; i < n; i++) {
+                       if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
+                               loc_network_list_swap(list, i-1, i);
+                               swapped = 1;
+                       }
+               }
+
+               n--;
+       } while (swapped);
 }

diff --git a/src/test-network.c b/src/test-network.c
index b6776b48be914f6ca75051f63905d93462bd3161..af1b2e609bcaa833d8dbe5d91c4e323c412510f6 100644 (file)
--- a/src/test-network.c
+++ b/src/test-network.c
@@ -118,6 +118,19 @@ int main(int argc, char** argv) {
        size_t nodes = loc_network_tree_count_nodes(tree);
        printf("The tree has %zu nodes\n", nodes);
 
+       // Check equals function
+       err = loc_network_eq(network1, network1);
+       if (!err) {
+               fprintf(stderr, "Network is not equal with itself\n");
+               exit(EXIT_FAILURE);
+       }
+
+       err = loc_network_eq(network1, network2);
+       if (err) {
+               fprintf(stderr, "Networks equal unexpectedly\n");
+               exit(EXIT_FAILURE);
+       }
+
        // Check subnet function
        err = loc_network_is_subnet_of(network1, network2);
        if (err != 0) {
@@ -131,6 +144,54 @@ int main(int argc, char** argv) {
                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");
+               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(subnet);
+               printf("Received subnet %s\n", s);
+               free(s);
+
+               if (!loc_network_is_subnet_of(subnet, network1)) {
+                       fprintf(stderr, "Not a subnet\n");
+                       exit(EXIT_FAILURE);
+               }
+
+               loc_network_unref(subnet);
+       }
+
+       loc_network_list_unref(subnets);
+
+       struct loc_network_list* excluded = loc_network_exclude(network1, network2);
+       if (!excluded) {
+               fprintf(stderr, "Could not create excluded list\n");
+               exit(EXIT_FAILURE);
+       }
+
+       loc_network_list_dump(excluded);
+
+       // Reverse it
+       loc_network_list_reverse(excluded);
+       loc_network_list_dump(excluded);
+
+       // Sort them and dump them again
+       loc_network_list_sort(excluded);
+       loc_network_list_dump(excluded);
+
+       loc_network_list_unref(excluded);
+
        // Create a database
        struct loc_writer* writer;
        err = loc_writer_new(ctx, &writer, NULL, NULL);