[vlc-devel] [RFC 1/1] vlc_vector: add helpers for vectors

[Rémi Denis-Courmont]

Le mercredi 29 août 2018, 23:28:20 EEST Romain Vimont a écrit :
> Add a new API for handling general-purpose vectors, intended to replace
> ARRAY_*.
> 
> Like ARRAY_*, it provides macros to handle a dynamic array generic
> over the type of its items.
> 
> Contrary to ARRAY_*:
>  - it does not abort on allocation failure (but reports the error);
>  - it uses size_t instead of int to store the capacity and the size;
>  - it checks for overflows on reallocation.
> 
> For illustration purpose, embedding a vector of input_item_t* in a
> struct looks like:
> 
>     struct playlist {
>         struct VLC_VECTOR(input_item_t *) items;
>         // ...
>     };
> 
> The main features (with names inspired by std::vector from C++ and
> std::vec::Vec from Rust) are:
>  - void vlc_vector_init(pv)
>       init the vector (use VLC_VECTOR_INITIALIZER for static init)
>  - void vlc_vector_clear(pv)
>       clear the vector, and release any associated resources
>  - vec.size
>       read the size of the vector
>  - vec.data[i]
>       access the i_th item
>  - bool vlc_vector_push(pv, item)
>       push an item at the end of the vector
>  - bool vlc_vector_insert(pv, index, item)
>       insert an item at index
>  - bool vlc_vector_insert_all(pv, index, items, count)
>       insert several items at index
>  - void vlc_vector_remove(pv, index)
>       remove an item
>  - void vlc_vector_remove_slice(pv, index, count)
>       remove a slice of items
>  - void vlc_vector_swap_remove(pv, index)
>       remove an item in O(1) without preserving ordering
>  - bool vlc_vector_reserve(pv, mincap)
>       increase the capacity of the vector in advance
>  - void vlc_vector_shrink_to_fit(pv)
>       resize the vector to its actual size
>  - void vlc_vector_index_of(pv, index, pidx)
>       find the index of an item (returns the result in *pidx)
>  - vlc_vector_foreach(item, pv)
>       a for-each loop
> 
> It uses an exponential growth policy for both increasing and decreasing
> the size. As a consequence, the amortized complexity of
> vlc_vector_push() is O(1).

This seems to imply that shrinking is automatic, but is it? Automatic 
shrinking seems contradictory with advance space reservation.

Also, please separate implementation and tests.


-- 
Rémi Denis-Courmont