【C】理解StoneValley库中的回调函数

usr

0.序言
Traverse回调函数在StoneValley库中扮演者极其重要的角色。StoneValley库中提供的绝大多数数据结构都设计有用来遍历结构的Traverse函数接口。这时候，要遍历一个数据结构就少不了Traverse回调函数。StoneValley库的README文件中这样介绍Traverse回调函数：

vi  Callback functions and their usages

        Another crucial point of using StoneValley is to understand callback functions. There are two main types of callback functions. One is the type of callback function that used to traverse items in structures. The other is the type of callback function that used to compare values by pointers. The first one named as "CBF_TRAVERSE". The second one labeled as "CBF_COMPARE". Details about how to use these two types of callback functions are located at file "svdef.h". Additionally, two important values of callback function "CBF_TRAVERSE" returns are "CBF_TERMINATE" and "CBF_CONTINUE". 0, 1 and -1 will return after calling a "CBF_COMPARE" function. The callees for caller callback functions should obey their specific calling conventions.

1.CBF_TRAVERSE函数的使用：
我们先看第一种回调函数（CBF_TRAVERSE）。以下是CBF_TRAVERSE函数原型的声明：

1. typedef int (* CBF_TRAVERSE) (void * pitem, size_t param);

复制代码

实现一个CBF_TRAVERSE的定义也十分方便：

1. int cbftvs(void * pitem, size_t param)
   
2. {
   
3.     return CBF_CONTINUE;
   
4. }

复制代码

1）使用CBF_TRAVERSE遍历链表：
下面我们将用一个单指针链表的例子来说明CBF_TRAVERSE回调函数的使用：

1. #include <stdio.h>
   
2. #include "StoneValley-master/src/svstring.h"
   
3. 
   
4. int cbftvsls(void * pitem, size_t param)
   
5. {
   
6.         printf("%ld ", *(size_t *)((P_NODE_S)pitem)->pdata);
   
7.         return CBF_CONTINUE;
   
8. }
   
9. 
   
10. int main(void)
    
11. {
    
12.         LIST_S list; // 定义单指针链表结构
    
13.         size_t n;
    
14.         // 初始化链表
    
15.         n = 1; list = strCreateNodeS(&n, sizeof n);
    
16.         n = 2; list->pnode = strCreateNodeS(&n, sizeof n);
    
17.         n = 3; list->pnode->pnode = strCreateNodeS(&n, sizeof n);
    
18.         n = 4; list->pnode->pnode->pnode = strCreateNodeS(&n, sizeof n);
    
19.         n = 5; list->pnode->pnode->pnode->pnode = strCreateNodeS(&n, sizeof n);
    
20.         // 遍历链表
    
21.         strTraverseLinkedListSC_A(list, NULL, cbftvsls, 0);
    
22.         // 从内存中删除链表
    
23.         strDeleteLinkedListSC(list);
    
24.         return 0;
    
25. }

复制代码

1. 
   
2. P_NODE_S_       P_NODE_S_       P_NODE_S_       P_NODE_S_       P_NODE_S_
   
3. |pnode    |     |pnode    |     |pnode    |     |pnode    |     |pnode    |
   
4. |_________*---->|_________*---->|_________*---->|_________*---->|_________*---->NULL
   
5. |pdata    |     |pdata    |     |pdata    |     |pdata    |     |pdata    |
   
6. |*________|     |*________|     |*________|     |*________|     |*________|
   
7. |size_t_        |size_t_        |size_t_        |size_t_        |size_t_
   
8. |_______1|      |_______2|      |_______3|      |_______4|      |_______5|

复制代码

