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

[Steve Lhomme]

I think there should be a commit before this one with adding the test 
(with the preexisting API) and then adding more tests with the new API 
if there's any.

On 19/07/2018 17:57, Romain Vimont wrote:
> +
>   /*****************************************************************************
>    * I18n stuff
>    *****************************************************************************/
> @@ -1180,6 +1184,7 @@ VLC_API const char * VLC_Compiler( void ) VLC_USED;
>   /*****************************************************************************
>    * Additional vlc stuff
>    *****************************************************************************/
> +#include "vlc_arrays.h"
>   #include "vlc_messages.h"
>   #include "vlc_objects.h"
>   #include "vlc_variables.h"
> diff --git a/src/test/arrays.c b/src/test/arrays.c
> index 82277bbbc12..b7f5b829bd4 100644
> --- a/src/test/arrays.c
> +++ b/src/test/arrays.c
> @@ -1,5 +1,5 @@
>   /*****************************************************************************
> - * arrays.h : Test for ARRAY_* macros
> + * arrays.h : Test for VLC arrays
>    *****************************************************************************
>    * Copyright (C) 2018 VLC authors and VideoLAN
>    *
> @@ -158,10 +158,176 @@ static void test_array_bsearch(void)
>       ARRAY_RESET(array);
>   }
>   
> +static void test_vlc_array_insert_remove(void)
> +{
> +    vlc_array_t array;
> +    vlc_array_init(&array);
> +
> +    char data[32];
> +
> +    vlc_array_append(&array, &data[0]);
> +    assert(vlc_array_count(&array) == 1);
> +    assert(vlc_array_get(&array, 0) == &data[0]);
> +
> +    vlc_array_remove(&array, 0);
> +    assert(vlc_array_count(&array) == 0);
> +
> +    vlc_array_append(&array, &data[1]);
> +    vlc_array_append(&array, &data[2]);
> +    vlc_array_append(&array, &data[3]);
> +    vlc_array_remove(&array, 1);
> +    assert(vlc_array_count(&array) == 2);
> +    assert(vlc_array_get(&array, 0) == &data[1]);
> +    assert(vlc_array_get(&array, 1) == &data[3]);
> +
> +    vlc_array_insert(&array, &data[4], 1);
> +    assert(vlc_array_count(&array) == 3);
> +    assert(vlc_array_get(&array, 0) == &data[1]);
> +    assert(vlc_array_get(&array, 1) == &data[4]);
> +    assert(vlc_array_get(&array, 2) == &data[3]);
> +
> +    vlc_array_clear(&array);
> +}
> +
> +static void test_vlc_array_find(void)
> +{
> +    vlc_array_t array;
> +    vlc_array_init(&array);
> +
> +    char data[10];
> +
> +    for (int i = 0; i < 10; ++i)
> +        vlc_array_append(&array, &data[i]);
> +
> +    ssize_t idx;
> +
> +    idx = vlc_array_find(&array, &data[0]);
> +    assert(idx == 0);
> +
> +    idx = vlc_array_find(&array, &data[1]);
> +    assert(idx == 1);
> +
> +    idx = vlc_array_find(&array, &data[4]);
> +    assert(idx == 4);
> +
> +    idx = vlc_array_find(&array, &data[9]);
> +    assert(idx == 9);
> +
> +    idx = vlc_array_find(&array, "some other pointer");
> +    assert(idx == -1);
> +
> +    vlc_array_clear(&array);
> +}
> +
> +static void test_vlc_array_grow()
> +{
> +    vlc_array_t array;
> +    vlc_array_init(&array);
> +
> +    char data;
> +
> +    for (int i = 0; i < 50; ++i)
> +        vlc_array_append(&array, &data); /* append */
> +
> +    assert(vlc_array_count(&array) == 50);
> +
> +    for (int i = 0; i < 25; ++i)
> +        vlc_array_insert(&array, &data, 20); /* insert from the middle */
> +
> +    assert(vlc_array_count(&array) == 75);
> +
> +    for (int i = 0; i < 25; ++i)
> +        vlc_array_insert(&array, &data, 0); /* prepend */
> +
> +    assert(vlc_array_count(&array) == 100);
> +
> +    for (int i = 0; i < 50; ++i)
> +        vlc_array_remove(&array, 20); /* remove from the middle */
> +
> +    assert(vlc_array_count(&array) == 50);
> +
> +    for (int i = 0; i < 25; ++i)
> +        vlc_array_remove(&array, 0); /* remove from the head */
> +
> +    assert(vlc_array_count(&array) == 25);
> +
> +    for (int i = 24; i >= 0; --i)
> +        vlc_array_remove(&array, i); /* remove from the tail */
> +
> +    assert(vlc_array_count(&array) == 0);
> +
> +    vlc_array_clear(&array);
> +}
> +
> +static void test_vlc_array_exp_growth()
> +{
> +    vlc_array_t array;
> +    vlc_array_init(&array);
> +
> +    char data;
> +    size_t old_capacity = array.i_capacity;
> +    int realloc_count = 0;
> +    for (int i = 0; i < 10000; ++i)
> +    {
> +        vlc_array_append(&array, &data);
> +        if (array.i_capacity != old_capacity)
> +        {
> +            realloc_count++;
> +            old_capacity = array.i_capacity;
> +        }
> +    }
> +
> +    /* Test specifically for an expected growth factor of 1.5. In practice, the
> +     * result is even lower (19) due to the first alloc of size 10 */
> +    assert(realloc_count <= 23); /* ln(10000) / ln(1.5) ~= 23 */
> +
> +    realloc_count = 0;
> +    for (int i = 9999; i >= 0; --i)
> +    {
> +        vlc_array_remove(&array, i);
> +        if (array.i_capacity != old_capacity)
> +        {
> +            realloc_count++;
> +            old_capacity = array.i_capacity;
> +        }
> +    }
> +
> +    /* Same expectation for removals */
> +    assert(realloc_count <= 23);
> +
> +    vlc_array_clear(&array);
> +}
> +
> +static void test_vlc_array_reserve()
> +{
> +    vlc_array_t array;
> +    vlc_array_init(&array);
> +
> +    vlc_array_reserve(&array, 800);
> +    assert(array.i_capacity >= 800);
> +
> +    size_t initial_capacity = array.i_capacity;
> +
> +    char data;
> +    for (int i = 0; i < 800; ++i)
> +    {
> +        vlc_array_append(&array, &data);
> +        assert(array.i_capacity == initial_capacity); /* no realloc */
> +    }
> +
> +    vlc_array_clear(&array);
> +}
> +
>   int main(void)
>   {
>       test_array_insert_remove();
>       test_array_foreach();
>       test_array_find();
>       test_array_bsearch();
> +
> +    test_vlc_array_insert_remove();
> +    test_vlc_array_find();
> +    test_vlc_array_grow();
> +    test_vlc_array_reserve();
> +    test_vlc_array_exp_growth();
>   }
> -- 
> 2.18.0
>
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel