diff options
| -rw-r--r-- | src/compgen.c | 27 | ||||
| -rw-r--r-- | src/compgen.h | 3 | ||||
| -rw-r--r-- | src/main.c | 7 |
3 files changed, 32 insertions, 5 deletions
diff --git a/src/compgen.c b/src/compgen.c index 2fb2a04..e8422b7 100644 --- a/src/compgen.c +++ b/src/compgen.c @@ -234,7 +234,7 @@ static int cmpscorep(const void *restrict a, const void *restrict b) return str2->history_score - str1->history_score; } -void compgen_history_sort(struct string_ref_vec *programs, struct history *history) +struct string_ref_vec compgen_history_sort(struct string_ref_vec *programs, struct history *history) { log_debug("Moving already known programs to the front.\n"); for (size_t i = 0; i < history->count; i++) { @@ -246,5 +246,28 @@ void compgen_history_sort(struct string_ref_vec *programs, struct history *histo res->history_score = history->buf[i].run_count; } - qsort(programs->buf, programs->count, sizeof(programs->buf[0]), cmpscorep); + /* + * For compgen, we expect there to be many more commands than history + * entries. For speed, we therefore create a copy of the command + * vector with all of the non-zero history score items pushed to the + * front. We can then call qsort() on just the first few items of the + * new vector, rather than on the entire original vector. + */ + struct string_ref_vec vec = { + .count = programs->count, + .size = programs->size, + .buf = xcalloc(programs->size, sizeof(*vec.buf)) + }; + + size_t n_hist = 0; + for (ssize_t i = programs->count - 1; i >= 0; i--) { + if (programs->buf[i].history_score == 0) { + vec.buf[i + n_hist] = programs->buf[i]; + } else { + vec.buf[n_hist] = programs->buf[i]; + n_hist++; + } + } + qsort(vec.buf, n_hist, sizeof(vec.buf[0]), cmpscorep); + return vec; } diff --git a/src/compgen.h b/src/compgen.h index 5e36576..b3105db 100644 --- a/src/compgen.h +++ b/src/compgen.h @@ -10,6 +10,7 @@ char *compgen(void); [[nodiscard("memory leaked")]] char *compgen_cached(void); -void compgen_history_sort(struct string_ref_vec *programs, struct history *history); +[[nodiscard("memory leaked")]] +struct string_ref_vec compgen_history_sort(struct string_ref_vec *programs, struct history *history); #endif /* COMPGEN_H */ @@ -1321,14 +1321,17 @@ int main(int argc, char *argv[]) log_debug("Generating command list.\n"); log_indent(); tofi.window.entry.command_buffer = compgen_cached(); - tofi.window.entry.commands = string_ref_vec_from_buffer(tofi.window.entry.command_buffer); + struct string_ref_vec commands = string_ref_vec_from_buffer(tofi.window.entry.command_buffer); if (tofi.use_history) { if (tofi.history_file[0] == 0) { tofi.window.entry.history = history_load_default_file(tofi.window.entry.drun); } else { tofi.window.entry.history = history_load(tofi.history_file); } - compgen_history_sort(&tofi.window.entry.commands, &tofi.window.entry.history); + tofi.window.entry.commands = compgen_history_sort(&commands, &tofi.window.entry.history); + string_ref_vec_destroy(&commands); + } else { + tofi.window.entry.commands = commands; } log_unindent(); log_debug("Command list generated.\n"); |