C语言中泛型列表的实现

打算用C重新实现一个更完善的通讯协议描述语言，写的时候发现很多地方会需要用到可以自动增长的列表，于是尝试用宏定义的方式实现了一个简单的“泛型”列表。

用法很简单，主要的宏有两个，一个用于列表类型的定义，一个用于列表类型的实现，通常会在头文件里面定义列表类型在代码文件里实现它。

下面是声明一个整数列表的代码：


// 定义
LIST_DEF(int_list, int);

// 实现
LIST_IMP(int_list, int);

第一个宏参数 int_list 是列表类型名，int 是列表的元素类型，这里也可以换成自己的结构体。但是有时候我们会需要列表元素是指针类型，并且在销毁列表的时候要能自动回收每个项，所以另外有一个实现指针类型列表的宏，下面是声明一个字符串列表的代码：


// 定义
LIST_DEF(str_list, char *);

// 实现
LIST_IMP_P(str_list, char *, free);

这个宏比非指针版多了一个用于回收列表项的函数作为参数，回收字符串我们用 free 函数所以这里就传 free，有时候我们的自定义类型需要自己实现更复杂的 free，那就可以传自己实现的 free 进去。

LIST_DEF 展开会声明一个结构体和一组列表操作函数，列表操作函数有： add、del、get、new、free 五个基本操作，分别会以 [列表类型]_add、[列表类型]_del、[列表类型]_get、[列表类型]_new、[列表类型]_free 声明并实现，LIST_IMP 宏展开来就是这五个函数的实现代码。

下面是整数列表的示例代码：


#include <stdio.h>
#include <stdlib.h>

#include "gen_list.h"

LIST_DEF(int_list, int);

LIST_IMP(int_list, int);

int main(int argc, char **argv) {
    int i;
    int pos;

    int_list *list = int_list_new(1);

    printf("cap = %02d, len = %02d\n", list->cap, list->len);

    printf("*** add test ***\n");

    for (i = 0; i < 20; i ++) {
        pos = int_list_add(list, i);

        printf(
            "%02d - cap = %02d, len = %02d, list[%02d] = %d\n", 
            i, list->cap, list->len, pos, int_list_get(list, pos)
        );
    }

    printf("*** del test ***\n");

    for (i = 0; i < 20; i ++) {
        int_list_del(list, 0);

        printf(
            "%02d - cap = %02d, len = %02d, list[%02d] = %d\n", 
        i, list->cap, list->len, 0, int_list_get(list, 0)
        );
    }

    int_list_free(list);

    return 0;
}

下面是 gen_list.h 的完整代码：


#ifndef _GEN_LIST_H_
#define _GEN_LIST_H_

#define LIST_DEF(LIST, T)             \
typedef struct {                      \
  T   *items;                         \
  int  cap;                           \
  int  len;                           \
} LIST;                               \
                                      \
LIST *LIST##_new(int cap);            \
                                      \
void LIST##_free(LIST *list);         \
                                      \
int LIST##_add(LIST *list, T item);   \
                                      \
void LIST##_del(LIST *list, int pos); \
                                      \
T LIST##_get(LIST *list, int pos);    \

#define LIST_IMP_(LIST, T, ALLOC, REALLOC, FREE, ERROR, FREE_ITEMS, TFREE) \
LIST *LIST##_new(int cap) {                                                \
    LIST *list = (LIST *)(ALLOC)(sizeof(LIST));                            \
    list->items = (T *)(ALLOC)(sizeof(T *) * cap);                         \
    list->cap   = cap;                                                     \
    list->len   = 0;                                                       \
    return list;                                                           \
}                                                                          \
                                                                           \
void LIST##_free(LIST *list) {                                             \
    FREE_ITEMS                                                             \
    (FREE)(list->items);                                                   \
    (FREE)(list);                                                          \
}                                                                          \
                                                                           \
int LIST##_add(LIST *list, T item) {                                       \
    if (list->len == list->cap) {                                          \
        int new_cap = list->cap * 2;                                       \
        list->items = (T *)(REALLOC)(list->items, sizeof(T) * new_cap);    \
        if (list->items == NULL) {                                         \
            (ERROR)(#LIST" realloc failed!\n");                            \
            exit(1);                                                       \
        }                                                                  \
        list->cap = new_cap;                                               \
    }                                                                      \
    int pos = list->len;                                                   \
    list->items[pos] = item;                                               \
    list->len += 1;                                                        \
    return pos;                                                            \
}                                                                          \
                                                                           \
void LIST##_del(LIST *list, int pos) {                                     \
    if (pos >= list->len)                                                  \
        return;                                                            \
                                                                           \
    TFREE(list->items[pos]);                                               \
                                                                           \
    int i;                                                                 \
                                                                           \
    for (i = pos + 1; i < list->len; i ++) {                               \
        list->items[i - 1] = list->items[i];                               \
    }                                                                      \
                                                                           \
    list->len -= 1;                                                        \
}                                                                          \
                                                                           \
T LIST##_get(LIST *list, int pos) {                                        \
    if (pos >= list->len)                                                  \
        return 0;                                                          \
                                                                           \
    return list->items[pos];                                               \
}                                                                          \

#define LIST_FREE_ITEMS(TFREE)                    \
    int i = 0;                                    \
    for(i = 0; i < list->len; i ++) {             \
        TFREE(list->items[i]);                    \
    }                                             \

#define LIST_IMP(LIST, T)                         \
    LIST_IMP_(                                    \
        LIST, T, malloc, realloc, free, printf, , \
    )                                             \

#define LIST_IMP_P(LIST, T, TFREE)                \
    LIST_IMP_(                                    \
        LIST, T, malloc, realloc, free, printf,   \
        LIST_FREE_ITEMS(TFREE), TFREE             \
    )                                             \

#endif

从代码可以看出来对于更复杂的自定义方式也是支持的，必要的时候可以用自己的函数替换 malloc、realloc、free、printf :)