数据连接件

数据连接件为嵌入于数据结构体内的通用部件，主要用于构造双向链表，使得同种或异种的数据结构能用过连接部件关联在一起，数据结构体向外部暴露连接件，外部应用通过连接件访问数据结构，这样可以屏蔽数据结构的内部细节，并且使访问接口的设计显得简洁和一致。

举例来说：一个文档集合有多个文档聚合而成，每个文档又含有许多条目，那么采用连接件来构造通常可以图示如下：

文档集合、文档、条目的数据结构在这里可以模拟申明如下：

typedef struct _DocumentSet{

LINK lkDocuments;

…/*declare some document set properties*/

}DocumentSet;

typedef struct _Document{

LINK lkSelf;

LINK lkItems;

…/*declare some document properties*/

}Document;

typedef struct _Item{

LINK lkSelf;

/*declare some item properties*/

}Item;

文档集合的数据结构中含有一个连接件lkDocuments，为文档集合的根部件，用于维护文档的链表。文档的数据结构中含有两个数据连接件，一个为自身部件lkSelf，用于向外部暴露自己，作为文档的访问入口，并链接到文档集合结构中的lkDocuments根部件中，形成文档集合，另一个为条目集合的根部件lkItems，用于维护条目的链表。条目的数据结构中含有一个数据连接件，用于向外部暴露自己，作为条目的访问入口，并链接到文档结构中的lkItems根部件中，形成条目集合。

连接件的操作即为双向链表的操作，包括插入、删除、检索、位置交换、节点计数等操作，其中需要的注意的是，根连接件和数据连接件的作用是不同的，数据连接件表征一个数据条目，而根连接件始终是维护数据连接件链表的唯一部件，根连接件在使用之前必须初始化，即构造一个空的双向链表。

/*************************************************************

       EasySoft xdl v3.0

       (c) 2003-2006 EasySoft Corporation.  All Rights Reserved.

       @doc xdl.rtf: link component

       @module       link.h | link component interface file

       @devnote PowerSuite 2003.01 - 2006.12

*************************************************************/

#ifndef _LINK_H

#define _LINK_H

#include "xdl\xdlexp.h"

#ifdef __cplusplus

extern "C" {

#endif

/*根连接件节点标识*/

#define lkRoot        0

typedef struct _Link* LINKPTR ;

typedef struct _Link{

       LINKPTR prev; /*前驱*/

       LINKPTR next; /*后继*/

       int tag;

}LINK;

/*连接件首位标识符*/

#define LINK_FIRST (LINKPTR)0x00000000

/*连接件末位标识符*/

#define LINK_LAST (LINKPTR)0xFFFFFFFF

XDL_API void InitRootLink(LINKPTR root);

/*

功能：初始化连接件

参数：root为根连接件指针

返回：无

*/

XDL_API void InsertLink(LINKPTR root,LINKPTR plk,LINKPTR pnew);

/*

功能：附加数据连接件到链表

参数：root为根连接件指针，plk为位置标识符或数据连接件指针，pnew为待插入的数据连接件指针

返回：无

*/

XDL_API LINKPTR DeleteLink(LINKPTR root,LINKPTR plk);

/*

功能：从链表中撤离数据连接件

参数：root为根连接件指针，plk为位置标识符或存在于链表中的数据连接件指针

返回：从链表中撤离的数据连接件指针，不存在则返回NULL

*/

XDL_API int LinkCount(LINKPTR root);

/*

功能：取得链表中数据连接件的个数

参数：root为根连接件指针

返回：数据连接件的计数

*/

XDL_API LINKPTR GetLinkAt(LINKPTR root,int index);

/*

功能：由索引从链表取得数据连接件

参数：root为根连接件指针，index为由0开始的索引序号

返回：相应位置的数据连接件指针，不存在则返回NULL

*/

XDL_API int GetLinkIndex(LINKPTR root,LINKPTR plk);

/*

功能：从链表取得数据连接件位置索引

参数：root为根连接件指针，plk为数据连接件指针或位置标识符

返回：数据连接件的位置索引，不存在则返回-1

*/

XDL_API LINKPTR GetFirstLink(LINKPTR root);

/*

功能：从链表取得首位数据连接件

参数：root为根连接件指针

返回：首位数据连接件指针，不存在则返回NULL

*/

XDL_API LINKPTR GetNextLink(LINKPTR plk);

/*

功能：从链表取得后继数据连接件

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：后继数据连接件指针，不存在则返回NULL

*/

XDL_API LINKPTR GetPrevLink(LINKPTR plk);

/*

功能：从链表取得前驱数据连接件

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：前驱数据连接件指针，不存在则返回NULL

*/

XDL_API LINKPTR GetLastLink(LINKPTR root);

/*

功能：从链表取得末位数据连接件

参数：root为根连接件指针

返回：首位数据连接件指针，不存在则返回NULL

*/

XDL_API LINKPTR GetRootLink(LINKPTR plk);

/*

功能：由数据连接件取得根连接件

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：根连接件指针，不存在则返回NULL

*/

XDL_API void SwitchLink(LINKPTR plk1,LINKPTR plk2);

/*

功能：交换两个数据连接件的位置

参数：plk1,plk2为存在于链表中的数据连接件指针，不能为位置标识符

返回：无

*/

XDL_API void SwitchLinkToNext(LINKPTR plk);

/*

功能：与后继数据连接件交换位置

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：无

*/

XDL_API void SwitchLinkToPrev(LINKPTR plk);

/*

功能：与前驱数据连接件交换位置

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：无

*/

XDL_API void SwitchLinkToFirst(LINKPTR plk);

/*

功能：把数据连接件交换至首位

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：无

*/

XDL_API void SwitchLinkToLast(LINKPTR plk);

/*

功能：把数据连接件交换至末位

参数：plk为存在于链表中的数据连接件指针，不能为位置标识符

返回：无

*/

XDL_API void PushLink(LINKPTR root,LINKPTR plk);

/*

功能：附加数据连接件到链表首位

参数：root为根连接件指针，plk为待插入的数据连接件指针

返回：无

*/

XDL_API LINKPTR PopLink(LINKPTR root);

/*

功能：从链表撤离首位数据连接件

参数：root为根连接件指针

返回：数据连接件指针，不存在则返回NULL

*/

XDL_API LINKPTR PeekLink(LINKPTR root);

/*

功能：取得链表首位数据连接件

参数：root为根连接件指针

返回：数据连接件指针，不存在则返回NULL

*/

#ifdef __cplusplus

}

