文档章节

C 侵入式数据结构

ylme
 ylme
发布于 2016/05/16 23:38
字数 565
阅读 102
收藏 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
粉丝 11
博文 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
架构设计:系统间通信(31)——其他消息中间件及场景应用(下1)

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

yinwenjie
2016/05/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

11月NEO技术社区开发进展汇总

为了帮助大家了解NEO平台上技术社区的开发进展,NEONewsToday将每月发布一份值得关注的更新报告。这些报告将包括对NEO核心项目的贡献以及对社区创建项目的改进。 这个报告不是包括所有项目进...

NEO-FANS
15分钟前
2
0
flutter FlatButton有间隔

这个按钮上下会有空隙,不是铺满的

大灰狼wow
18分钟前
2
0
WiFi攻击的三种方式

WiFi的安全问题已经引起了不少的使用者重视,甚至已经出现草木皆兵的现象。那么黑客到底是如何做到绕过身份验证来获取WiFi使用权的呢?主要有以下三种方式,其中最后一种方式十分简单。 WiFi...

Linux就该这么学
19分钟前
2
0
添加并发

<!-- 认购线程池,支持最大并发送10 最大排队队列为一万--> <task:executor id="investBuyPool" pool-size="1-10" queue-capacity="10000"/> 方法添加注解@Async("investBuyPool")......

一夜
29分钟前
2
0
Gensim?

Gensim是一款开源的第三方Python工具包,用于从原始的非结构化的文本中,无监督地学习到文本隐层的主题向量表达。它支持包括TF-IDF,LSA,LDA,和word2vec在内的多种主题模型算法,支持流式训...

火力全開
42分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部