刷OJ的时候惊喜的发现，我竟然不会给二维数组动态分配内存。写了n年的代码了，竟然被这个难倒了！自惭形秽，难以言表。

方法一

先分配指针数组的内存，然后给数组中的每个int *指针分配内存：

int **data, i;
data = (int *)malloc(sizeof(int *) * row);

for (i = 0; i < row; i++) {
    data[i] = (int *)malloc(sizeof(int) * col);
}

数组的表现形式：

方法二

使用一维指针模拟成二维指针，分配row * col个连续的元素，访问的时候模拟成二维指针访问：

data = (int *)malloc(sizeof(int) * row * col);

for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) {
        *(data + i * col + j) = i * j;
    }
}

参考

How to dynamically allocate a 2D array in C?

linux内核中的container_of函数

一、container_of的用途

众所周知，linux内核是用C写的，并且内核中是存在许多数据结构的，栈、链表、哈希表以及红黑树等等。但是C语言中一个致命的缺点就是没有泛型，没有泛型的话所有的数据结构就无法通过一套代码来实现。那有没有办法可以使得这些数据结构成为通用的呢？答案肯定是有的，不然如果每个结构体都要实现一套自己的链表，内核将会变得臃肿、复杂且不好维护。要知道C语言虽然没有泛型，但是它有指针，实现内核的大佬们就通过指针来实现了属于C的泛型。

以链表为例，首先定义一个全局通用的链表节点：

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

节点中只包含了prev和next两个成员，不含有任何数据内容。所有的数据内容都要另外再定义结构体，把这个链表节点包含进来，再通过这个链表节点实现链表移动。例如实现一个lru缓存节点的链表：

struct lru_cache {
    int page_addr;
    struct list_node ln;
}

数据节点说的是lru_cache结构类型的节点，链表节点是lru_cache中ln成员节点。

它通过ln元素串起来的数据形式为：

图片看起来很好理解，关键的问题就在于如何通过这个节点来组成链表，以及如何通过这个链表节点找到本身的数据节点呢？这便是container_of发挥作用的时候了。

container_of的作用就是给定结构体类型和数据成员名返回结构体本身的地址，它需要三个参数：

数据节点指针，表示当前某个数据节点中的链表节点地址，即某个lru_cache节点中ln的地址。
当前数据节点的数据类型，即struct lru_cache这个结构体。
链表节点在数据节点中的名字，即ln。

假设ptr是某个节点中ln元素的地址，那么通过container_of(ptr, struct lru_cache, ln)就能得到这个节点的地址了。通过它来完成一次节点遍历的过程可以描述为：

struct list_node *p = head;
struct lru_cache *lru_node;
while (p) {
    lur_node = container_of(ptr, struct lru_cache, ln);
    // 处理节点
    // print(lru_node);
    // ...
    
    p = p->next == head ? NULL : p->next;
}

二、container_of的实现

container_of的宏定义：

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

宏定义有三个变量，展开后一共有两行语句：

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

这两行语句的解析：

先通过传入的type生成一个该类型的指针，(type *)0表示指向NULL的type类型的指针，假设这个指针为p，语句就变成了：

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

然后定义一个链表节点类型的指针__mptr指向ptr，因为不知道ptr的数据类型，所以要通过typeof (p->member)得到数据类型。此时__mptr的指向是：

因此，到这里想要得到lru_cache的地址，只要把__mptr的地址减去ln成员在结构体中的偏移就行了。

这也正是第二个语句的作用：先通过offset_of获取到偏移，再通过(char *)强制转换__mptr的数据类型，使得它的步长是1。最后减去偏移就得到数据节点的地址。

标签 c语言下的文章

如何在c语言中动态分配二维数组