[PATCH v2 1/4] shell32/autocomplete: Implement a cache and sort the enumerated strings for proper behavior
Gabriel Ivăncescu
gabrielopcode at gmail.com
Wed Oct 24 13:49:46 CDT 2018
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
+
+ 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;
+}
+
+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);
}
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)
+{
+ /* Return FALSE if we need to hide the listbox */
+ WCHAR **str = ac->enum_strs;
+ UINT cnt, a, b, i;
+ if (!str) return (ac->options & ACO_AUTOSUGGEST) ? FALSE : TRUE;
+
+ if (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
+ {
+ UINT mid = (a + b - 1) / 2u;
+ if (!strncmpiW(text, str[mid], len))
+ a = mid + 1;
+ else
+ b = mid;
+ } while (a < b);
+ }
+ 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)
{
- HRESULT hr;
WCHAR *text;
- UINT cpt, size, len = SendMessageW(hwnd, WM_GETTEXTLENGTH, 0, 0);
+ BOOL expanded = FALSE;
+ UINT size, len = SendMessageW(hwnd, WM_GETTEXTLENGTH, 0, 0);
if (flag != autoappend_flag_displayempty && len == 0)
{
@@ -313,79 +525,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 (ac->options & ACO_AUTOSUGGEST)
+ if (!display_matching_strs(ac, text, len, hwnd, flag))
{
- SendMessageW(ac->hwndListBox, WM_SETREDRAW, FALSE, 0);
+ /* 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);
}
- for (cpt = 0;;)
- {
- LPOLESTR strs = NULL;
- ULONG fetched;
-
- hr = IEnumString_Next(ac->enumstr, 1, &strs, &fetched);
- if (hr != S_OK)
- break;
-
- if (!strncmpiW(text, strs, len))
- {
- 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);
- }
-
- if (ac->options & ACO_AUTOSUGGEST)
- {
- if (cpt)
- {
- RECT r;
- UINT height = SendMessageW(ac->hwndListBox, LB_GETITEMHEIGHT, 0, 0);
- SendMessageW(ac->hwndListBox, LB_CARETOFF, 0, 0);
- GetWindowRect(hwnd, &r);
- /* It seems that Windows XP displays 7 lines at most
- and otherwise displays a vertical scroll bar */
- SetWindowPos(ac->hwndListBox, HWND_TOP,
- r.left, r.bottom + 1, r.right - r.left, height * min(cpt + 1, 7),
- SWP_SHOWWINDOW );
- SendMessageW(ac->hwndListBox, WM_SETREDRAW, TRUE, 0);
- }
- else
- hide_listbox(ac, ac->hwndListBox);
- }
}
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
More information about the wine-devel
mailing list