NetBSD Make源代码阅读二：链表之创建与销毁

浏览数：43 / 时间：2015年06月09日

1.创建链表

/*-
 *-----------------------------------------------------------------------
 * Lst_Init --
 *    创建并初始化一个链表 
 *
 * 输入:
 *    circ    如果是循环链表则为TRUE     
 *
 * 结果:
 *    创建好的链表（空链表）.
 *
 * 副作用:
 *    链表已经创建，还需要做啥?
 *
 *-----------------------------------------------------------------------
 */
Lst
Lst_Init(Boolean circ)
{
    List    nList;          /* List为链表结构指针类型*/

    PAlloc (nList, List);    /*分配链表结构内存，并让nList指向该结构*/

    nList->firstPtr = NULL;     /*初始化链表结构各成员变量*/
    nList->lastPtr = NULL;
    nList->isOpen = FALSE;
    nList->isCirc = circ;
    nList->atEnd = Unknown;

    return (nList);           /*返回链表结构指针*/
}

其实，这个函数就是分配链表结构内存，然后初始化结构成员变量。值得注意的是，分配链表结构内存的操作PAlloc。

/*
 * PAlloc (var, ptype) --
 *    分配 ‘ptype‘ 类型结构的内存，并把地址赋给变量 ‘var‘
 */
#define    PAlloc(var,ptype)    var = (ptype) bmake_malloc(sizeof *(var))

/*
 * bmake_malloc --
 *    调用malloc分配内存，如果出错，打印错误信息到stderr并退出
 */
void *
bmake_malloc(size_t len)
{
    void *p;

    if ((p = malloc(len)) == NULL)
        enomem();
    return(p);
}

2. 销毁链表

链表结构分为两部分一个是链表头结构List,一个是其节点ListNode。而在ListNode中包含一个指向客户自定义数据的指针。下面这个函数，为了遍历各个节点方便，把最后一个节点的nextptr设成null，这主要针对循环列表。

链表销毁的步骤：

　　1.依次释放链表的节点，如果指定了freeProc，则调用它释放节点对应的客户数据

　　2.然后释放链表头结构。

/*-
 *-----------------------------------------------------------------------
 * Lst_Destroy --
 *    销毁链表并释放其所有资源。如果指定了freeProc ，则在每个节点释放前
 *    对其应用该函数。
 *    
 *
 * 返回值:
 *    无
 *
 * 副作用:
 *    所给的链表完全销毁
 *
 *-----------------------------------------------------------------------
 */
void
Lst_Destroy(Lst list, FreeProc *freeProc)
{
    ListNode    ln;
    ListNode    tln = NULL;

    if (list == NULL)
    return;

    /* 为了让遍历更简单 */
    if (list->lastPtr != NULL)                    /×如果所给的链表不是空的×/
    list->lastPtr->nextPtr = NULL;      
    else {
    free(list);                                    /×释放链表头结构×/
    return;
    }

    if (freeProc) {
    for (ln = list->firstPtr; ln != NULL; ln = tln) {
         tln = ln->nextPtr;
         freeProc(ln->datum);    /×释放节点指向的数据*/
         free(ln);                      /*释放节点*/
    }
    } else {
    for (ln = list->firstPtr; ln != NULL; ln = tln) {
         tln = ln->nextPtr;
         free(ln);
    }
    }

    free(list);   / *释放链表头×/
}