移植linux内核红黑树

头文件及定义
typedef struct _RB_NODE
{
    unsigned long m_Color;
    struct _RB_NODE *pRight;
    struct _RB_NODE *pLeft;
}RB_NODE,*PRB_NODE;

typedef struct _RB_ROOT
{
    struct _RB_NODE *pRootNode;
}RB_ROOT,*PRB_ROOT;

typedef struct _SYMBOL
{
    RB_NODE rb_node;
    int start;
    int end;
    int namelen;
    int binding;
    char name[0];
}SYMBOL,*PSYMBOL;

typedef struct _DSO
{
    LIST_HEAD node;
    RB_ROOT symbols;
    char loaded;
    char build_id[32];
    const char *short_name;
    char *long_name;
    int long_name_len;
    int short_name_len;
    char name[0];
}DSO,*PDSO;

实现
/*
 ************************************************************************************************************************************************************************
 * 常数与宏定义
 ************************************************************************************************************************************************************************
*/
#define RB_RED 0
#define RB_BLACK 1

#define _RB_PARENT(pc)     ((RB_NODE*)(pc&~3))
#define _RB_COLOR(pc)     ((pc)&1)
#define _RB_IS_BLACK(pc)   _RB_COLOR(pc)
#define _RB_IS_RED(pc)     (!_RB_COLOR(pc))

#define RB_COLOR(rb)       _RB_COLOR((rb)->m_Color)
#define RB_IS_RED(rb)       _RB_IS_RED((rb)->m_Color)
#define RB_IS_BLACK(rb)   _RB_IS_BLACK((rb)->m_Color)

#define RB_PARENT(r)   ((RB_NODE*)((r)->m_Color&~3))
#define RB_EMPTY_NODE(node)   ((node)->m_Color==(unsigned long)(node))

#define RB_ENTRY(ptr, type, member) container_of(ptr,type,member)

/*
 ************************************************************************************************************************************************************************
 * 数据类型定义
 ************************************************************************************************************************************************************************
*/

static inline void DummyPropagate(RB_NODE *pNode,RB_NODE *pStop){}
static inline void DummyCopy(RB_NODE *pOld,RB_NODE *pNew){}
static inline void DummyRotate(RB_NODE *pOld,RB_NODE *pNew){}

typedef struct _RB_AUGMENT_CALLBACKS
{

void (*Propagate)(RB_NODE *pNode,RB_NODE *pStop);
void (*Copy)(RB_NODE *pOld,RB_NODE *pNew);
void (*Rotate)(RB_NODE *pOld,RB_NODE *pNew);

}RB_AUGMENT_CALLBACKS,*PRB_AUGMENT_CALLBACKS;

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

static const RB_AUGMENT_CALLBACKS DummyCallbacks= 
{

DummyPropagate,DummyCopy,DummyRotate

};

static DSO sDsoInfo;

/*
 ****************************************************************************************************************************************************
 * 函数定义
 *****************************************************************************************************************************************************
*/
static inline void RbSetBlack(RB_NODE *pRbNode)
{

pRbNode->m_Color|=RB_BLACK;

}

static inline RB_NODE* RbGetParent(RB_NODE *pRbNode)
{

return (RB_NODE *)pRbNode->m_Color;

}

static inline void RbSetParent(RB_NODE *pRbNode,RB_NODE *pParent)
{

pRbNode->m_Color= RB_COLOR(pRbNode)|(unsigned long)pParent;

}

static inline void RbSetParentColor(RB_NODE *pRbNode,RB_NODE *pParent,int Color)
{

pRbNode->m_Color=(unsigned long)pParent|Color;

}

static inline void RbChangeChild(RB_NODE *pOldNode,RB_NODE *pNewNode,RB_NODE *pParent,RB_ROOT *pRbRoot)
{

if(pParent) 
{

if(pParent->pLeft==pOldNode)

pParent->pLeft=pNewNode;

else

pParent->pRight=pNewNode;

} 
else
{

pRbRoot->pRootNode=pNewNode;

}

}

