第17章OSPF路由协议的软件模拟与设计要点

1、第17章 OSPF路由协议的软件模拟与设计第 17 章 OSPF 路由协议的软件模拟与设计Internet 是一个分组交换网络，一个源节点应用程序所产生的数据分组要到达目的节点的 对等层应用程序， 通常要经过若干中间交换节点的转发中继， 除非源和目的节点既在同一条数 据链路上又在同一个子网中。 如果转发设备是路由器或三层交换机， 则设备中的数据链路层协 议负责将待转发数据帧沿给定的数据链路传递到相邻的下一个节点， 而网络层协议则要负责路 由选择，即从可达目的节点的多条转发链路中选择出一条最佳的数据链路。路由有两种类型： 静态路由和动态路由。静态路由即网络管理员手工配置的路由，这种路由有两个主要

2、的缺陷： 一个是不能对路由设备或链路的失效以及网络拓扑的变化做出反应， 一个是不适合于具有复杂 拓扑结构的大规模网络（可扩展性） 。因此，当需要管理的网络不是小型网络时，就需要使用 动态路由。动态路由是路由选择协议根据网络中所有路由器及其接口链路的当前状态自动计算 生成的。 路由选择协议能够自动检测路由设备及其接口链路的状态，能够自动适应网络拓扑的变化。开放最短路径优先协议（ OSPF， Open Shortest Path First ）是一个基于链路状态算法、适 合大型复杂网络、 具有高效健壮特性的动态内部网关协议 （工业上将路由器被称为网关） 。“开 放最短路径优先” 的名字来源于以下事

3、实： （ 1）这个协议基于 Dijkstra 的最短路径优先 （ SPF， Shortest Path First）路由算法。（2）"开放”反映了这个标准是开放的标准而不是一个私有的标 准，这与一系列由特定厂商专有的或专用于某种特定网络的链路状态协议形成了对比，如 Novell Netware 的链路服务协议 NLSP（Netware Link Servise Protocol ）、IBM SNA 的高级对等 网络协议 APPN（Advanced Peer-to-Peer Networking ）和 ATM 的专用网间接口协议 PNN（I Private Network-to-Net

4、work Interace ）。作为开放和通用标准运动的主要倡议者 DEC 公司为该协议 做了最初的大部分工作，并把它作为了私有产品 DECnet 体系结构的一部分。OSPF起源于1979年Bolt、Bera nek和Newma n公司为ARPANET开发的“新的实验性路 由算法”以及随后 ISO 为 OSI 开发的 IS-IS 路由协议，是 John T. Moy 等人在 1987 年为克服 RIP 协议耗费带宽资源多、 应对链路故障或拓扑变化收敛速度慢、 适应树状拓扑结构难等缺点 而开发的。OSPF最初的其它功能需求还包括：（1）采用更具描述性的路由度量值，以摆脱RIP 协议网络直径最大

5、15 个路由器跳步的限制，以及可以将延时、带宽等其它路由度量因素考虑进来。（ 2 ）可利用等代价的多条路径，以达到均衡负载等转发策略。（3）具有路由选择的层次结构，以适应大规模复杂网络以及树状层次网络拓扑结构。（4）支持更灵活的子网化技术，以适应变长子网掩码以及更进一步的无类别域间路由。（5）保证安全性，避免伪路由器通过发布默认或其它路由而使路由选择过程陷入混乱。（ 6）为保证可信性而区分内部和外部路由信息，内部路由信息可覆盖外部路由信息。虽然OSPF还支持基于服务类型 TOS的路由选择，允许为每个不同的 TOS配置不同的链 路度量值并建立不同的路由表，但基于 TOS的路由选择从未在In te

6、rnet上流行。OSPF的各个 版本间是不兼容的。 第 1 版的 RFC 1131 定义于 1989年， 目前的第 2版在 RFC 2328 中有详细说明，1999年12月，IETF发布了基于IPv6的OSPF标准RFC2740，并称之为 0SPFv3。17.1对等层协议模拟基础知识17.1.1标识符命名和编写规范标识符命名和编写规范为了使程序易于理解和维护，在一个项目中的代码编写要遵循统一的规范。由于这种规范并不是强制的，因此，有时也将其称为风格。 在此只对本章程序代码中结构、类、函数、变量、常量等标识符在命名时所遵循的规范和保持的风格进行说明。标识符命名有两种风格：Unix风格和 Wind

