[vlc-devel] [RFC 3/3] vlc_arrays: append items in amortized O(1)

[Steve Lhomme]

On 20/07/2018 11:24, Romain Vimont wrote:
> Thank you for your review.
>
> On Fri, Jul 20, 2018 at 10:46:42AM +0200, Filip Roséen wrote:
>> Hi Romain,
>>
>> I recommend adding documentation for the newly introduced functions,
>> as we will never have a good documentation of the codebase if we keep
>> adding things without writing some for them.
> Absolutely.
>
>> There are a ton of entities without documentation, but let's walk
>> towards documenting everything, and not away from it.
>>
>> On 2018-07-19 17:57, Romain Vimont wrote:
>>
>>> Use exponential growth to append items in _amortized constant time_,
>>> instead of realloc() on every append/remove.
>>>
>>> The strategy is similar to the one used by ARRAY_* macros (and C++
>>> std::vector, Java ArrayList, Rust std::vec, etc.).
>>>
>>> Also expose vlc_array_reserve() to avoid unnecessary reallocations, and
>>> vlc_array_shrink_to_fit() to give a better control on the array size.
>>> ---
>>>   include/vlc_arrays.h | 107 +++++++++++++++++++++------
>>>   include/vlc_common.h |   9 ++-
>>>   src/test/arrays.c    | 168 ++++++++++++++++++++++++++++++++++++++++++-
>>>   3 files changed, 259 insertions(+), 25 deletions(-)
>>>
>>> diff --git a/include/vlc_arrays.h b/include/vlc_arrays.h
>>> index ce2936f1452..ce22c2e1a92 100644
>>> --- a/include/vlc_arrays.h
>>> +++ b/include/vlc_arrays.h
>>> @@ -25,6 +25,9 @@
>>>   #ifndef VLC_ARRAYS_H_
>>>   #define VLC_ARRAYS_H_
>>>   
>>> +#include <vlc_common.h>
>>> +#include <assert.h>
>>> +
>>>   /**
>>>    * \file
>>>    * This file defines functions, structures and macros for handling arrays in vlc
>>> @@ -257,12 +260,16 @@ static inline void *realloc_or_free( void *p, size_t sz )
>>>    ************************************************************************/
>>>   typedef struct vlc_array_t
>>>   {
>>> +    size_t i_capacity;
>>>       size_t i_count;
>>>       void ** pp_elems;
>>>   } vlc_array_t;
>> If one is to be pedantic you should order the data-members in
>> likelihood of being read, to prevent cache-misses. It's an extremely
>> minor thing so probably not worth changing though.
>>
>>>   
>>> +#define VLC_ARRAY_MAX_LENGTH (SIZE_MAX / sizeof(void *))
>>> +
>>>   static inline void vlc_array_init( vlc_array_t * p_array )
>>>   {
>>> +    p_array->i_capacity = 0;
>>>       p_array->i_count = 0;
>>>       p_array->pp_elems = NULL;
>>>   }
>>> @@ -308,21 +315,75 @@ static inline ssize_t vlc_array_find( const vlc_array_t *ar,
>>>       return -1;
>> Use `VLC_EGENERIC`, `VLC_ENOMEM`, and `VLC_SUCCESS` (this applies to
>> every `return` introduced in this commit. I know the file currently
>> uses `0` and `-1` do denote *success* vs *error*, so you could take
>> some extra time and fix those too (in a separate commit, probably
>> before you start adding new things).
> OK.

I disagree. VLC_Exxx and VLC_SUCCESS are for functions and even VLC_API 
functions that return an int.

Here we return an invalid array index which may have its own define but 
is not an error code. But maybe I misread because the -1 is not even 
from this commit.