#endif

#endif /*_LINK_H*/

/*************************************************************

       EasySoft xdl v3.0

       (c) 2003-2006 EasySoft Corporation.  All Rights Reserved.

       @doc xdl.rtf: link component

       @module       link.c | link component implement file

       @devnote PowerSuite 2003.01 - 2006.12

*************************************************************/

#include <stdlib.h>

#include <assert.h>

#include "xdl\link.h"

/***************************************************

***************************************************/

void InitRootLink(LINKPTR root)

{

       assert(root);

       assert(root->tag == lkRoot);

       /*initialize double link*/

       root->next = root;

       root->prev = root;

}

void InsertLink(LINKPTR root,LINKPTR plk,LINKPTR pnew)

{

       assert(root && root->tag == lkRoot);

       assert(root != plk);

       assert(pnew && pnew->tag != lkRoot);

       if(plk == LINK_FIRST)

       {

              plk = root;       /* will insert into first */

       }else if(plk == LINK_LAST)

       {

              plk = root->prev;     /* will insert into last */

       }else

       {

              assert(root == GetRootLink(plk)); /* assert plk in the list*/

       }

       /*insert pnew into list after plk*/

       pnew->prev = plk;

       pnew->next = plk->next;

       assert(plk->next);

       plk->next->prev = pnew;

       plk->next = pnew;           

}

LINKPTR DeleteLink(LINKPTR root,LINKPTR plk)

{    

       assert(root && root->tag == lkRoot);

       assert(root != plk);

       if(root->next->tag == lkRoot)

              return NULL;

       if(plk == LINK_FIRST)

       {

              plk = root->next;     /* delete first link ptr */

       }else if(plk == LINK_LAST)

       {

              plk = root->prev;     /* delete last link ptr */

       }else

       {

              assert(plk->tag != lkRoot);

              assert(root == GetRootLink(plk)); /* assert plk in the list*/

       }

       /*delete plk from list*/

       plk->prev->next = plk->next;

       plk->next->prev = plk->prev;

       return plk;

}

LINKPTR GetLinkAt(LINKPTR root,int index)

{

       LINKPTR cur;

       assert(root);

       assert(root->tag == lkRoot);

       assert(index >= 0);

       cur = root->next;

       while(cur->tag != lkRoot && index--)

              cur = cur->next;

       if(cur->tag == lkRoot)

              return NULL; /* empty list*/

       else

              return cur;

}

int GetLinkIndex(LINKPTR root,LINKPTR plk)

{

       int count;

       assert(root && root->tag == lkRoot);

       assert(root != plk);

       if(plk == LINK_FIRST)

       {

              plk = root->next;     /* delete first link ptr */

       }else if(plk == LINK_LAST)

       {

              plk = root->prev;     /* delete last link ptr */

       }else

       {

              assert(plk->tag != lkRoot);

       }

       count = 0;

       while(plk && plk->tag != lkRoot)

       {

              plk = plk->prev;

              count ++;

       }

       return count - 1;

}

