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