dmenu-fuzzymatch-4.6.diff - sites - public wiki contents of suckless.org
(HTM) git clone git://git.suckless.org/sites
(DIR) Log
(DIR) Files
(DIR) Refs
---
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