From af4689bf5c56ad79e9e90396b41be460e49ef384 Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Tue, 24 Nov 2020 14:55:08 +0000 Subject: [PATCH] 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 --- src/libloc.sym | 1 + src/loc/network.h | 1 + src/network-list.c | 84 +++++++++++++++++++++++++++++++++++++++++----- src/network.c | 22 ++++++++++++ 4 files changed, 99 insertions(+), 9 deletions(-) diff --git a/src/libloc.sym b/src/libloc.sym index b2d8a31..28cc8e8 100644 --- 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 b31c8a2..8ab1562 100644 --- 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 b455caf..6e9cd37 100644 --- a/src/network-list.c +++ b/src/network-list.c @@ -16,6 +16,7 @@ #include #include +#include #include #include @@ -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 72b77e6..38d557a 100644 --- 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) -- 2.39.2