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

[Rémi Denis-Courmont]

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).

> 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).

> 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.

-- 
Rémi Denis-Courmont