7、ows风格。以网络接口数据结构为例，按照两种风格定义的数据结构比较如下：Network In terface ）的Unix风格struct ifnet struct ifnet*if_ next;struct ifaddr *if_addrlist; char*if_ name;Windows 风格 struct IfNet struct IfNet*struct IfAddr*char*m_pNext; m_pAddrList; m_szName;struct ifqueue struct mbuf *ifq_head;struct IfQueuestruct Mbuf* m_pHead i

8、f_sndm_Se nd综合上述两种标识符命名风格，本章的程序代码采用了如下的标识符命名规范:（1）结构、类和函数的标识符均要包括一个标识其所属功能层次或程序包的前缀，前缀 和标识符以下划线“ _”隔开，女口 PHY_、DRV_、DEV_、ARP_、OSPF_、SNMP_等。另外, 组成标识符的每个英文单词的首字母大写，其余字母小写。（2） 常量标识符均采用大写字母。另外，函数返回的提示性常量标识符均添加“RV_ ” 前缀。例如：const int RV_OKco nst int RV_FAILURE 在协议分组格式的设计中， 组中各字节通常都是对齐的：10为了使协议分组在常见的计算机体系结构

9、下易于处理，协议分4字节字段从偏移量为 4的倍数的字节单元开始，而2字节字段从偏移量为偶数的字节单元开始。排列整齐的分组使得在协议实现时可以采用诸如“分组模板”等数据结构，从而使分组收发程序的实现得以简化，效率也得以提高。为了便于将描述协议分组的数据结构与分组格式相对照， 从而使之更容易阅读和理解，在通用头文件中定义了常量标 识符 BITS_8、BITS_16 和 BITS_32。#ifndef BITS_8#defi neBITS_8un sig ned char#en dif#ifndefBITS_16#defi neBITS_16un sig ned short int#en dif#i

10、fndefBITS_32#defi neBITS_32un sig ned long#en dif(3) 变量标识符中单词均使用小写字母，结构和类的成员变量名前加"m_ ”前缀。(4) 除了指针和句柄变量名前必须分别添加前缀“p-”和“ h-”外，其余变量名前通常不加表示数据类型的前缀(如数值前缀“n-”，布尔前缀“ b-”，字符串前缀“ sz”，等等)，只有在通过以下两种方式无法标识变量的数据类型时，才采用标注前缀的方法：一种方式是通过变量名中包含的特征单词来标识数据类型，例如，包含size、number、length、count、interval、time、index等单词的变量

11、均为数值变量，包含单词name、path的变量总是字符串变量，布尔变量名均以助词is或do开始。另外一种方式是通过“就近声明”的原则来省略数据类型前缀。(5) 对于过长或过多单词构成的标识符，使用了通用和易理解的单词缩写或单词首字头 缩写形式。这样做是为了使学生熟悉规范代码中的简写形式，从而有助于学生去阅读源代码。(6) 循环变量使用字母i及其组合(如ii和iii，字母i的重复次数表示循环嵌套层数)， 或i、j和k分别表示循环嵌套的第 1、2和3层。循环嵌套层次不得超过3层。出于占用篇幅和易于阅读的考虑，在描述函数的实现时，构造函数、析构函数和一些实现代码比较简单的类成员函数都在头文件的类定义

12、中进行了描述。但在实际的课程设计中，还是应该将其定义在实现文件中。另外，许多语句的编写没有遵循统一的风格也是出于同样的原因。 如有的条件语句是分行编写的，有的则直接编写在了同一行上。在实际实现时，都应分行编写。17.1.2 进程间通信机制和线程间同步机制在进行模拟实现时，每台网络设备通过一个单独运行的进程来模拟，而网络设备上的每个驱动程序则通过进程下各个单独运行的线程来模拟。这样，就涉及到数据包在模拟不同设备的进程之间和在模拟不同协议层驱动程序的线程之间的传递问题。由于在单进程多线程环境中诸线程共享单进程的内存空间，因此，模拟不同协议层驱动程序的线程之间的数据传递问题并不难解决，只要将多线程共

