[vlc-devel] [RFC 3/3] vlc_arrays: append items in amortized O(1)
robux4 at ycbcr.xyz
Fri Jul 20 13:54:24 CEST 2018
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.
>> 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).
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.
More information about the vlc-devel