2019独角兽企业重金招聘Python工程师标准>>> 
经常使用C＋＋、JAVA等面向对象语言开发的程序员都会比较喜欢容器的迭代器功能，用起来方便简洁。象一些常用的数据结构，如：哈希表、动态数组、链表等，在这些面向对象语言中都可以非常方便地使用迭代器。当然，在C语言中也有对这些常用数据结构的函数封装，但要对容器中元素的遍历，则一般会通过注册回调函数的方式。如下：
/* 以C语言中非常流行的 glib 库中的哈希表操作为例 */
static void print_record(gpointer key, gpointer val, gpointer ctx)
{
printf("%s: key(%s), value(%s)\n", (char*) ctx, (char*) key, (char*) val));
}
static void free_record(gpointer key, gpointer val, gpointer ctx)
{
printf("%s: free(%s) now\n", (char*) ctx, (char*) key);
free(val);
}
static void htable_test(void)
{
char *myname = "hash_test";
char key[32], *value;
GHashTable *table;
int i;
/* 创建哈希表 */
table = g_hash_table_new(g_str_hash, g_str_equal);
/* 依次向哈希表中添加数据 */
for (i = 0; i < 10; i++) {
snprintf(key, sizeof(key), "key:%d", i);
value = malloc(64);
snprintf(value, 64, "value:%d", i);
g_hash_table_insert(table, key, value);
}
/* 遍历并输出哈希表中的数据 */
g_hash_table_foreach(table, print_record, myname);
/* 依次释放哈希表中的数据 */
g_hash_table_foreach(table, free_record, myname);
/* 销毁哈希表 */
g_hash_table_destroy(table);
}
这是C函数库中比较常用的回调函数方式，它主要有两个缺点：多写了一些代码，使用不太直观。下面介绍一下ACL库中的设计与实现是如何克服这两个缺点的。首先先请看一个ACL库中使用哈希表的例子：
void htable_test(void)
{
ACL_HTABLE *table = acl_htable_create(10, 0); /* 创建哈希表 */
ACL_ITER iter; /* 通用迭代器对象 */
char key[32], *value;
int i;
/* 依次向哈希表中添加数据 */
for (i = 0; i < 20; i++) {
snprintf(key, sizeof(key), "key: %d", i);
value = acl_mymalloc(32);
snprintf(value, 32, "value: %d", i);
assert(acl_htable_enter(table, key, value));
}
printf("\n>>>acl_foreach for htable:\n");
/* 正向遍历哈希表中数据 */
acl_foreach(iter, table) {
printf("hash i=%d, [%s]\n", iter.i, (char*) iter.data);
}
/* 释放哈希表中数据 */
acl_foreach(iter, table) {
acl_myfree(iter.data);
}
/* 销毁哈希表 */
acl_htable_free(table, NULL);
}
由以上例子可以明显看出ACL库中的哈希表遍历更加简单直观，不需要回调函数方式便可以遍历哈希表中的所有元素。ACL库不仅哈希表可以用 "ACL_ITER iter; acl_foreach(iter, hash_table) {}" 的方式进行遍历，其它的通用数据结构容器都可以如此使用，如ACL库中的先进先出队列：ACL_FIFO 使用迭代器的例子：
static void fifo_iter(void)
{
ACL_FIFO fifo;
ACL_ITER iter;
ACL_FIFO_INFO *info;
int i;
char *data;
/* 初始化堆栈队列 */
acl_fifo_init(&fifo);
/* 向队列中添加数据 */
for (i = 0; i < 10; i++) {
data = acl_mymalloc(32);
snprintf(data, 32, "data: %d", i);
acl_fifo_push(&fifo, data);
}
printf("\n>>> acl_foreach for fifo:\n");
/* 正向遍历队列中数据 */
acl_foreach(iter, &fifo) {
printf("i: %d, value: %s\n", iter.i, (char*) iter.data);
}
printf("\n>>> acl_foreach_reverse for fifo:\n");
/* 反向遍历队列中数据 */
acl_foreach_reverse(iter, &fifo) {
printf("i: %d, value: %s\n", iter.i, (char*) iter.data);
}
/* 弹出并释放队列中数据 */
while (1) {
data = acl_fifo_pop(&fifo);
if (data == NULL)
break;
acl_myfree(data);
}
}
可以看出，ACL库中的迭代器都是同样的东东 ACL_ITER, 遍历方式也都一样，这是如何做到的？下面请先看一下ACL库中 ACL_ITER 结构的定义：
#ifndef __ACL_ITERATOR_INCLUDE_H__
#define __ACL_ITERATOR_INCLUDE_H__
typedef struct ACL_ITER ACL_ITER;
/**
* ACL 库中数据结构用的通用迭代器结构定义
*/
struct ACL_ITER {
void *ptr; /**< 迭代器指针, 与容器相关 */
void *data; /**< 用户数据指针 */
int dlen; /**< 用户数据长度, 实现者可设置此值也可不设置 */
const char *key; /**< 若为哈希表的迭代器, 则为哈希键值地址 */
int klen; /**< 若为ACL_BINHASH迭代器, 则为键长度 */
int i; /**< 当前迭代器在容器中的位置索引 */
int size; /**< 当前容器中元素总个数 */
};
/**
* 正向遍历容器中元素
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
* @examples: samples/iterator/
*/
#define ACL_FOREACH(iter, container) \
if ((container)) \
for ((container)->iter_head(&(iter), (container)); \
(iter).ptr; \
(container)->iter_next(&(iter), (container)))
/**
* 反向遍历容器中元素
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
* @examples: samples/iterator/
*/
#define ACL_FOREACH_REVERSE(iter, container) \
if ((container)) \
for ((container)->iter_tail(&(iter), (container)); \
(iter).ptr; \
(container)->iter_prev(&(iter), (container)))
/**
* 获得当前迭代指针与某容器关联的成员结构类型对象
* @param iter {ACL_ITER}
* @param container {void*} 容器地址
*/
#define ACL_ITER_INFO(iter, container) \
((container) ? (container)->iter_info(&(iter), (container)) : NULL)
#define acl_foreach_reverse ACL_FOREACH_REVERSE
#define acl_foreach ACL_FOREACH
#define acl_iter_info ACL_ITER_INFO
#endif
其实，ACL_ITER 只是定义了一些规则，具体实现由各个容器自己来实现，如果容器要实现正向遍历，则需要遵守如下原则：
1）则容器的结构中必须要有成员变量：iter_head(ACL_ITER* iter, /* 容器本身的对象指针 */), iter_next(ACL_ITER* iter, /* 容器本身的对象指针 */); 如果没有这两个成员变量怎么办？那在编译时如果有函数使用该容器的 acl_foreach(){} 则编译器会报错，这样的好处是尽量让错误发生在编译阶段。
2）同时在容器内部需要实现两个注册函数: iter_head()/2, iter_next()/2, 此两函数内部需要将容器的数据赋值给 iter->data；同时改变容器中下一个对象的位置并赋值给 iter->ptr；如果容器本身是由整数值来标识元素索引位置的，则可以把索引位置赋值给 iter->i，但别忘记依然需要将 iter->ptr 赋值－－可以赋与iter->data 同样的值，这样可以避免acl_foreach() 提前退出。
至于反向遍历容器中元素，规则约束下正向遍历类似，在此不再详述。
下面，以一个大家常用的字符串分隔功能的函数例子来结束本文：
void argv_iter(void)
{
const char *s = "hello world, you are welcome!"; /* 源串 */
ACL_ARGV *argv = acl_argv_split(s, " ,!"); /* 对源串进行分隔 */
ACL_ITER iter; /* 通用的迭代器 */
printf("\nacl_foreach for ACL_ARGV:\n");
/* 正向遍历字符串数组 argv 中的所有元素 */
acl_foreach(iter, argv) {
printf(">> i: %d, value: %s\n", iter.i, (char*) iter.data);
}
printf("\nacl_foreach_reverse for ACL_ARGV:\n");
/* 反向遍历字符串数组 argv 中的所有元素 */
acl_foreach_reverse(iter, argv) {
printf(">> i: %d, value: %s\n", iter.i, (char*) iter.data);
}
/* 释放字符串数组 argv */
acl_argv_free(argv);
}
ACL中有哪些常见的容器实现了 ACL_ITER 所要求的功能，可以通过 samples/iterator/ 下的例子进行查看.
ACL 库下载位置：http://acl.sourceforge.net/
个人微博：http://weibo.com/zsxxsz
QQ 群：242722074