[数据结构][LINUX内核编程]学习笔记（一）

浏览数：19 / 时间：2015年06月20日

linux内核使用bitmap相关
1,声明一个bitmap数组,可以表示100个bit，数组名字是bitmap

[cpp] view plain copy

DECLARE_BITMAP(bitmap,100)

相关宏定义如下：

[cpp] view plain copy

#define DECLARE_BITMAP(name,bits) unsigned long name[BITS_TO_LONGS(bits)]
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr,BITS_PER_BYTE*sizeof(long))
#define DIV_ROUND_UP(n,d) (((n)+(d)-1)/(d))
#define BITS_PER_BYTE 8

2,使用以上定义的bitmap数组
检测bitmap某一位是否为1，用test_bit()函数，如检测第一个bit，则调用test_bit(0,bitmap)

[cpp] view plain copy

static int test_bit(unsigned int nr,const unsigned long *addr)
{
return ((1UL<<(nr%BITS_PER_LONG))&(((unsigned*)addr)[nr/BITS_PER_LONG])) !=0)
}
#define BITS_PER_LONG 32

使用实例：bootmem分配器~~

内核使用双向链表相关

[cpp] view plain copy

struct list_head{
struct list_head *next;
struct list_head *priv;
};

list_entry()函数可以返回包含双向链表的结构，指针ptr指向结构体type中的member成员，通过ptr返回结构体type的起始地址

[cpp] view plain copy

#define list_entry(ptr,type,member) container_of(ptr,type,member)

[cpp] view plain copy

list_add(struct list_head *new ,struct list_head *head)

该函数向指定链表的head节点后插入new节点，

[cpp] view plain copy

list_for_each_entry(pos,head,member)

pos是一个指向包含list_head节点对象的指针，可以看成是list_entry()返回的值，head是遍历开始的位置，

[cpp] view plain copy

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

第一步，首先定义一个临时的数据类型（通过typeof( ((type *)0)->member )获得）与ptr相同的指针变量__mptr，然后用它来保存ptr的值。第二步，用(char *)__mptr减去member在结构体中的偏移量，得到的值就是整个结构体变量的首地址（整个宏的返回值就是这个首地址）。

typeof的解释如下：

[cpp] view plain copy