C 侵入式数据结构

Wesley13
• 阅读 698

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

参考

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
3年前
Linux查看GPU信息和使用情况
1、Linux查看显卡信息:lspci|grepivga2、使用nvidiaGPU可以:lspci|grepinvidia!(https://oscimg.oschina.net/oscnet/36e7c7382fa9fe49068e7e5f8825bc67a17.png)前边的序号"00:0f.0"是显卡的代
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这