• R
    fix overly pessimistic realloc strategy in getdelim · c673158d
    Rich Felker 提交于
    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.
    c673158d
getdelim.c 1.1 KB