C 侵入式数据结构
C 侵入式数据结构
吃辣不放糖 发表于2年前
C 侵入式数据结构
  • 发表于 2年前
  • 阅读 58
  • 收藏 0
  • 点赞 2
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: 以一个简单的单向链表为例,来了解 Linux 内核开发中用到的侵入式数据结构。

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

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

  • 实现一个简单的单向链表。
  • 然后模拟一个游戏的背包实现。添加道具到背包,然后遍历背包中的道具,最后销毁道具。
  • 我在 mingw 上测试的,若是在 Linux 上编译不过去,可以试试 -std 选项。
/**
 * 采用侵入式数据结构,实现一个简单的单向链表。
 * gcc -o test test.c
 */
#include <stdio.h>
#include <stdlib.h>

//////////////////////////////////////////////////////////////
// 链表的实现 
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;
}

思考

  • 侵入式链表中的节点并未包含具体的数据,又是如何获取到数据的呢?
  • offsetof 宏获取的偏移值,是不是在编译时就计算出来的呢,还是允许时动态算出来的。

参考

标签: c
共有 人打赏支持
粉丝 10
博文 33
码字总数 35341
×
吃辣不放糖
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: