[PATCH 15/21] dynarray: Reimplement with nicer semantics

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 06/19/2013 05:40 PM, Tanu Kaskinen wrote:
> A dynamic array is a nice simple container, but the old interface
> wasn't quite what I wanted it to be. I like GLib's way of providing
> the free callback at the container creation time, because that way
> the free callback doesn't have to be given every time something is
> removed from the array.
>
> The allocation pattern was changed too: instead of increasing the
> array size always by 25 when the array gets full, the size gets
> doubled now.

Not sure if you need this now that the node ownership stuff is changed, 
but anyway, it makes sense to have both (new_size = old_size * 2 + 25), 
both as an optimisation in the beginning, and especially so if 
n_allocated ever gets down to zero (I don't know if that can happen).

>
> The set of supported operations may seem a bit arbitrary. The
> operation set is by no means complete at this point. I have included
> only those operations that are required by the current code and some
> unpublished code of mine.
> ---
>   src/pulsecore/cli-command.c |  4 +--
>   src/pulsecore/dynarray.c    | 85 +++++++++++++++++++--------------------------
>   src/pulsecore/dynarray.h    | 49 +++++++++++++++-----------
>   src/pulsecore/tokenizer.c   |  8 +++--
>   4 files changed, 71 insertions(+), 75 deletions(-)
>
> diff --git a/src/pulsecore/cli-command.c b/src/pulsecore/cli-command.c
> index f5489d6..75d3c91 100644
> --- a/src/pulsecore/cli-command.c
> +++ b/src/pulsecore/cli-command.c
> @@ -1987,7 +1987,7 @@ int pa_cli_command_execute_line_stateful(pa_core *c, const char *s, pa_strbuf *b
>                               char **sorted_files;
>                               struct dirent *de;
>                               pa_bool_t failed = FALSE;
> -                            pa_dynarray *files = pa_dynarray_new();
> +                            pa_dynarray *files = pa_dynarray_new(NULL);
>
>                               while ((de = readdir(d))) {
>                                   char *extn;
> @@ -2007,7 +2007,7 @@ int pa_cli_command_execute_line_stateful(pa_core *c, const char *s, pa_strbuf *b
>                               sorted_files = pa_xnew(char*, count);
>                               for (i = 0; i < count; ++i)
>                                   sorted_files[i] = pa_dynarray_get(files, i);
> -                            pa_dynarray_free(files, NULL);
> +                            pa_dynarray_free(files);
>
>                               for (i = 0; i < count; ++i) {
>                                   for (unsigned j = 0; j < count; ++j) {
> diff --git a/src/pulsecore/dynarray.c b/src/pulsecore/dynarray.c
> index 78b2eb9..3927612 100644
> --- a/src/pulsecore/dynarray.c
> +++ b/src/pulsecore/dynarray.c
> @@ -31,82 +31,67 @@
>
>   #include "dynarray.h"
>
> -/* If the array becomes to small, increase its size by 25 entries */
> -#define INCREASE_BY 25
> -
>   struct pa_dynarray {
>       void **data;
>       unsigned n_allocated, n_entries;
> +    pa_free_cb_t free_cb;
>   };
>
> -pa_dynarray* pa_dynarray_new(void) {
> -    pa_dynarray *a;
> +pa_dynarray* pa_dynarray_new(pa_free_cb_t free_cb) {
> +    pa_dynarray *array;
>
> -    a = pa_xnew(pa_dynarray, 1);
> -    a->data = NULL;
> -    a->n_entries = 0;
> -    a->n_allocated = 0;
> +    array = pa_xnew0(pa_dynarray, 1);
> +    array->data = pa_xnew(void *, 1);
> +    array->n_allocated = 1;
> +    array->free_cb = free_cb;
>
> -    return a;
> +    return array;
>   }
>
> -void pa_dynarray_free(pa_dynarray *a, pa_free_cb_t free_func) {
> +void pa_dynarray_free(pa_dynarray *array) {
>       unsigned i;
> -    pa_assert(a);
> +    pa_assert(array);
>
> -    if (free_func)
> -        for (i = 0; i < a->n_entries; i++)
> -            if (a->data[i])
> -                free_func(a->data[i]);
> +    if (array->free_cb)
> +        for (i = 0; i < array->n_entries; i++)
> +            array->free_cb(array->data[i]);
>
> -    pa_xfree(a->data);
> -    pa_xfree(a);
> +    pa_xfree(array->data);
> +    pa_xfree(array);
>   }
>
> -void pa_dynarray_put(pa_dynarray*a, unsigned i, void *p) {
> -    pa_assert(a);
> -
> -    if (i >= a->n_allocated) {
> -        unsigned n;
> +void pa_dynarray_append(pa_dynarray *array, void *p) {
> +    pa_assert(array);
> +    pa_assert(p);
>
> -        if (!p)
> -            return;
> +    if (array->n_entries == array->n_allocated) {
> +        unsigned n = array->n_allocated * 2;
>
> -        n = i+INCREASE_BY;
> -        a->data = pa_xrealloc(a->data, sizeof(void*)*n);
> -        memset(a->data+a->n_allocated, 0, sizeof(void*)*(n-a->n_allocated));
> -        a->n_allocated = n;
> +        array->data = pa_xrealloc(array->data, sizeof(void *) * n);
> +        array->n_allocated = n;
>       }
>
> -    a->data[i] = p;
> -
> -    if (i >= a->n_entries)
> -        a->n_entries = i+1;
> +    array->data[array->n_entries++] = p;
>   }
>
> -unsigned pa_dynarray_append(pa_dynarray*a, void *p) {
> -    unsigned i;
> +void *pa_dynarray_get(pa_dynarray *array, unsigned i) {
> +    pa_assert(array);
> +    pa_assert(i < array->n_entries);
>
> -    pa_assert(a);
> -
> -    i = a->n_entries;
> -    pa_dynarray_put(a, i, p);
> -
> -    return i;
> +    return array->data[i];
>   }
>
> -void *pa_dynarray_get(pa_dynarray*a, unsigned i) {
> -    pa_assert(a);
> +void *pa_dynarray_steal_last(pa_dynarray *array) {
> +    pa_assert(array);
>
> -    if (i >= a->n_entries)
> +    if (array->n_entries > 0)
> +        return array->data[--array->n_entries];
> +    else
>           return NULL;
> -
> -    pa_assert(a->data);
> -    return a->data[i];
>   }
>
> -unsigned pa_dynarray_size(pa_dynarray*a) {
> -    pa_assert(a);
> +unsigned pa_dynarray_size(pa_dynarray *array) {
> +    pa_assert(array);
>
> -    return a->n_entries;
> +    return array->n_entries;
>   }
> diff --git a/src/pulsecore/dynarray.h b/src/pulsecore/dynarray.h
> index 70deebb..04dd2d2 100644
> --- a/src/pulsecore/dynarray.h
> +++ b/src/pulsecore/dynarray.h
> @@ -26,26 +26,33 @@
>
>   typedef struct pa_dynarray pa_dynarray;
>
> -/* Implementation of a simple dynamically sized array. The array
> - * expands if required, but doesn't shrink if possible. Memory
> - * management of the array's entries is the user's job. */
> -
> -pa_dynarray* pa_dynarray_new(void);
> -
> -/* Free the array calling the specified function for every entry in
> - * the array. The function may be NULL. */
> -void pa_dynarray_free(pa_dynarray *a, pa_free_cb_t free_func);
> -
> -/* Store p at position i in the array */
> -void pa_dynarray_put(pa_dynarray*a, unsigned i, void *p);
> -
> -/* Store p a the first free position in the array. Returns the index
> - * of that entry. If entries are removed from the array their position
> - * are not filled any more by this function. */
> -unsigned pa_dynarray_append(pa_dynarray*a, void *p);
> -
> -void *pa_dynarray_get(pa_dynarray*a, unsigned i);
> -
> -unsigned pa_dynarray_size(pa_dynarray*a);
> +/* Implementation of a simple dynamically sized array for storing pointers.
> + *
> + * When the array is created, a free callback can be provided, which will be
> + * then used when removing items from the array and when freeing the array. If
> + * the free callback is not provided, the memory management of the stored items
> + * is the responsibility of the array user. If there is need to remove items
> + * from the array without freeing them, while also having the free callback
> + * set, the functions with "steal" in their name can be used.
> + *
> + * Removing items from the middle of the array causes the subsequent items to
> + * be moved to fill the gap, so it's not efficient with large arrays. If the
> + * order of the array is not important, however, functions with "fast" in their
> + * name can be used, in which case the gap is filled by moving only the last
> + * item(s). XXX: Currently there are no functions with "fast" in their name,
> + * but such functions will be added if they are ever needed.
> + *
> + * The array doesn't support storing NULL pointers. */
> +
> +pa_dynarray* pa_dynarray_new(pa_free_cb_t free_cb);
> +void pa_dynarray_free(pa_dynarray *array);
> +
> +void pa_dynarray_append(pa_dynarray *array, void *p);
> +void *pa_dynarray_get(pa_dynarray *array, unsigned i);
> +
> +/* Returns the removed item, or NULL if the array is empty. */
> +void *pa_dynarray_steal_last(pa_dynarray *array);
> +
> +unsigned pa_dynarray_size(pa_dynarray *array);
>
>   #endif
> diff --git a/src/pulsecore/tokenizer.c b/src/pulsecore/tokenizer.c
> index cb682d6..4c610e8 100644
> --- a/src/pulsecore/tokenizer.c
> +++ b/src/pulsecore/tokenizer.c
> @@ -63,7 +63,7 @@ static void parse(pa_dynarray*a, const char *s, unsigned args) {
>   pa_tokenizer* pa_tokenizer_new(const char *s, unsigned args) {
>       pa_dynarray *a;
>
> -    a = pa_dynarray_new();
> +    a = pa_dynarray_new(pa_xfree);
>       parse(a, s, args);
>       return (pa_tokenizer*) a;
>   }
> @@ -72,12 +72,16 @@ void pa_tokenizer_free(pa_tokenizer *t) {
>       pa_dynarray *a = (pa_dynarray*) t;
>
>       pa_assert(a);
> -    pa_dynarray_free(a, pa_xfree);
> +    pa_dynarray_free(a);
>   }
>
>   const char *pa_tokenizer_get(pa_tokenizer *t, unsigned i) {
>       pa_dynarray *a = (pa_dynarray*) t;
>
>       pa_assert(a);
> +
> +    if (i >= pa_dynarray_size(a))
> +        return NULL;
> +
>       return pa_dynarray_get(a, i);
>   }
>



-- 
David Henningsson, Canonical Ltd.
https://launchpad.net/~diwic


[Index of Archives]     [Linux Audio Users]     [AMD Graphics]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux