ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > > 移植linux的基数树到应用程序中

移植linux的基数树到应用程序中

作者：gabbro 时间：2019-08-19 15:55:39 0 删除 编辑

头文件及定义

#define RADIX_TREE_MAX_TAGS 3

#define RADIX_TREE_INIT() {.m_Height=0,.pRootNode=NULL,}

#define RADIX_TREE(name) RADIX_ROOT name=RADIX_TREE_INIT()

#define INIT_RADIX_TREE(root) do{(root)->m_Height=0;(root)->pRootNode=NULL;}while(0)

/*

 ************************************************************************************************************************************************************************

 * 数据类型定义

 ************************************************************************************************************************************************************************

*/

typedef struct _RADIX_ROOT

{

    unsigned int m_Height;

    unsigned int m_GfpMask;

    struct _RADIX_NODE *pRootNode;

}RADIX_ROOT,*PRADIX_ROOT;

typedef struct _IO_CONTEXT

{

    RADIX_ROOT icq_tree;

}IO_CONTEXT,*PIO_CONTEXT;

typedef struct _IO_CQ

{

    IO_CONTEXT *ioc;

    unsigned int flags;

    char name[32];

}IO_CQ,*PIO_CQ;

实现

#define GFP_BITS_SHIFT 25

#define GFP_BITS_MASK (((1< 

#define RADIX_TREE_MAP_SHIFT(6)

#define RADIX_TREE_MAP_SIZE(1UL< #define RADIX_TREE_TAG_LONGS((RADIX_TREE_MAP_SIZE+32-1)/32)

#define RADIX_TREE_MAP_MASK(RADIX_TREE_MAP_SIZE-1)

#define RADIX_TREE_INDEX_BITS  (8*sizeof(unsigned long))

#define DIV_ROUND_UP(n,d) (((n)+(d)-1)/(d))

#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS,RADIX_TREE_MAP_SHIFT))

#define ARRAY_SIZE(x) (sizeof(x)/sizeof((x)[0]))

/*

************************************************************************************************************************************************************************

* 数据类型定义

************************************************************************************************************************************************************************

*/

typedef struct _RADIX_NODE

{

unsigned intm_Height;

unsigned intm_Count;

struct _RADIX_NODE*pParent;

void*pSlot[RADIX_TREE_MAP_SIZE];

unsigned longm_Tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

}RADIX_NODE,*PRADIX_NODE;

/*

************************************************************************************************************************************************************************

* 全局变量

************************************************************************************************************************************************************************

*/

static unsigned long sHeightToMaxIndex[RADIX_TREE_MAX_PATH+1];

static IO_CONTEXTsIoContext;

/*

****************************************************************************************************************************************************

* 函数定义

*****************************************************************************************************************************************************

*/

static inline int RaIsIndirectP(void *ptr)

{

return (int)((unsigned long)ptr&1);

}

static inline void *RaPtrToIndirect(void *ptr)

{

return (void *)((unsigned long)ptr|1);

}

static inline void *RaIndirectToPtr(void *ptr)

{

return (void *)((unsigned long)ptr&~1);

}

static inline unsigned long RaMaxIndex(unsigned int height)

{

return sHeightToMaxIndex[height];

}

static inline void RaClrBit(unsigned long nr,volatile void *addr)

{

volatile unsigned long *a=addr;

int mask;

a+=nr>>5;

mask=1<<(nr&31);

*a&=~mask;

}

static inline void RaSetBit(unsigned long nr,volatile void *addr)

{

volatile unsigned long *a=addr;

int mask;

a+=nr>>5;

mask=1<<(nr&31);

*a|=mask;

}

static inline int RaTestBit(int nr,const volatile void *addr)

{

return 1&(((const volatile __u32 *)addr)[nr>>5]>>(nr&31));

}

static inline int RaGetTag(RADIX_NODE *pRadixNode,unsigned int Tag,int Offset)

{

return RaTestBit(Offset,pRadixNode->m_Tags[Tag]);

}