以上代码简单定义了链表结构并初始化了链表。在strTraverseLinkedListSC_A函数中传入了cbftvsls回调函数的地址并完成了遍历。举个简单的例子来说明strTraverseLinkedListSC_A是怎样完成遍历的：假设strTraverseLinkedListSC_A函数是火车司机，每一个P_NODE_S结构体都是火车站。火车从第一站始发，依次运行通过二、三、四站，最后到达第五站。火车每到达一站都会请cbftvsls函数作为一名乘客下车检查车站内存放的箱子，并把箱子里的东西取出来打印到屏幕上。然后这名乘客会告诉火车司机继续行驶还是停留在此站。这是通过cbftvsls返回CBF_CONTINUE或者CBF_TERMINATE来实现的。
每一次strTraverseLinkedListSC_A遍历到结构体，都会把指向结构体的指针传入cbftvsls函数的pitem参数中。也就是说，pitem参数在遍历时指向每个P_NODE_S结构体。P_NODE_S结构体又包含一个pdata成员。pdata存放指向数据的指针。在以上例子的链表中，每个数据都是长度为size_t的整数。所以pdata也就指向每个size_t整数的地址。在cbftvsls函数内先将pitem转换为指向NODE_S结构体的指针，再取出成员pdata，最后将pdata转换为指向size_t整数的指针，数据就从内存里拿出来了。cbftvsls函数在最后返回CBF_CONTINUE；告诉火车司机strTraverseLinkedListSC_A一直开到最后一站。这样就完成了链表的遍历。
我们现在将cbftvsls函数改写为以下形式，再来运行代码：

1. int cbftvsls(void * pitem, size_t param)
   
2. {
   
3.         printf("%ld ", *(size_t *)((P_NODE_S)pitem)->pdata);
   
4.         if (3 == *(size_t *)((P_NODE_S)pitem)->pdata)
   
5.                 return CBF_TERMINATE;
   
6.         return CBF_CONTINUE;
   
7. }
   

复制代码

新的cbftvsls函数在函数体内做了判断。如果本站的箱子内存放着整数3，那么就停止火车运行。否则火车一直运行到结束。这时候再次调用strTraverseLinkedListSC_A我们会发现屏幕上只打印出了 1 2 3 三个数字。这里要说明一下：strTraverseLinkedListSC_A是尾递归版的遍历函数。一般来说，尾递归可以被编译器优化以增加效率。在没有尾递归优化的时候我们可以使用函数strTraverseLinkedListSC_N。函数strTraverseLinkedListSC_N通过循环来实现链表的遍历。如果我们将以上代码的第21行改为 strTraverseLinkedListSC_R(list, NULL, cbftvsls, 0); 再来运行看看会发生什么效果呢？打印链表的顺序就会反过来，屏幕上显示出 5 4 3 2 1.那为什么这时候到达第三站不会停下来了呢？原来strTraverseLinkedListSC_R函数也使用了递归。不同于strTraverseLinkedListSC_A函数的是strTraverseLinkedListSC_R函数在递去的阶段没有调用cbftvsls回调函数，而在归来的阶段自动调用了cbftvsls。因为在归来的阶段不会经过cbftvsls'函数返回值的检查，所以便利会一直运行回到第一站结束。相当于火车从第一站直接开到了第五站，在返程的过程中派出乘客cbftvsls检查每一站箱子里的内容。
合理使用函数strTraverseLinkedListSC_A、strTraverseLinkedListSC_R、strTraverseLinkedListSC_N我们就可以灵活地控制遍历方向，并且满足效率要求。这里要注意的是，因为使用递归函数，所遍历的链表长度必须满足函数调用栈最大开销。否则递归函数就会崩栈，遍历也会失败。而使用循环的strTraverseLinkedListSC_N函数就没有此项要求。

2）使用CBF_TRAVERSE遍历数组：
下面我们使用Traverse回调函数遍历一些不同的结构：

1. #include <stdio.h>
   
2. #include "StoneValley-master/src/svgraph.h"
   
3. 
   
4. int cbftvsa(void * pitem, size_t param)
   
