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