[vlc-devel] [RFC 0/3] Improving vlc_array_t
remi at remlab.net
Fri Jul 20 12:44:25 CEST 2018
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
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
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
All that with only bound object sizes.
So I'm really unconvinced that we should push vlc_array_t.
More information about the vlc-devel