5. {
   
6.         printf("%c %lu\n", ((P_VTXREC)pitem)->vid, ((P_VTXREC)pitem)->dist);
   
7.         return CBF_CONTINUE;
   
8. }
   
9. 
   
10. int main(void)
    
11. {
    
12.         GRAPH_L grp;
    
13.         grpInitL(&grp);
    
14.         P_ARRAY_Z parrz = NULL;
    
15. 
    
16.         grpInsertVertexL(&grp, 'a');
    
17.         grpInsertVertexL(&grp, 'b');
    
18.         grpInsertVertexL(&grp, 'c');
    
19.         grpInsertVertexL(&grp, 'd');
    
20.         grpInsertVertexL(&grp, 'e');
    
21. 
    
22.         grpInsertEdgeL(&grp, 'a', 'b', 1);
    
23.         grpInsertEdgeL(&grp, 'b', 'd', 3);
    
24.         grpInsertEdgeL(&grp, 'd', 'c', 7);
    
25.         grpInsertEdgeL(&grp, 'c', 'e', 6);
    
26.         grpInsertEdgeL(&grp, 'a', 'c', 4);
    
27.         grpInsertEdgeL(&grp, 'b', 'a', 5);
    
28. 
    
29.         parrz = grpShortestPathL(&grp, 'b');
    
30.         if (NULL != parrz)
    
31.                 strTraverseArrayZ(parrz, sizeof(VTXREC), cbftvsa, 0, FALSE);
    
32.         else
    
33.                 printf("Can not find shortest path.\n");
    
34. 
    
35.         strDeleteArrayZ(parrz);
    
36.         grpFreeL(&grp);
    
37.         return 0;
    
38. }

复制代码

以上代码我们构造了一个图。给图添加了节点和边。我们使用grpShortestPathL生成了点b到其他点的最短路径。最后使用strTraverseArrayZ函数回调cbftvsa打印出了最短路径表。结果如下：
a 5
b 0
c 9
d 3
e 15
这时我们来看Traverse函数如何遍历定长数组。已知定长数组内包含若干个VTXREC结构体。使用strTraverseArrayZ函数的时候，每次前进调用cbftvsa，cbftvsa函数的pitem参数都会指向数组中的一个结构体开始处。strTraverseArrayZ函数的最后一个参数FALSE表明遍历数组的顺序是从第一个到最后一个，不反向遍历。这时候，在函数cbftvsa内，将pitem转换为指向VTXREC结构体的指针，就能逐个打印VTXREC结构体的成员vid和dist了。vid表示了图中节点的id，dist表示任意一点到该顶点所花费的权值。对数组的遍历很简单，稍加理解就可以掌握了。

3）使用CBF_TRAVERSE遍历二叉树

1. #include <stdio.h>
   
2. #include "StoneValley-master/src/svtree.h"
   
3. 
   
4. int cbftvst(void * pitem, size_t param)
   
5. {
   
6.         printf("%c ", *(char *)((P_NODE_D)pitem)->pdata);
   
7.         return CBF_CONTINUE;
   
8. }
   
9. 
   
10. int main(void)
    
11. {
    
12.         char c;
    
13.         P_NODE_D pa, pb, pc, pd;
    
14.         c = 'a';  pa = strCreateNodeD(&c, sizeof c);
    
15.         c = 'b';  pb = strCreateNodeD(&c, sizeof c);
    
16.         c = 'c';  pc = strCreateNodeD(&c, sizeof c);
    
17.         c = 'd';  pd = strCreateNodeD(&c, sizeof c);
    
18. 
    
19.         pa->ppnode[LEFT] = pb;
    
20.         pa->ppnode[RIGHT] = pc;
    
21.         pb->ppnode[LEFT] = pd;
    
22. 
    
23.         treTraverseBIn(pa, cbftvst, 0);
    
24.         puts("\n");
    
25.         treTraverseBPre(pa, cbftvst, 0);
    
26.         puts("\n");
    
27.         treTraverseBPost(pa, cbftvst, 0);
    
28.         puts("\n");
    
29.         treTraverseBLevel(pa, cbftvst, 0);
    
30.         puts("\n");
    
31. 
    
32.         strDeleteNodeD(pa);
    
33.         strDeleteNodeD(pb);
    
34.         strDeleteNodeD(pc);
    
35.         strDeleteNodeD(pd);
    
36.         return 0;
    
37. }

