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