zlog日志库源码解析 —— 数据结构:动态列表 zc_arraylist

2022/9/15 14:19:31

本文主要是介绍zlog日志库源码解析 —— 数据结构:动态列表 zc_arraylist,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 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);


这篇关于zlog日志库源码解析 —— 数据结构:动态列表 zc_arraylist的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程