From 77e6d5379ea0de3264be5b8918d620d16e6bcbd3 Mon Sep 17 00:00:00 2001 From: Michael Tremer Date: Tue, 24 Nov 2020 19:39:35 +0000 Subject: [PATCH] network-list: Check last element before doing binary search This is helpful because very often we walk through a list in order and are most interested in the last element. Signed-off-by: Michael Tremer --- src/network-list.c | 24 ++++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) diff --git a/src/network-list.c b/src/network-list.c index 7e8b5f3..c86ad07 100644 --- a/src/network-list.c +++ b/src/network-list.c @@ -137,8 +137,26 @@ 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; + int result; - *found = 0; + // Since we are working on an ordered list, there is often a good chance that + // the network we are looking for is at the end or has to go to the end. + if (hi >= 0) { + result = loc_network_cmp(network, list->elements[hi]); + + // Match, so we are done + if (result == 0) { + *found = 1; + + return hi; + + // This needs to be added after the last one + } else if (result > 0) { + *found = 0; + + return hi + 1; + } + } #ifdef ENABLE_DEBUG // Save start time @@ -151,7 +169,7 @@ static off_t loc_network_list_find(struct loc_network_list* list, i = (lo + hi) / 2; // Check if this is a match - int result = loc_network_cmp(network, list->elements[i]); + result = loc_network_cmp(network, list->elements[i]); if (result == 0) { *found = 1; @@ -173,6 +191,8 @@ static off_t loc_network_list_find(struct loc_network_list* list, hi = i - 1; } + *found = 0; + #ifdef ENABLE_DEBUG clock_t end = clock(); -- 2.39.2