static inline void RbRotateSetParents(RB_NODE *pOldNode,RB_NODE *pNewNode,RB_ROOT *pRbRoot,int Color)
{

RB_NODE *pParent=RB_PARENT(pOldNode);
pNewNode->m_Color=pOldNode->m_Color;
RbSetParentColor(pOldNode,pNewNode,Color);
RbChangeChild(pOldNode,pNewNode,pParent,pRbRoot);

}

static inline void RbInsertNode(RB_NODE *pNode,RB_ROOT *pRbRoot,void (*AugmentRotate)(RB_NODE *pOld,RB_NODE *pNew))
{

RB_NODE *pParent=RbGetParent(pNode),*pGparent,*pTmpNode;

while(1) 
{

if(!pParent) 

{

RbSetParentColor(pNode,NULL,RB_BLACK);

break;

} 

else if(RB_IS_BLACK(pParent))

{

break;

}

pGparent=RbGetParent(pParent);

pTmpNode=pGparent->pRight;

if(pParent!=pTmpNode) 

{

if(pTmpNode && RB_IS_RED(pTmpNode)) 

{

RbSetParentColor(pTmpNode,pGparent,RB_BLACK);

RbSetParentColor(pParent,pGparent,RB_BLACK);

pNode=pGparent;

pParent=RB_PARENT(pNode);

RbSetParentColor(pNode,pParent,RB_RED);

continue;

}

pTmpNode=pParent->pRight;

if(pNode==pTmpNode) 

{

pParent->pRight=pTmpNode=pNode->pLeft;

pNode->pLeft=pParent;

if(pTmpNode)

RbSetParentColor(pTmpNode,pParent,RB_BLACK);

RbSetParentColor(pParent,pNode,RB_RED);

AugmentRotate(pParent,pNode);

pParent=pNode;

pTmpNode=pNode->pRight;

}

pGparent->pLeft=pTmpNode; 

pParent->pRight=pGparent;

if(pTmpNode)

RbSetParentColor(pTmpNode,pGparent,RB_BLACK);

RbRotateSetParents(pGparent,pParent,pRbRoot,RB_RED);

AugmentRotate(pGparent,pParent);

break;

}
else 
{

pTmpNode=pGparent->pLeft;

if(pTmpNode && RB_IS_RED(pTmpNode)) 

{

RbSetParentColor(pTmpNode,pGparent,RB_BLACK);

RbSetParentColor(pParent,pGparent,RB_BLACK);

pNode=pGparent;

pParent=RB_PARENT(pNode);

RbSetParentColor(pNode,pParent,RB_RED);

continue;

}

pTmpNode=pParent->pLeft;

if(pNode==pTmpNode) 

{

pParent->pLeft=pTmpNode=pNode->pRight;

pNode->pRight=pParent;

if(pTmpNode)

RbSetParentColor(pTmpNode,pParent,RB_BLACK);

RbSetParentColor(pParent,pNode,RB_RED);

AugmentRotate(pParent,pNode);

pParent=pNode;

pTmpNode=pNode->pLeft;

}

pGparent->pRight=pTmpNode;

pParent->pLeft=pGparent;

if(pTmpNode)

RbSetParentColor(pTmpNode,pGparent,RB_BLACK);

RbRotateSetParents(pGparent,pParent,pRbRoot,RB_RED);

AugmentRotate(pGparent,pParent);

break;

}

}

}

