[vlc-devel] [RFC 0/3] Improving vlc_array_t

[Romain Vimont]

On Fri, Jul 20, 2018 at 01:44:25PM +0300, Rémi Denis-Courmont wrote:
> Le jeudi 19 juillet 2018, 18:57:15 EEST Romain Vimont a écrit :
> > There are 3 arrays API in vlc_arrays.h:
> >  1. TAB_* macros
> >  2. ARRAY_* macros
> >  3. vlc_array_t + functions
> > 
> > When we want a dynamic array of pointers, the vlc_array_t seems more
> > appropriate.
> 
> The benefit of the TAB_* macros is that they are type-agnostic. vlc_array_t 
> does not accomodate all the TAB_* use cases, and even when it does, it 
> sacrifices type-safety.
> 
> That is not to say that TAB_* is good. Not only it lacks error handling as you 
> noted, but in many cases, another structure, e.g. singly linked list, doubly 
> linked list, or binary tree would work better than an array.
> 
> > Moreover, the macro versions abort() on allocation failure.
> 
> Yes but vlc_array_t comes with its own issues, such as type safety. And 
> handling arrays manually is often easy enough that we have a lot of hand-coded 
> type-safe _and_ error-safe implementation (not only from me).

In short, they all have benefits and drawbacks. We agree.

> > To make it more user-friendly, I suggest to rename:
> >  - vlc_array_item_at_index() by vlc_array_get() (patch 1)
> >  - vlc_array_index_of_item() by vlc_array_find() (patch 2)
> 
> TBH, if you need to look-up an item by index, you are probably using the wrong 
> data structure. Binary tree is probably better suited (logarithmic time). Or 
> if the lookup is only for random deletion, then doubly linked list is probably 
> even better suited (constant time).

It depends. For example, if you often use random access in O(1), and
rarely need to find an item, it may be appropriate. There are often
trade-offs depending on the specific case.

But at least the basic structures and common functions must be exposed,
so that we can choose what is more appropriate.

> > To make it more general (suitable for more cases), I suggest to change
> > its growth strategy so that we can append items in amortized constant
> > time (similar to what ARRAY_* macros use, or, FWIW, C++ std::vector,
> > Java ArrayList, Rust std::vec, etc.). (patch 3)
> 
> For potential large datasets, we already have trees supporting logarithmic 
> time for insertion, look-up, replacement and deletion, and linear time for 
> enumeration.
> 
> All that with only bound object sizes.
> 
> So I'm really unconvinced that we should push vlc_array_t.

IIUC, you are saying that since there are trees, we don't need vectors?