From 260eaba88ec8f54fe2bdbe391b18fcd2db70836f Mon Sep 17 00:00:00 2001
From: M Stoeckl <code@mstoeckl.com>
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.h | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
(limited to 'menu.h')
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,
--
cgit v1.2.3