头文件及定义
typedef struct _RB_NODE
{
    unsigned longm_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_NODErb_node;
    intstart;
    intend;
    intnamelen;
    intbinding;
    charname[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;

实现
/*
 ************************************************************************************************************************************************************************
 * 常数与宏定义
 ************************************************************************************************************************************************************************
*/
#defineRB_RED0
#defineRB_BLACK1

#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))

#defineRB_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
{
}RB_AUGMENT_CALLBACKS,*PRB_AUGMENT_CALLBACKS;

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

static const RB_AUGMENT_CALLBACKS DummyCallbacks= 
{
};

static DSO sDsoInfo;

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

static inline RB_NODE* RbGetParent(RB_NODE *pRbNode)
{
}

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

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

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

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

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

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)) 
{
}
pTmpNode1=pSibling->pRight;
if(!pTmpNode1||RB_IS_BLACK(pTmpNode1)) 
{
pTmpNode2=pSibling->pLeft;
if(!pTmpNode2||RB_IS_BLACK(pTmpNode2)) 
{
}
break;
}
}

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)) 
{
}
pTmpNode1=pSibling->pLeft;
if(!pTmpNode1||RB_IS_BLACK(pTmpNode1)) 
{
}

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)
{
}

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


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

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

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

extern RB_NODE *RbFirstNode(const RB_ROOT *pRbRoot)
{
}

extern RB_NODE *RbLastNode(const RB_ROOT *pRbRoot)
{
}

extern RB_NODE *RbNextNode(const RB_NODE *pNode)
{
}

extern RB_NODE *RbPrevNode(const RB_NODE *pNode)
{
}

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

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

extern void SymbolsDelete(RB_ROOT *pSymbols)
{
}

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

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

extern void SymbolDelTest(void)
{
}

extern BOOL SymbolAddTest(void)
{
}

extern SYMBOL *SymbolFindTest(int pos)
{
}

11-20 00:23
查看更多