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

[Romain Vimont]

On Thu, Aug 30, 2018 at 04:10:08PM +0200, Thomas Guillem wrote:
> 
> 
> On Thu, Aug 30, 2018, at 16:05, Romain Vimont wrote:
> > 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.
> 
> I think Rémi meant separate commit for implementation and test.

Ah ok! Sorry, I didn't get it.

However, I thought it was a good practice to include tests in the same
commit as the implementation.

<https://stackoverflow.com/questions/6228550/should-change-to-code-be-committed-separately-from-corresonding-change-to-test-s>

What do you think?