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 :)