network-list: Make this a sorted list

The list is now organised so that it is always ordered.

This allows us to find if a network is on the list a lot
quicker using binary search as well as inserting a new
network at the right place.

This will benefit loc_network_exclude with very large networks.

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

diff --git a/src/libloc.sym b/src/libloc.sym
index b2d8a31e2889273072c5833d2c888b731dd1d38f..28cc8e8531440bbd317838717ed1cb996e859db7 100644 (file)
--- a/src/libloc.sym
+++ b/src/libloc.sym
@@ -106,6 +106,7 @@ global:
 
        # Network
        loc_network_address_family;
+       loc_network_cmp;
        loc_network_eq;
        loc_network_exclude;
        loc_network_exclude_list;

diff --git a/src/loc/network.h b/src/loc/network.h
index b31c8a269b499a2a5a76f59ab9d0f2ea983cc05a..8ab156251e344116009ad0384c4aabc7377f7d65 100644 (file)
--- a/src/loc/network.h
+++ b/src/loc/network.h
@@ -58,6 +58,7 @@ 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_cmp(struct loc_network* self, struct loc_network* other);
 int loc_network_eq(struct loc_network* self, struct loc_network* other);
 int loc_network_gt(struct loc_network* self, struct loc_network* other);
 int loc_network_overlaps(struct loc_network* self, struct loc_network* other);

diff --git a/src/network-list.c b/src/network-list.c
index b455cafc38de1900e8a1e295331c2d09fe50b486..6e9cd379e942aba90a25b36776778b111289f5b7 100644 (file)
--- a/src/network-list.c
+++ b/src/network-list.c
@@ -16,6 +16,7 @@
 
 #include <errno.h>
 #include <stdlib.h>
+#include <time.h>
 
 #include <loc/libloc.h>
 #include <loc/network.h>
@@ -130,11 +131,71 @@ LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* lis
        return loc_network_ref(list->elements[index]);
 }
 
+//MOVE FUNCTION GOES HERE
+
+static off_t loc_network_list_find(struct loc_network_list* list,
+               struct loc_network* network, int* found) {
+       off_t lo = 0;
+       off_t hi = list->size - 1;
+
+       *found = 0;
+
+#ifdef ENABLE_DEBUG
+       // Save start time
+       clock_t start = clock();
+#endif
+
+       off_t i = 0;
+
+       while (lo <= hi) {
+               i = (lo + hi) / 2;
+
+               // Check if this is a match
+               int result = loc_network_cmp(network, list->elements[i]);
+
+               if (result == 0) {
+                       *found = 1;
+
+#ifdef ENABLE_DEBUG
+                       clock_t end = clock();
+
+                       // Log how fast this has been
+                       DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
+                               (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
+#endif
+
+                       return i;
+               }
+
+               if (result > 0)
+                       lo = i + 1;
+               else
+                       hi = i - 1;
+       }
+
+#ifdef ENABLE_DEBUG
+       clock_t end = clock();
+
+       // Log how fast this has been
+       DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
+               (double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
+#endif
+
+       return i;
+}
+
 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
-       // Do not add networks that are already on the list
-       if (loc_network_list_contains(list, network))
+       int found = 0;
+
+       off_t index = loc_network_list_find(list, network, &found);
+
+       // The network has been found on the list. Nothing to do.
+       if (found)
                return 0;
 
+       DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
+               list, network, (intmax_t)index);
+
        // Check if we have space left
        if (list->size >= list->elements_size) {
                int r = loc_network_list_grow(list, 64);
@@ -142,9 +203,15 @@ LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_n
                        return r;
        }
 
-       DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
+       // The list is now larger
+       list->size++;
+
+       // Move all elements out of the way
+       for (unsigned int i = list->size - 1; i > index; i--)
+               list->elements[i] = list->elements[i - 1];
 
-       list->elements[list->size++] = loc_network_ref(network);
+       // Add the new element at the right place
+       list->elements[index] = loc_network_ref(network);
 
        return 0;
 }
@@ -183,12 +250,11 @@ LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_lis
 }
 
 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
-       for (unsigned int i = 0; i < list->size; i++) {
-               if (loc_network_eq(list->elements[i], network))
-                       return 1;
-       }
+       int found = 0;
 
-       return 0;
+       loc_network_list_find(list, network, &found);
+
+       return found;
 }
 
 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {

diff --git a/src/network.c b/src/network.c
index 72b77e65e7e8ed2cb03e60f58978aadf16faf57f..38d557a4fe5e04dee787576a8c5f686d1892fcf4 100644 (file)
--- a/src/network.c
+++ b/src/network.c
@@ -441,6 +441,28 @@ 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_cmp(struct loc_network* self, struct loc_network* other) {
+       // Compare family
+       if (self->family > other->family)
+               return 1;
+       else if (self->family < other->family)
+               return -1;
+
+       // Compare address
+       int r = in6_addr_cmp(&self->first_address, &other->first_address);
+       if (r)
+               return r;
+
+       // Compare prefix
+       if (self->prefix > other->prefix)
+               return 1;
+       else if (self->prefix < other->prefix)
+               return -1;
+
+       // Both networks are equal
+       return 0;
+}
+
 LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
        // Family must be the same
        if (self->family != other->family)