Make it possible filter manually, and optimized filtering.

4 files changed, 96 insertions, 54 deletions

diff --git a/lib/bemenu.h b/lib/bemenu.h
index 4534966..6348693 100644
--- a/lib/bemenu.h
+++ b/lib/bemenu.h
@@ -319,6 +319,17 @@ bmItem** bmMenuGetFilteredItems(const bmMenu *menu, unsigned int *outNmemb);
 void bmMenuRender(const bmMenu *menu);
 
 /**
+ * Trigger filtering of menu manually.
+ * This is useful when adding new items and want to dynamically see them filtered.
+ *
+ * Do note that filtering might be heavy, so you should only call it after batch manipulation of items.
+ * Not after manipulation of each single item.
+ *
+ * @param menu bmMenu instance which to filter.
+ */
+void bmMenuFilter(bmMenu *menu);
+
+/**
  * Poll key and unicode from underlying UI toolkit.
  *
  * This function will block on @link ::bmDrawMode BM_DRAW_MODE_CURSES @endlink draw mode.
diff --git a/lib/filter.c b/lib/filter.c
index 7e87b11..c8cbfff 100644
--- a/lib/filter.c
+++ b/lib/filter.c
@@ -76,12 +76,13 @@ fail:
  * Dmenu filterer that accepts substring function.
  *
  * @param menu bmMenu instance to filter.
+ * @param addition This will be 1, if filter is same as previous filter with something appended.
  * @param fstrstr Substring function used to match items.
  * @param outNmemb unsigned int reference to filtered items outNmemb.
  * @param outHighlighted unsigned int reference to new outHighlighted item index.
  * @return Pointer to array of bmItem pointers.
  */
-bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const char *b), unsigned int *outNmemb, unsigned int *outHighlighted)
+bmItem** _bmFilterDmenuFun(bmMenu *menu, char addition, char* (*fstrstr)(const char *a, const char *b), unsigned int *outNmemb, unsigned int *outHighlighted)
 {
     assert(menu);
     assert(outNmemb);
@@ -89,7 +90,13 @@ bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const c
     *outNmemb = *outHighlighted = 0;
 
     unsigned int itemsCount;
-    bmItem **items = bmMenuGetItems(menu, &itemsCount);
+    bmItem **items;
+
+    if (addition) {
+        items = bmMenuGetFilteredItems(menu, &itemsCount);
+    } else {
+        items = bmMenuGetItems(menu, &itemsCount);
+    }
 
     bmItem **filtered = calloc(itemsCount, sizeof(bmItem*));
     if (!filtered)
@@ -99,6 +106,7 @@ bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const c
     unsigned int tokc;
     char *buffer = _bmFilterTokenize(menu, &tokv, &tokc);
 
+    char found = 0;
     unsigned int i, f;
     for (f = i = 0; i < itemsCount; ++i) {
         bmItem *item = items[i];
@@ -112,8 +120,11 @@ bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const c
                 continue;
         }
 
-        if (f == 0 || item == bmMenuGetHighlightedItem(menu))
+        if (!found && item == bmMenuGetHighlightedItem(menu)) {
             *outHighlighted = f;
+            found = 1;
+        }
+
         filtered[f++] = item;
     }
 
@@ -130,26 +141,28 @@ bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const c
  * Filter that mimics the vanilla dmenu filtering.
  *
  * @param menu bmMenu instance to filter.
+ * @param addition This will be 1, if filter is same as previous filter with something appended.
  * @param outNmemb unsigned int reference to filtered items outNmemb.
  * @param outHighlighted unsigned int reference to new outHighlighted item index.
  * @return Pointer to array of bmItem pointers.
  */
-bmItem** _bmFilterDmenu(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted)
+bmItem** _bmFilterDmenu(bmMenu *menu, char addition, unsigned int *outNmemb, unsigned int *outHighlighted)
 {
-    return _bmFilterDmenuFun(menu, strstr, outNmemb, outHighlighted);
+    return _bmFilterDmenuFun(menu, addition, strstr, outNmemb, outHighlighted);
 }
 
 /**
  * Filter that mimics the vanilla case-insensitive dmenu filtering.
  *
  * @param menu bmMenu instance to filter.
+ * @param addition This will be 1, if filter is same as previous filter with something appended.
  * @param outNmemb unsigned int reference to filtered items outNmemb.
  * @param outHighlighted unsigned int reference to new outHighlighted item index.
  * @return Pointer to array of bmItem pointers.
  */
