Skip to content

Build outlines in amortized constant time

Ben Wagner requested to merge bungeman/freetype:expand_loader_points_and_contours_faster into master

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): resize point and countour arrays to at least 1.5 times their current size.

Fixes: #1173 (closed)

Merge request reports