13、享的内存资源定义为进程中的全局变量即可，这时不需要进程间的通信机制。但在多进程环境中，每个进程都有自己的运行空间，不同进程的运行空间是相互隔离的，因此，数据在不同进程之间的传递则要通过各种进程间通信机制(IPC，InterProcessCommunication )来实现。在模拟实现中，该问题是通过内存映射文件(MMF , Memory MappingFile)这一进程间通信机制来实现的。MMF缓冲区共享方案的原理是：首先，在一个单独的进程中调用函数CreateMMF生成一个由系统页文件支持的被命名的共享缓冲区。接着，需要使用缓冲区的进程用生成该缓冲区时所使用的名字调用函数OpenMMF打开共

14、享缓冲区，并通过函数GetMMFView将其映射到自己的进程地址空间中，就可以使用该缓冲区与其它进程交换数据了。注意，无论是生成还是打开共享缓冲区的进程，最后都必须调用FreeMMF，以释放文件映射(映射到内存页)句柄和文件视(映射到进程空间)句柄。在模拟实现中，线程间的同步问题是采用事件通知的方式解决的。其中，处理数据的线程调用函数 WaitForEve nt睡眠等待一个命名事件(Named Eve nt)；提供数据的线程将数据送入 队列后，调用函数 SignalEvent通知该命名事件，唤醒因等待数据而睡眠的线程。os.cpp#ifndef _OS_H_#define _OS_H_#i n

