文档章节

C 侵入式数据结构

ylme
 ylme
发布于 2016/05/16 23:38
字数 565
阅读 86
收藏 0
c

之前在网上了解到 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 宏获取的偏移值,是不是在编译时就计算出来的呢,还是允许时动态算出来的。

参考

© 著作权归作者所有

共有 人打赏支持
ylme
粉丝 10
博文 40
码字总数 41754
作品 0
广州
程序员
教程 | 用脑电波控制智能假肢:如何利用深度学习技术进行EGG数据分类

  选自TowardsDataScience   作者:Norman Di Palo   机器之心编译   参与:张倩、雪      脑电图是一种利用电极记录大脑活动的非侵入式技术,但大脑活动和脑电图信号之间的关系...

机器之心
06/24
0
0
用脑电波控制智能假肢:如何利用深度学习技术进行EGG数据分类

选自TowardsDataScience,作者:Norman Di Palo,机器之心编译。 脑电图是一种利用电极记录大脑活动的非侵入式技术,但大脑活动和脑电图信号之间的关系非常复杂,如何「解码」成为困扰研究者...

06/25
0
0
序列化介绍

什么是序列化 程序员在编写应用程序的时候往往需要将程序的某些数据存储在内存中,然后将其写入某个文件或是将它传输到网络中的另一台计算机上以实现通讯。这个将程序数据转化成能被存储并传...

botkenni
2016/10/08
35
0
Go接口——基本概念

Go接口——基本概念 Interfaces are named collections of method signatures. 当你有看到一个接口类型时,你不知道它是什么,唯一知道的就是可以通过它的方法来做什么。 C++,Java 使用“侵入...

秋风醉了
2016/07/11
35
0
Hprose PHP 扩展 1.5.5 发布

Hprose PHP 扩展 1.5.5 与时俱进的发布,本次更新增加对新发布的PHP 7.0.0 Alpha 2的支持。 Hprose是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是...

andot
2015/06/26
2.9K
10

没有更多内容

加载失败,请刷新页面

加载更多

github精选:微信小程序开发技巧(12月31日更新)2016

框架部分 所有页面都需要在 app.json 文件中注册在 pages 数组中,注册格式为:"路径/文件名" 注:文件名无需添加扩展名 app.josn 中的 pages 数组中的第一个页面为小程序的启动页 每个页面的...

阿K1225
31分钟前
1
0
OSChina 周日乱弹 —— 小心着凉 @红薯

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:5.33起,其声呜呜然,如怨如慕,如泣如诉。余音袅袅,不绝如缕。分享Arch Enemy的单曲《Bridge Of Destiny (2009)》 《Bridge Of...

小小编辑
今天
343
4
what f,,

anlve
今天
10
0
初级开发-编程题

` public static void main(String[] args) { System.out.println(changeStrToUpperCase("user_name_abc")); System.out.println(changeStrToLowerCase(changeStrToUpperCase("user_name_abc......

小池仔
今天
15
0
现场看路演了!

HiBlock
昨天
28
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部