• zc_arraylist的设计思想
  • zc_arraylist数据结构
  • zc_arraylist接口
• zc_arraylist实现
  • 构造和析构
  • 插入、更新元素 + 扩容
  • 尾部添加元素
  • 有序添加元素
• 知识点
  • calloc, realloc

zc_arraylist的设计思想

zc_arraylist数据结构

C++中有vector来表示动态列表（数组），C中如何实现呢？

通常，我们用这样一个数据结构，来表示一个动态列表：

typedef struct {
    int *array;   /* 数组指针 */
    int len;      /* 长度 */
    int capacity; /* 容量 */
} arraylist_t;

上面这个数据结构很常见，但存在一个缺点：array元素类型固定为int，无法适应其他数据类型，比如char/float，甚至其他结构体。

如何解决这个问题？
zlog提供一种通用的动态列表zc_arraylist。先来看看其数据结构：

#define ARRAY_LIST_DEFAULT_SIZE 32   /* arraylist 初始默认大小 */

typedef void (*zc_arraylist_del_fn) (void *data);
typedef int  (*zc_arraylist_cmp_fn) (void *data1, void *data2);

typedef struct {
    void **array; /* every element, a void* pointer, indicates an object */
    int len;      /* number of element */
    int size;     /* capacity */
    zc_arraylist_del_fn del; /* delete element object */
} zc_arraylist_t;

array不再是某个固定类型的指针，而是void**，也就是说array[0..size-1]每个元素都是一个void*，可以指向任意类型数据。

注意到结构体提供了del成员，用于delete元素对象，但没有提供new成员创建元素对象。也就是说，元素的创建工作由调用者完成；元素的释放工作由zc_arraylist完成。

zc_arraylist接口

提供基本的创建对象、释放对象，添加、有序添加元素的接口。另外，zc_arraylist提供了一个十分特殊的接口zc_arraylist_set，设置列表的索引i位置元素，如果溢出现有数据边界，就会自动扩容；如果没有越界，就会先释放原有元素，然后指向新传入的元素。

注意到zc_arraylist并没有提供remove/erase之类的接口用于移除元素，原因可能有2：
1）因为zlog是一个专用日志库，而非标准库，内部对zc_arraylist没有单个删除元素需求；
2）动态列表删除元素效率很低；

/* 创建一个zc_arraylist_t对象 */
zc_arraylist_t *zc_arraylist_new(zc_arraylist_del_fn del);
/* 释放一个zc_arraylist_t对象 */
void zc_arraylist_del(zc_arraylist_t *a_list);

/* 设置a_list的第i个元素指向data, 相当于a_list[i] = data */
int zc_arraylist_set(zc_arraylist_t *a_list, int i, void *data);
/* 往a_list末尾添加一个元素data, 相当于a_list[a_list->len] = data */
int zc_arraylist_add(zc_arraylist_t *a_list, void *data);
/* 用直接插入排序, 向a_list插入一个元素data, 保持原有的(非递减)顺序 */
int zc_arraylist_sortadd(zc_arraylist_t *a_list, zc_arraylist_cmp_fn cmp,
        void *data);

/* 获取a_list元素个数, 相当于a_list->len */
#define zc_arraylist_len(a_list) (a_list->len)

/* 获取a_list的第i个元素, 相当于a_list[i] */
#define zc_arraylist_get(a_list, i) \
    ((i >= a_list->len) ? NULL : a_list->array[i])

/* 遍历a_list */
#define zc_arraylist_foreach(a_list, i, a_unit) \
    for (i = 0, a_unit = a_list->array[0]; (i < a_list->len) && (a_unit = a_list->array[i], 1); i++)

zc_arraylist实现

构造和析构

一个对象的构造和析构，往往是成对的，我将它们放到一起来分析。前面提到过，zc_arraylist的array是void**类型，每个元素array[i]都是指向一个void*类型对象。

zc_arraylist 初始容量ARRAY_LIST_DEFAULT_SIZE（32）。

