[patch] Slow performance in TEXT_Ellipsify

[Paul Rupe <prupe@myrealbox.com>]

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@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>
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);