fuzzymatch.c (2972B)
1 #include <math.h> 2 3 int 4 compare_distance(const void *a, const void *b) 5 { 6 struct item *da = *(struct item **) a; 7 struct item *db = *(struct item **) b; 8 9 if (!db) 10 return 1; 11 if (!da) 12 return -1; 13 14 return da->distance == db->distance ? 0 : da->distance < db->distance ? -1 : 1; 15 } 16 17 void 18 fuzzymatch(void) 19 { 20 /* bang - we have so much memory */ 21 struct item *it; 22 struct item **fuzzymatches = NULL; 23 char c; 24 int number_of_matches = 0, i, pidx, sidx, eidx; 25 int text_len = strlen(text), itext_len; 26 #if HIGHPRIORITY_PATCH 27 struct item *lhpprefix, *hpprefixend; 28 lhpprefix = hpprefixend = NULL; 29 #endif // HIGHPRIORITY_PATCH 30 matches = matchend = NULL; 31 32 /* walk through all items */ 33 for (it = items; it && it->text; it++) { 34 if (text_len) { 35 itext_len = strlen(it->text); 36 pidx = 0; /* pointer */ 37 sidx = eidx = -1; /* start of match, end of match */ 38 /* walk through item text */ 39 for (i = 0; i < itext_len && (c = it->text[i]); i++) { 40 /* fuzzy match pattern */ 41 if (!fstrncmp(&text[pidx], &c, 1)) { 42 if (sidx == -1) 43 sidx = i; 44 pidx++; 45 if (pidx == text_len) { 46 eidx = i; 47 break; 48 } 49 } 50 } 51 /* build list of matches */ 52 if (eidx != -1) { 53 /* compute distance */ 54 /* add penalty if match starts late (log(sidx+2)) 55 * add penalty for long a match without many matching characters */ 56 it->distance = log(sidx + 2) + (double)(eidx - sidx - text_len); 57 /* fprintf(stderr, "distance %s %f\n", it->text, it->distance); */ 58 appenditem(it, &matches, &matchend); 59 number_of_matches++; 60 } 61 } else { 62 appenditem(it, &matches, &matchend); 63 } 64 } 65 66 if (number_of_matches) { 67 /* initialize array with matches */ 68 if (!(fuzzymatches = realloc(fuzzymatches, number_of_matches * sizeof(struct item*)))) 69 die("cannot realloc %u bytes:", number_of_matches * sizeof(struct item*)); 70 for (i = 0, it = matches; it && i < number_of_matches; i++, it = it->right) { 71 fuzzymatches[i] = it; 72 } 73 74 #if NO_SORT_PATCH 75 if (sortmatches) 76 #endif // NO_SORT_PATCH 77 /* sort matches according to distance */ 78 qsort(fuzzymatches, number_of_matches, sizeof(struct item*), compare_distance); 79 /* rebuild list of matches */ 80 matches = matchend = NULL; 81 for (i = 0, it = fuzzymatches[i]; i < number_of_matches && it && \ 82 it->text; i++, it = fuzzymatches[i]) { 83 #if HIGHPRIORITY_PATCH 84 #if NO_SORT_PATCH 85 if (sortmatches && it->hp) 86 #else 87 if (it->hp) 88 #endif // NO_SORT_PATCH 89 appenditem(it, &lhpprefix, &hpprefixend); 90 else 91 appenditem(it, &matches, &matchend); 92 #else 93 appenditem(it, &matches, &matchend); 94 #endif // HIGHPRIORITY_PATCH 95 } 96 free(fuzzymatches); 97 } 98 #if HIGHPRIORITY_PATCH 99 if (lhpprefix) { 100 hpprefixend->right = matches; 101 matches = lhpprefix; 102 } 103 #endif // HIGHPRIORITY_PATCH 104 curr = sel = matches; 105 106 #if INSTANT_PATCH 107 if (instant && matches && matches==matchend) { 108 printitem(matches); 109 cleanup(); 110 exit(0); 111 } 112 #endif // INSTANT_PATCH 113 114 calcoffsets(); 115 }