2019-06-10

c/c++

入职培训C

入职培训感想

想到终于有机会上手一个正式的c/c++项目了，又把之前的一些旧文拿出来整理整理，这一篇是入职培训时候的一个小项目感想。

培训的最后一个阶段是小型项目的上手演练，有很多有意思的体会。

表驱动法编程模式

实际的需求是一个地铁站的计费功能，要根据不同的里程数计算地铁票的价格，最容易想到的模式是按照以下方式进行

if (dis<d1&&dis>=d2){
   price caculating;
}else if(dis>d2&&dis<=d3){
   price caculating;
}else {
   ...
}

表驱动法的核心思路是尽量把以后可能要变化的部分都抽取出来，就是通过定义table来对应实际的映射关系，实际上就是把对应的映射关系预先存储在一个表中，之后直接读取表就行，说白了就是空间换时间的思路。针对于逻辑性不是很强但是分支比较多的代码。简而言之就是通过查表的方式来获取值。数据驱动（表驱动）编程的核心出发点是相对于程序逻辑，人类更擅长于处理数据。

比如对于以上的情景，可以自己先定义一个struct，把具体的逻辑表述数据化：

typedef struct distanceTable{
	int price;
	int start;
	int end;
}

之后把实际的关键点对应的票价存储在这个数组中，具体判断的时候，如果发现实际输入的dist在某个start与end之间，就得到了对应的price。

错误处理

在实际项目中，错误处理是严谨而全面的。一个严谨的项目中对于错误的处理也应该是严谨全买客观的，一般涉及ERROR_CODE（代码中常用枚举类型表示，返回SUCCESS的形式常定义在第一个位置）以及ERROR_STR（用户可读的信息），ERROR_STR中的每一种与ERROR_CODE中的每个枚举值应该都是对应的，这些信息最好是单独定义在一个错误处理的模块中，对于新手来说，错误处理常常表现的过于随意，常常都是什么时候想用就什么时候输出。

在C++编程的时候，由于返回值只能返回一个结果，这个结果常常就是ERROR_CODE，如果函数有其他的多个返回值，常常通过形式参数引用的形式放在形式参数的位置上传入进来，之后在函数中就可以直接对这个值进行修改（set这个值）这样就起到了返回值的效果。对于Golang来说比较烦的就是每次判断err!=nil{}这种，在C++中也是有类似的判断，一种是在每次关键步骤完成之后就判断，如果有对应的错误就返回，另外一种是使用 do while的方式：

do {
   returncode=functiona(...);
   if(returncode!=SUCCESS){
      //process err
      break;
   }
   
   ...
   
   returncode=functionb(...);
   if(returncode!=SUCCESS){
      //proess err
      break;
   }
   
   ...
   
   //final output
}while(0)

在整个的do语句中对每次的返回值进行判断如果中途有err则直接break出来进行最后的处理。

不带数据项的链表实现

在项目中使用了一个不带数据项的双向链表的实现，具体的链表节点的插入删除操作都是通过宏定义来进行的，貌似是直接从Linux内核的代码中借鉴过来的，这里罗列一些关键步骤，感觉还是很有启发的。

typedef struct ListHead{
	struct ListHead* next;
	struct ListHead* prev;
}ListHead;

这里的链表节点在定义的时候没有数据元素仅仅是定义了标记位置，具体求元素的操作主要依赖了这个宏定义：

#define container_of(ptr, type, member) ({                 
const typeof( ((type *)0)->member ) *__mptr = (ptr);    
(type *)( (char *)__mptr - offsetof(type,member) );})

网上的参考资料很多，当前链表元素的开始部分为ptr，链表中存储的具体元素是类型为type，其中需要访问的字段为member。第一步的意思是求出结构中的具体元素相对于结构体起始位置的偏移。也就是这一句：

const typeof( ((type *)0)->member ) *__mptr = (ptr);

大概就是说把type类型放在0号位置上然后看member的位置是什么，此处的member的值就是其相对于起始位置的偏移。之后再把指针从起始位置向后移动偏移的位置就得到实际需要访问的字段的位置。巧妙之处在于将地址0强制转换为type类型的指针，从而定位到member在结构体中偏移位置。编译器认为0是一个有效的地址，从而认为0是type指针的起始地址。

