diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | fuzzy.c | 110 | ||||
| -rw-r--r-- | fuzzy.h | 6 | ||||
| -rw-r--r-- | main.c | 36 |
4 files changed, 138 insertions, 16 deletions
@@ -1,7 +1,7 @@ EXE = xmenu OBJ != find . -name '*.c' | sed -e 's/\.c$$/.o/' -e 's|^\./||' -CFLAGS += -Wall -Wpedantic -I/usr/X11R7/include -g +CFLAGS += -Wall -Wpedantic -I/usr/X11R7/include -O0 -g LDFLAGS += -lX11 -lxcb -lXt -lXau -lXdmcp -L/usr/X11R7/lib -static PREFIX ?= ${HOME} @@ -0,0 +1,110 @@ +#include <stdint.h> +#include <string.h> + +#include "str.h" +#include "arena.h" + +typedef struct { + uint16_t score, start; +} FuzzyScore; + +static inline char +to_lower(char c) +{ + /* TODO: consider utf-8 support */ + if (c >= 'A' && c <= 'Z') return c + ('a' - 'A'); + return c; +} + +static inline int +fz_start_score(Str s, Str p) +{ + if (!p.n || str_eql(s, p)) return 0; + int n = 1; + int pi = 0, si = 0; + for (;;) { + if (to_lower(p.s[pi]) == to_lower(s.s[si])) { + si++; + pi++; + if (si == s.n) { + return pi < p.n ? -1 : n; + } else if (pi == p.n) { + return n; + } + } else { + si++; + n++; + if (si == s.n) return -1; + } + } +} + +static inline FuzzyScore +fz_score(Str s, Str p) +{ + if (!p.n) return (FuzzyScore) { 0, 0 }; + int score = -1; + int score_start = 0; + for (int i = 0; i < s.n; i++) { + int f = fz_start_score(str_skip(s, i), p); + if (f == -1) continue; + if (score == -1 || f < score) { + score = f; + score_start = i; + } + } + if (score == -1) return (FuzzyScore) { 0xffff, 0 }; + return (FuzzyScore) { score, score_start }; +} + +static inline int +fz_cmp(FuzzyScore a, FuzzyScore b, Str sa, Str sb) +{ + if (a.score < b.score) return -1; + if (b.score < a.score) return 1; + if (sa.n < sb.n) return -1; + if (sb.n < sa.n) return 1; + return (b.start < a.start) - (a.start < b.start); +} + +void +fz_qsort_opt(Str * restrict dest, FuzzyScore * restrict scr, int n) +{ + int i = 0, j = n - 1; + FuzzyScore x = scr[n / 2]; + Str xs = dest[n / 2]; + do { + while (fz_cmp(scr[i], x, dest[i], xs) < 0) i++; + while (fz_cmp(x, scr[j], xs, dest[j]) < 0) j--; + if (i <= j) { + Str t0 = dest[i]; + dest[i] = dest[j]; + dest[j] = t0; + FuzzyScore t1 = scr[i]; + scr[i] = scr[j]; + scr[j] = t1; + i++; + j--; + } + } while (i <= j); + if (0 < j) fz_qsort_opt(dest, scr, j + 1); + if (i+1 < n) fz_qsort_opt(dest + i, scr + i, n - i); +} + +int +fz_sort(Str * restrict out, const Str * restrict src, int n, Str pat, Arena *scratch) +{ + FuzzyScore *scr = new_arr(scratch, FuzzyScore, n); + int scrn = 0; + for (int i = 0; i < n; i++) { + FuzzyScore s = fz_score(src[i], pat); + if (s.score != 0xffff) { + scr[scrn] = s; + out[scrn] = src[i]; + scrn++; + } + } + if (pat.n > 0) + fz_qsort_opt(out, scr, scrn); + return scrn; +} @@ -0,0 +1,6 @@ +#ifndef FUZZY_H +#define FUZZY_H + +int fz_sort(Str * restrict out, const Str * restrict src, int n, Str pat, Arena *scratch); + +#endif @@ -13,6 +13,7 @@ #include "dynarr.h" #include "str.h" #include "ui.h" +#include "fuzzy.h" typedef DYNARR(char) DynStr; @@ -64,23 +65,30 @@ read_all(FILE *f, DynStr *out, Arena *a) int main(int argc, char **argv) { - Arena a = { 0 }; + Arena perm = { 0 }; + Arena scratch = { 0 }; DynStr input = { 0 }; int inpi = 0; int seli = 0; - UiOpts opt = { 0 }; + UiOpts opt_src = { 0 }; DynStr buf = { 0 }; - if (read_all(stdin, &buf, &a)) err(1, "stdin"); + if (read_all(stdin, &buf, &perm)) err(1, "stdin"); for (Str src = { buf.v, buf.n }; src.n > 0; ) { Cut c = str_cut(src, '\n'); - DA_APUSH(&opt, &a, c.head); + DA_APUSH(&opt_src, &perm, c.head); src = c.tail; } - if (!opt.n) return 0; + if (!opt_src.n) return 0; - ui_init(argc, argv, opt); + UiOpts opt = { + .v = new_arr(&perm, Str, opt_src.n), + .n = opt_src.n, + }; + + ui_init(argc, argv, opt_src); + DA_FIT(&input, 32); for (UiEvent ev; ui_wait_event(&ev); ) { switch (ev.type) { @@ -121,14 +129,11 @@ main(int argc, char **argv) } break; case UI_REDRAW: - draw: - ui_draw( - (Str) { input.v, input.n }, - inpi, - seli, - opt - ); - break; + draw: { + Str s = { input.v, input.n }; + opt.n = fz_sort(opt.v, opt_src.v, opt_src.n, s, &scratch); + ui_draw(s, inpi, seli, opt); + } break; case UI_QUIT: goto done; default: @@ -138,6 +143,7 @@ main(int argc, char **argv) done: ui_fini(); - arena_free(&a); + arena_free(&perm); + arena_free(&scratch); return 0; } |