dmenu-fuzzymatch-4.6.diff (3611B)
1 From f5caf807c884f92e6f07ad8b461334343287eca3 Mon Sep 17 00:00:00 2001 2 From: Hiltjo Posthuma <hiltjo@codemadness.org> 3 Date: Fri, 17 Jun 2016 15:09:30 +0200 4 Subject: [PATCH] fuzzy match, fix off-by-one in previous patch. 5 6 --- 7 dmenu.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 8 1 file changed, 83 insertions(+), 4 deletions(-) 9 10 diff --git a/dmenu.c b/dmenu.c 11 index e0c2f80..b4a6f70 100644 12 --- a/dmenu.c 13 +++ b/dmenu.c 14 @@ -32,6 +32,7 @@ struct item { 15 char *text; 16 struct item *left, *right; 17 int out; 18 + int distance; 19 }; 20 21 static char text[BUFSIZ] = ""; 22 @@ -253,6 +254,84 @@ match(void) 23 calcoffsets(); 24 } 25 26 +static int 27 +compare_distance(const void *a, const void *b) 28 +{ 29 + struct item const *da = *(struct item **) a; 30 + struct item const *db = *(struct item **) b; 31 + 32 + if (!db) 33 + return 1; 34 + if (!da) 35 + return -1; 36 + return da->distance - db->distance; 37 +} 38 + 39 +static void 40 +fuzzymatch(void) 41 +{ 42 + struct item *item; 43 + struct item **fuzzymatches = NULL; 44 + char c; 45 + int number_of_matches = 0, i, pidx, sidx, eidx; 46 + int text_len = strlen(text), itext_len; 47 + 48 + matches = matchend = NULL; 49 + 50 + /* walk through all items */ 51 + for (item = items; item && item->text; item++) { 52 + if (text_len) { 53 + itext_len = strlen(item->text); 54 + pidx = 0; 55 + sidx = eidx = -1; 56 + /* walk through item text */ 57 + for (i = 0; i < itext_len && (c = item->text[i]); i++) { 58 + /* fuzzy match pattern */ 59 + if (text[pidx] == c) { 60 + if (sidx == -1) 61 + sidx = i; 62 + pidx++; 63 + if (pidx == text_len) { 64 + eidx = i; 65 + break; 66 + } 67 + } 68 + } 69 + /* build list of matches */ 70 + if (eidx != -1) { 71 + /* compute distance */ 72 + /* factor in 30% of sidx and distance between eidx and total 73 + * text length .. let's see how it works */ 74 + item->distance = eidx - sidx + (itext_len - eidx + sidx) / 3; 75 + appenditem(item, &matches, &matchend); 76 + number_of_matches++; 77 + } 78 + } 79 + else 80 + appenditem(item, &matches, &matchend); 81 + } 82 + 83 + if (number_of_matches) { 84 + /* initialize array with matches */ 85 + if (!(fuzzymatches = realloc(fuzzymatches, number_of_matches * sizeof(struct item*)))) 86 + die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item *)); 87 + for (i = 0, item = matches; item && i < number_of_matches; i++, item = item->right) 88 + fuzzymatches[i] = item; 89 + 90 + /* sort matches according to distance */ 91 + qsort(fuzzymatches, number_of_matches, sizeof(struct item *), compare_distance); 92 + /* rebuild list of matches */ 93 + matches = matchend = NULL; 94 + for (i = 0, item = fuzzymatches[0]; i < number_of_matches && item && \ 95 + item->text; item = fuzzymatches[i], i++) 96 + appenditem(item, &matches, &matchend); 97 + 98 + free(fuzzymatches); 99 + } 100 + curr = sel = matches; 101 + calcoffsets(); 102 +} 103 + 104 static void 105 insert(const char *str, ssize_t n) 106 { 107 @@ -263,7 +342,7 @@ insert(const char *str, ssize_t n) 108 if (n > 0) 109 memcpy(&text[cursor], str, n); 110 cursor += n; 111 - match(); 112 + fuzzymatch(); 113 } 114 115 static size_t 116 @@ -308,7 +387,7 @@ keypress(XKeyEvent *ev) 117 118 case XK_k: /* delete right */ 119 text[cursor] = '\0'; 120 - match(); 121 + fuzzymatch(); 122 break; 123 case XK_u: /* delete left */ 124 insert(NULL, 0 - cursor); 125 @@ -444,7 +523,7 @@ keypress(XKeyEvent *ev) 126 strncpy(text, sel->text, sizeof text - 1); 127 text[sizeof text - 1] = '\0'; 128 cursor = strlen(text); 129 - match(); 130 + fuzzymatch(); 131 break; 132 } 133 drawmenu(); 134 @@ -586,7 +665,7 @@ setup(void) 135 } 136 promptw = (prompt && *prompt) ? TEXTW(prompt) : 0; 137 inputw = MIN(inputw, mw/3); 138 - match(); 139 + fuzzymatch(); 140 141 /* create menu window */ 142 swa.override_redirect = True; 143 -- 144 2.8.3 145