static inline void RaSetTag(RADIX_NODE *pRadixNode,unsigned int Tag,int Offset)

{

RaSetBit(Offset,pRadixNode->m_Tags[Tag]);

}

static inline void RaClrTag(RADIX_NODE *pRadixNode,unsigned int Tag,int Offset)

{

RaClrBit(Offset,pRadixNode->m_Tags[Tag]);

}

static inline int RaAnyTagIsSet(RADIX_NODE *pRadixNode,unsigned int Tag)

{

unsigned int idx;

for(idx=0;idx {

if(pRadixNode->m_Tags[Tag][idx])

return 1;

}

return 0;

}

static inline int RaGetRootTag(RADIX_ROOT *pRadixRoot,unsigned int Tag)

{

return (unsigned int)pRadixRoot->m_GfpMask&(1<<(Tag+GFP_BITS_SHIFT));

}

static inline void RaClrRootTag(RADIX_ROOT *pRadixRoot,unsigned int Tag)

{

pRadixRoot->m_GfpMask&=~(1<<(Tag+GFP_BITS_SHIFT));

}

static inline void RaSetRootTag(RADIX_ROOT *pRadixRoot,unsigned int Tag)

{

pRadixRoot->m_GfpMask|=(1<<(Tag+GFP_BITS_SHIFT));

}

static inline void RaClrAllRootTag(RADIX_ROOT *pRadixRoot)

{

pRadixRoot->m_GfpMask&=GFP_BITS_MASK;

}

static inline RADIX_NODE *RaNodeAlloc(RADIX_ROOT *pRadixRoot)

{

RADIX_NODE *pNode=NULL;

pNode=malloc(sizeof(*pNode));

if(pNode==NULL)

return NULL;

return pNode;

}

static inline void RaNodeFree(RADIX_NODE *pRadixNode)

{

int i;

for(i=0;i RaClrTag(pRadixNode,i,0);

pRadixNode->pSlot[0]=NULL;

pRadixNode->m_Count=0;

free(pRadixNode);

}

static inline void RaNodeShrink(RADIX_ROOT *pRadixRoot)

{

while(pRadixRoot->m_Height>0)

{

RADIX_NODE *to_free=pRadixRoot->pRootNode;

RADIX_NODE *slot;

to_free=RaIndirectToPtr(to_free);

if(to_free->m_Count!=1)

break;

if(!to_free->pSlot[0])

break;

slot=to_free->pSlot[0];

if(pRadixRoot->m_Height>1)

{

slot->pParent=NULL;

slot=RaPtrToIndirect(slot);

}

pRadixRoot->pRootNode=slot;

pRadixRoot->m_Height--;

if(pRadixRoot->m_Height==0)

*((unsigned long *)&to_free->pSlot[0])|=1;

RaNodeFree(to_free);

}

}

extern void *RadixTreeClrTag(RADIX_ROOT *pRadixRoot,unsigned long Index,unsigned int Tag)

{

RADIX_NODE *pNode=NULL,*pSlot=NULL;

unsigned int height,shift;

int offset;

height=pRadixRoot->m_Height;

if(Index>RaMaxIndex(height))

goto out;

shift=height*RADIX_TREE_MAP_SHIFT;

pSlot=RaIndirectToPtr(pRadixRoot->pRootNode);

while(shift)

{

if(pSlot==NULL)

goto out;

shift-=RADIX_TREE_MAP_SHIFT;

offset=(Index>>shift)&RADIX_TREE_MAP_MASK;

pNode=pSlot;

pSlot=pSlot->pSlot[offset];

}

if(pSlot==NULL)

goto out;

while(pNode)

{

if(!RaGetTag(pNode,Tag,offset))

goto out;

RaClrTag(pNode,Tag,offset);

if(RaAnyTagIsSet(pNode,Tag))

goto out;

Index>>=RADIX_TREE_MAP_SHIFT;

offset=Index&RADIX_TREE_MAP_MASK;

pNode=pNode->pParent;

}

if(RaGetRootTag(pRadixRoot,Tag))

RaClrRootTag(pRadixRoot,Tag);

out:

return pSlot;

}

extern void *RadixTreeSetTag(RADIX_ROOT *pRadixRoot,unsigned long Index,unsigned int Tag)

{

unsigned int height,shift;

RADIX_NODE *pSlot;

height=pRadixRoot->m_Height;

if(Index>RaMaxIndex(height))

return NULL;

pSlot=RaIndirectToPtr(pRadixRoot->pRootNode);

shift=(height-1)*RADIX_TREE_MAP_SHIFT;

while(height>0)

{

int offset;

offset=(Index>>shift)&RADIX_TREE_MAP_MASK;

if(!RaGetTag(pSlot,Tag,offset))

RaSetTag(pSlot,Tag,offset);

pSlot=pSlot->pSlot[offset];

shift-=RADIX_TREE_MAP_SHIFT;

height--;

}

if(pSlot&&!RaGetRootTag(pRadixRoot,Tag))

RaSetRootTag(pRadixRoot,Tag);

return pSlot;

}

static int RadixTreeExtendSlot(RADIX_ROOT *pRadixRoot,unsigned long Index)

{

RADIX_NODE *pNode,*pSlot;

unsigned int height;

int tag;

height=pRadixRoot->m_Height+ 1;

while(Index>RaMaxIndex(height))

height++;

if(pRadixRoot->pRootNode==NULL)

{

pRadixRoot->m_Height=height;

goto out;

}

do

{

unsigned int newheight;

if(!(pNode=RaNodeAlloc(pRadixRoot)))

return -ENOMEM;

memset(pNode,0,sizeof(*pNode));

for(tag=0;tag {

if(RaGetRootTag(pRadixRoot,tag))

RaSetTag(pNode,tag,0);

}

newheight=pRadixRoot->m_Height+1;

pNode->m_Height=newheight;

pNode->m_Count=1;

pNode->pParent=NULL;

pSlot=pRadixRoot->pRootNode;

if(newheight>1)

{

pSlot=RaIndirectToPtr(pSlot);

pSlot->pParent=pNode;

}

pNode->pSlot[0]=pSlot;

pNode=RaPtrToIndirect(pNode);

pRadixRoot->pRootNode=pNode;

pRadixRoot->m_Height=newheight;

}

while(height>pRadixRoot->m_Height);

out:

return 0;

}

static void *RadixTreeFindElem(RADIX_ROOT *pRadixRoot,unsigned long Index,int IsSlot)

{

unsigned int height,shift,i;

RADIX_NODE *pNode,**ppSlot;

pNode=pRadixRoot->pRootNode;

if(pNode==NULL)

return NULL;

if(!RaIsIndirectP(pNode))

{

if(Index>0)

return NULL;

return IsSlot?(void *)&pRadixRoot->pRootNode:pNode;

}

pNode=RaIndirectToPtr(pNode);

height=pNode->m_Height;

if(Index>RaMaxIndex(height))

return NULL;

shift=(height-1)*RADIX_TREE_MAP_SHIFT;

do

{

ppSlot=(RADIX_NODE **)(pNode->pSlot+((Index>>shift)&RADIX_TREE_MAP_MASK));

pNode=*ppSlot;

if(pNode==NULL)

return NULL;

shift-=RADIX_TREE_MAP_SHIFT;

height--;

}

while(height>0);

return IsSlot?(void *)ppSlot:RaIndirectToPtr(pNode);

}

extern int RadixTreeAddNode(RADIX_ROOT *pRadixRoot,unsigned long Index,void *pItem)

{

RADIX_NODE *pNode=NULL,*pSlot;

unsigned int height,shift;

int offset,error=-1,ret=0;

if(Index>RaMaxIndex(pRadixRoot->m_Height))

{

error=RadixTreeExtendSlot(pRadixRoot,Index);

if(error)

return error;

}

pSlot=RaIndirectToPtr(pRadixRoot->pRootNode);

height=pRadixRoot->m_Height;

shift=(height-1)*RADIX_TREE_MAP_SHIFT;

offset=0; 

while(height>0)

{

if(pSlot==NULL)

{

if(!(pSlot=RaNodeAlloc(pRadixRoot)))

return -ENOMEM;

memset(pSlot,0,sizeof(*pSlot));

pSlot->m_Height=height;

pSlot->pParent=pNode;

if(pNode)

{

pNode->pSlot[offset]=pSlot;

pNode->m_Count++;

}

else

{

pRadixRoot->pRootNode=RaPtrToIndirect(pSlot);

}

}

offset=(Index>>shift)&RADIX_TREE_MAP_MASK;

pNode=pSlot;

pSlot=pNode->pSlot[offset];

shift-=RADIX_TREE_MAP_SHIFT;

height--;

}

if(pSlot!=NULL)

return -EEXIST;

if(pNode)

{

pNode->m_Count++;

pNode->pSlot[offset]=pItem;

RaGetTag(pNode,0,offset);

RaGetTag(pNode,1,offset);

}

else

{

pRadixRoot->pRootNode=pItem;

RaGetRootTag(pRadixRoot,0);

RaGetRootTag(pRadixRoot,1);

}

return 0;

}

extern void *RadixTreeDelNode(RADIX_ROOT *pRadixRoot,unsigned long Index)

{

RADIX_NODE *pNode=NULL,*pSlot=NULL,*pFreeNode;

unsigned int height,shift;

int tag,offset;

height=pRadixRoot->m_Height;

if(Index>RaMaxIndex(height))

goto out;

pSlot=pRadixRoot->pRootNode;

if(height==0)

{

RaClrAllRootTag(pRadixRoot);

pRadixRoot->pRootNode=NULL;

goto out;

}

pSlot=RaIndirectToPtr(pSlot);

shift=height*RADIX_TREE_MAP_SHIFT;

do

{

if(pSlot==NULL)

goto out;

shift-=RADIX_TREE_MAP_SHIFT;

offset=(Index>>shift)&RADIX_TREE_MAP_MASK;

pNode=pSlot;

pSlot=pSlot->pSlot[offset];

}

while(shift);

if(pSlot==NULL)

goto out;

for(tag=0;tag {

if(RaGetTag(pNode,tag,offset))

RadixTreeClrTag(pRadixRoot,Index,tag);

}

pFreeNode=NULL;

while(pNode)

{

pNode->pSlot[offset]=NULL;

pNode->m_Count--;

if(pFreeNode)

RaNodeFree(pFreeNode);

if(pNode->m_Count)

{

if(pNode==RaIndirectToPtr(pRadixRoot->pRootNode))

RaNodeShrink(pRadixRoot);

goto out;

}

pFreeNode=pNode;

Index>>=RADIX_TREE_MAP_SHIFT;

offset=Index&RADIX_TREE_MAP_MASK;

pNode=pNode->pParent;

}

RaClrAllRootTag(pRadixRoot);

pRadixRoot->m_Height=0;

pRadixRoot->pRootNode=NULL;

if(pFreeNode)

RaNodeFree(pFreeNode);

out:

return pSlot;

}

extern void *RadixTreeFindNode(RADIX_ROOT *pRadixRoot,unsigned long Index)

{

return RadixTreeFindElem(pRadixRoot,Index,0);

}

extern void RadixTreeInit(void)

{

unsigned int i;

for(i=0;i {

sHeightToMaxIndex[i]=RaMaxIndexCalc(i);

}

}

测试程序

extern int RtCreateTest(void)

{

INIT_RADIX_TREE(&sIoContext.icq_tree);

}

extern int RtAddTest(unsigned long index,IO_CQ *pIoCq)

{

return RadixTreeAddNode(&sIoContext.icq_tree,index,pIoCq);

}

extern void RtDelTest(unsigned long index)

{

RtDebugTest(FALSE);

RadixTreeDelNode(&sIoContext.icq_tree,index);

}

extern IO_CQ *RtFindTest(unsigned long index)

{

IO_CQ *icq;

icq=RadixTreeFindNode(&sIoContext.icq_tree,index);

return icq;

}

{

#include "RadixTreeAlg.h"

IO_CQ *pAddiocq,*pAddiocq2,*pAddiocq3,*pAddiocq4,*pAddiocq5,*pAddiocq6;

IO_CQ *pTmpiocq;

intret=0;

RadixTreeInit();

RtCreateTest();

pAddiocq=malloc(sizeof(*pAddiocq));

if(pAddiocq!=NULL)

{

memset(pAddiocq,0,sizeof(*pAddiocq));

pAddiocq->flags=1;

strcpy(pAddiocq->name,"jsya1");

ret=RtAddTest(1,pAddiocq);

PRINTF("--------ret=%d------------",ret);

}

pAddiocq2=malloc(sizeof(*pAddiocq2));

if(pAddiocq2!=NULL)

{

memset(pAddiocq2,0,sizeof(*pAddiocq2));

pAddiocq2->flags=2;

strcpy(pAddiocq2->name,"jsya2");

ret=RtAddTest(2,pAddiocq2);

PRINTF("-----2---ret=%d------------",ret);

}

pAddiocq3=malloc(sizeof(*pAddiocq3));

if(pAddiocq3!=NULL)

{

memset(pAddiocq3,0,sizeof(*pAddiocq3));

pAddiocq3->flags=3;

strcpy(pAddiocq3->name,"jsya3");

ret=RtAddTest(3,pAddiocq3);

PRINTF("----3----ret=%d------------",ret);

}

pAddiocq4=malloc(sizeof(*pAddiocq4));

if(pAddiocq4!=NULL)

{

memset(pAddiocq4,0,sizeof(*pAddiocq4));

pAddiocq4->flags=4;

strcpy(pAddiocq4->name,"jsya4");

ret=RtAddTest(4,pAddiocq4);

PRINTF("----4----ret=%d------------",ret);

}

pAddiocq5=malloc(sizeof(*pAddiocq5));

if(pAddiocq5!=NULL)

{

memset(pAddiocq5,0,sizeof(*pAddiocq5));

pAddiocq5->flags=131;

strcpy(pAddiocq5->name,"jsya131");

ret=RtAddTest(131,pAddiocq5);

PRINTF("----131----ret=%d------------",ret);

}

pTmpiocq=RtFindTest(3);

if(pTmpiocq!=NULL)

{

PRINTF("---3----flags=%ld------------",pTmpiocq->flags);

PRINTF("-------name=%s------------",pTmpiocq->name);

}

pTmpiocq=RtFindTest(131);

if(pTmpiocq!=NULL)

{

PRINTF("----1---flags=%ld------------",pTmpiocq->flags);

PRINTF("-------name=%s------------",pTmpiocq->name);

}

pAddiocq6=malloc(sizeof(*pAddiocq6));

if(pAddiocq6!=NULL)

{

memset(pAddiocq6,0,sizeof(*pAddiocq6));

pAddiocq6->flags=6;

strcpy(pAddiocq6->name,"jsya6");

ret=RtAddTest(6,pAddiocq6);

PRINTF("---6-----ret=%d------------",ret);

}

RtDelTest(3);

pTmpiocq=RtFindTest(3);

if(pTmpiocq!=NULL)

{

PRINTF("----33---flags=%ld------------",pTmpiocq->flags);

PRINTF("-------name=%s------------",pTmpiocq->name);

}

if(pAddiocq!=NULL)

free(pAddiocq);

if(pAddiocq2!=NULL)

free(pAddiocq2);

if(pAddiocq3!=NULL)

free(pAddiocq3);

if(pAddiocq4!=NULL)

free(pAddiocq4);

if(pAddiocq5!=NULL)

free(pAddiocq5);

if(pAddiocq6!=NULL)

free(pAddiocq6);

}

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/2873/viewspace-3141316/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 如何利用Python进行垃圾分类
下一篇： python读写json
请登录后发表评论 登录
全部评论
gabbro

注册时间：2019-08-19

  • 博文量
    85
  • 访问量
    722

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593