Proper filtering functions.

4 files changed, 188 insertions, 44 deletions

diff --git a/lib/filter.c b/lib/filter.c
index 4677e73..7e87b11 100644
--- a/lib/filter.c
+++ b/lib/filter.c
@@ -4,37 +4,139 @@
 #include <string.h>
 
 /**
- * Filter that mimics the vanilla dmenu filtering.
+ * Shrink bmItem** list pointer.
+ *
+ * Useful helper function for filter functions.
+ *
+ * @param list Pointer to pointer to list of bmItem pointers.
+ * @param osize Current size of the list.
+ * @param nsize New size the list will be shrinked to.
+ * @return Pointer to list of bmItem pointers.
+ */
+static bmItem** _bmFilterShrinkList(bmItem ***inOutList, size_t osize, size_t nsize)
+{
+    assert(inOutList);
+
+    if (nsize == 0) {
+        free(*inOutList);
+        return (*inOutList = NULL);
+    }
+
+    if (nsize >= osize)
+        return *inOutList;
+
+    void *tmp = malloc(sizeof(bmItem*) * nsize);
+    if (!tmp)
+        return *inOutList;
+
+    memcpy(tmp, *inOutList, sizeof(bmItem*) * nsize);
+    free(*inOutList);
+    return (*inOutList = tmp);
+}
+
+/**
+ * Text filter tokenizer helper.
+ *
+ * @param menu bmMenu instance which filter to tokenize.
+ * @param outTokv char pointer reference to list of tokens, this should be freed after use.
+ * @param outTokc unsigned int reference to number of tokens.
+ * @return Pointer to buffer that contains tokenized string, this should be freed after use.
+ */
+static char* _bmFilterTokenize(bmMenu *menu, char ***outTokv, unsigned int *outTokc)
+{
+    assert(menu);
+    assert(outTokv);
+    assert(outTokc);
+    *outTokv = NULL;
+    *outTokc = 0;
+
+    char **tokv = NULL, *buffer = NULL;
+    if (!(buffer = _bmStrdup(menu->filter)))
+        goto fail;
+
+    char *s, **tmp = NULL;
+    unsigned int tokc = 0, tokn = 0;
+    for (s = strtok(buffer, " "); s; tmp[tokc - 1] = s, s = strtok(NULL, " "), tokv = tmp)
+        if (++tokc > tokn && !(tmp = realloc(tmp, ++tokn * sizeof(char*))))
+            goto fail;
+
+    *outTokv = tmp;
+    *outTokc = tokc;
+    return buffer;
+
+fail:
+    if (buffer)
+        free(buffer);
+    if (tokv)
+        free(tokv);
+    return NULL;
+}
+
+/**
+ * Dmenu filterer that accepts substring function.
  *
  * @param menu bmMenu instance to filter.
+ * @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** _bmFilterDmenu(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted)
+bmItem** _bmFilterDmenuFun(bmMenu *menu, char* (*fstrstr)(const char *a, const char *b), unsigned int *outNmemb, unsigned int *outHighlighted)
 {
     assert(menu);
     assert(outNmemb);
     assert(outHighlighted);
     *outNmemb = *outHighlighted = 0;
 
-    /* FIXME: not real dmenu like filtering at all */
+    unsigned int itemsCount;
+    bmItem **items = bmMenuGetItems(menu, &itemsCount);
 
-    bmItem **filtered = calloc(menu->items.count, sizeof(bmItem*));
+    bmItem **filtered = calloc(itemsCount, sizeof(bmItem*));
     if (!filtered)
         return NULL;
 
+    char **tokv;
+    unsigned int tokc;
+    char *buffer = _bmFilterTokenize(menu, &tokv, &tokc);
+
     unsigned int i, f;
