[PATCH v2 1/4] shell32/autocomplete: Implement a cache and sort the enumerated strings for proper behavior
Huw Davies
huw at codeweavers.com
Thu Oct 25 07:43:13 CDT 2018
On Wed, Oct 24, 2018 at 09:49:46PM +0300, 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>
> ---
>
> v2: Merged the first 3 patches, used qsort, replaced goto that broke out
> of nested scope with a BOOL check, and moved the goto failure path at the
> end outside of any blocks.
>
> dlls/shell32/autocomplete.c | 288 +++++++++++++++++++++++++++++++++++---------
> 1 file changed, 228 insertions(+), 60 deletions(-)
>
> diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
> index dfe7638..751bda0 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,160 @@ 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. Rough summary:
> +
> + - Enumerate the strings and place their addresses in a chain of blocks (stack-like)
> + - Copy the pointers from the blocks into a contiguous array/list
> + - Sort the contiguous array/list
Why don't you add them to a contiguous array as you go, by realloc'ing the array.
This would avoid all this complicated block stuff (and if the reallocs don't
need to move, you avoid the copy).
> +
> + We don't free the enumerated strings (except on error) to avoid needless
> + copies, until the next reset (or the object itself is destroyed)
> + */
> + struct
> + {
> + void *prev;
> + LPOLESTR str[1020];
> + } *prevblock, *curblock;
> +
> + UINT i, cur, numstrs = 0;
> + LPOLESTR *strs;
> +
> + prevblock = NULL;
> + for (;;)
> + {
> + LONG rem;
> + BOOL break_enum = FALSE;
> +
> + if ((curblock = heap_alloc(sizeof(*curblock))) == NULL)
> + {
> + if (!prevblock)
> + return;
> + curblock = prevblock;
> + cur = ARRAY_SIZE(curblock->str);
> + goto fail_and_free_blocks;
> + }
> + curblock->prev = prevblock;
> + rem = ARRAY_SIZE(curblock->str);
> +
> + while (rem > 0)
> + {
> + ULONG n = 0;
> + cur = ARRAY_SIZE(curblock->str) - rem;
> + IEnumString_Next(ac->enumstr, rem, &curblock->str[cur], &n);
> + if (n == 0)
> + {
> + break_enum = TRUE;
> + break;
> + }
> + rem -= n;
> + }
> + if (break_enum) break;
> + prevblock = curblock;
> + numstrs += ARRAY_SIZE(curblock->str);
> + }
> +
> + /* Allocate even if there were zero strings enumerated, to mark it non-NULL */
> + numstrs += cur;
> + if ((strs = heap_alloc(numstrs * sizeof(*strs))))
> + {
> + if (numstrs == 0)
> + {
> + ac->enum_strs = strs;
> + ac->enum_strs_num = numstrs;
> + heap_free(curblock);
> + return;
> + }
> +
> + /* Copy the pointers from the chain of blocks to the contiguous list */
> + i = numstrs;
> + do
> + {
> + i -= cur;
> + memcpy(&strs[i], curblock->str, cur * sizeof(*strs));
> +
> + prevblock = curblock->prev;
> + heap_free(curblock);
> + curblock = prevblock;
> + cur = ARRAY_SIZE(curblock->str);
> + } while (curblock);
> +
> + /* Now sort the list */
> + qsort(strs, numstrs, sizeof(*strs), enumerate_strings_cmpfn);
> +
> + ac->enum_strs = strs;
> + ac->enum_strs_num = numstrs;
> + return;
> + }
> +
> +fail_and_free_blocks:
> + do
> + {
> + LPOLESTR *str = curblock->str;
> + while (cur--)
> + CoTaskMemFree(str[cur]);
> + prevblock = curblock->prev;
> + heap_free(curblock);
> + curblock = prevblock;
> + cur = ARRAY_SIZE(curblock->str);
> + } while (curblock);
> +}
> +
> +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;
> +}
Can't you use bsearch() ?
> +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)
> +{
> + RECT r;
> + UINT width, height;
> +
> + GetWindowRect(ac->hwndEdit, &r);
> + SendMessageW(ac->hwndListBox, LB_CARETOFF, 0, 0);
> +
> + /* Windows XP displays 7 lines at most, then it uses a scroll bar */
> + height = SendMessageW(ac->hwndListBox, LB_GETITEMHEIGHT, 0, 0) * min(cnt + 1, 7);
> + width = r.right - r.left;
> +
> + SetWindowPos(ac->hwndListBox, HWND_TOP, r.left, r.bottom + 1, width, height, SWP_SHOWWINDOW);
> }
There's quite a lot of code movement going on from here on down. I'd
suggest pulling out the show_listbox() helper from autocomplete_text()
first, before adding the caching stuff.
> static size_t format_quick_complete(WCHAR *dst, const WCHAR *qc, const WCHAR *str, size_t str_len)
> @@ -225,7 +376,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;
> @@ -261,6 +416,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;
> @@ -293,11 +451,65 @@ static void autoappend_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len, WCHAR *
> heap_free(tmp);
> }
>
> +static BOOL display_matching_strs(IAutoCompleteImpl *ac, WCHAR *text, UINT len,
> + HWND hwnd, enum autoappend_flag flag)
> +{
Likewise the filling listbox code should be pulled out before adding the caching stuff.
In other words, in the patch the finally adds the cache, there shouldn't be (m)any
changes to autocomplete_text(), just to its helper functions.
Huw.
More information about the wine-devel
mailing list