From 260eaba88ec8f54fe2bdbe391b18fcd2db70836f Mon Sep 17 00:00:00 2001 From: M Stoeckl Date: Thu, 31 Oct 2024 09:23:26 -0400 Subject: Optimize menu sorting Sorting and deduplicating elements after all items have been registered improves the time complexity of constructing the item list from O(n^2) to O(n log n). On a system with about 4000 menu items, this reduces startup time from about 0.21 seconds to 0.13 seconds. --- menu.c | 76 +++++++++++++++++++++++++++++++++---------------------------- menu.h | 8 +++---- render.c | 3 ++- wmenu-run.c | 3 ++- wmenu.c | 2 +- 5 files changed, 50 insertions(+), 42 deletions(-) diff --git a/menu.c b/menu.c index efd3e4a..52f0810 100644 --- a/menu.c +++ b/menu.c @@ -1,4 +1,5 @@ #define _POSIX_C_SOURCE 200809L +#include #include #include #include @@ -45,18 +46,12 @@ static void free_pages(struct menu *menu) { } } -static void free_item(struct item *item) { - free(item->text); - free(item); -} - static void free_items(struct menu *menu) { - struct item *next = menu->items; - while (next) { - struct item *item = next; - next = item->next; - free_item(item); + for (size_t i = 0; i < menu->item_count; i++) { + struct item *item = &menu->items[i]; + free(item->text); } + free(menu->items); } // Destroys the menu, freeing memory associated with it. @@ -167,34 +162,44 @@ void menu_getopts(struct menu *menu, int argc, char *argv[]) { } // Add an item to the menu. -void menu_add_item(struct menu *menu, char *text, bool sort) { - struct item *new = calloc(1, sizeof(struct item)); - if (!new) { - return; +void menu_add_item(struct menu *menu, char *text) { + if ((menu->item_count & (menu->item_count - 1)) == 0) { + size_t alloc_size = menu->item_count ? 2 * menu->item_count : 1; + void *new_array = realloc(menu->items, sizeof(struct item) * alloc_size); + if (!new_array) { + fprintf(stderr, "could not realloc %zu bytes", sizeof(struct item) * alloc_size); + exit(EXIT_FAILURE); + } + menu->items = new_array; } + + struct item *new = &menu->items[menu->item_count]; new->text = text; - if (sort) { - for (struct item **item = &menu->items; *item; item = &(*item)->next) { - int result = strcmp(new->text, (*item)->text); - if (result == 0) { - free_item(new); - return; - } - if (result < 0) { - new->next = *item; - *item = new; - return; - } - } - } + menu->item_count++; +} - if (menu->lastitem) { - menu->lastitem->next = new; - } else { - menu->items = new; +static int compare_items(const void *a, const void *b) { + const struct item *item_a = a; + const struct item *item_b = b; + return strcmp(item_a->text, item_b->text); +} + +void menu_sort_and_deduplicate(struct menu *menu) { + size_t j = 1; + size_t i; + + qsort(menu->items, menu->item_count, sizeof(*menu->items), compare_items); + + for (i = 1; i < menu->item_count; i++) { + if (strcmp(menu->items[i].text, menu->items[j - 1].text) == 0) { + free(menu->items[i].text); + } else { + menu->items[j] = menu->items[i]; + j++; + } } - menu->lastitem = new; + menu->item_count = j; } static void append_page(struct page *page, struct page **first, struct page **last) { @@ -291,6 +296,7 @@ static void match_items(struct menu *menu) { char buf[sizeof menu->input], *tok; char **tokv = NULL; int i, tokc = 0; + size_t k; size_t tok_len; menu->matches = NULL; menu->matches_end = NULL; @@ -314,8 +320,8 @@ static void match_items(struct menu *menu) { } tok_len = tokc ? strlen(tokv[0]) : 0; - struct item *item; - for (item = menu->items; item; item = item->next) { + for (k = 0; k < menu->item_count; k++) { + struct item *item = &menu->items[k]; for (i = 0; i < tokc; i++) { if (!fstrstr(menu, item->text, tokv[i])) { /* token does not match */ diff --git a/menu.h b/menu.h index 261c2f2..280cdd0 100644 --- a/menu.h +++ b/menu.h @@ -13,7 +13,6 @@ typedef void (*menu_callback)(struct menu *menu, char *text, bool exit); struct item { char *text; int width; - struct item *next; // traverses all items struct item *prev_match; // previous matching item struct item *next_match; // next matching item struct page *page; // the page holding this item @@ -64,8 +63,8 @@ struct menu { char input[BUFSIZ]; size_t cursor; - struct item *items; // list of all items - struct item *lastitem; // last item in the list + struct item *items; // array of all items + size_t item_count; struct item *matches; // list of matching items struct item *matches_end; // last matching item struct item *sel; // selected item @@ -79,7 +78,8 @@ struct menu { struct menu *menu_create(menu_callback callback); void menu_destroy(struct menu *menu); void menu_getopts(struct menu *menu, int argc, char *argv[]); -void menu_add_item(struct menu *menu, char *text, bool sort); +void menu_add_item(struct menu *menu, char *text); +void menu_sort_and_deduplicate(struct menu *menu); void menu_render_items(struct menu *menu); void menu_paste(struct menu *menu, const char *text, ssize_t len); void menu_keypress(struct menu *menu, enum wl_keyboard_key_state key_state, diff --git a/render.c b/render.c index 3813af5..070fad9 100644 --- a/render.c +++ b/render.c @@ -28,7 +28,8 @@ void calc_widths(struct menu *menu) { menu->right_arrow = text_width(cairo, menu->font, ">") + 2 * menu->padding; // Calculate item widths and input area width - for (struct item *item = menu->items; item; item = item->next) { + for (size_t i = 0; i < menu->item_count; i++) { + struct item *item = &menu->items[i]; item->width = text_width(cairo, menu->font, item->text); if (item->width > menu->inputw) { menu->inputw = item->width; diff --git a/wmenu-run.c b/wmenu-run.c index dc86b6d..1b7b8c1 100644 --- a/wmenu-run.c +++ b/wmenu-run.c @@ -20,10 +20,11 @@ static void read_items(struct menu *menu) { if (ent->d_name[0] == '.') { continue; } - menu_add_item(menu, strdup(ent->d_name), true); + menu_add_item(menu, strdup(ent->d_name)); } closedir(dir); } + menu_sort_and_deduplicate(menu); free(path); } diff --git a/wmenu.c b/wmenu.c index 0ce9d08..38e78b9 100644 --- a/wmenu.c +++ b/wmenu.c @@ -13,7 +13,7 @@ static void read_items(struct menu *menu) { if (p) { *p = '\0'; } - menu_add_item(menu, strdup(buf), false); + menu_add_item(menu, strdup(buf)); } } -- cgit v1.2.3