/* 构造一个zc_arraylist_t对象, del指定元素的释放函数 */
zc_arraylist_t *zc_arraylist_new(zc_arraylist_del_fn del)
{
    zc_arraylist_t *a_list;
   
    // calloc = malloc + bzero
    a_list = (zc_arraylist_t *) calloc(1, sizeof(zc_arraylist_t));
    if (!a_list) {
        zc_error("calloc fail, errno[%d]", errno);
        return NULL;
    }

    a_list->size = ARRAY_LIST_DEFAULT_SIZE; /* 初始容量*/
    a_list->len = 0; /* 初始元素个数 */

    /* this could be NULL */
    a_list->del = del;
    a_list->array = (void**) calloc(a_list->size, sizeof(void *));
    if (!a_list->array) {
        zc_error("calloc fail, errno[%d]", errno);
        free(a_list);
        return NULL;
    }

    return a_list;
}

/* 析构一个zc_arraylist_t对象 */
void zc_arraylist_del(zc_arraylist_t *a_list)
{
    if (!a_list) return;

    if (a_list->del) {
        int i;
        // 遍历array, 回调元素的删除函数
        /* delete all elements of array */
        for (i = 0; i < a_list->len; i++) {
            if (a_list->array[i])
                a_list->del(a_list->array[i]);
        }
    }

    /* delete array */
    if (a_list->array)
        free(a_list->array);
    free(a_list);
}

为何构造时，需要提供元素的删除函数（释放函数del）？
因为，zc_arraylist不知道array[i]实际指向何种对象，更不知道如何释放，因为这是调用者才知道的事情，因此由调用者提供元素的释放函数del，在必要的时候（如析构zc_arraylist），由zc_arraylist进行回调以释放元素，以免未及时释放造成内存泄露。

注意：
1）zc_arraylist并没有为每个元素都提供一个删除函数，而是提供统一的删除函数(zc_arraylist_t::del)，也就是说，指向每个元素的是void*指针，但所指元素必须是同种类型，否则可能无法正常释放。
2）zc_error是zlog的自诊断模块提供的记录错误log的接口，详见【zc_error模块】。

插入、更新元素 + 扩容

zlog并没有单独为插入、更新元素提供单独的接口，而是综合为同一个接口zc_arraylist_set，用于设置指定位置idx元素值。
设置元素策略：
1）当要设置的元素索引越界时，先扩容，再设置；
2）当要设置的元素索引未越界时，先释放旧元素，再设置新元素；

/**
* array位置idx处元素赋值为data. idx越界时, 扩容
*
* Pseudo code:
* a_list->array[idx] = data;
*/
int zc_arraylist_set(zc_arraylist_t *a_list, int idx, void *data)
{
    if (idx > a_list->size - 1) { /* idx越界 需要扩容 */
        // FIXME: 如果zc_arraylist_expand_inner中,
        // new_size取max, 实际上并没有扩容, 因为实参idx代表的是序号. 解决办法:
        // zc_arraylist_expand_inner(a_list, idx + 1)
        // 原代码这里是zc_arraylist_expand_inner(a_list, idx), 可能存在bug
        if (zc_arraylist_expand_inner(a_list, idx + 1)) { /* 扩容 error */
            zc_error("expand_inner fail");
            return -1;
        }
    }

    /* idx未越界(未扩容 or 扩容成功) */

    if (a_list->array[idx] && a_list->del) /* delete现有元素 */
        a_list->del(a_list->array[idx]);
   
    a_list->array[idx] = data; /* 设置idx位置元素 */
    if (a_list->len <= idx)    /* 更新数据长度 */
        a_list->len = idx + 1;
    return 0;
}

设置元素值时，可能会发生扩容。那么，zc_arraylist是如何扩容的呢？
扩容策略：当请求的容量max比当前容量2倍还大时, 新容量为请求容量；否则, 新容量为当前容量2倍。扩容操作通过库函数realloc来完成。

/**
* 扩容策略:
* 当请求的容量max比当前容量2倍还大时, 新容量为请求容量; 否则, 新容量为当前容量2倍
*/
static int zc_arraylist_expand_inner(zc_arraylist_t *a_list, int max)
{
    void *tmp;
    int new_size;
    int diff_size;

    new_size = zc_max(a_list->size * 2, max);
    /* realloc 不会改变原有内存上的数据, 原有内存长度: a_list->size,
     * 多余的空间new_size - a_list->size, 并未初始化
     */
    tmp = realloc(a_list->array, new_size * sizeof(void *));
    if (!tmp) {
        zc_error("realloc fail, errno[%ld]", errno);
        return -1;
    }

    /* 初始化多余空间 */
    a_list->array = (void **)tmp;
    diff_size = new_size - a_list->size;
    if (diff_size) memset(a_list->array + a_list->size, 0x00, diff_size * sizeof(void *));
    a_list->size = new_size; /* 更新容量 */
    return 0;
}

