OO Programing in C (3)

OO Programing in C is not only POSSIBLE but also PRACTICAL
--------------------------------------------------------------------------------

OO的一个亮点是类的"继承"，通过"继承"，可以重用许多代码。而且"继承"也是现实生活中非常自然的一种关系。但是很不幸，C没有class，更没有提供"继承"的表达方式。既然能用C的struct来仿真class, 那能不能继续来仿真"继承"呢？答案是:possible。就像<<Inside the C++ Object Modal>>书中所叙述的那样——你可以用C来达到所有C++能做到的事。但这种仿真显然毫无实际应用价值。

"继承"是一种表达方式，代码重用才是目的。

为了重用代码，C++可以用"继承"的方式来巧妙的达到目的，但是也必须付出代价：你必须非常仔细地设计你的类族谱，要有前瞻性，要有可扩展性，要决定分多少个层次....这些都不是容易做到的事。

C别无选择，模块化设计，函数，宏....只能通过巧妙的设计才能达到代码可重用的目的。还是举个例子来说明C是如何做到"殊途同归"的吧。

"链表"是一个非常常用的数据结构，常用于管理无序的数据(对象)集合。链表操作，特别是双向链表操作很容易出错。重用一套通用操作链表的代码可以为我们省不少事。在C++中，我们可以用经典的STL中的list类。为了适应各种数据类型，list类用模板来实现。list类实现的很巧妙，功能很强，但是，不得不说，很少人用。其实不仅list类很少用，STL都很少人用。（希望这是我的一家之言，反正我所熟悉的C++程序员都不怎么用STL :-）当然在C++中你还有另外一个选择：实现一个List基类完成链表操作，要放入链表的类从List类继承而来，就拥有了一套操作list的方法。

Linux内核中用C提供了一套非常巧妙的方法操作链表，位于.../linux/include/linux/list.h，只用一些宏和inline函数来实现双向链表。摘抄一部分出来：

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


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

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
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;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

.....

/**
 * 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)

/**
 * list_for_each    -    iterate over a list
 * @pos:    the &struct list_head to use as a loop counter.
 * @head:    the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

......

其中 container_of 宏如下：

/**
 * 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.
 *
 */
#define container_of(ptr, type, member) ({            \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

这里使用了GCC特有的 "typeof" 关键字，如果想用其他编译器也想编译通过的话，可以修改成：

#define container_of(ptr, type, member) (            \
        (type *)( (char *)ptr - offsetof(type,member) ) )

为了便于说明，prefetch定义成：

static inline void prefetch(const void *x) {;}

offsetof的一个简单版本：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

好了，让我们看看怎么用：

struct my_data {
    int x;
    int y;
    struct list_head list;
}

/* 链表头 */
LIST_HEAD(my_listhead);

void my_function()
{
    ...
    /* 节点对象 */
    struct my_data *node_1 = (struct my_data *) malloc(sizeof(struct my_data));
    struct my_data *node_2 = (struct my_data *) malloc(sizeof(struct my_data));
    ...
    /* 加入链表 */
    list_add (node_1->list, &my_listhead);
    list_add (node_2->list, &my_listhead);
    ...
    /* 遍历链表 */
    struct my_data * node;
    struct list_head *pos;
    list_for_each (pos, &my_listhead) {
       node = list_entry (pos, struct my_data, list);
       ...
    }

其中最精彩的部分是遍历链表的表达方式：
list_for_each (...) {
...
}
这种表达方式另我想起了Ruby，C++ STL中的到处出现的iterator，和VB中的for each...in...next语句。

从内部结构角度来看，Linux的list实现方式有点类似C++中的"组合类"——在需要放入链表的对象内部放入list类（struct list_head）。但是从遍历链表的时候，可以根据list指针得到包含list节点的对象指针来看，又有点超出了"组合类"的范畴。能否把 struct my_data看成继承了struct list_head呢？从内存映像来看倒有点像（C++子类对象的内存映像是父类对象的超级）。当然，这种强行联系完全没有必要，C就是C，何必去往C+ +套呢？C自有C的表达方式 :D

--THE END--

注：这几篇是我原来在MSN SPACE的老blog，实在受不了MSN SPACE的速度，于是搬到了javaeye。写这些东西，只是想和使用C的同志分享自己的体验，也想告诉新学习C的同志，C语言也是很有魅力的:)

啊 我一直用源自bsd家的queue.h
queue.h貌似更通用并且更强大呢

c当中还有个地方也用到很多oo的思想-网络编程

初步看了一下bsd的queue.h, 确实该有的操作都有了，虽然没实际使用，不过貌似挺不错的。不过，Linux的版本有一个优点，那就是通常使用时把struct list_head嵌入到数据节点中，这样无需为list_head结构本身分配内存，而且利用container_of宏可以方便的根据list_head来获得数据节点的指针，这样使得list_for_each变得非常的自然和优雅。

不知是否可以用queue.h实现个例子我们来看看？



举个例子来看看？

man 3 queue 里面有几个很简单的例子 不过足以说明大概用法了
在内存管理，文件系统，这些地方很多用到queue.h来管理pageing和inode的，可以刨出来看看做参考