复制代码

以上代码中，我们构建了一颗二叉树，并用中序、先序、后序和按层遍历的方式打印出了二叉树结点中的内容。结果如下：
d b a c

a b d c

d b c a

a b c d
不难理解treTraverseBIn、treTraverseBPre、treTraverseBPost和treTraverseBLevel函数在二叉树上游走。每经过一个节点都会调用cbftvst函数。在cbftvst函数内，pitem指向二叉树结点的数据结构。所以将pitem转换为P_NODE_D再将P_NODE_D内的指针pdata转换成char *就可以拿出二叉树节点中的内容了。文章到此，我们需要掌握CBF_TRAVERSE函数的几个要点：一、一般来说，CBF_TRAVERSE函数通过返回CBF_CONTINUE来继续遍历，返回CBF_TERMINATE来结束遍历。二、在使用CBF_TRAVERSE的时候要注意pitem参数指向的是哪个结构。

4）使用CBF_TRAVERSE遍历二叉搜索树及集合
在二分搜索树中使用Traverse函数。我们需要将有关图的那段代码改造成如下形式：

1. #include <stdio.h>
   
2. #include "StoneValley-master/src/svgraph.h"
   
3. #include "StoneValley-master/src/svtree.h"
   
4. 
   
5. int cbftvst(void * pitem, size_t param)
   
6. {
   
7.         printf("%c ", *(char *)((P_TNODE_B)pitem)->pdata);
   
8.         return CBF_CONTINUE;
   
9. }
   
10. 
    
11. /*
    
12. int cbftvsa(void * pitem, size_t param)
    
13. {
    
14.         printf("%c %lu\n", ((P_VTXREC)pitem)->vid, ((P_VTXREC)pitem)->dist);
    
15.         return CBF_CONTINUE;
    
16. }
    
17. */
    
18. 
    
19. int main(void)
    
20. {
    
21.         GRAPH_L grp;
    
22.         grpInitL(&grp);
    
23.         P_ARRAY_Z parrz = NULL;
    
24. 
    
25.         grpInsertVertexL(&grp, 'a');
    
26.         grpInsertVertexL(&grp, 'b');
    
27.         grpInsertVertexL(&grp, 'c');
    
28.         grpInsertVertexL(&grp, 'd');
    
29.         grpInsertVertexL(&grp, 'e');
    
30.         grpInsertVertexL(&grp, 'f');
    
31. 
    
32.         grpInsertEdgeL(&grp, 'a', 'b', 1);
    
33.         grpInsertEdgeL(&grp, 'b', 'd', 3);
    
34.         grpInsertEdgeL(&grp, 'd', 'c', 7);
    
35.         grpInsertEdgeL(&grp, 'c', 'e', 6);
    
36.         grpInsertEdgeL(&grp, 'a', 'c', 4);
    
37.         grpInsertEdgeL(&grp, 'b', 'a', 5);
    
38. 
    
39.         /*
    
40.         parrz = grpShortestPathL(&grp, 'b');
    
41.         if (NULL != parrz)
    
42.                 strTraverseArrayZ(parrz, sizeof(VTXREC), cbftvsa, 0, FALSE);
    
43.         else
    
44.                 printf("Can not find shortest path.\n");
    
45.         */
    
46.         treTraverseBLevel(P2P_TNODE_B(grp), cbftvst, 0);
    
47. 
    
48.         // strDeleteArrayZ(parrz);
    
49.         grpFreeL(&grp);
    
50.         return 0;
    
51. }

