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

头文件及定义
#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 int m_Height;
    unsigned int m_Count;
    struct _RADIX_NODE *pParent;
    void *pSlot[RADIX_TREE_MAP_SIZE];
    unsigned long m_Tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
}RADIX_NODE,*PRADIX_NODE;

/*
 ************************************************************************************************************************************************************************
 * 全局变量
 ************************************************************************************************************************************************************************
*/

static unsigned long sHeightToMaxIndex[RADIX_TREE_MAX_PATH+1];
static IO_CONTEXT sIoContext;

/*
 ****************************************************************************************************************************************************
 * 函数定义
 *****************************************************************************************************************************************************
*/
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;
int ret=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);
}