GopherProxy

	dmenu-fuzzymatch-20170603-f428f3e.diff - sites - public wiki contents of suckle…
	git clone git://git.suckless.org/sites
	Log
	Files
	Refs
	---
	dmenu-fuzzymatch-20170603-f428f3e.diff (4561B)
	---
	1 Author: Jan Christoph Ebersbach <[email protected]>
	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->di…
	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 mat…
	61 + /* walk through item text */
	62 + for (i = 0; i < itext_len && (c = it->text[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 (lo…
	78 + * add penalty for long a match without…
	79 + it->distance = log(sidx + 2) + (double)…
	80 + /* fprintf(stderr, "distance %s %f\n", …
	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_ma…
	92 + die("cannot realloc %u bytes:", number_of_match…
	93 + for (i = 0, it = matches; it && i < number_of_matches; …
	94 + fuzzymatches[i] = it;
	95 + }
	96 + /* sort matches according to distance */
	97 + qsort(fuzzymatches, number_of_matches, sizeof(struct it…
	98 + /* rebuild list of matches */
	99 + matches = matchend = NULL;
	100 + for (i = 0, it = fuzzymatches[i]; i < number_of_matche…
	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 be…
	123 fast = 1;
	124 + else if (!strcmp(argv[i], "-F")) /* grabs keyboard be…
	125 + fuzzy = 0;
	126 else if (!strcmp(argv[i], "-i")) { /* case-insensitive …
	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 …
	137 +static int fuzzy = 1; /* -F option; if 0, dmenu d…
	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…