文档章节

C 侵入式数据结构

ylme
 ylme
发布于 2016/05/16 23:38
字数 565
阅读 67
收藏 0
点赞 2
评论 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
广州
程序员
序列化介绍

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

botkenni ⋅ 2016/10/08 ⋅ 0

Go接口——基本概念

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

秋风醉了 ⋅ 2016/07/11 ⋅ 0

Hprose PHP 扩展 1.5.4 发布

Hprose 是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是一个先进的轻量级的跨语言跨平台面向对象的高性能远程动态通讯中间件。它不仅简单易用,而...

andot ⋅ 2015/05/24 ⋅ 12

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 ⋅ 10

Hprose for Java 1.5.1 发布

Hprose 是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是一个先进的轻量级的跨语言跨平台面向对象的高性能远程动态通讯中间件。它不仅简单易用,而...

andot ⋅ 2015/05/26 ⋅ 4

架构设计:系统间通信(31)——其他消息中间件及场景应用(下1)

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

yinwenjie ⋅ 2016/05/19 ⋅ 0

Hprose for Java 1.5.2 发布

Hprose 是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是一个先进的轻量级的跨语言跨平台面向对象的高性能远程动态通讯中间件。它不仅简单易用,而...

andot ⋅ 2015/06/09 ⋅ 15

Hprose for HTML5 1.5.3 发布

Hprose 是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是一个先进的轻量级的跨语言跨平台面向对象的高性能远程动态通讯中间件。它不仅简单易用,而...

andot ⋅ 2015/05/21 ⋅ 0

Hprose for PHP 1.5.4 发布

Hprose 是高性能远程对象服务引擎(High Performance Remote Object Service Engine)的缩写。 它是一个先进的轻量级的跨语言跨平台面向对象的高性能远程动态通讯中间件。它不仅简单易用,而...

andot ⋅ 2015/05/11 ⋅ 9

其他消息中间件及场景应用(下1)

版权声明:欢迎转载,但是看在我辛勤劳动的份上,请注明来源:http://blog.csdn.net/yinwenjie(未经允许严禁用于商业用途!) https://blog.csdn.net/yinwenjie/article/details/51354773 目...

yunlielai ⋅ 04/15 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

IDEA PermGen space内存溢出

解决方案: File -> Settings -> Build, Execution, Deployment / Build Tools / Maven / Runner下,找到VM Options选项,默认是空的,改为如下内容(或更大值)...

快乐的小火柴 ⋅ 16分钟前 ⋅ 0

前端常见跨域解决方案

什么是跨域? 跨域是指一个域下的文档或脚本试图去请求另一个域下的资源,这里跨域是广义的。 广义的跨域: 1.) 资源跳转: A链接、重定向、表单提交2.) 资源嵌入: <link>、<script>、<im...

临江仙卜算子 ⋅ 16分钟前 ⋅ 0

系统管理命令service

service命令用来控制系统服务的实用工具,例如启动、停止、重启和关闭系统服务,以及当前状态。当然也可以直接操作,例如/etc/init.d/mysqld restart等。 语法 service (选项)(参数) 选项...

Jpchina ⋅ 21分钟前 ⋅ 0

MySQL 联合索引的命中规则

为什么要用联合索引? 对于查询语句“SELECT T.* FROM T WHERE T.c1=1 AND T.c3=2”涉及到两列,这个时候我们一般采用一个联合索引(c1, c3);而不用两个单列索引,这是因为一条查询语句往往应...

hensemlee ⋅ 29分钟前 ⋅ 0

Spring 自动组件扫描

通常情况下都是在XML配置文件中手动声明Bean和组件的。不过Spring也可以自动扫描组件实例化Bean,这样就可以避免在XML文件中繁琐的Bean声明。 手动声明Bean: 这里不再啰嗦,就是简单地在XML...

霍淇滨 ⋅ 33分钟前 ⋅ 0

MapReduce简单需求分析-共同好友及查找互粉的情况

MapReduce的设计,最重要的是要找准key,然后制定一系列的数据处理流程。MapReduce的Map中,会把key相同的分配到同一个reduce中,对于key的选择,可以找到某个相同的因素。以下面的几个例子说...

Jason_typ ⋅ 35分钟前 ⋅ 0

springboot多数据源自动切换

SpringBoot多数据源切换,先上配置文件: 1.pom: <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20......

JackyRiver ⋅ 37分钟前 ⋅ 0

Boost库编译应用

版本:Boost 1.66.0 Windows库编译 官网指南:直接执行bootstrap.bat处理文件即可,可以我却遇到一堆的问题。 环境:Windows 10 + Visual Studio 2017 Boost编译出来库命名 boost库生成文件命...

水海云 ⋅ 42分钟前 ⋅ 0

解决Eclipse发布到Tomcat丢失依赖jar包的问题

如果jar文件是以外部依赖的形式导入的。Eclipse将web项目发布到Tomcat时,是不会自动发布这些依赖的。 可以通过Eclipse在项目上右击 - Propertics - Deployment Assembly,添加“Java Build ...

ArlenXu ⋅ 42分钟前 ⋅ 0

iview tree组件层级过多时可左右滚动

使用vue+iview的tree组件,iview官网iview的tree树形控件 问题描述:tree层级过多时左右不可滚动 问题解决:修改overflow属性值 .el-tree-node>.el-tree-node_children { overflow: vi...

YXMBetter ⋅ 44分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部