From 3c443264cbef7b1e1fe08cc51cb7ad6d5752e7ae Mon Sep 17 00:00:00 2001 From: "Yann E. MORIN" Date: Mon, 6 May 2013 14:57:47 +0200 Subject: [PATCH] kconfig: sort found symbols by relevance When searching for symbols, return the symbols sorted by relevance. Sorting is done as thus: - first, symbols that match exactly - then, alphabetical sort Since the search can be a regexp, it is possible that more than one symbol matches exactly. In this case, we can't decide which to sort first, so we fallback to alphabeticall sort. Explain this (new!) sorting heuristic in the documentation. Reported-by: Jean Delvare Signed-off-by: "Yann E. MORIN" Cc: Jean Delvare Cc: Michal Marek Cc: Roland Eggner Cc: Wang YanQing -- Changes v1->v2: - drop the previous, complex heuristic in favour of a simpler heuristic that is both easier to understand, *and* to maintain (Jean) - explain sorting heuristic in the doc (Jean) Signed-off-by: Christian Lamparter --- config/symbol.c | 78 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 69 insertions(+), 9 deletions(-) diff --git a/config/symbol.c b/config/symbol.c index ab8f4c8..387d554 100644 --- a/config/symbol.c +++ b/config/symbol.c @@ -954,38 +954,98 @@ const char *sym_escape_string_value(const char *in) return res; } +struct sym_match { + struct symbol *sym; + off_t so, eo; +}; + +/* Compare matched symbols as thus: + * - first, symbols that match exactly + * - then, alphabetical sort + */ +static int sym_rel_comp( const void *sym1, const void *sym2 ) +{ + struct sym_match *s1 = *(struct sym_match **)sym1; + struct sym_match *s2 = *(struct sym_match **)sym2; + int l1, l2; + + /* Exact match: + * - if matched length on symbol s1 is the length of that symbol, + * then this symbol should come first; + * - if matched length on symbol s2 is the length of that symbol, + * then this symbol should come first. + * Note: since the search can be a regexp, both symbols may match + * exactly; if this is the case, we can't decide which comes first, + * and we fallback to sorting alphabetically. + */ + l1 = s1->eo - s1->so; + l2 = s2->eo - s2->so; + if (l1 == strlen(s1->sym->name) && l2 != strlen(s2->sym->name)) + return -1; + if (l1 != strlen(s1->sym->name) && l2 == strlen(s2->sym->name)) + return 1; + + /* As a fallback, sort symbols alphabetically */ + return strcmp(s1->sym->name, s2->sym->name); +} + struct symbol **sym_re_search(const char *pattern) { struct symbol *sym, **sym_arr = NULL; + struct sym_match **sym_match_arr = NULL; int i, cnt, size; regex_t re; + regmatch_t match[1]; cnt = size = 0; /* Skip if empty */ if (strlen(pattern) == 0) return NULL; - if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB|REG_ICASE)) + if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE)) return NULL; for_all_symbols(i, sym) { + struct sym_match *tmp_sym_match; if (sym->flags & SYMBOL_CONST || !sym->name) continue; - if (regexec(&re, sym->name, 0, NULL, 0)) + if (regexec(&re, sym->name, 1, match, 0)) continue; if (cnt + 1 >= size) { - void *tmp = sym_arr; + void *tmp; size += 16; - sym_arr = realloc(sym_arr, size * sizeof(struct symbol *)); - if (!sym_arr) { - free(tmp); - return NULL; + tmp = realloc(sym_match_arr, size * sizeof(struct sym_match *)); + if (!tmp) { + goto sym_re_search_free; } + sym_match_arr = tmp; } sym_calc_value(sym); - sym_arr[cnt++] = sym; + tmp_sym_match = (struct sym_match*)malloc(sizeof(struct sym_match)); + if (!tmp_sym_match) + goto sym_re_search_free; + tmp_sym_match->sym = sym; + /* As regexec return 0, we know we have a match, so + * we can use match[0].rm_[se]o without further checks + */ + tmp_sym_match->so = match[0].rm_so; + tmp_sym_match->eo = match[0].rm_eo; + sym_match_arr[cnt++] = tmp_sym_match; } - if (sym_arr) + if (sym_match_arr) { + qsort(sym_match_arr, cnt, sizeof(struct sym_match*), sym_rel_comp); + sym_arr = malloc((cnt+1) * sizeof(struct symbol)); + if (!sym_arr) + goto sym_re_search_free; + for (i = 0; i < cnt; i++) + sym_arr[i] = sym_match_arr[i]->sym; sym_arr[cnt] = NULL; + } +sym_re_search_free: + if (sym_match_arr) { + for (i = 0; i < cnt; i++) + free(sym_match_arr[i]); + free(sym_match_arr); + } regfree(&re); return sym_arr; -- 2.31.1