LINKPTR GetFirstLink(LINKPTR root)

{

       assert(root);

       assert(root->tag == lkRoot);

       if(root->next->tag == lkRoot)

              return NULL;    /* empty list */

       else

              return root->next;

}

LINKPTR GetNextLink(LINKPTR plk)

{

       assert(plk);

       assert(plk->tag != lkRoot);

       if(plk->next->tag == lkRoot)

              return NULL;    /*plk is tail or list is empty*/

       else

              return plk->next;

}

LINKPTR GetPrevLink(LINKPTR plk)

{

       assert(plk);

       assert(plk->tag != lkRoot);

       if(plk->prev->tag == lkRoot)

              return NULL;    /* plk is head or list is empty*/

       else

              return plk->prev;

}

LINKPTR GetLastLink(LINKPTR root)

{

       assert(root);

       assert(root->tag == lkRoot);

       if(root->prev->tag == lkRoot)

              return NULL;    /* empty list */

       else

              return root->prev;

}

LINKPTR GetRootLink(LINKPTR plk)

{

       assert(plk);

       assert(plk->tag != lkRoot);

       while(plk->tag != lkRoot && plk->prev != NULL)

              plk = plk->prev;

       if(plk->tag != lkRoot)

              assert(0);

       return plk;

}

void SwitchLink(LINKPTR plk1,LINKPTR plk2)

{

       LINKPTR root,prev1,prev2;

       assert(plk1 && plk1->tag != lkRoot);

       assert(plk2 && plk2->tag != lkRoot);

       root = GetRootLink(plk1);

       assert(root == GetRootLink(plk2));

       /*delete then inster*/

       if(plk1 == GetPrevLink(plk2))

       {

              DeleteLink(root,plk1);

              InsertLink(root,plk2,plk1);

              return;

       }else if(plk2 == GetPrevLink(plk1))

       {

              DeleteLink(root,plk2);

              InsertLink(root,plk1,plk2);

              return;

       }

       prev1 = GetPrevLink(plk1);

       prev2 = GetPrevLink(plk2);

       DeleteLink(root,plk2);

       if(prev1 == NULL)

              InsertLink(root,LINK_FIRST,plk2);

       else

              InsertLink(root,prev1,plk2);

       DeleteLink(root,plk1);

       if(prev2 == NULL)

              InsertLink(root,LINK_FIRST,plk1);

       else

              InsertLink(root,prev2,plk1);

}

void SwitchLinkToNext(LINKPTR plk)

{

       LINKPTR root,next;

       assert(plk && plk->tag != lkRoot);

       root = GetRootLink(plk);

       assert(root);

       next = GetNextLink(plk);

       DeleteLink(root,plk);

       if(next == NULL)

              InsertLink(root,LINK_LAST,plk);

       else

              InsertLink(root,next,plk);

}

void SwitchLinkToPrev(LINKPTR plk)

{

       LINKPTR root,prev;

       assert(plk && plk->tag != lkRoot);

       root = GetRootLink(plk);

       assert(root);

       prev = GetPrevLink(plk);

       if(prev)

              prev = GetPrevLink(plk);

       DeleteLink(root,plk);

       if(prev == NULL)

              InsertLink(root,LINK_FIRST,plk);

       else

              InsertLink(root,prev,plk);

}

void SwitchLinkToLast(LINKPTR plk)

{

       LINKPTR root;

       assert(plk && plk->tag != lkRoot);

       root = GetRootLink(plk);

       assert(root);

       DeleteLink(root,plk);

       InsertLink(root,LINK_LAST,plk);

}

void SwitchLinkToFirst(LINKPTR plk)

{

       LINKPTR root;

       assert(plk && plk->tag != lkRoot);

       root = GetRootLink(plk);

       assert(root);

       DeleteLink(root,plk);

       InsertLink(root,LINK_FIRST,plk);

}

int LinkCount(LINKPTR root)

{

       LINKPTR plk;

       int count = 0;

       assert(root && root->tag == lkRoot);

       plk = GetFirstLink(root);

       while(plk)

       {

              count ++;

              plk = GetNextLink(plk);

       }

       return count;

}

void PushLink(LINKPTR root,LINKPTR ptr)

{

       assert(root && root->tag == lkRoot);

       assert(ptr && ptr->tag != lkRoot);

       InsertLink(root,LINK_FIRST,ptr);

}

LINKPTR PopLink(LINKPTR root)

{

       assert(root && root->tag == lkRoot);

       return DeleteLink(root,LINK_FIRST);

}

LINKPTR PeekLink(LINKPTR root)

{

       assert(root && root->tag == lkRoot);

       return GetFirstLink(root);

}