about summary refs log tree commit diff
path: root/arch
diff options
context:
space:
mode:
authorRich Felker <dalias@aerifal.cx>2015-12-20 00:32:46 -0500
committerRich Felker <dalias@aerifal.cx>2015-12-20 00:39:35 -0500
commitc673158d91ad995ed59dd910777cd6464f61fe8e (patch)
treebaa67ca39d97308ed68f453a8c1186dc1ea14302 /arch
parentd87f0a9a95f0a1228ee5579e5822a8c93bc96823 (diff)
downloadmusl-c673158d91ad995ed59dd910777cd6464f61fe8e.tar.gz
musl-c673158d91ad995ed59dd910777cd6464f61fe8e.tar.xz
musl-c673158d91ad995ed59dd910777cd6464f61fe8e.zip
fix overly pessimistic realloc strategy in getdelim
previously, getdelim was allocating twice the space needed every time
it expanded its buffer to implement exponential buffer growth (in
order to avoid quadratic run time). however, this doubling was
performed even when the final buffer length needed was already known,
which is the common case that occurs whenever the delimiter is in the
FILE's buffer.

this patch makes two changes to remedy the situation:

1. over-allocation is no longer performed if the delimiter has already
been found when realloc is needed.

2. growth factor is reduced from 2x to 1.5x to reduce the relative
excess allocation in cases where the delimiter is not initially in the
buffer, including unbuffered streams.

in theory these changes could lead to quadratic time if the same
buffer is reused to process a sequence of lines successively
increasing in length, but once this length exceeds the stdio buffer
size, the delimiter will not be found in the buffer right away and
exponential growth will still kick in.
Diffstat (limited to 'arch')
0 files changed, 0 insertions, 0 deletions