复制代码

因为在StoneValley中图结构的节点是用SET_T存放的，而SET_T就是BST结构。BST结构则是指向BSTNODE结构体的指针。这时候我们来看StoneValley作者玩的一个小Trick。BSTNODE结构包含一个knot成员。而knot成员的类型是TNODE_B，也就是NODE_D结构体。这个NODE_D结构体被安排在了BSTNODE结构的顶层，也就是说，如果一个指针指向BSTNODE结构体，那么这个指针同时也指向NODE_D结构体。而NODE_D结构体可以被treTraverseBLevel等函数遍历搜索，所以将一个SET_T结构强制转换为P_TNODE_B指针再输入treTraverseBLevel函数的第一个参数就可以完成遍历二叉搜索树。StoneValley就这么巧妙地完成了多态。那么至此，大家已经知道了如何在StoneValley里遍历二叉树，遍历二叉搜索树包括遍历树状集合了。我们再来看setTraverseT函数，此函数实际上就是调用了treTraverseBLevel等一系列函数。以上代码的执行结果是：
b a d c e f

2.在调用CBF_TRAVERSE函数的时候传参。
我们来看grpShortestPathL函数的实现。在grpShortestPathL函数内部有这么几行：

1. size_t a[4];
   
2. 
   
3.                 /* Take the front vertex from Queue. */
   
4.                 ...
   
5. 
   
6.                 a[0] = vidx;
   
7.                 a[1] = (size_t)parrd;
   
8.                 a[2] = (size_t)parrq;
   
9.                 a[3] = (size_t)&q;
   
10.                 /* Relaxing all the adjacent edges of vertex taken from the queue. */
    
11.                 if (CBF_CONTINUE != grpTraverseVertexEdgesL(pgrp, vidx, _grpCBFSPLTraverseVertexEdgesPuppet, (size_t)a))
    
12.                         goto Lbl_Bad_Result;

复制代码

不难发现grpTraverseVertexEdgesL函数回调调用了_grpCBFSPLTraverseVertexEdgesPuppet函数。而函数_grpCBFSPLTraverseVertexEdgesPuppet需要这么几个参数：1.当前节点ID。2.数组d。3.数组q。4.队列q。我们发现_grpCBFSPLTraverseVertexEdgesPuppet回调函数的参数只有两个，一个是void * pitem指向遍历到的每个结构体，第二个是param参数。怎样将4个参数传入_grpCBFSPLTraverseVertexEdgesPuppet函数呢？答案是使用参数结构体。在grpShortestPathL函数内部定义了一个名为a的size_t[4]的数组，数组中每个元素都被相应赋值。grpTraverseVertexEdgesL调用_grpCBFSPLTraverseVertexEdgesPuppet的时候将数组a的地址传入param参数当中即可。在函数_grpCBFSPLTraverseVertexEdgesPuppet中，是这样解析数组中的每个元素的：

1. int _grpCBFSPLTraverseVertexEdgesPuppet(void * pitem, size_t param)
   
