当初看LINUX时感觉他的通用连接件设计得非常巧妙，于是我写了一个，秉承了他的思想。写通用连接件的目的是为后续开发中的树型关系数据和线性关系数据提供一致的节点连接，连接件在数据节被创建是被嵌入到数据节点中，并最终返回连接件指针作为外部访问数据节点的一致入口，以求接口展示的简洁和一致性，并对内部数据起到隐藏和降低被非法篡改的危险性。
一、连接件的定义：
连接件的结构是一个双端链表结构，定义下：
typedef struct Link* LINKPTR ;
typedef struct Link{
LINKPTR prior; /*连接件的前趋指针*/
LINKPTR next; /*连接件的后续指针*/
int tag; /*连接件的宿主数据节点的类型*/
}LINK;
/*指明链表中的两个特殊位置*/
#define LINK_FIRST (LINKPTR)0x00000000 /*链表首位*/
#define LINK_LAST (LINKPTR)0xFFFFFFFF /*链表末位*/
/*定义连接件的宿主数据节点的类型*/
typedef enum{
lkRoot = 0, /*根节点*/
lkHashEntry = 1, /*哈希表子项节点*/
lkHashTable = 2, /*哈希表节点*/
...
}LinkType;
二、连接件的实现：
连接件链表由根节点和数据承节点组成，根节点是数据节点的桩连接件指针，用于控制和连接子数据节点，数据承节点是数据节点本身的连接件，用于返回给外部作为连接或访问之用。实现如下：
/*初始化根节点
root: 根节点指针*/
void InitRootLink(LINKPTR root)
{
assert(root);
root->tag == lkRoot; /*置为根节点*/
root->next = root; /*后继指向根节点*/
root->prior = root; /*前驱指向根节点*/
}
/*在链表中插入一连接件
root: 根节点指针
plk: 参考位置的连接件指针
pnew: 待插入的连接件指针
*/
void InsertLinkAt(LINKPTR root,LINKPTR plk,LINKPTR pnew)
{
assert(root);
assert(root->tag == lkRoot);
assert(root != plk);
assert(pnew);
if(plk == LINK_FIRST)
{
plk = root;/*如果参考指针为首位标识，则前驱指针为根指针*/
}else if(plk == LINK_LAST)
{
plk = root->prior;/*如果参考指针为末位标识，则前驱指针为末位指针*/
}else
{
assert(GetRootLink(plk) == root); /*断言参考指针应在链表中*/
}
/*插入指针到链表中*/
pnew->prior = plk;
pnew->next = plk->next;
assert(plk->next); /*断言在双端链表中，节点一定存在后继*/
plk->next->prior = pnew;
plk->next = pnew;
}
/*从链表中删除一个节点
root: 根节点
plk: 待删除的节点*/
LINKPTR DeleteLinkAt(LINKPTR root,LINKPTR plk)
{
LINKPTR cur;
assert(root);
assert(root->tag == lkRoot);
assert(root != plk);
if(plk == LINK_FIRST)
{
plk = root->next;?/*如果参考指针为首位标识，则删除首位节点*/
}else if(plk == LINK_LAST)
{
plk = root->prior;?/*如果参考指针为末位标识，则删除末位节点*/
}else
{
assert(GetRootLink(plk) == root); /*断言参考指针应在链表中*/
}
/*从链表中删除该节点，注意由于连接件是有数据节点创建的，归有数据节去释放，在此不作内存释放处理*/
plk->prior->next = plk->next;
plk->next->prior = plk->prior;
return plk;
}
/*从基于0的索引位置取得连接件指针
root: 根指针
index: 位置*/
LINKPTR GetLinkAt(LINKPTR root,int index)
{
LINKPTR cur;
assert(root);
assert(root->tag == lkRoot);
cur = root->next;
while(cur->tag != lkRoot && index--)
cur = cur->next;
/*空链表或索引大于等于节计数时返回空指针，根节不参与计数*/
if(cur->tag == lkRoot)
return NULL;
else
return cur;
}
/*取得首位指针
root: 根指针*/
LINKPTR GetFirstLink(LINKPTR root)
{
assert(root);
assert(root->tag == lkRoot);
if(root->next->tag == lkRoot)
return NULL;?/*空链表*/
else
return root->next;
}
/*取得后续指针
plk: 当前参考指针*/
LINKPTR GetNextLink(LINKPTR plk)
{
assert(plk);
assert(plk->tag != lkRoot);
if(plk->next->tag == lkRoot)
return NULL;?/*无后续指针*/
else
return plk->next;
}
/*取得前驱指针
plk: 当前参考指针*/
LINKPTR GetPrevLink(LINKPTR plk)
{
assert(plk);
assert(plk->tag != lkRoot);
if(plk->prior->tag == lkRoot)
return NULL;/*无前驱指针*/
else
return plk->prior;
}
/*取得末位指针
root: 根指针*/
LINKPTR GetLastLink(LINKPTR root)
{
assert(root);
assert(root->tag == lkRoot);
if(root->prior->tag == lkRoot)
return NULL;?/*空链表*/
else
return root->prior;
}
/*取得根指针
plk: 当前参考指针*/
LINKPTR GetRootLink(LINKPTR plk)
{
assert(plk);
assert(plk->tag != lkRoot);
while(plk->tag != lkRoot && plk->prior != NULL/*防止错误的链表导致死循环*/)
plk = plk->prior;
if(plk->tag != lkRoot)
assert(0); /*非正常的链表，则引发断言错误*/
return plk;
}
/*交换邻接的两个指针
pre: 前驱指针
next: 后续指针*/
void SwitchLink(LINKPTR pre,LINKPTR next)
{
LINKPTR root;
assert(pre && next && next->tag != lkRoot && pre->tag != lkRoot);
assert(pre->next == next && next->prior == pre);
root = GetRootLink(pre);
assert(root);
/*先删除后插入*/
assert(pre == DeleteLinkAt(root,pre));
InsertLinkAt(root,next,pre);
}
/*链表指针计数
root: 根节点*/
int LinkCount(LINKPTR root)
{
int count = 0;
LINKPTR plk;
plk = GetFirstLink(root);
while(plk)
{
count ++;
plk = GetNextLink(plk);
}
return count; /*根节不参与计数*/
}
四、连接件的应用举例：
定义一个父项目:
typedef struct _Parent{
LINK lk; /*自身连接件*/
LINK lkChilds; /*子项目连接件根节点*/
char szName[30];
... /*其他属性*/
}Parent;
定义一个子项目：
typedef struct _Child{
LINK lk; /*自身连接件*/
char szName[30];
... /*其他属性*/
}Child;
可以看到，连接件均被嵌入到数据节中。
/*定义数据节连接件标识*/
#define tagParent?100
#define tagChild??101
/*从连接件指针中恢复数据节点*/
#define ChildFromLink(p) ((Child*)((unsigned int)p - (unsigned int)&(((Child*)0)->lk)))
#define ParentFromLink(p) ((Parent*)((unsigned int)p - (unsigned int)&(((Parent*)0)->lk)))
LINKPTR create_parent(cont char* szName)
{
Parent* pPa;
pPa = (Parent*)calloc(1,sizeof(Parent));
pPa->lk.tag = tagParent;
InitRootLink(&pPa->lkChilds);
... /*set parent name*/
/*返回连接件指针*/
return &pPa->lk;
}
int get_parent_name(LINKPTR ptrParent,char* buf,int max)
{
Parent* pPa;
int len;
assert(ptrParent && ptrParent->tag == tagParent);
pPa = ParentFromLink(ptrParent);
... /*copy parent name to buf and return copyed bytes*/
return len;
}
void destroy_parent(LINKPTR ptrParent)
{
Parent* pPa;
LINKPTR ptrChild;
assert(ptrParent && ptrParent->tag == tagParent);
pPa = ParentFromLink(ptrParent);
/*clear you child node*/
while(ptrChild = GetFirstLink(&pPa->lkChilds))
del_child(ptrParent,ptrChild);
free(pPa);
}
LINKPTR add_child(LINKPTR ptrParent,const char* szName)
{
Parent* pPa;
Child* pCh;
assert(ptrParent && ptrParent->tag == tagParent);
pPa = ParentFromLink(ptrParent);
pCh = (Child*)calloc(1,sizeof(Child));
pCh->lk.tag = tagChild;
... /*set child name*/
InsertLinkAt(&pPa->lkChilds,LINK_LAST,&pCh->lk);
return &pCh->lk;
}
int get_child_name(LINKPTR ptrChild,char* buf,int max)
{
Child* pCh;
int len;
assert(ptrChild && ptrChild->tag == tagChild);
pCh = ChildFromLink(ptrChild);
... /*copy child name to buf and return copyed bytes*/
return len;
}
void del_child(LINKPTR ptrParent,LINKPTR ptrChild)
{
Parent* pPa;
Child* pCh;
assert(ptrParent && ptrParent->tag == tagParent);
pPa = ParentFromLink(ptrParent);
assert(ptrChild && ptrChild->tag == tagChild);
pCh = ChildFromLInk(ptrChild);
assert(ptrChild == DeleteLinkAt(&pPa->lkChilds,ptrChild));
free(pCh);
}
连接件的设计简述至此，感谢LINUX！在下一篇中，将叙述哈希表的设计以及连接件在其中的应用。诚望大家批评指正，有时间的话就给我发个Mail吧！jdhot2003@hotmail.com