static inline void RbEraseColor(RB_NODE *pParent,RB_ROOT *pRbRoot,void (*AugmentRotate)(RB_NODE *pOld,RB_NODE *pNew))
{
RB_NODE *pNode=NULL,*pSibling,*pTmpNode1,*pTmpNode2;

while(1) 
{
pSibling=pParent->pRight;
if(pNode!=pSibling) 
{
if(RB_IS_RED(pSibling)) 
{

pParent->pRight=pTmpNode1=pSibling->pLeft;
pSibling->pLeft=pParent;
RbSetParentColor(pTmpNode1,pParent,RB_BLACK);
RbRotateSetParents(pParent,pSibling,pRbRoot,RB_RED);
AugmentRotate(pParent,pSibling);
pSibling=pTmpNode1;

}
pTmpNode1=pSibling->pRight;
if(!pTmpNode1||RB_IS_BLACK(pTmpNode1)) 
{
pTmpNode2=pSibling->pLeft;
if(!pTmpNode2||RB_IS_BLACK(pTmpNode2)) 
{

RbSetParentColor(pSibling,pParent,RB_RED);
if(RB_IS_RED(pParent))
RbSetBlack(pParent);
else 
{
pNode=pParent;
pParent=RB_PARENT(pNode);
if(pParent)
continue;

}
break;
}

pSibling->pLeft=pTmpNode1=pTmpNode2->pRight;
pTmpNode2->pRight=pSibling;
pParent->pRight=pTmpNode2;
if(pTmpNode1)
RbSetParentColor(pTmpNode1,pSibling,RB_BLACK);
AugmentRotate(pSibling,pTmpNode2);
pTmpNode1=pSibling;
pSibling=pTmpNode2;

}

pParent->pRight=pTmpNode2=pSibling->pLeft;
pSibling->pLeft=pParent;
RbSetParentColor(pTmpNode1,pSibling,RB_BLACK);
if(pTmpNode2)
RbSetParent(pTmpNode2,pParent);
RbRotateSetParents(pParent,pSibling,pRbRoot,RB_BLACK);
AugmentRotate(pParent,pSibling);
break;
}
else 
{
pSibling=pParent->pLeft;
if(RB_IS_RED(pSibling)) 
{

pParent->pLeft=pTmpNode1=pSibling->pRight;
pSibling->pRight=pParent;
RbSetParentColor(pTmpNode1,pParent,RB_BLACK);
RbRotateSetParents(pParent,pSibling,pRbRoot,RB_RED);
AugmentRotate(pParent,pSibling);
pSibling=pTmpNode1;

}
pTmpNode1=pSibling->pLeft;
if(!pTmpNode1||RB_IS_BLACK(pTmpNode1)) 
{

pTmpNode2=pSibling->pRight;
if(!pTmpNode2||RB_IS_BLACK(pTmpNode2)) 
{
RbSetParentColor(pSibling,pParent,RB_RED);
if(RB_IS_RED(pParent))
RbSetBlack(pParent);
else 
{
pNode=pParent;
pParent=RB_PARENT(pNode);
if(pParent)
continue;
}
break;
}
pSibling->pRight=pTmpNode1=pTmpNode2->pLeft;
pTmpNode2->pLeft=pSibling;
pParent->pLeft=pTmpNode2;
if(pTmpNode1)
RbSetParentColor(pTmpNode1,pSibling,RB_BLACK);
AugmentRotate(pSibling,pTmpNode2);
pTmpNode1=pSibling;
pSibling=pTmpNode2;

}

pParent->pLeft=pTmpNode2=pSibling->pRight;
pSibling->pRight=pParent;
RbSetParentColor(pTmpNode1,pSibling,RB_BLACK);
if(pTmpNode2)
RbSetParent(pTmpNode2,pParent);
RbRotateSetParents(pParent,pSibling,pRbRoot,RB_BLACK);
AugmentRotate(pParent,pSibling);
break;
}
}
}


