• Rémi Denis-Courmont's avatar
    playlist: use search trees for ID and input to item mapping · f2a68559
    Rémi Denis-Courmont authored
    Regarding input item look-ups, this reduces asymptotic complexity from
    linear to logarithmic time.
    
    Regarding ID look-ups, this reduces insertion and deletion time to
    logarithmic. Previously it degraded to linear time because of memcpy()
    and memmove() in ARRAY_APPEND and ARRAY_REMOVE macros.
    
    This removes the "all_items" array, and its missing error handlers.
    
    Finally, this adds support for allocating more than INT_MAX items
    during the entire lifetime of the VLC instance. (The maximum number of
    _concurrent_ items is still INT_MAX, but memory would probably run out
    before that is reached.)
    
    Note: Item deletion still requires linear time. And playlist deletion
    still consequently requires quadractic time because of the "current"
    array.
    f2a68559
search.c 4.69 KB