FFmpeg中FF_DYNARRAY_ADD向动态数组中追加元素分析

想动态数组中增加元素的实现是一类常见的需求，但是在C99之前并不存在动态数组一说，都是需要预先设置好内存空间，然后再设定好的空间内操作数组，但是FFmpeg中早就已经实现了动态数组的操作相关的函数，下面看一下相关的最底层的定义：

/**
 * Add an element to a dynamic array.
 *
 * The array is reallocated when its number of elements reaches powers of 2.
 * Therefore, the amortized cost of adding an element is constant.
 *
 * In case of success, the pointer to the array is updated in order to
 * point to the new grown array, and the size is incremented.
 *
 * @param av_size_max  maximum size of the array, usually the MAX macro of
 *                     the type of the size
 * @param av_elt_size  size of the elements in the array, in bytes
 * @param av_array     pointer to the array, must be a lvalue
 * @param av_size      size of the array, must be an integer lvalue
 * @param av_success   statement to execute on success; at this point, the
 *                     size variable is not yet incremented
 * @param av_failure   statement to execute on failure; if this happens, the
 *                     array and size are not changed; the statement can end
 *                     with a return or a goto
 */
#define FF_DYNARRAY_ADD(av_size_max, av_elt_size, av_array, av_size, \
                        av_success, av_failure) \
do { \
    size_t av_size_new = (av_size); \
    if (!((av_size) & ((av_size) - 1))) { \
        av_size_new = (av_size) ? (av_size) << 1 : 1; \
        if (av_size_new > (av_size_max) / (av_elt_size)) { \
            av_size_new = 0; \
        } else { \
            void *av_array_new = \
                av_realloc((av_array), av_size_new * (av_elt_size)); \
            if (!av_array_new) \
                av_size_new = 0; \
            else \
                (av_array) = av_array_new; \
        } \
    } \
    if (av_size_new) { \
        { av_success } \
        (av_size)++; \
    } else { \
        av_failure \
    } \
} while (0)

从这段预处理的宏定义中可以看到，这个FF_DYNARRAY_ADD主要需要用到6个表达式，其中第一个是目标数组的最大值，通常是INT_MAX，第二个是将要插入到动态数组中的新成员元素，也就是表达式里面的av_elt_size，例如插入的是一个字符，那就是sizeof(char),如果插入的是一个字符串，那就是sizeof(*str)，如果插入的是一个结构体，那就是sizeof(struct xxx)，第3个是将要插入的目标动态数组，第4个是目标动态数组当前的大小，第5个是插入成功的表达式，第6个是插入失败的表达式。

单纯只看这么一个宏定义对立面的内容理解起来想像比较难受，那么就看一个函数定义的示例：

void av_dynarray_add(void *tab_ptr, int *nb_ptr, void *elem)
{
    void **tab;
    memcpy(&tab, tab_ptr, sizeof(tab));
    FF_DYNARRAY_ADD(INT_MAX, sizeof(*tab), tab, *nb_ptr, {
        tab[*nb_ptr] = elem;
// 这个就是那个目标数组，扩容后申请的内存放到了tab[*nb_ptr]中，扩容就完成了。
        memcpy(tab_ptr, &tab, sizeof(tab));
    }, {
        *nb_ptr = 0;
        av_freep(tab_ptr);
    });
}

套上这个例子看起来就简单一些了：

    1. av_dynarray_add包含三个参数：数组当前的首地址；将要插入的新元素的个数；将要插入的新成员

    2. 首先将数组保存到一个抽象的二维数组中，主要是为了后面申请新内存的时候放到这个里面进行指向操作，把地址保存好

    3. 然后开始执行FF_DYNARRAY_ADD操作

将这个分析好的表达式套用到FF_DYNARRAY_ADD里面

对应的6个表达式分别是：

    1. INT_MAX

    2. sizeof(*tab)

    3. tab

    4. *nb_ptr

    5.  是一个代码片段：

 {
    tab[*nb_ptr] = elem;
    memcpy(tab_ptr, &tab, sizeof(tab));
  }

{
    *nb_ptr = 0;
    av_freep(tab_ptr);
 }

套到宏定义里面：对应的实现是从do { \开始到while(0)结束，那么可以仔细阅读以下这一段代码：

    1. 先生声明一个临时的目标数组的大小值的暂存变量，并将目标数组当前大小值存在该变量中av_size_new；那么也就是*nb_ptr这个值临时存到av_size_new

    2. 如果*nb_ptr为1，那么(av_size) – 1就为0，if (!((av_size) & ((av_size) – 1))) 条件也就成立,当然，如果*nb_ptr为0，那么条件就不成立了因为(av_size) – 1)为负数了

    3. 因为前面条件成立，所以开始了在数组中添加新元素的操作，主要是乘以2操作，

    4. 然后是新分配内存，大小就是前面计算过的那个av_size_new

    5. 当然，如果前面操作是成功的，就会执行成功的那一片段，也就是：

{
    tab[*nb_ptr] = elem;
    memcpy(tab_ptr, &tab, sizeof(tab));
}

   内这局执行完之后内存新的元素也就被加入到动态数组中了。

    6. 前面提到过各种失败，均是av_size_new为0，那么就会执行片段：

{
    *nb_ptr = 0;
    av_freep(tab_ptr);
 }

这段代码分析完了，如果想深入学习一下的话，可以参考libavformat/hls.c，将对应的值带入进行详细验证，理解会更深入。

作者：悟空；公众号：流媒体技术