[Git][freetype/freetype][master] [base] Build outlines in amortized constant time.

[Werner Lemberg (@wl)]

Werner Lemberg pushed to branch master at FreeType / FreeType

Commits:

• 0417e54b
  by Ben Wagner at 2022-07-23T23:30:22+02:00

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

1 changed file:

• src/base/ftgloadr.c

Changes:

src/base/ftgloadr.c

---

...	...	@@ -212,7 +212,7 @@
212	212	FT_Outline* current = &loader->current.outline;
213	213	FT_Bool adjust = 0;
214	214
215		- FT_UInt new_max, old_max;
	215	+ FT_UInt new_max, old_max, min_new_max;
216	216
217	217
218	218	error = FT_GlyphLoader_CreateExtra( loader );
...	...	@@ -226,14 +226,19 @@
226	226
227	227	if ( new_max > old_max )
228	228	{
229		- new_max = FT_PAD_CEIL( new_max, 8 );
230		-
231	229	if ( new_max > FT_OUTLINE_POINTS_MAX )
232	230	{
233	231	error = FT_THROW( Array_Too_Large );
234	232	goto Exit;
235	233	}
236	234
	235	+ min_new_max = old_max + ( old_max >> 1 );
	236	+ if ( new_max < min_new_max )
	237	+ new_max = min_new_max;
	238	+ new_max = FT_PAD_CEIL( new_max, 8 );
	239	+ if ( new_max > FT_OUTLINE_POINTS_MAX )
	240	+ new_max = FT_OUTLINE_POINTS_MAX;
	241	+
237	242	if ( FT_RENEW_ARRAY( base->points, old_max, new_max ) ||
238	243	FT_RENEW_ARRAY( base->tags, old_max, new_max ) )
239	244	goto Exit;
...	...	@@ -265,14 +270,19 @@
265	270	n_contours;
266	271	if ( new_max > old_max )
267	272	{
268		- new_max = FT_PAD_CEIL( new_max, 4 );
269		-
270	273	if ( new_max > FT_OUTLINE_CONTOURS_MAX )
271	274	{
272	275	error = FT_THROW( Array_Too_Large );
273	276	goto Exit;
274	277	}
275	278
	279	+ min_new_max = old_max + ( old_max >> 1 );
	280	+ if ( new_max < min_new_max )
	281	+ new_max = min_new_max;
	282	+ new_max = FT_PAD_CEIL( new_max, 4 );
	283	+ if ( new_max > FT_OUTLINE_CONTOURS_MAX )
	284	+ new_max = FT_OUTLINE_CONTOURS_MAX;
	285	+
276	286	if ( FT_RENEW_ARRAY( base->contours, old_max, new_max ) )
277	287	goto Exit;
278	288

—
View it on GitLab.
You're receiving this email because of your account on gitlab.freedesktop.org. If you'd like to receive fewer emails, you can adjust your notification settings.