[freetype2] master 0417e54be: [base] Build outlines in amortized constant time.

[Werner Lemberg]

branch: master
commit 0417e54bec27aed35421a53271aaf0484adc892e
Author: Ben Wagner <bungeman@chromium.org>
Commit: Werner Lemberg <wl@gnu.org>

    [base] Build outlines in amortized constant time.
    
    When resizing the loader's points and contours, resize them to at least 1.5
    times their current size.  The code currently only reserves as much space as
    is currently required, leading to O(n^2) runtime when adding points one at a
    time.
    
    This change does not attempt to ever shrink the loader's point and contour
    storage since this was not attempted previously either.  The 1.5 multiple
    was chosen as a trade-off between potentially unused space and the runtime.
    
    * src/base/ftgloader.c (FT_GlyphLoader_CheckPoints): Implement it.
    
    Fixes #1173.
---
 src/base/ftgloadr.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/src/base/ftgloadr.c b/src/base/ftgloadr.c
index 90cc09c02..b2cdabfbd 100644
--- a/src/base/ftgloadr.c
+++ b/src/base/ftgloadr.c
@@ -212,7 +212,7 @@
     FT_Outline*  current = &loader->current.outline;
     FT_Bool      adjust  = 0;
 
-    FT_UInt      new_max, old_max;
+    FT_UInt  new_max, old_max, min_new_max;
 
 
     error = FT_GlyphLoader_CreateExtra( loader );
@@ -226,14 +226,19 @@
 
     if ( new_max > old_max )
     {
-      new_max = FT_PAD_CEIL( new_max, 8 );
-
       if ( new_max > FT_OUTLINE_POINTS_MAX )
       {
         error = FT_THROW( Array_Too_Large );
         goto Exit;
       }
 
+      min_new_max = old_max + ( old_max >> 1 );
+      if ( new_max < min_new_max )
+        new_max = min_new_max;
+      new_max = FT_PAD_CEIL( new_max, 8 );
+      if ( new_max > FT_OUTLINE_POINTS_MAX )
+        new_max = FT_OUTLINE_POINTS_MAX;
+
       if ( FT_RENEW_ARRAY( base->points, old_max, new_max ) ||
            FT_RENEW_ARRAY( base->tags,   old_max, new_max ) )
         goto Exit;
@@ -265,14 +270,19 @@
               n_contours;
     if ( new_max > old_max )
     {
-      new_max = FT_PAD_CEIL( new_max, 4 );
-
       if ( new_max > FT_OUTLINE_CONTOURS_MAX )
       {
         error = FT_THROW( Array_Too_Large );
         goto Exit;
       }
 
+      min_new_max = old_max + ( old_max >> 1 );
+      if ( new_max < min_new_max )
+        new_max = min_new_max;
+      new_max = FT_PAD_CEIL( new_max, 4 );
+      if ( new_max > FT_OUTLINE_CONTOURS_MAX )
+        new_max = FT_OUTLINE_CONTOURS_MAX;
+
       if ( FT_RENEW_ARRAY( base->contours, old_max, new_max ) )
         goto Exit;