文档章节

C 侵入式数据结构

ylme
 ylme
发布于 2016/05/16 23:38
字数 565
阅读 80
收藏 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
博文 39
码字总数 40752
作品 0
广州
程序员
用脑电波控制智能假肢:如何利用深度学习技术进行EGG数据分类

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

06/25
0
0
教程 | 用脑电波控制智能假肢:如何利用深度学习技术进行EGG数据分类

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

机器之心
06/24
0
0
序列化介绍

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

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

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

秋风醉了
2016/07/11
35
0
架构设计:系统间通信(31)——其他消息中间件及场景应用(下1)

接上文:《架构设计:系统间通信(30)——Kafka及场景应用(中3)》 5、场景应用——电商平台:浏览记录收集功能 事件/日志收集系统是大中型软件不得不面对的话题。目前第三方业务系统对 事...

yinwenjie
2016/05/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vue+element-ui操作删除(单行和批量删除)

页面展示: <template><!-- 表格内容 --><el-table :data="packData" border style="width: 100%" ref="multipleTable" @selection-change="handleSelectionChange"><el-tab......

琴妹
8分钟前
0
0
基于vue(element ui) + ssm + shiro 的权限框架

zhcc 基于vue(element ui) + ssm + shiro 的权限框架 引言 心声 现在的Java世界,各种资源很丰富,不得不说,从分布式,服务化,orm,再到前端控制,权限等等玲琅满目,网上有句话说,语言框架...

DarrenHu_吴邪
15分钟前
0
1
数据库水平切分(MyCat分片)

范围分片 io.mycat.route.function.AutoPartitionByLong 自动范围分片 Function名称:rang-long(配置文件默认) 枚举分片 io.mycat.route.function.PartitionByFileMap 枚举分片 Funtion名称...

这很耳东先生
16分钟前
0
0
读《HeadFirst设计模式》笔记之外观模式

外观模式:提供了一个统一的接口,用来访问子系统中的一群接口。外观定义了一个高层接口,让子系统更容易使用。 举个栗子: 建了一个家庭影院,但是每次享受家庭影院时,你发现需要执行 将灯...

suyain
17分钟前
0
0
MongoDB分片配置

简单注解: mongos 路由进程, 应用程序接入mongos再查询到具体分片,监听端口默认27017 config server 路由表服务, 每一台都具有全部chunk的路由信息 shard为数据存储分片, 每一片都可以是...

LUIS1983
25分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部