[PATCH v4 1/4] shell32/autocomplete: Implement a cache and sort the enumerated strings for proper behavior
Huw Davies
huw at codeweavers.com
Thu Nov 1 04:57:37 CDT 2018
On Wed, Oct 31, 2018 at 01:24:28PM +0200, Gabriel Ivăncescu wrote:
> 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 <gabrielopcode at gmail.com>
> ---
>
> 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)
> + */
Please move this comment to above the function.
> + 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);
Hopefully you agree that this looks much nicer than the previous
versions. There's a slight issue though in that you should check that
the return value from IEnumString_Next() == S_OK. You could simply
then set n = 0 if that condition isn't met, to break out of the loops.
Also, let's change 'n' -> 'read'.
> + /* 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;
'i' is superfluous, you can directly decrement '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);
So this search loop looks like the code in find_first_matching...().
I'd suggest making that function more general, and having a take a
parameter 'BOOL direction' parameter that would find the last in the
list if set. You could also pass the start and end indicies to avoid
unnecessary searching in this case.
> }
> -
> - 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;
> }
There's still a lot of code shuffling in this patch in
dispatch_matching_strs(). Can you try to reduce that by more patch
splitting? At the moment there's just too much going on to clearly
see what this patch is doing.
> 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);
> + }
So you moved this to a helper as I suggested and then moved it back in
the next patch?? You could add a BOOL flag to hide_listbox that
performs the reset if it's set.
Huw.
More information about the wine-devel
mailing list