2. {
   
3.         P_ARRAY_Z parrd = (P_ARRAY_Z)1[(size_t *)param];;
   
4.         P_ARRAY_Z parrq = (P_ARRAY_Z)2[(size_t *)param];
   
5.         P_QUEUE_L pq = (P_QUEUE_L)3[(size_t *)param];
   
6.         size_t u = 0[(size_t *)param];
   
7.         size_t v = ((P_EDGE)pitem)->vid;
   
8.         ...

复制代码

3.使用CBF_COMPARE回调函数。
在StoneValley中还有一个重要的回调函数便是CBF_COMPARE回调函数了。我们来看CBF_COMPARE函数的原型：

1. typedef int (* CBF_COMPARE)  (const void *, const void *);
   
2. /* If callback traversal function returned CBF_TERMINATE, traversal would be interrupted,
   
3. *  otherwise, traversal would continue to run till traversal function reached the end.
   
4. * A typical comparing function would like the following lines of codes
   
5. *  in which MYTYPE is a type that user defined previously:
   
6. * int cbfcmp(const void * px, const void * py)
   
7. * {
   
8. *     if (*(MYTYPE *)px > *(MYTYPE *)py) return  1;
   
9. *     if (*(MYTYPE *)px < *(MYTYPE *)py) return -1;
   
10. *     return 0;
    
11. * }
    
12. */

复制代码

StoneValley的代码中也给出了CBF_COMPARE简单的实现。下面我们通过一段代码来认识CBF_COMPARE函数：

1. #include <stdio.h>
   
2. #include <time.h>
   
3. #include "StoneValley-master/src/svgraph.h"
   
4. 
   
5. int cbftvsa(void * pitem, size_t param)
   
6. {
   
7.         printf("%c %lu\n", ((P_VTXREC)pitem)->vid, ((P_VTXREC)pitem)->dist);
   
8.         return CBF_CONTINUE;
   
9. }
   
10. 
    
11. int cbfcmpvtxrec(const void * px, const void * py)
    
12. {
    
13.         if (((P_VTXREC)px)->vid > ((P_VTXREC)py)->vid) return  1;
    
14.         if (((P_VTXREC)px)->vid < ((P_VTXREC)py)->vid) return -1;
    
15.         return 0;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         GRAPH_L grp;
    
21.         grpInitL(&grp);
    
22.         P_ARRAY_Z parrz = NULL;
    
23. 
    
24.         grpInsertVertexL(&grp, 'a');
    
25.         grpInsertVertexL(&grp, 'b');
    
26.         grpInsertVertexL(&grp, 'c');
    
27.         grpInsertVertexL(&grp, 'd');
    
28.         grpInsertVertexL(&grp, 'e');
    
29. 
    
30.         grpInsertEdgeL(&grp, 'a', 'b', 1);
    
31.         grpInsertEdgeL(&grp, 'b', 'd', 3);
    
32.         grpInsertEdgeL(&grp, 'd', 'c', 7);
    
33.         grpInsertEdgeL(&grp, 'c', 'e', 6);
    
34.         grpInsertEdgeL(&grp, 'a', 'c', 4);
    
35.         grpInsertEdgeL(&grp, 'b', 'a', 5);
    
36. 
    
37.        
    
38.         parrz = grpShortestPathL(&grp, 'b');
    
39.         if (NULL != parrz)
    
40.         {
    
41.                 VTXREC temp;
    
42.                 strShuffleArrayZ(parrz, &temp, sizeof temp, (unsigned)time(NULL));
    
43.                 strTraverseArrayZ(parrz, sizeof(VTXREC), cbftvsa, 0, FALSE);
    
44.                 strSortArrayZ(parrz, sizeof temp, cbfcmpvtxrec);
    
45.                 printf("After sorting:\n");
    
46.                 strTraverseArrayZ(parrz, sizeof(VTXREC), cbftvsa, 0, FALSE);
    
47.         }
    
48.         else
    
49.                 printf("Can not find shortest path.\n");
    
50. 
    
51.         strDeleteArrayZ(parrz);
    
52.         grpFreeL(&grp);
    
53.         return 0;
    
54. }

复制代码

在以上代码中我们使用了strShuffleArrayZ来打乱parrz里边的数据，然后使用strSortArrayZ函数对数组重新进行排序。strSortArrayZ函数回调调用了cbfcmpvtxrec函数。因为strSortArrayZ函数在排序时每次都将传给cbfcmpvtxrec函数的两个指针指向数组内的数据。已知parrz数组是存放VTXREC结构体的数组。那么cbfcmpvtxrec函数的参数px和py就指向VTXREC结构体。使用的时候将px和py转换成P_VTXREC就可以取出结构体成员vid进行比较了。