C 侵入式数据结构-白红宇

C 侵入式数据结构

阅读量：6675 次

发布时间：2019-06-25

本文共 2289 字，大约阅读时间需要 7 分钟。

之前在网上了解到 Linux 内核开发时用的是侵入式（intrusive）数据结构，就想了解下。然后读了这篇介绍 Linux 内核中用到的双向链表实现的。

看完那篇博客后，就想自己写个小例子感受下。

实现一个简单的单向链表。

然后模拟一个游戏的背包实现。添加道具到背包，然后遍历背包中的道具，最后销毁道具。

我在 mingw 上测试的，若是在 Linux 上编译不过去，可以试试 -std 选项。

/** * 采用侵入式数据结构，实现一个简单的单向链表。 * gcc -o test test.c */#include 
    
     #include 
     
      //// 链表的实现 struct list_head {	struct list_head *next;};#define LIST_HEAD_INIT(name) { &(name) }#define LIST_HEAD(name) \	struct list_head name = LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list) {	list->next = list;}static inline void list_add(struct list_head *new, struct list_head *head) {	new->next = head->next;	head->next = new;}// 对外接口// #define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );}) // 采用 typeof 编译不过#define list_entry(ptr, type, member) container_of(ptr, type, member)#define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)// 内部接口#define container_of(ptr, type, member) ({ \	const __auto_type __mptr = (ptr); \	(type *)( (char *)__mptr - offsetof(type,member) );})#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)//// 游戏中背包的道具。struct item_info {	struct list_head list;	int id;};static LIST_HEAD(items);// 向背包中添加一个道具。void additem(int id) {	struct item_info *item = (struct item_info*)malloc(sizeof(struct item_info));	INIT_LIST_HEAD(&item->list);	item->id = id;	list_add(&item->list, &items);}int main(int argc, char *argv[]) {	int count = 0;	additem(200);	additem(300);	additem(0);	struct item_info *nouse_item = NULL;	struct list_head *pos = NULL, *nouse = NULL;	list_for_each(pos, &items) {		if (nouse) { // 要在本循环销毁上一个循环获取的道具			nouse_item = list_entry(nouse, struct item_info, list);			printf("\nfree one item:%d\n", nouse_item->id);			free(nouse_item);		}		count++;		struct item_info *info = list_entry(pos, struct item_info, list);		printf("id:%d ", info->id);		nouse = pos;	}	if (nouse) {		nouse_item = list_entry(nouse, struct item_info, list);		printf("\nfree the last item:%d\n", nouse_item->id);		free(nouse_item);	}	printf("total count:%d\n", count);	return 0;}