diff options
| -rw-r--r-- | src/main.c | 3 | ||||
| -rw-r--r-- | src/string_vec.c | 33 | ||||
| -rw-r--r-- | src/string_vec.h | 3 |
3 files changed, 37 insertions, 2 deletions
@@ -1351,9 +1351,8 @@ int main(int argc, char *argv[]) if (tofi.history_file[0] == 0) { tofi.use_history = false; } else { - string_vec_sort(&tofi.window.entry.commands); tofi.window.entry.history = history_load(tofi.history_file); - compgen_history_sort(&tofi.window.entry.commands, &tofi.window.entry.history); + string_vec_history_sort(&tofi.window.entry.commands, &tofi.window.entry.history); } } } 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 <glib.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> @@ -5,6 +6,7 @@ #include <string.h> #include <sys/mman.h> #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; diff --git a/src/string_vec.h b/src/string_vec.h index f3e840c..f8ca3e0 100644 --- a/src/string_vec.h +++ b/src/string_vec.h @@ -5,6 +5,7 @@ #include <stddef.h> #include <stdint.h> #include <stdio.h> +#include "history.h" struct scored_string { char *string; @@ -30,6 +31,8 @@ void string_vec_add(struct string_vec *restrict vec, const char *restrict str); void string_vec_sort(struct string_vec *restrict vec); +void string_vec_history_sort(struct string_vec *restrict vec, struct history *history); + void string_vec_uniq(struct string_vec *restrict vec); struct scored_string *string_vec_find(struct string_vec *restrict vec, const char *str); |