15、clude <win dows.h>HANDLE CreateMMF(char*n ame, un sig ned int size) / Create a pagi ng file-backed MMF.HANDLE hFileMapp in gObject = NULL;hFileMappingObject = CreateFileMapping(INV ALID_HANDLE_V ALUE, NULL, PAGE_READWRITE, 0, size, TEXT( name);if (!hFileMapp in gObject)return NULL;if(GetLastEr

16、ror()=ERROR_ALREADY_EXISTS)CloseHa ndle(hFileMappi ngObject);return hFileMapp in gObject; /HANDLE Ope nM MF(char* name) / Map a view of the file into the address space.HANDLE hFileMapp in gObject = Ope nFileMappi ng(FILE_MAP_READ |FILE_MAP_WRITE, FALSE, TEXT( name);if (!hFileMapp in gObject)return N

17、ULL;return hFileMapp in gObject;/PVOID GetMMFView(HANDLE hFileMappi ngObject) / map The MMF into the process's address space.PVOID pView = MapViewOfFile(hFileMappi ngObject,FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, 0);if (!pView) return NULL;return pView;/void FreeMMF(HANDLE hFileMappi ngObject, PVO

18、ID pView) if (pView) Unm apViewOfFile(pView);if (hFileM appin gObject)CloseHa ndle(hFileM appin gObject);/void WaitForEvent(char* peventname) / 以 0 结束表明事件名的字符串LPSECURITY_ATTRIBUTES pi nherited = NULL;BOOLisma nualreset= TRUE;BOOL isi nitstatesig naled = FALSE;HANDLE heve nt = CreateEve nt(pi nherite

19、d, isma nu alreset,isin itstatesig naled, peve ntn ame);if (heve nt = NULL)return;DWORD milliseco nds = INFINITE;WaitForSi ngleObject(heve nt, millisec on ds);CloseHa ndle(heve nt);return;/void Sign alEve nt(char* peve ntn ame)DWORD desiredaccess = EVENT_ALL_ACCESS;BOOL is_in herited = FALSE;HANDLE

20、heve nt = Ope nEve nt(desiredaccess, isn herited, peve ntn ame);if (heve nt = NULL)retur n;SetEve nt(heve nt);CloseHa ndle(heve nt);/#in clude <process.h>in li ne un sig ned long Begin ThreadEx( un sig ned ( _stdcall *pF un cName )( void* ) PSECURITY_ATTRIBUTES psa = NULL;unsigned cbStackSize

21、= 0;void *pvParam = NULL;unsigned initfalg = 0;un sig ned threadID;unsigned *threadaddr =&threadID;retur n _begi nthreadex(psa, cbStackSize, pFun cName, pvParam, ini tfalg, threadaddr); #en difos.cpp17.1.3通用的数据结构和函数1 内存缓冲区这些要求包括：能够很容易地处理 要能够很容易地在缓冲区的头部 要能够很容易地对缓冲区中的协议网络协议对于内存缓冲区的管理提出了许多要求， 变长缓冲区

22、；当低层协议对来自高层协议的数据进行封装时, 或尾部添加数据；相反，当数据包在协议栈中向上传递时，头结构进行定位；另外，在这些操作过程中要尽可能地减少数据的复制。内存缓冲区的管理方 式直接关系着网络协议的性能。通过对开放源代码操作系统实现中所使用的缓冲区管理方式的研究，在本篇网络协议的模拟实现中使用了一个 MBuf结构及其相关函数，来对不同协议层间传递的数据块进行操作。与该结构有关的函数提供了申请数据缓冲区和设置/获取各协议层头指针的接口。由于数据缓冲区是一次性申请和分配的，所以，在发送数据时要根据实际需要估算所需的内存空间。内存空间按照三种规格进行分配：128字节的缓冲区用于较小的数据帧，如

23、ARP请求应答帧、TCP握手控制帧等；2048字节的缓冲区用于一般的数据帧，如以太帧最大长度为1518字节；而65535字节的缓冲区通常用于高层协议封装大量数据时使用，如IP数据包的数据部分最大长度可达65535字节。分配的缓冲区中已经包含了用于协议头结构的空间。mbuf.h#ifndef _MBUF_H#defi ne _MBUF_Hstruct Mbuf / Mbuf是为操作在协议层间传递的内存数据块而定义的数据结构un sig ned int m_size;#defi ne MBUF_SIZE_SMALL#define MBUF SIZE MIDDLE/#define MBUF SIZE

24、 LARGEun sig ned intchar*char*intm_datasize;m_pdatahead;m_pdatatail;m_directio n;#defi ne MBUF_DIRECTION/缓冲区大小128;2048;65535;服务数据单元/指明/指明SDU/PDUSDU/PDUSDU的大小的开始位置 的结束位置UP1 /用于向协议栈上层传递的数据块2 /用于向协议栈下层传递的数据块#define MBUF DIRECTION DOWN/接口层填写收到该数据的接口指针/ IP层填写源struct DEV NetIf*un sig ned longBITS 16m_pif;

25、 m_ip; m_flag;FLAG BCAST#defi ne MBUF#define MBUF FLAG MCAST0x00010x0002;#en difIP地址/广播/多播mbuf.h在内存缓冲区的实现中，除了申请缓冲区的函数MBuf_Get夕卜，其它函数都以一个 MBuf缓冲区指针作为第一个参数。 通过修改函数 MBuf_Get和函数MBuf_Free的实现，还可以使该 结构用于其它类型的缓冲区。如上述的用于进程间进行数据传递的MMF缓冲区。mbuf.cpp/函数MBuf_Get供最初收到或生成数据的例程调用，以分配缓冲数据和协议控制信息/的内存块。该数据块在协议层间传递，最后处理数

26、据的协议层负责释放该内存块。struct Mbuf*MBuf_Get(u nsig ned int size, i nt directio n) struct Mbuf* ptr = NULL;/ MBuf 首地址unsigned int bytes = 0;/初始化数据指针时从尾部计算的字节数if (size <= MBUF_SIZE_SMALL ) ptr = (struct Mbuf*) new (MBUF_SIZE_SMALL * sizeof(char);if (ptr = NULL) return NULL; ptr->m_size = MBUF_SIZE_SMALL;

27、 bytes = 32;else if (size <= MBUF_SIZE_MIDDLE ) ptr = new (MBUF_SIZE_MIDDLE * sizeof(char);if (ptr = NULL) return NULL;ptr->m_size = MBUF_SIZE_MIDDLE;bytes = 64;else if (size <= MBUF_SIZE_LARGE ) ptr = new (MBUF_SIZE_LARGE * sizeof(char);if (ptr = NULL) return NULL;ptr->m_size = MBUF_SIZ

28、E_LARGE;bytes = 128;ptr->m_datasize = 0;if (direction = MBUF_DIRECTION_UP)/ 向上层协议传递的数据块ptr->m_datahead = ptr->m_datatail = ptr + sizeof(struct MBuf);else if (directio n = MBUF_DIRECTION_DOWN) /向下层协议传递的数据块ptr->m_datahead = ptr->m_datatail = ptr + ptr->m_size - bytes;ptr->m_flag =

29、 ptr->m_flag & 0x00000000;return ptr;/void MBuf_Free(char* pmbuf) / 释放不再使用的空间。if (pmbuf) delete pmbuf;/函数MBuf_PrependHdr用于添加数据或协议头int MBuf_Prepe ndHdr(struct MBuf* pmbuf, char* pbuf, un sig ned int size ) int rv = RV_OKif (pmbuf->m_pdatahead -pmbuf -sizeof(struct MBuf) > size ) /前面有足够空间

30、pmbuf->m_pdatahead -= size;/ 为复制调整头指针memcpy(pmbuf->m_pdatahead, pbuf, size); / 复制数据或协议头 pmbuf->m_datasize += size;/ 力口上协议头长度elserv = RV_MBUF_NOROOM;return ptr;/函数MBuf_AppendTail用于添加协议尾，如校验字节等。int MBuf_Appe ndTail(struct MBuf* pmbuf, char* pbuf, un sig ned int size ) int rv = RV_OKif (pmbuf-

31、>m_datatail + size) < (pmbuf + pmbuf->m_size) / 后面有足够空间memcpy(pmbuf->m_pdatatail, pbuf, size);/复制协议尾pmbuf->m_pdatatail += size;/调整指针以包括协议尾部pmbuf->m_datasize += size;/加上协议尾部的长度elserv = RV_MBUF_NOROOM;return ptr;/int MBuf_GetPDUSize(struct MBuf* pmbuf) / 返回当前协议层的 PDU 大小。return (pmbuf

32、->m_datatail -pmbuf->m_pdatahead);/char* MBuf_GetHdrPtr(struct MBuf* pmbuf) / 获得本层协议头指针。retur n pmbuf->pdatahead;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII函数MBuf_AdjustHdrPtr为向上层协议传递数据块而调整指针，即将指针调整到 II上层协

33、议数据的开始处。int MBuf_AdjustHdrPtr(struct MBuf* pmbuf, unsigned int size) int rv = RV_OK;if (pmbuf->m_pdatahead + size) > pmbuf->m_pdatatail)rv = RV_MBUF_SIZETOOLARGE;elsepmbuf->m_pdatahead += size;return rv; IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

34、IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII函数MBuf_SetNetlfPtr用于设置指向接收数据包的网络接口的指针void MBuf_SetNetIfPtr(struct MBuf* pmbuf, struct DEV_NetIf* pif)m_pif = pif;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII函数MBuf_GetN

35、etlfPtr用于获取指向接收数据包的网络接口的指针struct DEV_NetIf* MBuf_GetNetIfPtr(struct MBuf* pmbuf )return m_pif;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII函数MBuf_SetSrclPAddr用于设置接收到的数据包的源IP地址void MBuf_SetSrcIPAddr(struct MBuf* pmb

36、uf, un sig ned long srcip) pmbuf->m_ip = srcip; IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII函数MBuf_ GetSrcIPAddr用于获取接收到的数据包的源IP地址un sig ned long MBuf_GetSrcIPAddr(struct MBuf* pmbuf )return pmbuf-> mp; IIII

37、IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII void MBuf_SetFlag(struct MBuf* pmbuf, int flag) II 设置数据帧为广播或多播帧。 m_flag |= flag;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

38、IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII int flag MBuf_GetFlag(struct MBuf* pmbuf) 获取广播或多播帧标志。retur n (pmbuf->m_flag); mbuf.cpp2 .队列和缓冲表相邻协议层间的数据传递接口是队列。此外，协议实现中还经常要用到列表和缓冲表。在模拟实现中用同一个类 Cache来完成这三种数据结构的功能。这里没有使用C+ STL库中的模板类list，主要是因为该类没有重载下标运算符“”，且通过迭代子进行循环操作的方式不容易理解。在实现中应该注意，模板类的定义和实现必须在同一个文件中，否则，无法进行编译

39、。cache.h#ifndef _CACHE_H_#define _CACHE_H_#i nclude "rv.h"#defi ne RV_CACHE/避免绝对性的宏定义RV_CACHE + 1RV_CACHE + 2#defi ne RV_CACHE_ALLOCERROR#defi ne RV_CACHE_FULLtemplate <type name T> class Cache public:struct Lin kList structLin kList*m_n ext;structLi nkList*m_prev;Tm_en try; *m_head;

40、/下一个表项的指针/前一个表项的指针/在抽象数据类型T中有指针成员时，要/注意必须实现赋值操作符"="/表头指针int m_entrynum;int m_size;#defi ne CACHE_SIZE_INFINITE/当前链表中表项个数/用户设置的链表大小0不设置相当于INFINITE/构造函数和析构函数Cache();Cache(i nt size);Cache();/操作函数11第17章 OSPF路由协议的软件模拟与设计13第17章 OSPF路由协议的软件模拟与设计const T& operator(c onst un sig ned intin dex);

41、int Add(c onst T entry, int pos);#defi ne CACHE_ADD_POS_HEAD0#defi ne CACHE_ADD_POS_TAIL1void Remove (un sig ned int in dex);/下标操作符重载/添加一个表项/删除一个表项#define Prepend(a) Add(a, CACHE_ADD_POS_HEAD); / 添加表项到表头#define Append(a)Add(a, CACHE_ADD_POS_TAIL); / 添加表项到表尾unsigned int GetEntryNum();/获得链表中表项个数bool l

42、sEmpty();bool IsFull();#defi ne Enq ueue(a)Appe nd(a);#defi ne Dequeue()Remove(O);#defi ne Push(a)Prepe nd(a);#defi ne Pop()Remove(O);const T& Top();void Clear();/入队列/出队列/入栈/出栈/读队首/栈顶表项/清除所有表项#第17章 OSPF路由协议的软件模拟与设计;/ template <type name T>Cache<T>:Cache() : m_head(NULL), m_e ntry nu

43、m(0), m_size(0) / template <type name T>Cache<T>:Cache(i nt size) : m_head(NULL), m_e ntry nu m(0), m_size(size) / template <type name T>Cache<T>:Cache() if (m_entrynum > 0) Clear(); / template <type name T>const T& Cache<T>:operator(c onst un sig ned intin

44、 dex) struct Lin kList*op = m_head; /元素0if (in dex >=0 && in dex < m_entrynum)for (un sig ned int i = 0; i < in dex; i+ ) op = op->m_ next;else op = m_head;/若下标越界则返回第一个元素return op->m_e ntry; / template <type name T>int Cache<T>:Add(c onst T entry, int pos) f (m_siz

45、e > 0 && m_en try num = m_size)return RV_CACHE_FULL;#第17章 OSPF路由协议的软件模拟与设计struct LinkList *tmp = new LinkList;/ 新节点if (tmp = NULL) return RV_CACHE_ALLOCERROR;tmp->m_e ntry = en try;if (m_head = NULL) / 第一个元素(空链表)tmp->m_ next = tmp;tmp->m_prev = tmp; m_head = tmp;else structLin kL

46、ist*op =m_head->m_prev;/新节点插入到链表尾部tmp->m_ next=op->m_ next;tmp->m_prev=op;op->m _n ext->m_prev=tmp;op->m_ next=tmp;if (pos = CACHE_ADD_POS HEAD)/调整新节点为链表首部m_head = tmp;m_e ntry nu m+;return RV_OK;/template <type name T>un sig ned intCache<T>:GetE ntryNum() retur nm_e

47、ntrynu m; / template <type name T>bool Cache<T>:lsEmpty() return (m_e ntrynum = 0); /template <type name T>bool Cache<T>:lsFull() return (m_en try num = m_size); /template <type name T>void Cache<T>:Remove( un sig ned intin dex) if (m_e ntry num < 0| in dex >

48、; m_entrynum ) return;struct Lin kList* op = m_head;if (in dex = 0 && m_e ntry num =1) delete op;op = NULL;m_head = NULL;else if (in dex < m_entrynum / 2 )for (un sig ned inti = 0; i < in dex; i+ )op = op->m_ next;elsefor (un sig ned inti = 0; i < m_entrynu m-i ndex; i+ ) op = op->m_prev;op->m_prev- >m_n ext = op->m_ next;op-> m_n ext->m_prev = op->m_prev;if (in dex