NetBSD Make源代码阅读三：链表之插入、查找、删除与对每个节点应用函数

/*- *----------------------------------------------------------------------- * Lst_InsertAfter -- * ???创建新节点并插入到所给链表的指定节点之后 * * 输入: * ???l ???????操作的链表 * ???ln ???????在此节点后插入 * ???d ???????数据 * * : * ???如果一切正常，返回SUCCESS ?* * 副作用: * ???创建了新的节点，并链入链表之中。如果ln是链表的最后一个节点链表的变 ??* ???量lastPtr将会改变。 ?* ???如果链表为空，且ln为NULL，lastPtr 与firstPtr都会改变。 ?* ????* *----------------------------------------------------------------------- */ReturnStatusLst_InsertAfter(Lst l, LstNode ln, void *d){ ???List ????list; ???ListNode ???lNode; ???ListNode ???nLNode; ??????/*下面两个if语句检查参数的有效性*/ ???if (LstValid (l) && (ln == NULL && LstIsEmpty (l))) { ???goto ok; ???} ???if (!LstValid (l) || LstIsEmpty (l) ?|| ! LstNodeValid (ln, l)) { ???return (FAILURE); ???} ???ok: /*参数有效*/ ???list = l; ???lNode = ln; ???/*分配新节点，并链入数据*/ ???PAlloc (nLNode, ListNode); ??????????????nLNode->datum = d; ???nLNode->useCount = nLNode->flags = 0; ???if (lNode == NULL) { ??/*链表为空*/ ???if (list->isCirc) { /*循环链表，节点前后指针指向自身*/ ???????nLNode->nextPtr = nLNode->prevPtr = nLNode; ????} else { ???????nLNode->nextPtr = nLNode->prevPtr = NULL;/*节点前后指针为NULL*/ ???} ???/*既是第一个节点，也是最后一个*/ ???list->firstPtr = list->lastPtr = nLNode; ?????} else { ???nLNode->prevPtr = lNode; ????????????nLNode->nextPtr = lNode->nextPtr; ???lNode->nextPtr = nLNode; ???if (nLNode->nextPtr != NULL) { ???????nLNode->nextPtr->prevPtr = nLNode; ???} ???if (lNode == list->lastPtr) { /*如果是在最后插入，改变lastPtr*/ ???????list->lastPtr = nLNode; ???} ???} ???return (SUCCESS);}

/*- *----------------------------------------------------------------------- * Lst_FindFrom -- * ???从指定节点开始查找与所给客户数据一致的节点，使用客户提供的比较函数 * ???来确定数据是否一致。 * ????* * 结果: * ???找到的节点或者NULL * * 副作用: * ???无 * *----------------------------------------------------------------------- */LstNodeLst_FindFrom(Lst l, LstNode ln, const void *d, ????????int (*cProc)(const void *, const void *)){ ???ListNode ???tln; ??????/*检查参数有效性*/ ???if (!LstValid (l) || LstIsEmpty (l) || !LstNodeValid (ln, l)) { ???return NULL; ???} ???tln = ln; ???/*遍历节点*/ ???do { ????????????????????if ((*cProc)(tln->datum, d) == 0) /*比较节点所含数据与所给的是否一样*/ ???????return (tln); ???tln = tln->nextPtr; ???} while (tln != ln && tln != NULL); ???return NULL;}

/*- *----------------------------------------------------------------------- * Lst_Remove -- * ???删除指定链表的指定节点 * * 返回值: * ???SUCCESS 或者 FAILURE. * * 副作用: * ???如果ln为最后一个节点，firstPtr将被设成NULL. ?* ???如果ln为第一个节点或者最后一个节点， * ???链表的firsPtr与lastPtreither 将相应地发生变化。 *----------------------------------------------------------------------- */ReturnStatusLst_Remove(Lst l, LstNode ln){ ???List ????list = l; ???ListNode ???lNode = ln; ???if (!LstValid (l) || ?????????????/*检查参数*/ ???!LstNodeValid (ln, l)) { ???????return (FAILURE); ???} ???/* ????* 从链表中断开链接 ????*/ ???if (lNode->nextPtr != NULL) { ???lNode->nextPtr->prevPtr = lNode->prevPtr; ???} ???if (lNode->prevPtr != NULL) { ???lNode->prevPtr->nextPtr = lNode->nextPtr; ???} ???/* ????* 如果 firstPtr或者lastPtr指向这个节点， ????* 则相应地调整它们。 ????*/ ???if (list->firstPtr == lNode) { ???list->firstPtr = lNode->nextPtr; ???} ???if (list->lastPtr == lNode) { ???list->lastPtr = lNode->prevPtr; ???} ???/* ????* 顺序访问相关代码.如果我们正在删除的是链表的当前节点 ?????* 重新设定当前节点为前一节点. 如果 ????* 前一节点不存在(prevPtr == NULL), 把链表的结尾设成 ????* Unknown. ????*/ ???if (list->isOpen && (list->curPtr == lNode)) { ???list->curPtr = list->prevPtr; ???if (list->curPtr == NULL) { ???????list->atEnd = Unknown; ???} ???} ???/* ????* firstPtr仍然指向ln的唯一一种情况就是它是列表剩下的 ?????* 最后一个节点。 (这是循环列表，所以lNode->nextptr == lNode） ????* ?因此，删除之后列表为空，要做如下的标记 ????*/ ???if (list->firstPtr == lNode) { ???list->firstPtr = NULL; ???} ???/* ????* 注意客户数据（the datum）没有删除。调用者必须 ????* 负责释放它。 ????*/ ???if (lNode->useCount == 0) { ???free(ln); ???} else { ???lNode->flags |= LN_DELETED; ???} ???return (SUCCESS);}

/*- *----------------------------------------------------------------------- * Lst_ForEachFrom -- * ???Apply the given function to each element of the given list. The * ???function should return 0 if traversal should continue and non- * ???zero if it should abort. * * Results: * ???None. * * Side Effects: * ???Only those created by the passed-in function. * *----------------------------------------------------------------------- *//*VARARGS2*/intLst_ForEachFrom(Lst l, LstNode ln, int (*proc)(void *, void *), ???????void *d){ ???ListNode ???tln = ln; ???List ????list = l; ???ListNode ???next; ???Boolean ????????????done; ???int ????????????????result; ???if (!LstValid (list) || LstIsEmpty (list)) { ???return 0; ???} ???do { ???/* ????* Take care of having the current element deleted out from under ????* us. ????*/ ???next = tln->nextPtr; ???/* ????* We‘re done with the traversal if ????* ?- the next node to examine is the first in the queue or ????* ???doesn‘t exist and ????* ?- nothing‘s been added after the current node (check this ????* ???after proc() has been called). ????*/ ???done = (next == NULL || next == list->firstPtr); ???(void) tln->useCount++; ???result = (*proc) (tln->datum, d); ???(void) tln->useCount--; ???/* ????* Now check whether a node has been added. ????* Note: this doesn‘t work if this node was deleted before ????* ??????the new node was added. ????*/ ???if (next != tln->nextPtr) { ???????next = tln->nextPtr; ???????done = 0; ???} ???if (tln->flags & LN_DELETED) { ???????free((char *)tln); ???} ???tln = next; ???} while (!result && !LstIsEmpty(list) && !done); ???return result;}