网络编程里面最常用的就是cast
mbuf, ip, tcp, udp之间的转换都是靠cast

看宏看得有点懵。
我一般只用宏来定义一些常量，做其他的事情程序可读性就不太好了，使用inline是一个不错的选择

使用文件来封装类，而不是struct更合理一点，因为c中有这些关键字:staic,extern可以实现类的访问控制功能

继承机制可以使用组合来代替

http://xombat.javaeye.com/blog/101300
这里是学数据结构的时候写的一些ADT，绞尽脑汁采用了oo的思想，.h文件中定义接口，而且巧妙的使用void *(可以将void *看成是所有type *的父类），比如：

typedef void * dlist_t;   
typedef const void *const_dlist_t;

这样对用户看，封装了.c中实际的数据结构

如此既实现了数据的封装，也实现了方法的封装。

自我感觉不好的一点是：

 ///////////////////////////////////////////////////   
 //用户可以任意修改结构的定义，除了结构名称。   
 ///////////////////////////////////////////////////   
   
 typedef struct dllElem{   
     int n;   
 }dllElem;   
   
 int dllElem_equal(const dllElem *,const dllElem*);   
   
 ///////////////////////////////////////////////////  

我的目的是提供一个像c++ 中template的功能，使这个ADT中的数据可以是任何对象，但代码好像开始变得晦涩起来

恰恰相反，使用宏来避免“魔数”当然是一个好处不用说了，大多数情况下，宏的使用是为了提高代码可读性的。例如：

struct my_point {
  int x;
  int y;
};

struct my_point *point;

#define WIDTH 640
#define HEIGHT 480

...

if (point->x >= 0 && point->y >= 0 && point->x < WIDTH && point->y < HEIGHT) {
 ...
}

换成如下代码：

#define IS_VALID_POINT(s) (s->x >= 0 && s->y >= 0 && s->x < WIDTH && s->y < HEIGHT)

if (IS_VALID_POINT(point)) {
 ...
}

可读性不是大大提高了么？


另外一个方面，可能使用宏有时侯会使某一部分代码看起来难懂一些，但是其目的是为了使用它的人的代码的可读性更强，我上面提到的linux的linklist.h就是个例子。linklist.h本身可能不容易一下子看透，但是使用linklist.h的代码的可读性就变得非常高，看看那个list_for_each，能使你遍历链表的操作变得如此自然，可以和有些语言内置的foreach语句相媲美！

为了进一步说明问题，我写一个稍微完整的例子来说明Linux内核那个链表操作宏是如何好用：

//定义你的数据结构
struct my_point {
  int x;
  int y;
  struct list_head list;  //嵌入链表管理节点
};


//在这个函数里，产生30个my_point，并且加入链表
void create_my_points(struct list_head *head)
{
  struct my_point *p;
  int x, y;
  
  for (x = 0; x < 10; x++) {
    for (y = 0; y < 3; y++) {
      p = (struct my_point *)malloc(sizeof(struct my_point));
      p->x = x; p->y = y;
      list_add(&p->list, head);
    }
  }
}

//遍历链表，打印信息
void print_list(struct list_head *head)
{
  struct list_head *node;
  struct my_point *p;
  
  list_for_each(node, head) {
    p = list_entry(node, struct my_list, list);
    printf("x = %d, y = %d\n", p->x, p->y);  
  }
}  


//使用：
LIST_HEAD(points_list);   //定义链表头

create_my_points(&points_list);
print_list(&points_list);  

Linux内核的那个链表操作的实现，淋漓尽致地体现了C语言之美，是我所看到的最好的C链表操作实现，C++实现？估计很难有这种优美。

另外，我们可以比较一下xombat的实现（http://xombat.javaeye.com/blog/101300），就可以看出Linux内核的那个实现在使用的时候是有明显的优势：
1. 链表管理节点内嵌入数据节点，这样不用单独的管理节点，好处是：

• 可以减少内存分配次数
• 可以很方便地把静态数据节点加入链表中来。

2. 用宏来实现迭代遍历链表，给予使用者最大的灵活性，代码可读性非常好，同时大大减少使用者的代码

我以前也经常在程序中实现自己的链表操作代码，现在我开始项目写代码的第一件事，就是把Linux下的include/linux/list.h拷贝一份出来到项目的头文件目录！
所以在这里我也劝大家不要再去发明轮子了，因为Linux的list.h这个轮子已经足够圆了

谢谢，我认真去看了看那个list.h文件，领悟了他的思想，感觉确实挺好的。

他的实现跟我的正好相反，我的实现是将数据放在被管理的节点里面，而他的节点是和数据放在同一个container里，然后使用container_of获得他们的container，而管理的时候只需要管理那些节点就可以了，实现起来简单多了，而且扩展性也非常强。

另外如果lz对/usr/include/linux中的头文件熟悉的话，期待楼主写一写对那些文件的介绍，我稍微看了看，感觉那些头文件中的函数还是很实用的，而且封装的也比较好。

贴一下感觉挺nb的代码：
获得member在type(一个struct)中的偏移:

 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)  

可读性强，而且省些好多代码的for_each

 #define list_for_each(pos, head) \  
     for (pos = (head)->next; prefetch(pos->next), pos != (head); \  
             pos = pos->next)