[PATCH v4 1/4] shell32/autocomplete: Implement a cache and sort the enumerated strings for proper behavior

Windows doesn't reset and re-enumerate it everytime autocompletion happens, and it also sorts the strings. This matches it more closely and makes it more useable on large lists as well. Signed-off-by: Gabriel Ivăncescu &lt;gabrielopcode(a)gmail.com&gt; --- v4: Simplified it more and culled many variables. dlls/shell32/autocomplete.c | 193 ++++++++++++++++++++++++++++++++------------ 1 file changed, 143 insertions(+), 50 deletions(-) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index b3f86f3..5a31259 100644 --- a/dlls/shell32/autocomplete.c +++ b/dlls/shell32/autocomplete.c @@ -25,7 +25,6 @@ - implement ACO_FILTERPREFIXES style - implement ACO_RTLREADING style - implement ResetEnumerator - - string compares should be case-insensitive, the content of the list should be sorted */ #include "config.h" @@ -62,6 +61,8 @@ typedef struct LONG ref; BOOL initialized; BOOL enabled; + UINT enum_strs_num; + WCHAR **enum_strs; HWND hwndEdit; HWND hwndListBox; WNDPROC wpOrigEditProc; @@ -103,10 +104,88 @@ static void set_text_and_selection(IAutoCompleteImpl *ac, HWND hwnd, WCHAR *text CallWindowProcW(proc, hwnd, EM_SETSEL, start, end); } +static int enumerate_strings_cmpfn(const void *a, const void *b) +{ + return strcmpiW(*(WCHAR* const*)a, *(WCHAR* const*)b); +} + +static void enumerate_strings(IAutoCompleteImpl *ac) +{ + /* + Enumerate all of the strings and sort them in the internal list. + + We don't free the enumerated strings (except on error) to avoid needless + copies, until the next reset (or the object itself is destroyed) + */ + UINT i, cur = 0, array_size = 1024; + LPOLESTR *strs = NULL, *tmp; + ULONG n; + + do + { + if ((tmp = heap_realloc(strs, array_size * sizeof(*strs))) == NULL) + goto fail; + strs = tmp; + + do + IEnumString_Next(ac->enumstr, array_size - cur, &strs[cur], &n); + while (n != 0 && (cur += n) < array_size); + + array_size *= 2; + } while (n != 0); + + /* Allocate even if there were zero strings enumerated, to mark it non-NULL */ + if ((tmp = heap_realloc(strs, cur * sizeof(*strs)))) + { + strs = tmp; + if (cur > 0) + qsort(strs, cur, sizeof(*strs), enumerate_strings_cmpfn); + + ac->enum_strs = strs; + ac->enum_strs_num = cur; + return; + } + +fail: + i = cur; + while (i--) + CoTaskMemFree(strs[i]); + heap_free(strs); +} + +static UINT find_first_matching_enum_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len) +{ + WCHAR **strs = ac->enum_strs; + UINT index = ~0, a = 0, b = ac->enum_strs_num; + while (a < b) + { + UINT i = (a + b - 1) / 2; + int cmp = strncmpiW(text, strs[i], len); + if (cmp == 0) index = i; + if (cmp <= 0) b = i; + else a = i + 1; + } + return index; +} + +static void free_enum_strs(IAutoCompleteImpl *ac) +{ + WCHAR **strs = ac->enum_strs; + if (strs) + { + UINT i = ac->enum_strs_num; + ac->enum_strs = NULL; + while (i--) + CoTaskMemFree(strs[i]); + heap_free(strs); + } +} + static void hide_listbox(IAutoCompleteImpl *ac, HWND hwnd) { ShowWindow(hwnd, SW_HIDE); SendMessageW(hwnd, LB_RESETCONTENT, 0, 0); + free_enum_strs(ac); } static void show_listbox(IAutoCompleteImpl *ac, UINT cnt) @@ -240,7 +319,11 @@ static LRESULT change_selection(IAutoCompleteImpl *ac, HWND hwnd, UINT key) static BOOL do_aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt, WCHAR *last_delim) { - WCHAR c = last_delim[1]; + WCHAR c; + free_enum_strs(ac); + IEnumString_Reset(ac->enumstr); /* call before expand */ + + c = last_delim[1]; last_delim[1] = '\0'; IACList_Expand(ac->aclist, txt); last_delim[1] = c; @@ -276,6 +359,9 @@ static BOOL aclist_expand(IAutoCompleteImpl *ac, WCHAR *txt) while (i--) if (strchrW(delims, txt[i])) return do_aclist_expand(ac, txt, &txt[i]); + + /* Windows doesn't expand without a delim, but it does reset */ + free_enum_strs(ac); } return FALSE; @@ -312,60 +398,60 @@ static BOOL display_matching_strs(IAutoCompleteImpl *ac, WCHAR *text, UINT len, HWND hwnd, enum autoappend_flag flag) { /* Return FALSE if we need to hide the listbox */ - UINT cpt; + WCHAR **str = ac->enum_strs; + UINT cnt, a, b, i; + if (!str) return (ac->options & ACO_AUTOSUGGEST) ? FALSE : TRUE; - if (ac->options & ACO_AUTOSUGGEST) - { - SendMessageW(ac->hwndListBox, WM_SETREDRAW, FALSE, 0); - SendMessageW(ac->hwndListBox, LB_RESETCONTENT, 0, 0); - } - for (cpt = 0;;) + if (len) { - HRESULT hr; - LPOLESTR strs = NULL; - ULONG fetched; - - hr = IEnumString_Next(ac->enumstr, 1, &strs, &fetched); - if (hr != S_OK) - break; - - if (!strncmpiW(text, strs, len)) + i = find_first_matching_enum_str(ac, text, len); + if (i == ~0) + return (ac->options & ACO_AUTOSUGGEST) ? FALSE : TRUE; + + if (flag == autoappend_flag_yes) + autoappend_str(ac, text, len, str[i], hwnd); + if (!(ac->options & ACO_AUTOSUGGEST)) + return TRUE; + + /* Find the last string that begins with text, starting the search from i, + which is guaranteed to find at least one string (if none other, then i) */ + a = i, b = ac->enum_strs_num; + do { - if (cpt == 0 && flag == autoappend_flag_yes) - { - autoappend_str(ac, text, len, strs, hwnd); - if (!(ac->options & ACO_AUTOSUGGEST)) - { - CoTaskMemFree(strs); - break; - } - } - - if (ac->options & ACO_AUTOSUGGEST) - SendMessageW(ac->hwndListBox, LB_ADDSTRING, 0, (LPARAM)strs); - - cpt++; - } - - CoTaskMemFree(strs); + UINT mid = (a + b - 1) / 2; + if (!strncmpiW(text, str[mid], len)) + a = mid + 1; + else + b = mid; + } while (a < b); } - - if (ac->options & ACO_AUTOSUGGEST) + else { - if (cpt) - { - show_listbox(ac, cpt); - SendMessageW(ac->hwndListBox, WM_SETREDRAW, TRUE, 0); - } - else + if (!(ac->options & ACO_AUTOSUGGEST)) + return TRUE; + i = 0; + a = ac->enum_strs_num; + if (a == 0) return FALSE; } + cnt = a - i; + + SendMessageW(ac->hwndListBox, WM_SETREDRAW, FALSE, 0); + SendMessageW(ac->hwndListBox, LB_RESETCONTENT, 0, 0); + SendMessageW(ac->hwndListBox, LB_INITSTORAGE, cnt, 0); + do + SendMessageW(ac->hwndListBox, LB_INSERTSTRING, -1, (LPARAM)str[i]); + while (++i < a); + + show_listbox(ac, cnt); + SendMessageW(ac->hwndListBox, WM_SETREDRAW, TRUE, 0); return TRUE; } static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_flag flag) { WCHAR *text; + BOOL expanded = FALSE; UINT size, len = SendMessageW(hwnd, WM_GETTEXTLENGTH, 0, 0); if (flag != autoappend_flag_displayempty && len == 0) @@ -382,28 +468,35 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_ if (len + 1 != size) text = heap_realloc(text, (len + 1) * sizeof(WCHAR)); - /* Reset it here to simplify the logic in aclist_expand for - empty strings, since it tracks changes using txtbackup, - and Reset needs to be called before IACList::Expand */ - IEnumString_Reset(ac->enumstr); if (ac->aclist) { - aclist_expand(ac, text); if (text[len - 1] == '\\' || text[len - 1] == '/') flag = autoappend_flag_no; + expanded = aclist_expand(ac, text); + } + if (expanded || !ac->enum_strs) + { + if (!expanded) IEnumString_Reset(ac->enumstr); + enumerate_strings(ac); } - /* Set txtbackup to point to text itself (which must not be released) */ + /* Set txtbackup to point to text itself (which must not be released), + and it must be done here since aclist_expand uses it to track changes */ heap_free(ac->txtbackup); ac->txtbackup = text; if (!display_matching_strs(ac, text, len, hwnd, flag)) - hide_listbox(ac, ac->hwndListBox); + { + /* Hide the listbox, but do not clear the enum strs, to match Windows */ + ShowWindow(ac->hwndListBox, SW_HIDE); + SendMessageW(ac->hwndListBox, LB_RESETCONTENT, 0, 0); + } } static void destroy_autocomplete_object(IAutoCompleteImpl *ac) { ac->hwndEdit = NULL; + free_enum_strs(ac); if (ac->hwndListBox) DestroyWindow(ac->hwndListBox); IAutoComplete2_Release(&ac->IAutoComplete2_iface); -- 1.9.1