TIPS：zlog通过给函数名加上"_inner"，表面这是一个模块内部函数，不建议外部模块直接调用。
通过static关键字修饰函数，限制只能在文件作用域内调用。

尾部添加元素

尾部添加元素是所有动态列表的通用操作，zc_arraylist用zc_arraylist_set()来实现尾部添加元素，具体做法是：设置索引位置为数组长度(a_list->len)的元素值为data。

int zc_arraylist_add(zc_arraylist_t *a_list, void *data)
{
    /*
     * 列表末尾添加一个元素. 空间不足时, 会发生扩容.
     */
    return zc_arraylist_set(a_list, a_list->len, data);
}

有序添加元素

zc_arraylist提供了一个用于保持原有大小顺序的添加元素方式，使用的算法本质上是直接插入排序算法：寻找数组中第一个 ">" 待插入元素的值，该元素位置i就是待插入新元素的位置。
但并不直接更新元素值，而要先将i..len-1的所有元素后移一个单位，然后才能在位置i插入元素。

2个元素如何比较大小？
前面已提到过，只有调用者才知道实际元素类型，因此，必须由调用者一并提供比较函数cmp。

/**
* 往列表插入元素data, 不改变列表原来的大小顺序
* @details 直接插入查找算法.
*/
int zc_arraylist_sortadd(zc_arraylist_t *a_list, zc_arraylist_cmp_fn cmp,
        void *data)
{
    int i;

    /* 找到第一个 "> data"的数组元素, 索引位置i即为元素待插入位置 */
    for (i = 0; i < a_list->len; i++) {
        if ((*cmp) (a_list->array[i], data) > 0) {
            break;
        }
    }

    if (i == a_list->len) /* 要插入元素的位置是列表末尾 */
        return zc_arraylist_add(a_list, data);
    else /* 要插入元素的位置是中间 */
        return zc_arraylist_insert_inner(a_list, i, data);
}

几个特殊的宏函数
由于实现较为简单，zc_arraylist将这3个函数用宏的方式实现：
1）zc_arraylist_len() 用于获取a_list元素个数；
2）zc_arraylist_get() 用于获取a_list索引i位置元素；
3）zc_arraylist_foreach() 用于遍历a_list所有元素；

/* 获取a_list元素个数, 相当于a_list->len */
#define zc_arraylist_len(a_list) (a_list->len)

/* 获取a_list的第i个元素, 相当于a_list[i] */
#define zc_arraylist_get(a_list, i) \
    ((i >= a_list->len) ? NULL : a_list->array[i])

/* 遍历a_list */
#define zc_arraylist_foreach(a_list, i, a_unit) \
    for (i = 0, a_unit = a_list->array[0]; (i < a_list->len) && (a_unit = a_list->array[i], 1); i++)

要遍历a_list，还需要结合其他代码来实现。例如，下面代码演示如何遍历列表levels（日志等级列表）：

zc_arraylist_t *levels;
zlog_level_t *a_level;
int i;

/* 往levels添加元素, 元素类型为(zlog_level_t *) */
...
zc_arraylist_foreach(levels, i, a_level) {
    /* 这样a_level相当于levels->arry[i], i = 0...levels->len-1
     * 对a_level操作, 也就是对levels每个元素进行操作
     */
}

知识点

calloc, realloc

• calloc = malloc + bzero
  也就是申请内存+清0。申请的内存大小 = nmemb * size。

• realloc是重新申请内存，不改变原有内存的内容。如果ptr为NULL，realloc等价于malloc(size)；如果ptr非空，则必须是之前调用malloc/calloc/realloc返回的指针。
  如果长度 > 原有内存长度，多余的部分未初始化；如果长度 < 原有内存长度，会发生截断。

• reallocarray = realloc(ptr, nmemb * size)

#include <stdlib.h>

void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
void *reallocarray(void *ptr, size_t nmemb, size_t size);