[PATCH 1/6] shell32/autocomplete: Introduce helpers for proper enumeration
These will be used to implement proper string enumeration, because Windows doesn't reset and re-enumerate it everytime autocompletion happens, and it also sorts them like Windows does. Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- For now, the first two patches in the series do nothing because the helpers are unused; they will be used afterwards, and were split to avoid the patches becoming too large. These helpers pave the way to implement the string sorting and ResetEnumerator, two of the TODO also listed at the top (tests provided at the end of the series). I will now describe the reason I ended up with this sort implementation. Merge Sort has been used to sort the strings because it is stable, and because it minimizes the amount of comparisons, which is essential for case-insensitive string comparisons. However it's not a plain bottom-up merge sort, it sorts in the same order as a recursive Merge Sort, but using iteration and a tiny stack. This is done to improve performance, which is quite significant in this case (bottom-up merge sort trashes the cache too much). When using Total Commander with a virtual database fs and an expand happens with around 450,000 items, it takes roughly 1.2 seconds on my CPU and 2 seconds on my older Core 2 Quad. Profiling shows that about 70% of the time is spent enumerating (and sorting), with the rest 30% just populating the listbox on the large expand, and it's way worse with a simple iterative Merge Sort, because it is very bad for the CPU's cache. Compared to a straight iterative bottom-up Merge Sort, it is at least 25% faster, and even more on older CPU with less cache. Compared with glibc's qsort (which also happens to be a merge sort on my setup) it is roughly 13% faster, which is a nice gain. But regardless, qsort can't be used since there's no guarantee it's a merge sort (and stable sort), it was just done for performance comparison purposes. The remaining 30%-40% time wasted on populating the listbox can be eliminated completely but that will happen in the future, not in this patch series, as LBS_NODATA for listboxes will have to be implemented first. This would reduce the time in this context from around 1 second to 0.6-0.7 seconds, which is much more manageable in my book. dlls/shell32/autocomplete.c | 230 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 230 insertions(+) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index dfe7638..ee3a6be 100644 --- a/dlls/shell32/autocomplete.c +++ b/dlls/shell32/autocomplete.c @@ -33,6 +33,7 @@ #include <stdarg.h> #include <stdlib.h> #include <string.h> +#include <limits.h> #define COBJMACROS @@ -62,6 +63,8 @@ typedef struct LONG ref; BOOL initialized; BOOL enabled; + UINT enum_strs_num; + WCHAR **enum_strs; HWND hwndEdit; HWND hwndListBox; WNDPROC wpOrigEditProc; @@ -103,10 +106,236 @@ static void set_text_and_selection(IAutoCompleteImpl *ac, HWND hwnd, WCHAR *text CallWindowProcW(proc, hwnd, EM_SETSEL, start, end); } +static BOOL sort_strs_excluding_pairs(WCHAR **strs, UINT numstrs) +{ + /* + Merge Sort the strings iteratively (excluding pairs, which are assumed sorted already), + using a stack instead of bottom-up mergesort, because the latter is cache unfriendly. + + The largest stack possible for a 32-bit UINT input (in terms of elements) looks like: + + 0, 31, 30, 29, ... , 1 (because we exclude pairs so we stop at 1) + + The initial 0 is the first stack slot which is special and must always compare false + */ + WCHAR **tmp; + BYTE stack[1 /* first special slot */ + (sizeof(UINT) * CHAR_BIT - 1)], w; + UINT a, top; + + if (numstrs <= 2) return TRUE; + if (!(tmp = heap_alloc(numstrs * sizeof(*tmp)))) return FALSE; + + stack[0] = 0; + top = 0; + + /* w contains the log2 (degree) of the width; i.e. width is 1 << w */ + w = 1; + + for (a = 0;;) + { + UINT b = a + (1 << w), i = a, j = b, end = min(b + (1 << w), numstrs); + WCHAR **p = tmp; + for (;;) + { + if (strcmpiW(strs[i], strs[j]) <= 0) + { + *p++ = strs[i++]; + if (i == b) break; + } + else + { + *p++ = strs[j++]; + if (j == end) + { + /* Copy them in reverse since i < dst */ + UINT dst = a + p - tmp, k = b - i; + do strs[dst + k - 1] = strs[i + k - 1]; while (--k); + break; + } + } + } + memcpy(&strs[a], tmp, (p - tmp) * sizeof(*strs)); + + /* If the top is the same width as our current one, sort them as a block */ + if (w == stack[top]) + { + top--; + w++; + a -= 1 << w; + continue; + } + + /* Otherwise push it and start from the smallest width for the next block */ + if (end + 2 < numstrs) + { + stack[++top] = w; + a = end; + w = 1; + continue; + } + + /* If there's no next block at all, sort it with double the top width */ + if (end == numstrs) + { + if (top == 0) + break; + w = stack[top--] + 1; + a -= 1 << w; + continue; + } + + /* Otherwise we have a partial block, merge it into the current block */ + w++; + } + + heap_free(tmp); + return TRUE; +} + +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) + - Sort pairs from the chain of blocks into a contiguous array of pointers to them + - Merge Sort the contiguous array/list (excluding pairs, since it's already done) + + 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[511 * 2]; /* this must be kept *even* */ + } *prevblock, *curblock; + + UINT i, cur, numstrs = 0; + LPOLESTR *strs; + + prevblock = NULL; + for (;;) + { + LONG rem; + 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) + goto break_from_enumeration; + rem -= n; + } + prevblock = curblock; + numstrs += ARRAY_SIZE(curblock->str); + } + +break_from_enumeration: + /* Allocate even if there were zero strings enumerated, to mark it non-NULL */ + numstrs += cur; + if (!(strs = heap_alloc(numstrs * sizeof(*strs)))) + { + 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); + return; + } + if (numstrs == 0) + { + ac->enum_strs = strs; + ac->enum_strs_num = numstrs; + heap_free(curblock); + return; + } + + /* Start by sorting pairs from the blocks into the contiguous list */ + i = numstrs; + if (numstrs % 2) + strs[--i] = curblock->str[--cur]; + do + { + while (cur) + { + WCHAR *a = curblock->str[cur - 2], *b = curblock->str[cur - 1], *c; + if (strcmpiW(a, b) > 0) + c = a, a = b, b = c; + strs[i - 2] = a; + strs[i - 1] = b; + i -= 2; + cur -= 2; + } + prevblock = curblock->prev; + heap_free(curblock); + curblock = prevblock; + cur = ARRAY_SIZE(curblock->str); + } while (curblock); + + /* Now sort the rest of the list */ + if (!sort_strs_excluding_pairs(strs, numstrs)) + { + do + CoTaskMemFree(strs[--numstrs]); + while (numstrs); + heap_free(strs); + return; + } + + ac->enum_strs = strs; + ac->enum_strs_num = numstrs; +} + +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 size_t format_quick_complete(WCHAR *dst, const WCHAR *qc, const WCHAR *str, size_t str_len) @@ -386,6 +615,7 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_ 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
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- These will eventually replace most of the code in autocomplete_text in the next patch. dlls/shell32/autocomplete.c | 69 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index ee3a6be..235225e 100644 --- a/dlls/shell32/autocomplete.c +++ b/dlls/shell32/autocomplete.c @@ -338,6 +338,21 @@ static void hide_listbox(IAutoCompleteImpl *ac, HWND hwnd) 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) { /* Replace the first %s directly without using snprintf, to avoid @@ -522,6 +537,60 @@ 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; -- 1.9.1
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/shell32/autocomplete.c | 81 ++++++++++++--------------------------------- 1 file changed, 21 insertions(+), 60 deletions(-) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index 235225e..3083a10 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" @@ -469,7 +468,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; @@ -505,6 +508,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; @@ -593,9 +599,9 @@ static BOOL display_matching_strs(IAutoCompleteImpl *ac, WCHAR *text, UINT len, 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) { @@ -611,74 +617,29 @@ 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) -- 1.9.1
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/shell32/autocomplete.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index 3083a10..b0a5208 100644 --- a/dlls/shell32/autocomplete.c +++ b/dlls/shell32/autocomplete.c @@ -757,10 +757,15 @@ static LRESULT APIENTRY ACEditSubclassProc(HWND hwnd, UINT uMsg, WPARAM wParam, hide_listbox(This, This->hwndListBox); return 0; case WM_KILLFOCUS: - if ((This->options & ACO_AUTOSUGGEST) && ((HWND)wParam != This->hwndListBox)) + if (This->options & ACO_AUTOSUGGEST) { - hide_listbox(This, This->hwndListBox); + if ((HWND)wParam == This->hwndListBox) break; + ShowWindow(This->hwndListBox, SW_HIDE); + SendMessageW(This->hwndListBox, LB_RESETCONTENT, 0, 0); } + + /* Reset the enumerator if it's not visible anymore */ + if (!IsWindowVisible(hwnd)) free_enum_strs(This); break; case WM_KEYDOWN: return ACEditSubclassProc_KeyDown(This, hwnd, uMsg, wParam, lParam); -- 1.9.1
This is needed for auto-append only AutoComplete controls. Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/shell32/autocomplete.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c index b0a5208..ffde6a5 100644 --- a/dlls/shell32/autocomplete.c +++ b/dlls/shell32/autocomplete.c @@ -607,6 +607,8 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_ { if (ac->options & ACO_AUTOSUGGEST) hide_listbox(ac, ac->hwndListBox); + else + free_enum_strs(ac); return; } -- 1.9.1
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- dlls/shell32/tests/autocomplete.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/dlls/shell32/tests/autocomplete.c b/dlls/shell32/tests/autocomplete.c index 66bd472..8265bf9 100644 --- a/dlls/shell32/tests/autocomplete.c +++ b/dlls/shell32/tests/autocomplete.c @@ -274,6 +274,7 @@ struct string_enumerator WCHAR **data; int data_len; int cur; + UINT num_resets; UINT num_expand; WCHAR last_expand[32]; }; @@ -349,6 +350,7 @@ static HRESULT WINAPI string_enumerator_Reset(IEnumString *iface) struct string_enumerator *this = impl_from_IEnumString(iface); this->cur = 0; + this->num_resets++; return S_OK; } @@ -456,6 +458,7 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator) static WCHAR str2[] = {'t','e','s','t','\\','f','o','o','\\','b','a','r','\\','b','a',0}; static WCHAR str2a[] = {'t','e','s','t','\\','f','o','o','\\','b','a','r','\\',0}; static WCHAR str2b[] = {'t','e','s','t','\\','f','o','o','\\','b','a','r','\\','b','a','z','_','b','b','q','\\',0}; + obj->num_resets = 0; ok(obj->num_expand == 0, "Expected 0 expansions, got %u\n", obj->num_expand); SendMessageW(hwnd_edit, WM_SETTEXT, 0, (LPARAM)str1); @@ -464,12 +467,14 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator) dispatch_messages(); ok(obj->num_expand == 1, "Expected 1 expansion, got %u\n", obj->num_expand); ok(lstrcmpW(obj->last_expand, str1a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str1a), wine_dbgstr_w(obj->last_expand)); + ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, WM_SETTEXT, 0, (LPARAM)str2); SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str2) - 1, ARRAY_SIZE(str2) - 1); SendMessageW(hwnd_edit, WM_CHAR, 'z', 1); dispatch_messages(); ok(obj->num_expand == 2, "Expected 2 expansions, got %u\n", obj->num_expand); ok(lstrcmpW(obj->last_expand, str2a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str2a), wine_dbgstr_w(obj->last_expand)); + ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets); SetFocus(hwnd_edit); SendMessageW(hwnd_edit, WM_CHAR, '_', 1); SendMessageW(hwnd_edit, WM_CHAR, 'b', 1); @@ -479,20 +484,24 @@ static void test_aclist_expand(HWND hwnd_edit, void *enumerator) SendMessageW(hwnd_edit, WM_CHAR, 'q', 1); dispatch_messages(); ok(obj->num_expand == 2, "Expected 2 expansions, got %u\n", obj->num_expand); + ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, WM_CHAR, '\\', 1); dispatch_messages(); ok(obj->num_expand == 3, "Expected 3 expansions, got %u\n", obj->num_expand); ok(lstrcmpW(obj->last_expand, str2b) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str2b), wine_dbgstr_w(obj->last_expand)); + ok(obj->num_resets == 3, "Expected 3 resets, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str1a) - 1, -1); SendMessageW(hwnd_edit, WM_CHAR, 'x', 1); SendMessageW(hwnd_edit, WM_CHAR, 'y', 1); dispatch_messages(); ok(obj->num_expand == 4, "Expected 4 expansions, got %u\n", obj->num_expand); ok(lstrcmpW(obj->last_expand, str1a) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str1a), wine_dbgstr_w(obj->last_expand)); + ok(obj->num_resets == 4, "Expected 4 resets, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, EM_SETSEL, ARRAY_SIZE(str1) - 1, -1); SendMessageW(hwnd_edit, WM_CHAR, 'x', 1); dispatch_messages(); ok(obj->num_expand == 4, "Expected 4 expansions, got %u\n", obj->num_expand); + ok(obj->num_resets == 5, "Expected 5 resets, got %u\n", obj->num_resets); } static void test_custom_source(void) @@ -502,6 +511,7 @@ static void test_custom_source(void) static WCHAR str_beta[] = {'a','u','t','o',' ','c','o','m','p','l','e','t','e',0}; static WCHAR str_au[] = {'a','u',0}; static WCHAR *suggestions[] = { str_alpha, str_alpha2, str_beta }; + struct string_enumerator *obj; IUnknown *enumerator; IAutoComplete2 *autocomplete; HWND hwnd_edit; @@ -516,6 +526,7 @@ static void test_custom_source(void) ok(hr == S_OK, "CoCreateInstance failed: %x\n", hr); string_enumerator_create((void**)&enumerator, suggestions, ARRAY_SIZE(suggestions)); + obj = (struct string_enumerator*)enumerator; hr = IAutoComplete2_SetOptions(autocomplete, ACO_AUTOSUGGEST | ACO_AUTOAPPEND); ok(hr == S_OK, "IAutoComplete2_SetOptions failed: %x\n", hr); @@ -528,11 +539,14 @@ static void test_custom_source(void) dispatch_messages(); SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer); ok(lstrcmpW(str_beta, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_beta), wine_dbgstr_w(buffer)); + ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, EM_SETSEL, 0, -1); SendMessageW(hwnd_edit, WM_CHAR, '\b', 1); dispatch_messages(); SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer); ok(buffer[0] == '\0', "Expected empty string, got %s\n", wine_dbgstr_w(buffer)); + ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets); + obj->num_resets = 0; /* hijack the window procedure */ HijackerWndProc_prev = (WNDPROC)SetWindowLongPtrW(hwnd_edit, GWLP_WNDPROC, (LONG_PTR)HijackerWndProc); @@ -545,6 +559,7 @@ static void test_custom_source(void) dispatch_messages(); SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer); ok(lstrcmpW(str_au, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_au), wine_dbgstr_w(buffer)); + ok(obj->num_resets == 1, "Expected 1 reset, got %u\n", obj->num_resets); SendMessageW(hwnd_edit, EM_SETSEL, 0, -1); SendMessageW(hwnd_edit, WM_CHAR, '\b', 1); dispatch_messages(); @@ -558,6 +573,7 @@ static void test_custom_source(void) dispatch_messages(); SendMessageW(hwnd_edit, WM_GETTEXT, ARRAY_SIZE(buffer), (LPARAM)buffer); ok(lstrcmpW(str_beta, buffer) == 0, "Expected %s, got %s\n", wine_dbgstr_w(str_beta), wine_dbgstr_w(buffer)); + ok(obj->num_resets == 2, "Expected 2 resets, got %u\n", obj->num_resets); /* end of hijacks */ test_aclist_expand(hwnd_edit, enumerator); -- 1.9.1
On Tue, Oct 23, 2018 at 02:26:02PM +0300, Gabriel Ivăncescu wrote:
These will be used to implement proper string enumeration, because Windows doesn't reset and re-enumerate it everytime autocompletion happens, and it also sorts them like Windows does.
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> ---
For now, the first two patches in the series do nothing because the helpers are unused; they will be used afterwards, and were split to avoid the patches becoming too large.
Please don't do this. Every patch needs to stand by itself; adding unused code doesn't count.
Merge Sort has been used to sort the strings because it is stable, and because it minimizes the amount of comparisons, which is essential for case-insensitive string comparisons.
I don't see why do you need a stable sort here. Using libc's qsort should be fine at first.
+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) + - Sort pairs from the chain of blocks into a contiguous array of pointers to them + - Merge Sort the contiguous array/list (excluding pairs, since it's already done) + + 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[511 * 2]; /* this must be kept *even* */ + } *prevblock, *curblock; + + UINT i, cur, numstrs = 0; + LPOLESTR *strs; + + prevblock = NULL; + for (;;) + { + LONG rem; + 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) + goto break_from_enumeration; + rem -= n; + } + prevblock = curblock; + numstrs += ARRAY_SIZE(curblock->str); + } + +break_from_enumeration: + /* Allocate even if there were zero strings enumerated, to mark it non-NULL */ + numstrs += cur; + if (!(strs = heap_alloc(numstrs * sizeof(*strs)))) + { + 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); + return; + }
And even though I've mentioned it twice already you're still using gotos. Please get them out of your system; there's no way anyone is going sign off on this. A 'goto fail' is ok, but the fail label needs to be at the outer-level and near the end of the function. If you think you need a goto for anything else then it's a sign you need to restructure your code. Huw.
On Wed, Oct 24, 2018 at 10:50 AM Huw Davies <huw(a)codeweavers.com> wrote:
Please don't do this. Every patch needs to stand by itself; adding unused code doesn't count.
So I should merge them into just one big patch then? (the first 3 in the series)
I don't see why do you need a stable sort here. Using libc's qsort should be fine at first.
Because the strings are compared case insensitively, so keeping the order in which they are originally enumerated is important to distinguish this, since some apps want to have them in a certain way (and probably even provide them already sorted, for example, like files on a case-insensitive filesystem, i.e. Total Commander, which should be in the exact same way). Furthermore, qsort would actually be slower still, since it doesn't take advantage of the fact that pairs are already sorted when moving them off the chain of blocks into the contiguous array. In some cases like my use case, I think it's significantly slower (~13%) and would be *very* slow on systems without a merge sort (because the string comparisons are the bottleneck, by far, *especially* due to caching reasons). These aren't random benchmarks with inflated time numbers, I've literally profiled it for my use case, not with artificial code and loops. (of course, it's still somewhat unusable since populating the listbox would be the next bottleneck to take care of)
And even though I've mentioned it twice already you're still using gotos. Please get them out of your system; there's no way anyone is going sign off on this. A 'goto fail' is ok, but the fail label needs to be at the outer-level and near the end of the function. If you think you need a goto for anything else then it's a sign you need to restructure your code.
Huw.
But one of the goto *is* a failure goto though? The "fail_and_free_blocks" is literally a failure and cleanup goto as its name says. Yes, it does jump into a block, but that block *returns* at the end and I've done it this way to avoid indenting everything else after it, which is literally the same as jumping to the end? So instead of: if (error) { fail: /* free stuff */ return; } /* non-error path */ It would look like: if (!error) { /* non-error path */ return; } fail: /* free stuff */ Which would indent the entire non-error path for no reason and I think it is worse off. Note that you can't "free stuff" after the non-error path because the non-error path has to free them as it actually uses them later, but not at the end (they blocks are already gone by that point). Lastly, the other goto is literally a "break twice" goto to break out of nested scope, which is normal in many code bases and I thought it's not an issue in the least. It also breaks *outside* any scopes and in fact many files in the wine code-base do that as well (e.g. user32/win.c with "goto other_process" is literally a goto to break out of inner scopes and jumps *far* further than this goto, why is that one ok?). I fail to see why a normal break is different than this goto, and if C supported nested breaks, it would be literally identical to a "break label" or the like. But maybe you only had issue with the first goto? The alternative would be to add BOOL checks on the outer scope but IMO that's way more ugly and requires more code.
On 24 Oct 2018, at 13:49, Gabriel Ivăncescu <gabrielopcode(a)gmail.com> wrote:
On Wed, Oct 24, 2018 at 10:50 AM Huw Davies <huw(a)codeweavers.com> wrote:
I don't see why do you need a stable sort here. Using libc's qsort should be fine at first.
Because the strings are compared case insensitively, so keeping the order in which they are originally enumerated is important to distinguish this, since some apps want to have them in a certain way (and probably even provide them already sorted, for example, like files on a case-insensitive filesystem, i.e. Total Commander, which should be in the exact same way).
I still don't see why this matters. Huw.
On Wed, Oct 24, 2018 at 5:18 PM Huw Davies <huw(a)codeweavers.com> wrote:
On 24 Oct 2018, at 13:49, Gabriel Ivăncescu <gabrielopcode(a)gmail.com> wrote:
On Wed, Oct 24, 2018 at 10:50 AM Huw Davies <huw(a)codeweavers.com> wrote:
I don't see why do you need a stable sort here. Using libc's qsort should be fine at first.
Because the strings are compared case insensitively, so keeping the order in which they are originally enumerated is important to distinguish this, since some apps want to have them in a certain way (and probably even provide them already sorted, for example, like files on a case-insensitive filesystem, i.e. Total Commander, which should be in the exact same way).
I still don't see why this matters.
Huw.
Because it will change the order of some strings "randomly" and depending on the platform it's ran under? How is that good behavior? Even adding items to a database will result in the rest being placed differently (compared to before) if they only differ in case, I don't see how that doesn't matter. AutoComplete is also used for URLs and ftp in apps, and those are case-sensitive (but the search isn't). I think obtaining consistent behavior on all platforms is definitely preferable. Nevermind the fact that it would be unusable for certain workloads if it doesn't use merge sort, due to very poor performance of other algorithms when it comes to expensive comparisons. Since qsort is not obliged to be implemented in merge sort (and in fact, I think only glibc uses merge sort, BSD doesn't), it's inadequate to rely on this to side-effect wine in this way.
On 24 Oct 2018, at 16:32, Gabriel Ivăncescu <gabrielopcode(a)gmail.com> wrote:
On Wed, Oct 24, 2018 at 5:18 PM Huw Davies <huw(a)codeweavers.com> wrote:
On 24 Oct 2018, at 13:49, Gabriel Ivăncescu <gabrielopcode(a)gmail.com> wrote:
On Wed, Oct 24, 2018 at 10:50 AM Huw Davies <huw(a)codeweavers.com> wrote:
I don't see why do you need a stable sort here. Using libc's qsort should be fine at first.
Because the strings are compared case insensitively, so keeping the order in which they are originally enumerated is important to distinguish this, since some apps want to have them in a certain way (and probably even provide them already sorted, for example, like files on a case-insensitive filesystem, i.e. Total Commander, which should be in the exact same way).
I still don't see why this matters.
Because it will change the order of some strings "randomly" and depending on the platform it's ran under? How is that good behavior? Even adding items to a database will result in the rest being placed differently (compared to before) if they only differ in case, I don't see how that doesn't matter.
I don't think this is an issue. Let's just use qsort for now and if it turns out to be needed you can roll your own sort later on. The idea is to make things easy to review, that way you'll stand much more chance of getting your patches in. Huw.
On Wed, Oct 24, 2018 at 8:03 PM Huw Davies <huw(a)codeweavers.com> wrote:
I don't think this is an issue. Let's just use qsort for now and if it turns out to be needed you can roll your own sort later on.
The idea is to make things easy to review, that way you'll stand much more chance of getting your patches in.
Huw.
Well honestly, this would already be an issue for me (as a user, in usability) if I used this on a non-merge-sort qsort system that doesn't use glibc, I can imagine there's surely other people with my use cases... I'm talking mostly about performance here, not even the stability of the sort (merge sort minimizes the amount of comparisons, so it's *much* faster in this situation than for example quicksort, since that's the bottleneck). Most of those large lists also have very long prefixes that expand (e.g. foo\bar\baz\bla\x\y\z\...) so that compounds the performance problem (string comparisons). Yeah, it's probably best to start with a qsort to simplify the patch for now, but I still think a merge sort should definitely be used eventually in a later patch, just for consistency on all platforms instead of it being sluggish on those not using merge sort (e.g. taking 2 seconds instead of 1 second is a large difference).
participants (2)
-
Gabriel Ivăncescu -
Huw Davies