diff options
| author | M Stoeckl <code@mstoeckl.com> | 2024-10-31 09:23:26 -0400 |
|---|---|---|
| committer | M Stoeckl <code@mstoeckl.com> | 2024-10-31 09:30:09 -0400 |
| commit | 260eaba88ec8f54fe2bdbe391b18fcd2db70836f (patch) | |
| tree | 252ac7bfe70b464117dc9aba7eb6d6dc98ac2906 /menu.h | |
| parent | 12b8f83be447379eded03c6109fe944945cd48aa (diff) | |
| download | wmenu-260eaba88ec8f54fe2bdbe391b18fcd2db70836f.tar.gz | |
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.
Diffstat (limited to 'menu.h')
| -rw-r--r-- | menu.h | 8 |
1 files changed, 4 insertions, 4 deletions
@@ -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, |