[FFmpeg-devel] [PATCH 1/4] lavu: add simple array implementation
Lukasz Marek
lukasz.m.luki at gmail.com
Tue Feb 25 01:06:06 CET 2014
todo: minor bump and update doc/APIChanges
Signed-off-by: Lukasz Marek <lukasz.m.luki at gmail.com>
---
libavutil/Makefile | 3 +
libavutil/array.c | 243 +++++++++++++++++++++++++++++++++++++++++++++++++++++
libavutil/array.h | 129 ++++++++++++++++++++++++++++
3 files changed, 375 insertions(+)
create mode 100644 libavutil/array.c
create mode 100644 libavutil/array.h
diff --git a/libavutil/Makefile b/libavutil/Makefile
index e4ee47c..373a30a 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -4,6 +4,7 @@ NAME = avutil
HEADERS = adler32.h \
aes.h \
+ array.h \
attributes.h \
audio_fifo.h \
audioconvert.h \
@@ -70,6 +71,7 @@ BUILT_HEADERS = avconfig.h \
OBJS = adler32.o \
aes.o \
+ array.o \
atomic.o \
audio_fifo.o \
avstring.o \
@@ -139,6 +141,7 @@ SKIPHEADERS-$(CONFIG_OPENCL) += opencl.h
TESTPROGS = adler32 \
aes \
+ array \
atomic \
avstring \
base64 \
diff --git a/libavutil/array.c b/libavutil/array.c
new file mode 100644
index 0000000..3484030
--- /dev/null
+++ b/libavutil/array.c
@@ -0,0 +1,243 @@
+/*
+ * Copyright (c) 2014 Lukasz Marek
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <string.h>
+#include "array.h"
+#include "mem.h"
+#include "avassert.h"
+
+AVArrayBuffer *av_array_alloc(uint32_t size, avarray_element_deleter deleter)
+{
+ AVArrayBuffer *array = av_mallocz(sizeof(AVArrayBuffer));
+ if (!array)
+ return NULL;
+ if (deleter)
+ array->deleter = deleter;
+ else
+ array->deleter = av_free;
+ array->size = size ? size : 1;
+ array->buffer = av_malloc(array->size * sizeof(void *));
+ if (!array->buffer) {
+ av_free(array);
+ return NULL;
+ }
+ return array;
+}
+
+void av_array_free(AVArrayBuffer **array)
+{
+ int i;
+ if (!array || !*array)
+ return;
+ for (i = 0; i < (*array)->pos; i++)
+ (*array)->deleter((*array)->buffer[i]);
+ av_free((*array)->buffer);
+ av_freep(array);
+}
+
+void av_array_release(AVArrayBuffer **array, void **data)
+{
+ if (data)
+ *data = NULL;
+ if (!array || !*array)
+ return;
+ if (data) {
+ *data = (*array)->buffer;
+ } else {
+ int i;
+ for (i = 0; i < (*array)->pos; i++)
+ (*array)->deleter((*array)->buffer[i]);
+ av_free((*array)->buffer);
+ }
+ av_freep(array);
+}
+
+int av_array_insert(AVArrayBuffer *array, uint32_t pos, void *data)
+{
+ if (!array)
+ return AVERROR(EINVAL);
+ if (pos > array->pos)
+ pos = array->pos;
+ if (array->pos == array->size) {
+ void *new_buff = av_realloc(array->buffer, array->size * 2 * sizeof(void *));
+ if (!new_buff)
+ return AVERROR(ENOMEM);
+ array->buffer = new_buff;
+ array->size *= 2;
+ }
+ if (pos != array->pos)
+ memmove(array->buffer + pos + 1, array->buffer + pos, (array->pos - pos) * sizeof(void *));
+ array->buffer[pos] = data;
+ array->pos++;
+ return pos;
+}
+
+int av_array_append(AVArrayBuffer *array, void *data)
+{
+ if (!array)
+ return AVERROR(EINVAL);
+ return av_array_insert(array, array->pos, data);
+}
+
+int av_array_prepend(AVArrayBuffer *array, void *data)
+{
+ return av_array_insert(array, 0, data);
+}
+
+int av_array_remove(AVArrayBuffer *array, uint32_t pos)
+{
+ if (!array || pos >= array->pos)
+ return AVERROR(EINVAL);
+ array->deleter(array->buffer[pos]);
+ memmove(array->buffer + pos, array->buffer + pos + 1, (array->pos - (pos + 1)) * sizeof(void *));
+ return --array->pos;
+}
+
+void *av_array_at(AVArrayBuffer *array, uint32_t pos)
+{
+ if (!array || !array->pos)
+ return NULL;
+ if (pos >= array->pos)
+ pos = array->pos - 1;
+ return array->buffer[pos];
+}
+
+uint32_t av_array_size(AVArrayBuffer *array)
+{
+ return array ? array->pos : 0;
+}
+
+uint32_t av_array_reserved(AVArrayBuffer *array)
+{
+ return array ? array->size : 0;
+}
+
+#ifdef TEST
+
+#define PRINTING 0
+
+static void print_array(AVArrayBuffer *array)
+{
+ int i, e, size;
+ size = av_array_size(array);
+ if (PRINTING)
+ printf("[\n");
+ for (i = 0; i < size; i++) {
+ e = *(int *)av_array_at(array, i);
+ if (PRINTING)
+ printf(" %d\n", e);
+ }
+ if (PRINTING)
+ printf("]\n");
+}
+
+static int insert_int(AVArrayBuffer *array, int i, int insert_type, int pos)
+{
+ int *el;
+ el = av_malloc(sizeof(int));
+ if (!el)
+ exit(0);
+ *el = i;
+ if (insert_type == 0)
+ return av_array_insert(array, pos, el);
+ else if (insert_type == 1)
+ return av_array_prepend(array, el);
+ else if (insert_type == 2)
+ return av_array_append(array, el);
+ return -1;
+}
+
+int main(int argc, char ** argv)
+{
+ int i, e;
+ AVArrayBuffer *array = NULL;
+ av_array_free(NULL);
+ av_array_free(&array);
+ av_array_release(NULL, NULL);
+ av_array_release(&array, NULL);
+
+ array = av_array_alloc(0, NULL);
+ if (!array)
+ return 0;
+
+ print_array(array);
+ av_assert0(av_array_size(array) == 0);
+ av_assert0(insert_int(array, 2, 0, 1000) == 0);
+ print_array(array);
+ av_assert0(av_array_size(array) == 1);
+ av_assert0(insert_int(array, 3, 0, 1) == 1);
+ print_array(array);
+ av_assert0(av_array_size(array) == 2);
+ av_assert0(insert_int(array, 1, 1, 0) == 0);
+ print_array(array);
+ av_assert0(av_array_size(array) == 3);
+ av_assert0(insert_int(array, 4, 2, 0) == 3);
+ print_array(array);
+ av_assert0(av_array_size(array) == 4);
+ av_assert0(av_array_reserved(array) == 4);
+
+ print_array(array);
+ for (i = 0; i < 4; i++) {
+ e = *(int *)av_array_at(array, i);
+ av_assert0(e == i + 1);
+ }
+ e = *(int *)av_array_at(array, 1000);
+ av_assert0(e == 4);
+
+ av_assert0(av_array_remove(array, 10000) < 0);
+ av_assert0(av_array_size(array) == 4);
+
+ av_assert0(av_array_remove(array, 0) == 3);
+ av_assert0(av_array_size(array) == 3);
+ print_array(array);
+ for (i = 0; i < 3; i++) {
+ e = *(int *)av_array_at(array, i);
+ av_assert0(e == i + 2);
+ }
+
+ av_assert0(av_array_remove(array, 1) == 2);
+ av_assert0(av_array_size(array) == 2);
+ print_array(array);
+ for (i = 0; i < 2; i++) {
+ e = *(int *)av_array_at(array, i);
+ av_assert0(e == (i + 1) * 2);
+ }
+
+ av_assert0(av_array_remove(array, 1) == 1);
+ av_assert0(av_array_size(array) == 1);
+ print_array(array);
+ e = *(int *)av_array_at(array, 0);
+ av_assert0(e == 2);
+
+ av_assert0(av_array_remove(array, 0) == 0);
+ av_assert0(av_array_size(array) == 0);
+ print_array(array);
+
+ av_assert0(insert_int(array, 2, 0, 1000) == 0);
+ av_assert0(insert_int(array, 3, 0, 1) == 1);
+ av_assert0(insert_int(array, 1, 1, 0) == 0);
+ av_assert0(insert_int(array, 4, 2, 0) == 3);
+
+ av_array_free(&array);
+ av_assert0(!array);
+
+ return 0;
+}
+#endif
diff --git a/libavutil/array.h b/libavutil/array.h
new file mode 100644
index 0000000..e13c209
--- /dev/null
+++ b/libavutil/array.h
@@ -0,0 +1,129 @@
+/*
+ * Copyright (c) 2014 Lukasz Marek
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_ARRAY_H
+#define AVUTIL_ARRAY_H
+
+#include <inttypes.h>
+
+/**
+ * callback called inside av_array_free() to free each element of the array.
+ */
+typedef void (*avarray_element_deleter)(void *element);
+
+typedef struct AVArrayBuffer {
+ void **buffer;
+ uint32_t size, pos;
+ avarray_element_deleter deleter;
+} AVArrayBuffer;
+
+/**
+ * Initialize an AVArrayBuffer.
+ *
+ * @param size initial size of the array.
+ * @param deleter callback called against each element of the array when
+ * av_array_free() is called. av_free() is used when NULL.
+ * @return AVArrayBuffer or NULL in case of memory allocation failure.
+ */
+AVArrayBuffer *av_array_alloc(uint32_t size, avarray_element_deleter deleter);
+
+/**
+ * Free AVArrayBuffer.
+ *
+ * @param array array to be freed.
+ */
+void av_array_free(AVArrayBuffer **array);
+
+/**
+ * Free AVArrayBuffer and pass internal data.
+ *
+ * @param array array to be freed.
+ * @param data user pointer to takeover array data.
+ */
+void av_array_release(AVArrayBuffer **array, void **data);
+
+/**
+ * Insert new element into array.
+ *
+ * @param array array which insert into.
+ * @param pos 0 based position of the new element. If pos is beyound the end
+ * of array then element is inserted at the end of the array.
+ * @param data new element to be inserted.
+ * @return real position of the inserted element or negative on error.
+ */
+int av_array_insert(AVArrayBuffer *array, uint32_t pos, void *data);
+
+/**
+ * Append new element at the end of the array.
+ *
+ * @param array array which insert into.
+ * @param data new element to be inserted.
+ * @return real position of the inserted element or negative on error.
+ */
+int av_array_append(AVArrayBuffer *array, void *data);
+
+/**
+ * Prepend new element at the beginning of the array.
+ *
+ * @param array array which insert into.
+ * @param data new element to be inserted.
+ * @return 0 on success, negative otherwise.
+ */
+int av_array_prepend(AVArrayBuffer *array, void *data);
+
+/**
+ * Remove element from the array.
+ *
+ * @param array array which remove from.
+ * @param data position of the element to be removed.
+ * @return new size of the array or negative on error.
+ */
+int av_array_remove(AVArrayBuffer *array, uint32_t pos);
+
+/**
+ * Return element from the array.
+ *
+ * @param array array to get element from.
+ * @param pos position of the element. If pos is beyound the end of array
+ * then last element is returned.
+ * @return element at specified position or NULL on error.
+ */
+void *av_array_at(AVArrayBuffer *array, uint32_t pos);
+
+/**
+ * Return number of elements in the array.
+ *
+ * @param array array which elements should be counted.
+ * @return number of the elements in the array.
+ */
+uint32_t av_array_size(AVArrayBuffer *array);
+
+/**
+ * Return number of reserved elements.
+ *
+ * Inserting elements until reserved elements space is reached guarantees no
+ * reallocation.
+ *
+ * @param array array which elements should be counted.
+ * @return number of reserved elements.
+ */
+uint32_t av_array_reserved(AVArrayBuffer *array);
+
+#endif /* AVUTIL_ARRAY_H */
--
1.8.3.2
More information about the ffmpeg-devel
mailing list