-bmItem** _bmFilterDmenuCaseInsensitive(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted)
+bmItem** _bmFilterDmenuCaseInsensitive(bmMenu *menu, char addition, unsigned int *outNmemb, unsigned int *outHighlighted)
 {
-    return _bmFilterDmenuFun(menu, _bmStrupstr, outNmemb, outHighlighted);
+    return _bmFilterDmenuFun(menu, addition, _bmStrupstr, outNmemb, outHighlighted);
 }
 
 /* vim: set ts=8 sw=4 tw=0 :*/
diff --git a/lib/internal.h b/lib/internal.h
index 043c906..985d366 100644
--- a/lib/internal.h
+++ b/lib/internal.h
@@ -103,6 +103,11 @@ struct _bmMenu {
     char filter[1024];
 
     /**
+     * Used as optimization.
+     */
+    char *oldFilter;
+
+    /**
      * Current byte offset on filter text.
      */
     unsigned int cursor;
@@ -136,8 +141,8 @@ int _bmDrawCursesInit(struct _bmRenderApi *api);
 int _bmMenuItemIsSelected(const bmMenu *menu, const bmItem *item);
 
 /* filter.c */
-bmItem** _bmFilterDmenu(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted);
-bmItem** _bmFilterDmenuCaseInsensitive(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted);
+bmItem** _bmFilterDmenu(bmMenu *menu, char addition, unsigned int *outNmemb, unsigned int *outHighlighted);
+bmItem** _bmFilterDmenuCaseInsensitive(bmMenu *menu, char addition, unsigned int *outNmemb, unsigned int *outHighlighted);
 
 /* list.c */
 void _bmItemListFreeList(struct _bmItemList *list);
diff --git a/lib/menu.c b/lib/menu.c
index acf9ffc..c5c98ad 100644
--- a/lib/menu.c
+++ b/lib/menu.c
@@ -7,27 +7,11 @@
 /**
  * Filter function map.
  */
-static bmItem** (*filterFunc[BM_FILTER_MODE_LAST])(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted) = {
+static bmItem** (*filterFunc[BM_FILTER_MODE_LAST])(bmMenu *menu, char addition, unsigned int *outNmemb, unsigned int *outHighlighted) = {
     _bmFilterDmenu, /* BM_FILTER_DMENU */
     _bmFilterDmenuCaseInsensitive /* BM_FILTER_DMENU_CASE_INSENSITIVE */
 };
 
-static void _bmMenuFilter(bmMenu *menu)
-{
-    assert(menu);
-
-    if (!strlen(menu->filter) || !menu->items.list || menu->items.count <= 0) {
-        _bmItemListFreeList(&menu->filtered);
-        return;
-    }
-
-    unsigned int count, selected;
-    bmItem **filtered = filterFunc[menu->filterMode](menu, &count, &selected);
-
-    _bmItemListSetItemsNoCopy(&menu->filtered, filtered, count);
-    menu->index = selected;
-}
-
 int _bmMenuItemIsSelected(const bmMenu *menu, const bmItem *item)
 {
     assert(menu);
@@ -87,6 +71,9 @@ void bmMenuFree(bmMenu *menu)
     if (menu->title)
         free(menu->title);
 
+    if (menu->oldFilter)
+        free(menu->oldFilter);
+
     bmMenuFreeItems(menu);
     free(menu);
 }
@@ -138,12 +125,7 @@ void* bmMenuGetUserdata(bmMenu *menu)
 void bmMenuSetFilterMode(bmMenu *menu, bmFilterMode mode)
 {
     assert(menu);
-
-    bmFilterMode oldMode = mode;
     menu->filterMode = (mode >= BM_FILTER_MODE_LAST ? BM_FILTER_MODE_DMENU : mode);
-
-    if (oldMode != mode)
-        _bmMenuFilter(menu);
 }
 
 /**
@@ -202,13 +184,7 @@ const char* bmMenuGetTitle(const bmMenu *menu)
 int bmMenuAddItemAt(bmMenu *menu, bmItem *item, unsigned int index)
 {
     assert(menu);
-
-    int ret = _bmItemListAddItemAt(&menu->items, item, index);
-
-    if (ret)
-        _bmMenuFilter(menu);
-
-    return ret;
+    return _bmItemListAddItemAt(&menu->items, item, index);
 }
 
 /**
@@ -220,12 +196,7 @@ int bmMenuAddItemAt(bmMenu *menu, bmItem *item, unsigned int index)
  */
 int bmMenuAddItem(bmMenu *menu, bmItem *item)
 {
-    int ret = _bmItemListAddItem(&menu->items, item);
-
-    if (ret)
-        _bmMenuFilter(menu);
-
-    return ret;
+    return _bmItemListAddItem(&menu->items, item);
 }
 
 /**
@@ -250,7 +221,6 @@ int bmMenuRemoveItemAt(bmMenu *menu, unsigned int index)
     if (ret) {
         _bmItemListRemoveItem(&menu->selection, item);
         _bmItemListRemoveItem(&menu->filtered, item);
-        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -274,7 +244,6 @@ int bmMenuRemoveItem(bmMenu *menu, bmItem *item)
     if (ret) {
         _bmItemListRemoveItem(&menu->selection, item);
         _bmItemListRemoveItem(&menu->filtered, item);
-        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -393,7 +362,6 @@ int bmMenuSetItems(bmMenu *menu, const bmItem **items, unsigned int nmemb)
     if (ret) {
         _bmItemListFreeList(&menu->selection);
         _bmItemListFreeList(&menu->filtered);
-        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -448,6 +416,57 @@ void bmMenuRender(const bmMenu *menu)
 }
 
 /**
+ * Trigger filtering of menu manually.
+ * This is useful when adding new items and want to dynamically see them filtered.
+ *
+ * Do note that filtering might be heavy, so you should only call it after batch manipulation of items.
+ * Not after manipulation of each single item.
+ *
+ * @param menu bmMenu instance which to filter.
+ */
+void bmMenuFilter(bmMenu *menu)
+{
+    assert(menu);
+
+    char addition = 0;
+    size_t len = strlen(menu->filter);
+
+    if (!len || !menu->items.list || menu->items.count <= 0) {
+        _bmItemListFreeList(&menu->filtered);
+
+        if (menu->oldFilter)
+            free(menu->oldFilter);
+
+        menu->oldFilter = NULL;
+        return;
+    }
+
+    if (menu->oldFilter) {
+        size_t oldLen = strlen(menu->oldFilter);
+        addition = (oldLen < len && !memcmp(menu->oldFilter, menu->filter, oldLen));
+    }
+
+    if (menu->oldFilter && addition && menu->filtered.count <= 0)
+        return;
+
+    if (menu->oldFilter && !strcmp(menu->filter, menu->oldFilter))
+        return;
+
+    unsigned int count, selected;
+    bmItem **filtered = filterFunc[menu->filterMode](menu, addition, &count, &selected);
+
+    _bmItemListSetItemsNoCopy(&menu->filtered, filtered, count);
+    menu->index = selected;
+
+    if (count) {
+        if (menu->oldFilter)
+            free(menu->oldFilter);
+
+        menu->oldFilter = _bmStrdup(menu->filter);
+    }
+}
+
+/**
  * Poll key and unicode from underlying UI toolkit.
  *
  * This function will block on @link ::bmDrawMode BM_DRAW_MODE_CURSES @endlink draw mode.
@@ -485,8 +504,6 @@ bmRunResult bmMenuRunWithKey(bmMenu *menu, bmKey key, unsigned int unicode)
     unsigned int itemsCount;
     bmMenuGetFilteredItems(menu, &itemsCount);
 
-    char *oldFilter = _bmStrdup(menu->filter);
-
     switch (key) {
         case BM_KEY_LEFT:
             {
@@ -619,11 +636,7 @@ bmRunResult bmMenuRunWithKey(bmMenu *menu, bmKey key, unsigned int unicode)
         default: break;
     }
 
-    if (oldFilter && strcmp(oldFilter, menu->filter))
-        _bmMenuFilter(menu);
-
-    if (oldFilter)
-        free(oldFilter);
+    bmMenuFilter(menu);
 
     switch (key) {
         case BM_KEY_RETURN: return BM_RUN_RESULT_SELECTED;