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

[Thomas Guillem]

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.

> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel