16、基于共享内存二叉树的LRU

devtools/2024/9/19 6:08:53/ 标签: 共享内存, 数据结构, LRU

初级代码游戏的专栏介绍与文章目录-CSDN博客

我的github：codetoys，所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。

这些代码大部分以Linux为目标但部分代码是纯C++的，可以在任何平台上使用。

        在共享内存的二叉树上尝试了LRU，思路很简单，通过重新定义HANDLE，所需的节点不在共享内存则从文件读取，如果满了就把访问队列里最长时间没有被访问的节点换出去。

        先说结论：对于二叉树毫无意义，想寻求LRU解决方案就不用往下看了。

目录

一、头结构

二、节点结构

三、句柄结构

LRU%E4%BB%A3%E7%A0%81-toc" style="margin-left:0px;">四、LRU代码

五、解释

        主要的意义是作为编程技巧的练习，如何巧妙地通过对一个对象的重新定义来改变整个容器的行为。

一、头结构

        由于是基于二叉树模板来实现，所以增加的节点链表放在二叉树的USER_HEAD里面：

#define LRU_HEAD_VIRTUAL_SET_HEAD_SIZE 1024struct T_USER_HEAD_LRU{T_SHM_SIZE head_FLRU;//访问过的节点的链表T_SHM_SIZE head_MLRU;//修改过的节点的链表char vitrual_set_head[LRU_HEAD_VIRTUAL_SET_HEAD_SIZE];//虚拟SET的HEADT_USER_HEAD_LRU():head_FLRU(-1),head_MLRU(-1){}string & toString(string & str)const{char buf[2048];sprintf(buf,"head_FLRU %ld , head_MLRU %ld",head_FLRU,head_MLRU);return str=buf;}};

二、节点结构

        节点其实就是链表：

	template<typename T >struct T_DATA_LRU : public CActiveObjectBase{T_SHM_SIZE handle;T_SHM_SIZE next_FLRU; T_SHM_SIZE next_MLRU; T data;bool operator < (T_DATA_LRU const & tmp)const{return handle<tmp.handle;}string & toString(string & str)const{char buf[2048];sprintf(buf,"h=%ld next_FLRU=%ld data=",handle,next_FLRU);return str=buf+data.toString(str);}};

        handle是二叉树的句柄。

