[pulseaudio-discuss] [PATCH] dynarray: Reimplement with nicer semantics
Tanu Kaskinen
tanu.kaskinen at linux.intel.com
Wed Jun 26 06:13:47 PDT 2013
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;
+ 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);
}
--
1.8.1.2
More information about the pulseaudio-discuss
mailing list