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

[Rémi Denis-Courmont]

Le jeudi 19 juillet 2018, 18:57:18 EEST Romain Vimont a écrit :
> 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;

AFAICT, a new member is not really necessary.

If you allocated by power of two, it'd be easy to detect when to expand/shrink 
the allocation.

>      size_t i_count;
>      void ** pp_elems;
>  } vlc_array_t;
> 

-- 
Rémi Denis-Courmont