三、句柄结构

        句柄是核心：

	template<typename T,int PI_N >struct T_HANDLE_LRU{typedef T_DATA_LRU<T > T_DATA_BUFFER;//缓存结构typedef T_SHMSET_NO_MUTEX<T_DATA_BUFFER,PI_N,T_USER_HEAD_LRU > T_SET_LRU_BUFFER;//缓存容器T_SHM_SIZE handle;T_HANDLE_LRU(T_SHM_SIZE h=-1):handle(h){}T_HANDLE_LRU & operator ++ (){++handle;return *this;}T_HANDLE_LRU & operator = (T_HANDLE_LRU const & tmp){handle=tmp.handle;return *this;}bool operator == (T_HANDLE_LRU const & tmp)const{return handle==tmp.handle;}bool operator != (T_HANDLE_LRU const & tmp)const{return !((*this)==tmp);}T & operator * ()const{return * operator ->();}T * operator -> ()const{if(0==PI_N)throw "SHM PI_N=0";//thelog<<"进入T_HANDLE_LRU -> handle="<<handle<<endi;T_SET_LRU_BUFFER * pLRUBuffer=(T_SET_LRU_BUFFER *)GET_PP_LRU(PI_N);typename T_SET_LRU_BUFFER::const_iterator it;T_DATA_BUFFER tmp;tmp.handle=handle;string str;//pLRUBuffer->Report();it=pLRUBuffer->find(tmp);if(it==pLRUBuffer->end()){if(pLRUBuffer->capacity()<=pLRUBuffer->size()){STATIC_G bool exchange=false;if(exchange){thelog<<"LRU置换重入"<<endi;throw "LRU置换重入";}else exchange=true;//throw exception_my(__FILE__,__LINE__,"空间已满，需要LRU置换");//thelog<<"空间已满，需要LRU置换 "<<handle<<endi;//pLRUBuffer->Report();//找最久没有访问的并替换出去T_SHM_SIZE flru=pLRUBuffer->GetUserHead()->head_FLRU;it.handle=flru;while(it->next_FLRU>=0){flru=it.handle;it.handle=it->next_FLRU;}//现在it指向最久没有访问的节点，flru指向前一个//thelog<<"最久没有被访问的是　"<<it.handle<<" ；逻辑节点 "<<it->handle<<endi;CStdOSFile f;string file;file=pLRUBuffer->GetName();file+=".lru";if(!f.OpenRW(file.c_str())){thelog<<"打开文件失败 "<<file<<ende;throw exception_my(__FILE__,__LINE__,"打开文件失败");}f.SeekEnd();long f_length=f.Tell();long pos=LRU_HEAD_VIRTUAL_SET_HEAD_SIZE+it->handle*sizeof(T);if(pos>=f_length){//补足文件长度for(long tmpi=f_length;tmpi<pos;++tmpi)f.Write("\0",1);}//将最久没有访问的那个写出去并从共享内存删除f.SeekBegin(pos);if(!f.Write(&it->data,sizeof(T)))throw exception_my(__FILE__,__LINE__,"写文件失败");//thelog<<it->data.toString(str)<<endi;pLRUBuffer->erase(it);f.Close();it.handle=flru;it->next_FLRU=-1;//pLRUBuffer->Report();exchange=false;}//已经确保有了一个可用空间，检查是否节点已经在文件中，若在则读入{CStdOSFile f;string file;file=pLRUBuffer->GetName();file+=".lru";if(!f.OpenRW(file.c_str())){thelog<<"打开文件失败 "<<file<<ende;throw exception_my(__FILE__,__LINE__,"打开文件失败");}f.SeekEnd();long f_length=f.Tell();long pos=LRU_HEAD_VIRTUAL_SET_HEAD_SIZE+handle*sizeof(T);if(pos<f_length){//将文件中的内容读入f.SeekBegin(pos);if(!f.Read((char *)&tmp.data,sizeof(T)))throw exception_my(__FILE__,__LINE__,"读文件失败");//thelog<<tmp.data.toString(str)<<endi;}f.Close();tmp.next_FLRU=pLRUBuffer->GetUserHead()->head_FLRU;it=pLRUBuffer->insert(tmp).first;pLRUBuffer->GetUserHead()->head_FLRU=it.handle;//pLRUBuffer->Report();}}if(it!=pLRUBuffer->end()){return &it->data;}else{return NULL;}}static T_SHM_SIZE _me(T const * p){T_DATA_BUFFER tmp;T_DATA_BUFFER * plru;plru=(T_DATA_BUFFER *)((char *)p-((char *)&(tmp.data)-(char *)&tmp));return plru->handle;}static void ShowVMapPrivateData(){thelog<<"ShowVMapPrivateData未定义"<<ende;}};

LRU%E4%BB%A3%E7%A0%81">四、LRU代码

        主体代码：

	template<typename T_DATA,int PI_N,typename T_USER_HEAD=CDemoData,int VER=0 >class T_SHMLRU : public T_SHMSET<T_DATA,PI_N,T_USER_HEAD,0,VER,T_HANDLE_LRU<T_TREE_NODE_STRUCT<T_DATA > ,PI_N > >{public:typename T_HANDLE_LRU<T_TREE_NODE_STRUCT<T_DATA > ,PI_N >::T_SET_LRU_BUFFER m_LRUBuffer;typedef T_SHMSET<T_DATA,PI_N,T_USER_HEAD,0,VER,T_HANDLE_LRU<T_TREE_NODE_STRUCT<T_DATA > ,PI_N > > T_SET_PARENT;//父类型typedef typename T_SET_PARENT::iterator iterator;public:using T_SET_PARENT::capacity;using T_SET_PARENT::size;using T_SET_PARENT::GetName;T_SHMLRU(char const * name, int version) :T_SET_PARENT((string(name) + "_V").c_str(), version), m_LRUBuffer(name, version){GET_PP_LRU(PI_N)=&m_LRUBuffer;}T_SHMLRU(char const * name):T_SET_PARENT((string(name)+"_V").c_str(),VER),m_LRUBuffer(name,VER){GET_PP_LRU(PI_N)=&m_LRUBuffer;}pair<iterator, bool> insert(T_DATA const & data){if(capacity()==size()){SetVirtualCapacity(capacity()+1);}return T_SET_PARENT::insert(data);}public://IShmActiveObjectvirtual bool CreateShm(){if(sizeof(typename T_SET_PARENT::TREE_HEAD)>LRU_HEAD_VIRTUAL_SET_HEAD_SIZE){thelog<<"LRU_HEAD_VIRTUAL_SET_HEAD_SIZE "<<LRU_HEAD_VIRTUAL_SET_HEAD_SIZE<<" 不足，至少需要 "<<sizeof(typename T_SET_PARENT::TREE_HEAD)<<ende;return false;}bool ret=m_LRUBuffer.CreateShm() && m_LRUBuffer.Attach(false) && T_SET_PARENT::set_CreateShm_virtual(m_LRUBuffer.GetUserHead()->vitrual_set_head);if(!ret)return ret;//保存数据头CStdOSFile f;string file;file=m_LRUBuffer.GetName();file+=".lru";if(!f.OpenW(file.c_str())){thelog<<"打开文件失败 "<<file<<ende;return false;}if(LRU_HEAD_VIRTUAL_SET_HEAD_SIZE!=f.Write((char *)T_SET_PARENT::GetTreeHead(),LRU_HEAD_VIRTUAL_SET_HEAD_SIZE)){thelog<<"写文件头失败 "<<file<<ende;return false;}f.Close();m_LRUBuffer.Detach();return true;}virtual bool _Attach(bool isReadOnly){return m_LRUBuffer.Attach(isReadOnly) && T_SET_PARENT::set_AttachToShm_virtual(m_LRUBuffer.GetUserHead()->vitrual_set_head);}virtual bool Detach(){return m_LRUBuffer.Detach();}virtual bool LoadFromDir(char const * dir_name){thelog<<GetName()<<" IShmActiveObject::LoadFromDir 尚未支持"<<ende;return false;}virtual bool SaveToDir(char const * dir_name)const{thelog<<GetName()<<" IShmActiveObject::SaveToDir 尚未支持"<<ende;return false;}virtual bool Report()const{string str;thelog<<T_SET_PARENT::Report_virtual(str)<<endi;return  m_LRUBuffer.Report();}};

五、解释

        你现在问我这个模板咋工作的，我得花些时间重新想想，但是当初绝对是可以工作的。

（这里是结束）


http://www.ppmy.cn/devtools/61379.html

相关文章

Docker安装ELK（简易版）

Docker安装ELK（简易版）

1、下载ELK镜像&#xff1a;打开终端&#xff0c;并执行以下命令以下载Elasticsearch、Logstash和Kibana的Docker镜像。您也可以根据需要选择其他版本&#xff1a; docker pull docker.elastic.co/elasticsearch/elasticsearch:7.17.6 docker pull docker.elastic.co/logstash…
阅读更多...
R语言进行K折交叉验证问题

R语言进行K折交叉验证问题

在使用R语言进行模型参数评估优化时候，会使用K折交叉验证，其中会遇到各种各样问题： 错误: C5.0 models require a factor outcome > (1-mean(E0));(1-mean(E1)) [1] 1 [1] 1 报错说明C5.0模型需要因子变量输出，源代码如下： ### 10折交叉验证 ### # 导入car数据集 c…
阅读更多...
web前端 React 框架面试200题（三）

web前端 React 框架面试200题（三）

面试题 65. 在使用 React Router时&#xff0c;如何获取当前页面的路由或浏览器中地址栏中的地址&#xff1f; 参考回答&#xff1a; 在当前组件的 props中&#xff0c;包含 location属性对象&#xff0c;包含当前页面路由地址信息&#xff0c;在 match中存储当前路由的参数等…
阅读更多...
鼠标录制工具怎么挑选？9款电脑鼠标录制工具分享（2024）

鼠标录制工具怎么挑选？9款电脑鼠标录制工具分享（2024）

你知道鼠标录制工具吗&#xff1f;鼠标录制工具通过记录和回放用户的操作&#xff0c;帮助自动化重复性任务&#xff0c;提高工作效率和精确性。它可以帮助用户简化很多繁琐的操作步骤&#xff0c;非常适合运用在电脑自动化任务、游戏自动化中&#xff0c;给大家整理了2024年9款…
阅读更多...
解决selenium打印保存为PDF时图片未加载成功的问题

解决selenium打印保存为PDF时图片未加载成功的问题

使用selenium打印网页时&#xff0c;如果程序运行很快的话&#xff0c;可能会导致图片没有加载成功即进行了保存&#xff0c;出现这个问题最初的思考是在执行打印任务时使用js进行强制等待&#xff0c;后发现实现效果并不好。在加载页面时使用自动下滑的方式将网页拉到底&#…
阅读更多...
游戏中的敏感词算法初探

游戏中的敏感词算法初探

在游戏中起名和聊天需要服务器判断是否含有敏感词&#xff0c;从而拒绝或屏蔽敏感词显示&#xff0c;这里枚举一些常用的算法和实际效果。 1.字符串匹配算法 常用的有KMP&#xff0c;核心就是预处理出next数组&#xff0c;也就是失配信息&#xff0c;时间复杂度在O(mn) 。还有个…
阅读更多...
ASPICE在汽车软件开发中的作用

ASPICE在汽车软件开发中的作用

ASPICE是一个专门为汽车软件开发过程而设计的评估和改进框架。它基于ISO/IEC 15504标准&#xff0c;为汽车供应商提供了一个评估和改进其软件开发流程的方法。ASPICE的目标是确保软件开发过程的一致性和可预测性&#xff0c;从而提高软件的质量和可靠性。 ASPICE的实施对汽车软…
阅读更多...
FPGA学习笔记(一) FPGA最小系统

FPGA学习笔记(一) FPGA最小系统

文章目录 前言一、FPGA最小系统总结 前言 今天学习下FPGA的最小系统一、FPGA最小系统 FPGA最小系统与STM32最小系统类似&#xff0c;由供电电源&#xff0c;时钟电路晶振&#xff0c;复位和调试接口JTAG以及FLASH配置芯片组成&#xff0c;其与STM32最大的不同之处就是必须要有…
阅读更多...
Leetcode做题记录（第一天）----560

Leetcode做题记录（第一天）----560

560 和为K的子数组 标签&#xff1a;数组&#xff0c;哈希表&#xff0c;前缀和 题目&#xff1a; 题目要求返回数组中和为k的连续子数组的个数&#xff0c; 首先我们可以想想暴力做法&#xff1a; 挨个作为起点&#xff0c;然后往后推&#xff0c;一直到结尾&#xff0c;和…
阅读更多...
网络协议-SOTP 协议格式

网络协议-SOTP 协议格式

SOTP&#xff08;Secure Overlay Transport Protocol&#xff09;是一种安全的覆盖层传输协议&#xff0c;旨在提供增强的安全性和功能。尽管 SOTP 不是一个广泛标准化的协议&#xff0c;其具体实现和格式可能会因应用而异&#xff0c;但一般来说&#xff0c;SOTP 协议格式会包…
阅读更多...
全网最最实用--基于Mac ARM 芯片实现操作系统MIT 6.S081-lab9

全网最最实用--基于Mac ARM 芯片实现操作系统MIT 6.S081-lab9

文章目录 实验九 文件系统一、代码理解1.文件系统实现&#xff08;Blocks、Log、Files、 Directories、Names&#xff09;a. 磁盘布局b. 超级块&#xff08;Superblock&#xff09;c. 魔数&#xff08;Magic Number&#xff09;d. 直接和间接块e. 磁盘 inode 结构&#xff08;D…
阅读更多...
【Golang 面试基础题】每日 5 题（二）

【Golang 面试基础题】每日 5 题（二）

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏…
阅读更多...
【MySQL-17】存储过程-[变量篇]详解-(系统变量＆用户定义变量＆局部变量）

【MySQL-17】存储过程-[变量篇]详解-(系统变量＆用户定义变量＆局部变量）

前言 大家好吖&#xff0c;欢迎来到 YY 滴MySQL系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的《Lin…
阅读更多...
Modbus转BACnet/IP网关的技术实现与应用

Modbus转BACnet/IP网关的技术实现与应用

引言 随着智能建筑和工业自动化的快速发展&#xff0c;不同通信协议之间的数据交换也变得日益重要。Modbus和BACnet/IP是两种广泛应用于自动化领域的通信协议&#xff0c;Modbus以其简单性和灵活性被广泛用于工业自动化&#xff0c;而BACnet/IP则在楼宇自动化系统中占据主导地…
阅读更多...
Windows图形界面(GUI)-DLG-C/C++ - 列表视图(ListView)

Windows图形界面(GUI)-DLG-C/C++ - 列表视图(ListView)

公开视频 -> 链接点击跳转公开课程博客首页 -> ​​​​​​链接点击跳转博客主页 目录 列表视图(ListView) 控件类型 初始化控件环境 示例代码 列表视图(ListView) 控件类型 详细信息视图&#xff08;Report View&#xff09;&#xff1a;数据以列的形式显示&…
阅读更多...
PostgreSQL创建表和自增序列

PostgreSQL创建表和自增序列

一、创建表&#xff1a; 注意&#xff1a; 1、在mysql没有序列的概念&#xff0c;id自增通过auto_increment实现&#xff1b; 2、pgsql没有auto_increment的概念&#xff0c;如何实现id自增&#xff1f;有两种方式&#xff1a; 方式一&#xff1a;创建序列&#xff0c;绑定…
阅读更多...
[iOS]浅析isa指针

[iOS]浅析isa指针

[iOS]浅析isa指针 文章目录 [iOS]浅析isa指针isa指针isa的结构isa的初始化注意事项 上一篇留的悬念不止分类的实现 还有isa指针到底是什么 它是怎么工作的 class方法又是怎么运作的 class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags 这里面的class又是何方…
阅读更多...
Scala学习笔记18: Either 类型

Scala学习笔记18: Either 类型

目录 第十八章 Either 类型1- Either 语义: 两种可能的容器2- 创建 Either 实例3- Either 用法3.1 模式匹配3.2 fold 方法3.3 函数式操作3.4 与其他类型的结合 4- 总结end 第十八章 Either 类型 Either 类型是Scala函数式编程中处理可能失败操作的重要工具 ; 它提供了一种类型…
阅读更多...
Kafka - 生产者

Kafka - 生产者

生产者消息对象 public class ProducerRecord<K, V> {private final String topic; // 主题private final Integer partition; //分区号private final Headers headers; //消息头部private final K key; //键private final V value; //值private final Long timestamp; …
阅读更多...
园区AR导航系统构建详解：从三维地图构建到AR融合导航的实现

园区AR导航系统构建详解：从三维地图构建到AR融合导航的实现

随着现代园区规模的不断扩大与功能的日益复杂&#xff0c;传统的二维地图导航已难以满足访客高效、精准定位的需求。园区内部错综复杂的布局、频繁变更的商户位置常常让访客感到迷茫&#xff0c;造成寻路上的时间浪费。园区AR导航系统以创新的技术手段&#xff0c;破解了私域地…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站