sites

public wiki contents of suckless.org
git clone git://git.suckless.org/sites
Log | Files | 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}