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.

1 files changed, 33 insertions, 0 deletions

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;