[FFmpeg-devel] [PATCH 1/4] lavu: add simple array implementation
Nicolas George
george at nsup.org
Wed Feb 26 12:19:25 CET 2014
Le septidi 7 ventôse, an CCXXII, Lukasz Marek a écrit :
> 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;
Any reason to use a different construct for the same idiom?
> + array->buffer = av_malloc(array->size * sizeof(void *));
Missing check for integer overflow. To avoid risks, maybe init to NULL. You
can do both at once using calloc().
> + 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 *));
Missing integer overflow check.
> + 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);
A type name in all lowercase seems rather unusual in the av* API.
Also, a user-provided callback without a slot for an extra arbitrary
argument is often annoying.
> +
> +typedef struct AVArrayBuffer {
> + void **buffer;
> + uint32_t size, pos;
A particular reason to use uint32_t there? IMHO, size_t or plain unsigned
would be better.
> + 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.
IMHO, returning the AVERROR code and returning the array through a pointer
is more convenient: you do not need to hard-code AVERROR(ENOMEM) in all
calling code.
Also, any reason not to handle elements of arbitrary size?
> + */
> +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);
These function need to have their algorithmic complexity documented.
> +
> +/**
> + * 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 */
On the whole, I am very dubious with this API.
First, there are already several parts of array implementations in the code,
each with various pros and cons. Adding a new one will only make matter
worse. See av_dynarray_add() and av_dynarray2_add(): they both are
interesting, but IIRC they have flaw that prevent them to be used in a
generic case. Fixing them seems like a better idea.
Second, I do not like the insert/append/prepend stuff, and the av_array_at()
function even worse. To set the value of an array cell, you write tab[42] =
1729. The insert/append/prepend/at stuff is the kind of thing you find in
the ultra-generic abstract java classes. So really, you would just need a
single function that ensures a cell is free.
So really, for now my advice would be to imitate the av_dynarray[2] API but
making sure it is usable in more cases.
Regards,
--
Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20140226/0792f086/attachment.asc>
More information about the ffmpeg-devel
mailing list