[patch] Slow performance in TEXT_Ellipsify
Paul Rupe
prupe at myrealbox.com
Sun Jun 9 21:53:53 CDT 2002
I was getting really slow performance in an app I was testing. I
traced it to TEXT_Ellipsify, which works by moving backwards one
character at a time from the end of the string until it finds something
that fits in the given width. When cutting a 1000-char string to fit a
200-pixel area, this takes a while. I added a binary search to the
beginning of the loop and things move much faster now. I think it's
still doing a lot more work than needed, but at least it's no longer
O(n^2), maybe O((ln n)^2).
Changelog:
Paul Rupe <prupe at myrealbox.com>
dlls/user/text.c
Faster performance in TEXT_Ellipsify for long strings
--
Paul Rupe "She smiled, in the
end."
p r u p e @ m y r e a l b o x . c o m
| Oppose government police-ware on your PC!
| Stop the Consumer Broadband and Digital Television Promotion Act!
| <http://www.eff.org/alerts/20020322_eff_cbdtpa_alert.html>
-------------- next part --------------
Index: dlls/user/text.c
===================================================================
RCS file: /home/wine/wine/dlls/user/text.c,v
retrieving revision 1.37
diff -u -r1.37 text.c
--- dlls/user/text.c 31 May 2002 23:40:53 -0000 1.37
+++ dlls/user/text.c 10 Jun 2002 01:31:18 -0000
@@ -135,12 +135,31 @@
int *len_before, int *len_ellip)
{
unsigned int len_ellipsis;
+ unsigned int lo, mid, hi;
len_ellipsis = strlenW (ELLIPSISW);
if (len_ellipsis > max_len) len_ellipsis = max_len;
if (*len_str > max_len - len_ellipsis)
*len_str = max_len - len_ellipsis;
+ /* First do a quick binary search to get an upper bound for *len_str. */
+ if (*len_str > 0 &&
+ GetTextExtentExPointW(hdc, str, *len_str, width, NULL, NULL, size) &&
+ size->cx > width)
+ {
+ for (lo = 0, hi = *len_str; lo < hi; )
+ {
+ mid = (lo + hi) / 2;
+ if (!GetTextExtentExPointW(hdc, str, mid, width, NULL, NULL, size))
+ break;
+ if (size->cx > width)
+ hi = mid;
+ else
+ lo = mid + 1;
+ }
+ *len_str = hi;
+ }
+ /* Now this should take only a couple iterations at most. */
for ( ; ; )
{
strncpyW (str + *len_str, ELLIPSISW, len_ellipsis);
More information about the wine-patches
mailing list