static inline RB_NODE* RbEraseAugmented(RB_NODE *pNode,RB_ROOT *pRbRoot,const RB_AUGMENT_CALLBACKS *pAugment)
{

RB_NODE *pChild=pNode->pRight,*pTmpNode=pNode->pLeft;
RB_NODE *pParent,*pRebalanceNode;
unsigned long pc;
if(!pTmpNode) 
{
pc=pNode->m_Color;
pParent=_RB_PARENT(pc);
RbChangeChild(pNode,pChild,pParent,pRbRoot);
if(pChild) 
{
pChild->m_Color=pc;
pRebalanceNode=NULL;
}
else
{
pRebalanceNode=_RB_IS_BLACK(pc)?pParent:NULL;
}
pTmpNode=pParent;
}
else if(!pChild) 
{
pTmpNode->m_Color= pc=pNode->m_Color;
pParent=_RB_PARENT(pc);
RbChangeChild(pNode,pTmpNode,pParent,pRbRoot);
pRebalanceNode=NULL;
pTmpNode=pParent;
} 
else 
{
RB_NODE *successor=pChild,*child2;
pTmpNode=pChild->pLeft;
if(!pTmpNode) 
{
pParent=successor;
child2=successor->pRight;
pAugment->Copy(pNode,successor);
}
else 
{
do 
{
pParent=successor;
successor=pTmpNode;
pTmpNode=pTmpNode->pLeft;
} 
while(pTmpNode);
pParent->pLeft=child2=successor->pRight;
successor->pRight=pChild;
RbSetParent(pChild,successor);
pAugment->Copy(pNode,successor);
pAugment->Propagate(pParent,successor);
}

successor->pLeft=pTmpNode=pNode->pLeft;
RbSetParent(pTmpNode,successor);
pc=pNode->m_Color;
pTmpNode=_RB_PARENT(pc);
RbChangeChild(pNode,successor,pTmpNode,pRbRoot);
if(child2) 
{
successor->m_Color=pc;
RbSetParentColor(child2,pParent,RB_BLACK);
pRebalanceNode=NULL;
}
else 
{
unsigned long pc2=successor->m_Color;
successor->m_Color=pc;
pRebalanceNode=_RB_IS_BLACK(pc2)?pParent:NULL;
}
pTmpNode=successor;
}
pAugment->Propagate(pTmpNode,NULL);
return pRebalanceNode;

}

extern void RbInsertColor(RB_NODE *pNode,RB_ROOT *pRbRoot)
{

RbInsertNode(pNode,pRbRoot,DummyRotate);

}


extern void RbLinkNode(RB_NODE *pNode,RB_NODE *pParent,RB_NODE **ppRbLink)
{

pNode->m_Color=(unsigned long)pParent;
pNode->pLeft=pNode->pRight=NULL;
*ppRbLink=pNode;

}

extern void RbEraseNode(RB_NODE *pNode,RB_ROOT *pRbRoot)
{

RB_NODE *pRebalanceNode;
pRebalanceNode=RbEraseAugmented(pNode,pRbRoot,&DummyCallbacks);
if(pRebalanceNode)
RbEraseColor(pRebalanceNode,pRbRoot,DummyRotate);

}

extern void RbReplaceNode(RB_NODE *pVictim,RB_NODE *pNewNode,RB_ROOT *pRbRoot)
{

RB_NODE *pParent=RB_PARENT(pVictim);
RbChangeChild(pVictim,pNewNode,pParent,pRbRoot);
if(pVictim->pLeft)
RbSetParent(pVictim->pLeft,pNewNode);
if(pVictim->pRight)
RbSetParent(pVictim->pRight,pNewNode);
*pNewNode=*pVictim;

}

extern RB_NODE *RbFirstNode(const RB_ROOT *pRbRoot)
{

RB_NODE *pNode;

pNode=pRbRoot->pRootNode;
if(!pNode)
return NULL;
while(pNode->pLeft)
pNode=pNode->pLeft;
return pNode;

}

extern RB_NODE *RbLastNode(const RB_ROOT *pRbRoot)
{

RB_NODE *pNode;
pNode=pRbRoot->pRootNode;
if(!pNode)
return NULL;
while(pNode->pRight)
pNode=pNode->pRight;
return pNode;

}

extern RB_NODE *RbNextNode(const RB_NODE *pNode)
{

RB_NODE *pParent;
if(RB_EMPTY_NODE(pNode))
return NULL;
if(pNode->pRight) 
{
pNode=pNode->pRight; 
while(pNode->pLeft)
pNode=pNode->pLeft;
return (RB_NODE *)pNode;
}
while((pParent=RB_PARENT(pNode))&&pNode==pParent->pRight)
pNode=pParent;
return pParent;

}

