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

[Gabriel Ivăncescu]

On Thu, Oct 25, 2018 at 3:43 PM Huw Davies <huw at codeweavers.com> wrote:
>
> 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).
>

Wouldn't that be a problem if there's a lot of strings to enumerate?
There will be a huge amount of reallocations. Obviously, it's only in
*those* cases that performance even matters, not when the amount of
strings is small (thinking in range about 500k or more).

Also note that the copy is only done due to qsort; previously, there
was no copy needed, since Merge Sort was done directly on the blocks
in pairs first, and moved to the list -- in other words, it's probably
temporary for now to avoid more changes later.

>
> Can't you use bsearch() ?
>

I don't think that's possible since I need to get the *first* element
that starts with the given string, not just any matching element. Note
that the search keeps on despite the fact an element is found, but it
remembers the last cmp that was zero.

FWIW I looked at the listbox string search now, and it does something
similar... Also I think binary search is way too simple to even need
bsearch IMO, it would probably add more code even if it could have
been used (an extra function for it...).

>
> 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.
>

Ok, I'll do that. Originally it was a smaller patch since it was split
so I forgot to refactor. :-)

>
> 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.

Ok will do.