Optimize menu sorting - wmenu - 🔧 fork of wmenu
(HTM) git clone git@git.drkhsh.at/wmenu.git
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
(DIR) commit 260eaba88ec8f54fe2bdbe391b18fcd2db70836f
(DIR) parent 12b8f83be447379eded03c6109fe944945cd48aa
(HTM) Author: M Stoeckl <code@mstoeckl.com>
Date: Thu, 31 Oct 2024 09:23:26 -0400
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:
M menu.c | 76 +++++++++++++++++--------------
M menu.h | 8 ++++----
M render.c | 3 ++-
M wmenu-run.c | 3 ++-
M wmenu.c | 2 +-
5 files changed, 50 insertions(+), 42 deletions(-)
---
(DIR) diff --git a/menu.c b/menu.c
@@ -1,4 +1,5 @@
#define _POSIX_C_SOURCE 200809L
+#include <assert.h>
#include <ctype.h>
#include <poll.h>
#include <stdbool.h>
@@ -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 */
(DIR) diff --git 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,
(DIR) diff --git 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;
(DIR) diff --git 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);
}
(DIR) diff --git 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));
}
}