extern RB_NODE *RbPrevNode(const RB_NODE *pNode)
{

RB_NODE *pParent;
if(RB_EMPTY_NODE(pNode))
return NULL;
if(pNode->pLeft) 
{
pNode=pNode->pLeft; 
while(pNode->pRight)
pNode=pNode->pRight;
return (RB_NODE *)pNode;
}
while((pParent=RB_PARENT(pNode))&&pNode==pParent->pLeft)
pNode=pParent;
return pParent;

}

测试程序
extern void SymbolDel(SYMBOL *pSymbol)
{

free(((void *)pSymbol));

}

extern SYMBOL *SymbolNew(int start,int len,int binding,const char *name)
{

size_t namelen=strlen(name)+1;
SYMBOL *pSymbol=calloc(1,(sizeof(*pSymbol)+namelen));
if(pSymbol==NULL)
return NULL;
pSymbol->start=start;
pSymbol->end=len?start+len-1:start;
pSymbol->binding=binding;
pSymbol->namelen=namelen-1;
memcpy(pSymbol->name,name,namelen);
return pSymbol;

}

extern void SymbolsDelete(RB_ROOT *pSymbols)
{

SYMBOL *pPos;
RB_NODE *next=RbFirstNode(pSymbols);
while(next) 
{
pPos=RB_ENTRY(next,SYMBOL,rb_node);
next=RbNextNode(&pPos->rb_node);
RbEraseNode(&pPos->rb_node,pSymbols);
SymbolDel(pPos);
}

}

extern void SymbolsInsert(RB_ROOT *pSymbols,SYMBOL *pSymbol)
{

RB_NODE **ppNode=&pSymbols->pRootNode;
RB_NODE *parent=NULL;
SYMBOL *pTmpSymbol;
const int pos=pSymbol->start;
while(*ppNode!=NULL) 
{
parent=*ppNode;
pTmpSymbol=RB_ENTRY(parent,SYMBOL,rb_node);
if(posstart)
ppNode=&(*ppNode)->pLeft;
else
ppNode=&(*ppNode)->pRight;
}
RbLinkNode(&pSymbol->rb_node,parent,ppNode);
RbInsertColor(&pSymbol->rb_node,pSymbols);

}

extern SYMBOL *SymbolsFind(RB_ROOT *pSymbols,int pos)
{

RB_NODE *pNode;
if(pSymbols==NULL)
return NULL;
pNode=pSymbols->pRootNode;
while(pNode) 
{
SYMBOL *pSymbol=RB_ENTRY(pNode,SYMBOL,rb_node);
if(posstart)
pNode=pNode->pLeft;
else if(pos>pSymbol->end)
pNode=pNode->pRight;
else
return pSymbol;
}
return NULL;

}

extern void SymbolDelTest(void)
{

SymbolsDelete(&sDsoInfo.symbols);

}

extern BOOL SymbolAddTest(void)
{

SYMBOL *pSymbol;
RB_ROOT *root=&sDsoInfo.symbols;
pSymbol=SymbolNew(1,0,7,"jsya1");
if(pSymbol==NULL)
return FALSE;
SymbolsInsert(root,pSymbol);
pSymbol=SymbolNew(5,0,57,"jsya5");
if(pSymbol==NULL)
return FALSE;
SymbolsInsert(root,pSymbol);
pSymbol=SymbolNew(4,0,47,"jsya4");
if(pSymbol==NULL)
return FALSE;
SymbolsInsert(root,pSymbol);
pSymbol=SymbolNew(2,0,27,"jsya2");
if(pSymbol==NULL)
return FALSE;
SymbolsInsert(root,pSymbol);
pSymbol=SymbolNew(3,0,37,"jsya3");
if(pSymbol==NULL)
return FALSE;
SymbolsInsert(root,pSymbol);
return TRUE;

}

extern SYMBOL *SymbolFindTest(int pos)
{

return SymbolsFind(&sDsoInfo.symbols,pos);

}