From 5da0579864a13b11bf0808f7f69f7b22f18054b1 Mon Sep 17 00:00:00 2001 From: Phil Jones Date: Sat, 19 Nov 2022 19:28:52 +0000 Subject: Fix sorting in normal tofi mode with history. By using a hash table rather than binary search to find existing items, we can avoid the need to sort the input. --- src/string_vec.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) (limited to 'src/string_vec.c') diff --git a/src/string_vec.c b/src/string_vec.c index 4607727..f5cf899 100644 --- a/src/string_vec.c +++ b/src/string_vec.c @@ -1,3 +1,4 @@ +#include #include #include #include @@ -5,6 +6,7 @@ #include #include #include "fuzzy_match.h" +#include "history.h" #include "string_vec.h" #include "unicode.h" #include "xmalloc.h" @@ -36,6 +38,14 @@ static int cmpscorep(const void *restrict a, const void *restrict b) return hist_diff + search_diff; } +static int cmphistoryp(const void *restrict a, const void *restrict b) +{ + struct scored_string *restrict str1 = (struct scored_string *)a; + struct scored_string *restrict str2 = (struct scored_string *)b; + + return str2->history_score - str1->history_score; +} + struct string_vec string_vec_create(void) { struct string_vec vec = { @@ -91,6 +101,29 @@ void string_vec_sort(struct string_vec *restrict vec) qsort(vec->buf, vec->count, sizeof(vec->buf[0]), cmpstringp); } +void string_vec_history_sort(struct string_vec *restrict vec, struct history *history) +{ + /* + * To find elements without assuming the vector is pre-sorted, we use a + * hash table, which results in O(N+M) work (rather than O(N*M) for + * linear search. + */ + GHashTable *hash = g_hash_table_new(g_str_hash, g_str_equal); + for (size_t i = 0; i < vec->count; i++) { + g_hash_table_insert(hash, vec->buf[i].string, &vec->buf[i]); + } + for (size_t i = 0; i < history->count; i++) { + struct scored_string *res = g_hash_table_lookup(hash, history->buf[i].name); + if (res == NULL) { + continue; + } + res->history_score = history->buf[i].run_count; + } + g_hash_table_unref(hash); + + qsort(vec->buf, vec->count, sizeof(vec->buf[0]), cmphistoryp); +} + void string_vec_uniq(struct string_vec *restrict vec) { size_t count = vec->count; -- cgit v1.2.3