On 06/26/2013 03:13 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. Instead of starting with zero allocated size, the initial
> allocated size is now 25.
>
> The array can't store NULL pointers anymore, and pa_dynarray_get() was
> changed so that it's forbidden to try to access elements outside the
> valid range.
>
> 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, 72 insertions(+), 74 deletions(-)
>
> diff --git a/src/pulsecore/cli-command.c b/src/pulsecore/cli-command.c
> index 866cd16..6644d64 100644
> --- a/src/pulsecore/cli-command.c
> +++ b/src/pulsecore/cli-command.c
> @@ -1983,7 +1983,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;
> @@ -2003,7 +2003,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..008f8d3 100644
> --- a/src/pulsecore/dynarray.c
> +++ b/src/pulsecore/dynarray.c
> @@ -31,82 +31,69 @@
>
> #include "dynarray.h"
>
> -/* If the array becomes to small, increase its size by 25 entries */
> -#define INCREASE_BY 25
> +#define MIN_N_ALLOCATED 25U
>
> 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 *, MIN_N_ALLOCATED);
> + array->n_allocated = MIN_N_ALLOCATED;
With the MAX change below, we should probably default to an empty array
like it was done previously - it could save some memory if we have many
empty arrays.
If you agree, feel free to push with that change.
> + 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);
> +void pa_dynarray_append(pa_dynarray *array, void *p) {
> + pa_assert(array);
> + pa_assert(p);
>
> - if (i >= a->n_allocated) {
> - unsigned n;
> + if (array->n_entries == array->n_allocated) {
> + unsigned n = PA_MAX(array->n_allocated * 2, MIN_N_ALLOCATED);
>
> - if (!p)
> - return;
> -
> - 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;
> -
> - pa_assert(a);
> -
> - i = a->n_entries;
> - pa_dynarray_put(a, i, p);
> +void *pa_dynarray_get(pa_dynarray *array, unsigned i) {
> + pa_assert(array);
> + pa_assert(i < array->n_entries);
>
> - 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