-    for (f = i = 0; i < menu->items.count; ++i) {
-        bmItem *item = menu->items.list[i];
-        if (item->text && strstr(item->text, menu->filter)) {
-            if (f == 0 || item == bmMenuGetHighlightedItem(menu))
-                *outHighlighted = f;
-            filtered[f++] = item;
+    for (f = i = 0; i < itemsCount; ++i) {
+        bmItem *item = items[i];
+        if (!item->text && tokc != 0)
+            continue;
+
+        if (tokc && item->text) {
+            unsigned int t;
+            for (t = 0; t < tokc && fstrstr(item->text, tokv[t]); ++t);
+            if (t < tokc)
+                continue;
         }
+
+        if (f == 0 || item == bmMenuGetHighlightedItem(menu))
+            *outHighlighted = f;
+        filtered[f++] = item;
     }
 
-    return _bmShrinkItemList(&filtered, menu->items.count, (*outNmemb = f));
+    if (buffer)
+        free(buffer);
+
+    if (tokv)
+        free(tokv);
+
+    return _bmFilterShrinkList(&filtered, menu->items.count, (*outNmemb = f));
+}
+
+/**
+ * Filter that mimics the vanilla dmenu filtering.
+ *
+ * @param menu bmMenu instance to filter.
+ * @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)
+{
+    return _bmFilterDmenuFun(menu, strstr, outNmemb, outHighlighted);
 }
 
 /**
@@ -47,14 +149,7 @@ bmItem** _bmFilterDmenu(bmMenu *menu, unsigned int *outNmemb, unsigned int *outH
  */
 bmItem** _bmFilterDmenuCaseInsensitive(bmMenu *menu, unsigned int *outNmemb, unsigned int *outHighlighted)
 {
-    assert(menu);
-    assert(outNmemb);
-    assert(outHighlighted);
-    *outNmemb = *outHighlighted = 0;
-
-    /* FIXME: stub */
-
-    return NULL;
+    return _bmFilterDmenuFun(menu, _bmStrupstr, outNmemb, outHighlighted);
 }
 
 /* vim: set ts=8 sw=4 tw=0 :*/
diff --git a/lib/internal.h b/lib/internal.h
index 790b4ed..043c906 100644
--- a/lib/internal.h
+++ b/lib/internal.h
@@ -153,6 +153,8 @@ int _bmItemListRemoveItem(struct _bmItemList *list, const bmItem *item);
 
 /* util.c */
 char* _bmStrdup(const char *s);
+int _bmStrupcmp(const char *hay, const char *needle);
+char* _bmStrupstr(const char *hay, const char *needle);
 bmItem** _bmShrinkItemList(bmItem ***inOutList, size_t osize, size_t nsize);
 int _bmUtf8StringScreenWidth(const char *string);
 size_t _bmUtf8RuneNext(const char *string, size_t start);
diff --git a/lib/menu.c b/lib/menu.c
index bf26c51..e9cf647 100644
--- a/lib/menu.c
+++ b/lib/menu.c
@@ -16,6 +16,11 @@ static void _bmMenuFilter(bmMenu *menu)
 {
     assert(menu);
 
+    if (!menu->items.list || menu->items.count <= 0) {
+        _bmItemListFreeList(&menu->filtered);
+        return;
+    }
+
     unsigned int count, selected;
     bmItem **filtered = filterFunc[menu->filterMode](menu, &count, &selected);
 
@@ -82,9 +87,6 @@ void bmMenuFree(bmMenu *menu)
     if (menu->title)
         free(menu->title);
 
-    if (menu->filtered.list)
-        free(menu->filtered.list);
-
     bmMenuFreeItems(menu);
     free(menu);
 }
@@ -200,7 +202,13 @@ const char* bmMenuGetTitle(const bmMenu *menu)
 int bmMenuAddItemAt(bmMenu *menu, bmItem *item, unsigned int index)
 {
     assert(menu);
-    return _bmItemListAddItemAt(&menu->items, item, index);;
+
+    int ret = _bmItemListAddItemAt(&menu->items, item, index);
+
+    if (ret)
+        _bmMenuFilter(menu);
+
+    return ret;
 }
 
 /**
@@ -212,7 +220,12 @@ int bmMenuAddItemAt(bmMenu *menu, bmItem *item, unsigned int index)
  */
 int bmMenuAddItem(bmMenu *menu, bmItem *item)
 {
-    return _bmItemListAddItem(&menu->items, item);
+    int ret = _bmItemListAddItem(&menu->items, item);
+
+    if (ret)
+        _bmMenuFilter(menu);
+
+    return ret;
 }
 
 /**
@@ -237,6 +250,7 @@ int bmMenuRemoveItemAt(bmMenu *menu, unsigned int index)
     if (ret) {
         _bmItemListRemoveItem(&menu->selection, item);
         _bmItemListRemoveItem(&menu->filtered, item);
+        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -260,6 +274,7 @@ int bmMenuRemoveItem(bmMenu *menu, bmItem *item)
     if (ret) {
         _bmItemListRemoveItem(&menu->selection, item);
         _bmItemListRemoveItem(&menu->filtered, item);
+        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -275,7 +290,9 @@ int bmMenuRemoveItem(bmMenu *menu, bmItem *item)
 int bmMenuSetHighlightedIndex(bmMenu *menu, unsigned int index)
 {
     assert(menu);
-    unsigned int itemsCount = (menu->filtered.list ? menu->filtered.count : menu->items.count);
+
+    unsigned int itemsCount;
+    bmMenuGetFilteredItems(menu, &itemsCount);
 
     if (itemsCount <= index)
         return 0;
@@ -376,6 +393,7 @@ int bmMenuSetItems(bmMenu *menu, const bmItem **items, unsigned int nmemb)
     if (ret) {
         _bmItemListFreeList(&menu->selection);
         _bmItemListFreeList(&menu->filtered);
+        _bmMenuFilter(menu);
     }
 
     return ret;
@@ -410,7 +428,7 @@ bmItem** bmMenuGetFilteredItems(const bmMenu *menu, unsigned int *outNmemb)
 {
     assert(menu);
 
-    if (menu->filtered.list)
+    if (strlen(menu->filter))
         return _bmItemListGetItems(&menu->filtered, outNmemb);
 
     return _bmItemListGetItems(&menu->items, outNmemb);
@@ -463,8 +481,11 @@ bmKey bmMenuGetKey(bmMenu *menu, unsigned int *outUnicode)
 bmRunResult bmMenuRunWithKey(bmMenu *menu, bmKey key, unsigned int unicode)
 {
     assert(menu);
+
+    unsigned int itemsCount;
+    bmMenuGetFilteredItems(menu, &itemsCount);
+
     char *oldFilter = _bmStrdup(menu->filter);
-    unsigned int itemsCount = (menu->filtered.list ? menu->filtered.count : menu->items.count);
 
     switch (key) {
         case BM_KEY_LEFT:
diff --git a/lib/util.c b/lib/util.c
index 5eb980d..06c89cf 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -28,30 +28,56 @@ char* _bmStrdup(const char *string)
 }
 
 /**
- * Shrink bmItem** list pointer.
+ * Portable case-insensitive strcmp.
  *
- * Useful helper function for filter functions.
+ * @param hay C "string" to match against.
+ * @param needle C "string" to match.
+ */
+int _bmStrupcmp(const char *hay, const char *needle)
+{
+    size_t i, len;
+
+    if ((len = strlen(hay)) != strlen(needle))
+        return 1;
+
+    for (i = 0; i != len; ++i)
+        if (toupper(hay[i]) != toupper(needle[i]))
+            return 1;
+
+    return 0;
+}
+
+/**
+ * Portable case-insensitive strstr.
  *
- * @param list Pointer to pointer to list of bmItem pointers.
- * @param osize Current size of the list.
- * @param nsize New size the list will be shrinked to.
- * @return Pointer to list of bmItem pointers.
+ * @param hay C "string" to substring against.
+ * @param needle C "string" to substring.
  */
-bmItem** _bmShrinkItemList(bmItem ***inOutList, size_t osize, size_t nsize)
+char* _bmStrupstr(const char *hay, const char *needle)
 {
-    assert(inOutList);
+    size_t i, r = 0, p = 0, len, len2;
 
-    if (nsize >= osize)
-        return *inOutList;
+    if (!_bmStrupcmp(hay, needle))
+        return (char*)hay;
 
-    void *tmp = malloc(sizeof(bmItem*) * nsize);
-    if (!tmp)
-        return *inOutList;
+    if ((len = strlen(hay)) < (len2 = strlen(needle)))
+        return NULL;
+
+    for (i = 0; i != len; ++i) {
+        if (p == len2)
+            return (char*)hay + r;
+
+        if (toupper(hay[i]) == toupper(needle[p++])) {
+            if (!r)
+                r = i;
+        } else {
+            if (r)
+                i = r;
+            r = p = 0;
+        }
+    }
 
-    memcpy(tmp, *inOutList, sizeof(bmItem*) * nsize);
-    free(*inOutList);
-    *inOutList = tmp;
-    return *inOutList;
+    return (p == len2 ? (char*)hay + r : NULL);
 }
 
 /**