dmenu-fuzzymatch-20170603-f428f3e.diff - sites - public wiki contents of suckless.org
(HTM) git clone git://git.suckless.org/sites
(DIR) Log
(DIR) Files
(DIR) Refs
---
dmenu-fuzzymatch-20170603-f428f3e.diff (4561B)
---
1 Author: Jan Christoph Ebersbach <jceb@e-jc.de>
2 URL: http://tools.suckless.org/dmenu/patches/fuzzymatch
3 Add add fuzzy matching to dmenu
4
5 Index: dmenu-patches/dmenu/dmenu.c
6 ===================================================================
7 --- a/dmenu.c
8 +++ b/dmenu.c
9 @@ -1,6 +1,7 @@
10 /* See LICENSE file for copyright and license details. */
11 #include <ctype.h>
12 #include <locale.h>
13 +#include <math.h>
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 @@ -31,6 +32,7 @@ struct item {
18 char *text;
19 struct item *left, *right;
20 int out;
21 + double distance;
22 };
23
24 static char text[BUFSIZ] = "";
25 @@ -209,9 +211,94 @@ grabkeyboard(void)
26 die("cannot grab keyboard");
27 }
28
29 +int
30 +compare_distance(const void *a, const void *b)
31 +{
32 + struct item *da = *(struct item **) a;
33 + struct item *db = *(struct item **) b;
34 +
35 + if (!db)
36 + return 1;
37 + if (!da)
38 + return -1;
39 +
40 + return da->distance == db->distance ? 0 : da->distance < db->distance ? -1 : 1;
41 +}
42 +
43 +void
44 +fuzzymatch(void)
45 +{
46 + /* bang - we have so much memory */
47 + struct item *it;
48 + struct item **fuzzymatches = NULL;
49 + char c;
50 + int number_of_matches = 0, i, pidx, sidx, eidx;
51 + int text_len = strlen(text), itext_len;
52 +
53 + matches = matchend = NULL;
54 +
55 + /* walk through all items */
56 + for (it = items; it && it->text; it++) {
57 + if (text_len) {
58 + itext_len = strlen(it->text);
59 + pidx = 0; /* pointer */
60 + sidx = eidx = -1; /* start of match, end of match */
61 + /* walk through item text */
62 + for (i = 0; i < itext_len && (c = it->text[i]); i++) {
63 + /* fuzzy match pattern */
64 + if (!fstrncmp(&text[pidx], &c, 1)) {
65 + if(sidx == -1)
66 + sidx = i;
67 + pidx++;
68 + if (pidx == text_len) {
69 + eidx = i;
70 + break;
71 + }
72 + }
73 + }
74 + /* build list of matches */
75 + if (eidx != -1) {
76 + /* compute distance */
77 + /* add penalty if match starts late (log(sidx+2))
78 + * add penalty for long a match without many matching characters */
79 + it->distance = log(sidx + 2) + (double)(eidx - sidx - text_len);
80 + /* fprintf(stderr, "distance %s %f\n", it->text, it->distance); */
81 + appenditem(it, &matches, &matchend);
82 + number_of_matches++;
83 + }
84 + } else {
85 + appenditem(it, &matches, &matchend);
86 + }
87 + }
88 +
89 + if (number_of_matches) {
90 + /* initialize array with matches */
91 + if (!(fuzzymatches = realloc(fuzzymatches, number_of_matches * sizeof(struct item*))))
92 + die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item*));
93 + for (i = 0, it = matches; it && i < number_of_matches; i++, it = it->right) {
94 + fuzzymatches[i] = it;
95 + }
96 + /* sort matches according to distance */
97 + qsort(fuzzymatches, number_of_matches, sizeof(struct item*), compare_distance);
98 + /* rebuild list of matches */
99 + matches = matchend = NULL;
100 + for (i = 0, it = fuzzymatches[i]; i < number_of_matches && it && \
101 + it->text; i++, it = fuzzymatches[i]) {
102 + appenditem(it, &matches, &matchend);
103 + }
104 + free(fuzzymatches);
105 + }
106 + curr = sel = matches;
107 + calcoffsets();
108 +}
109 +
110 static void
111 match(void)
112 {
113 + if (fuzzy) {
114 + fuzzymatch();
115 + return;
116 + }
117 static char **tokv = NULL;
118 static int tokn = 0;
119
120 @@ -656,6 +743,8 @@ main(int argc, char *argv[])
121 topbar = 0;
122 else if (!strcmp(argv[i], "-f")) /* grabs keyboard before reading stdin */
123 fast = 1;
124 + else if (!strcmp(argv[i], "-F")) /* grabs keyboard before reading stdin */
125 + fuzzy = 0;
126 else if (!strcmp(argv[i], "-i")) { /* case-insensitive item matching */
127 fstrncmp = strncasecmp;
128 fstrstr = cistrstr;
129 Index: dmenu-patches/dmenu/config.def.h
130 ===================================================================
131 --- a/config.def.h
132 +++ b/config.def.h
133 @@ -2,6 +2,7 @@
134 /* Default settings; can be overriden by command line. */
135
136 static int topbar = 1; /* -b option; if 0, dmenu appears at bottom */
137 +static int fuzzy = 1; /* -F option; if 0, dmenu doesn't use fuzzy matching */
138 /* -fn option overrides fonts[0]; default X11 font or font set */
139 static const char *fonts[] = {
140 "monospace:size=10"
141 Index: dmenu-patches/dmenu/config.mk
142 ===================================================================
143 --- a/config.mk
144 +++ b/config.mk
145 @@ -20,7 +20,7 @@ FREETYPEINC = /usr/include/freetype2
146
147 # includes and libs
148 INCS = -I${X11INC} -I${FREETYPEINC}
149 -LIBS = -L${X11LIB} -lX11 ${XINERAMALIBS} ${FREETYPELIBS}
150 +LIBS = -L${X11LIB} -lX11 ${XINERAMALIBS} ${FREETYPELIBS} -lm
151
152 # flags
153 CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_POSIX_C_SOURCE=200809L -DVERSION=\"${VERSION}\" ${XINERAMAFLAGS}