下面是一个实际的例子，在具体介绍例子之前再强调一下container_of的功能，已经知道一个struct中某个元素的位置，通过这个元素以及这个元素所在的结构体的类型就可以找到这个结构体实例起始的位置：

/** 
 * container_of - cast a member of a structure out to the containing structure 
 * @ptr:        the pointer to the member. 
 * @type:       the type of the container struct this is embedded in. 
 * @member:     the name of the member within the struct. 
 * 
 */ 
  
#include <cstdio>
#include <iostream>
#define offsetof(type, member) (size_t)&(((type*)0)->member)
#define container_of(ptr, type, member) ({ \
     const typeof( ((type *)0)->member ) *__mptr = (ptr); \
     (type *)( (char *)__mptr - offsetof(type,member) );})
using namespace std;
struct test{
   char i;
   char j;
   char k;
};
typedef struct ListNode{
     ListNode* prev;
     ListNode* next;
}ListNode;
int main()
{
    struct test temp;
    printf("&temp = %p\n",&temp);
    printf("&temp.i = %p\n",&temp.i);
    printf("&temp.j = %p\n",&temp.j);
    printf("&temp.k = %p\n",&temp.k);
    printf("&((struct test *)0)->k = %d\n",((size_t)&((struct test*)0)->k));
    test * startAddr=container_of(&temp.j,test,j);
    printf("&temp start addr by containerof : %p\n",startAddr);
    return 0;
}
/*
output
&temp = 0069FF05
&temp.i = 0069FF05
&temp.j = 0069FF06
&temp.k = 0069FF07
&((struct test *)0)->k = 2
&temp addr by containerof : 0069FF05
*/

可以看到最后通过container_of找到的结构体的起始位置正好是结构体本身所在的位置。

关于双向链表的实现

主要内容参考这一篇。从linux2.6.39版本中摘录了一些双向list实现的代码，结合前面的内容一点点分析下，体会这种简洁的list实现。

这种list的实现思路与在教科书上最大的差别：教科书上的链表中，具体的元素被定义在链表的struct中，类似于下面这样：

typedef struct ListNode{
    ListNode* prev;
    ListNode* next;
    Elemtype item;
}

这样的问题就是链表的结构的无法复用。对于新元素类型的话，必须重新定义链表节点的数据结构。在Linux的代码中链表节点的结构是作为具体数据struct的一部分而存在的，相当于是包含在具体的数据节点的结构定义中。

换句话来说，第一种模式就像是连在一起的不同的盒子，每个盒子的规格是固定的，盒子里面可以装不同的元素。第二种模式是把用于连接的部分单独抽象了出来，不同的盒子可以使用同样的连接工具链接在一起。这个链接工具就是链表结构的定义，至于再往后一步，如何通过这个链表找到自定义数据结构的起始位置从而定位到结构中的任何其他元素，这里通过其中的list元素之后使用前面介绍的container_of的方式就可以定义到整个数据的起始部分。

struct list_head {
	struct list_head *next, *prev;
};

linux中的Simple doubly linked list implementation，具体的节点仅有前后两个指针。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

初始化的时候，前后两个指针都指向当前的元素，由于不涉及到具体的元素，仅仅是指针的移动，因此初始化的时候不会涉及到内存空间的申请与释放。

static inline void __list_add(struct list_head *new,
			      struct list_head *prev, struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}
//insert tail 采用尾插发
__list_add(new, head->prev, head);
//insert head 采用头插法
__list_add(new, head, head->next);

插入新元素的时候，就是常见的套路，注意头插和尾插在元素上位置上的调整，这个与课本中的都一样。

至于列出结构体元素起始部分的地址，需要使用list_entry函数：

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

可以看到其中直接使用的就是container_of的宏定义，列出当前结构体的首地址。

其他的方法暂时不列出了，总是比较有参考价值，可以慢慢学习一下，具体在Linux的代码中，不同组件中list的代码被复制了好多次，比如可以参考这个/tools/firewire/list.h这个里面实现了一些最基本的函数。

AverageMind

入职培训C

表驱动法编程模式

错误处理

不带数据项的链表实现

关于双向链表的实现

相关参考

推荐文章