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

[Romain Vimont]

On Thu, Aug 30, 2018 at 04:43:33PM +0300, Rémi Denis-Courmont wrote:
> 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.

 - vlc_vector_push() and vlc_vector_insert() automatically grow if
   necessary (of course);
 - vlc_vector_remove() and vlc_vector_remove_slice() automatically
   shrink when necessary.

The idea is that a caller need not care about growing/shrinking.

However, for advanced usage, a user wanting to manage growing/shrinking
manually should still be able to do it. For that purpose,
vlc_vector_reserve() allows to reserve in advance, and
vlc_vector_remove_noshrink() and vlc_vector_remove_slice_noshrink()
expose items removal without shrinking.

(Currently, ARRAY_REMOVE() also shrinks.)

> Also, please separate implementation and tests.

What do you mean?

Implementation is in include/vlc_vector.h.
Tests are in src/test/vector.c.

This is specific to vector though. It is sometimes useful to unit test
static functions (without making them non-static), in that case it is
convenient to put tests in the same file.