131a9abe6Sbostic /*
2d19a14ecSbostic * Copyright (c) 1988, 1989, 1990, 1993
3d19a14ecSbostic * The Regents of the University of California. All rights reserved.
431a9abe6Sbostic *
531a9abe6Sbostic * This code is derived from software contributed to Berkeley by
631a9abe6Sbostic * Adam de Boor.
731a9abe6Sbostic *
82b713f00Sbostic * %sccs.include.redist.c%
931a9abe6Sbostic */
1031a9abe6Sbostic
1131a9abe6Sbostic #ifndef lint
12*2bb4d294Schristos static char sccsid[] = "@(#)lstConcat.c 8.2 (Berkeley) 04/28/95";
1331a9abe6Sbostic #endif /* not lint */
1431a9abe6Sbostic
1586d9cf80Sbostic /*-
1686d9cf80Sbostic * listConcat.c --
1786d9cf80Sbostic * Function to concatentate two lists.
1886d9cf80Sbostic */
1986d9cf80Sbostic
2086d9cf80Sbostic #include "lstInt.h"
2186d9cf80Sbostic
2286d9cf80Sbostic /*-
2386d9cf80Sbostic *-----------------------------------------------------------------------
2486d9cf80Sbostic * Lst_Concat --
2586d9cf80Sbostic * Concatenate two lists. New elements are created to hold the data
2686d9cf80Sbostic * elements, if specified, but the elements themselves are not copied.
2786d9cf80Sbostic * If the elements should be duplicated to avoid confusion with another
2886d9cf80Sbostic * list, the Lst_Duplicate function should be called first.
2986d9cf80Sbostic * If LST_CONCLINK is specified, the second list is destroyed since
3086d9cf80Sbostic * its pointers have been corrupted and the list is no longer useable.
3186d9cf80Sbostic *
3286d9cf80Sbostic * Results:
3386d9cf80Sbostic * SUCCESS if all went well. FAILURE otherwise.
3486d9cf80Sbostic *
3586d9cf80Sbostic * Side Effects:
3686d9cf80Sbostic * New elements are created and appended the the first list.
3786d9cf80Sbostic *-----------------------------------------------------------------------
3886d9cf80Sbostic */
3986d9cf80Sbostic ReturnStatus
Lst_Concat(l1,l2,flags)4086d9cf80Sbostic Lst_Concat (l1, l2, flags)
4186d9cf80Sbostic Lst l1; /* The list to which l2 is to be appended */
4286d9cf80Sbostic Lst l2; /* The list to append to l1 */
4386d9cf80Sbostic int flags; /* LST_CONCNEW if LstNode's should be duplicated
4486d9cf80Sbostic * LST_CONCLINK if should just be relinked */
4586d9cf80Sbostic {
4686d9cf80Sbostic register ListNode ln; /* original LstNode */
4786d9cf80Sbostic register ListNode nln; /* new LstNode */
4886d9cf80Sbostic register ListNode last; /* the last element in the list. Keeps
4986d9cf80Sbostic * bookkeeping until the end */
5086d9cf80Sbostic register List list1 = (List)l1;
5186d9cf80Sbostic register List list2 = (List)l2;
5286d9cf80Sbostic
5386d9cf80Sbostic if (!LstValid (l1) || !LstValid (l2)) {
5486d9cf80Sbostic return (FAILURE);
5586d9cf80Sbostic }
5686d9cf80Sbostic
5786d9cf80Sbostic if (flags == LST_CONCLINK) {
5886d9cf80Sbostic if (list2->firstPtr != NilListNode) {
5986d9cf80Sbostic /*
6086d9cf80Sbostic * We set the nextPtr of the
6186d9cf80Sbostic * last element of list two to be NIL to make the loop easier and
6286d9cf80Sbostic * so we don't need an extra case should the first list turn
6386d9cf80Sbostic * out to be non-circular -- the final element will already point
6486d9cf80Sbostic * to NIL space and the first element will be untouched if it
6586d9cf80Sbostic * existed before and will also point to NIL space if it didn't.
6686d9cf80Sbostic */
6786d9cf80Sbostic list2->lastPtr->nextPtr = NilListNode;
6886d9cf80Sbostic /*
6986d9cf80Sbostic * So long as the second list isn't empty, we just link the
7086d9cf80Sbostic * first element of the second list to the last element of the
7186d9cf80Sbostic * first list. If the first list isn't empty, we then link the
7286d9cf80Sbostic * last element of the list to the first element of the second list
7386d9cf80Sbostic * The last element of the second list, if it exists, then becomes
7486d9cf80Sbostic * the last element of the first list.
7586d9cf80Sbostic */
7686d9cf80Sbostic list2->firstPtr->prevPtr = list1->lastPtr;
7786d9cf80Sbostic if (list1->lastPtr != NilListNode) {
7886d9cf80Sbostic list1->lastPtr->nextPtr = list2->firstPtr;
79*2bb4d294Schristos } else {
80*2bb4d294Schristos list1->firstPtr = list2->firstPtr;
8186d9cf80Sbostic }
8286d9cf80Sbostic list1->lastPtr = list2->lastPtr;
8386d9cf80Sbostic }
8486d9cf80Sbostic if (list1->isCirc && list1->firstPtr != NilListNode) {
8586d9cf80Sbostic /*
8686d9cf80Sbostic * If the first list is supposed to be circular and it is (now)
8786d9cf80Sbostic * non-empty, we must make sure it's circular by linking the
8886d9cf80Sbostic * first element to the last and vice versa
8986d9cf80Sbostic */
9086d9cf80Sbostic list1->firstPtr->prevPtr = list1->lastPtr;
9186d9cf80Sbostic list1->lastPtr->nextPtr = list1->firstPtr;
9286d9cf80Sbostic }
9386d9cf80Sbostic free ((Address)l2);
9486d9cf80Sbostic } else if (list2->firstPtr != NilListNode) {
9586d9cf80Sbostic /*
9686d9cf80Sbostic * We set the nextPtr of the last element of list 2 to be nil to make
9786d9cf80Sbostic * the loop less difficult. The loop simply goes through the entire
9886d9cf80Sbostic * second list creating new LstNodes and filling in the nextPtr, and
9986d9cf80Sbostic * prevPtr to fit into l1 and its datum field from the
10086d9cf80Sbostic * datum field of the corresponding element in l2. The 'last' node
10186d9cf80Sbostic * follows the last of the new nodes along until the entire l2 has
10286d9cf80Sbostic * been appended. Only then does the bookkeeping catch up with the
10386d9cf80Sbostic * changes. During the first iteration of the loop, if 'last' is nil,
10486d9cf80Sbostic * the first list must have been empty so the newly-created node is
10586d9cf80Sbostic * made the first node of the list.
10686d9cf80Sbostic */
10786d9cf80Sbostic list2->lastPtr->nextPtr = NilListNode;
10886d9cf80Sbostic for (last = list1->lastPtr, ln = list2->firstPtr;
10986d9cf80Sbostic ln != NilListNode;
11086d9cf80Sbostic ln = ln->nextPtr)
11186d9cf80Sbostic {
11286d9cf80Sbostic PAlloc (nln, ListNode);
11386d9cf80Sbostic nln->datum = ln->datum;
11486d9cf80Sbostic if (last != NilListNode) {
11586d9cf80Sbostic last->nextPtr = nln;
11686d9cf80Sbostic } else {
11786d9cf80Sbostic list1->firstPtr = nln;
11886d9cf80Sbostic }
11986d9cf80Sbostic nln->prevPtr = last;
12086d9cf80Sbostic nln->flags = nln->useCount = 0;
12186d9cf80Sbostic last = nln;
12286d9cf80Sbostic }
12386d9cf80Sbostic
12486d9cf80Sbostic /*
12586d9cf80Sbostic * Finish bookkeeping. The last new element becomes the last element
12686d9cf80Sbostic * of list one.
12786d9cf80Sbostic */
12886d9cf80Sbostic list1->lastPtr = last;
12986d9cf80Sbostic
13086d9cf80Sbostic /*
13186d9cf80Sbostic * The circularity of both list one and list two must be corrected
13286d9cf80Sbostic * for -- list one because of the new nodes added to it; list two
13386d9cf80Sbostic * because of the alteration of list2->lastPtr's nextPtr to ease the
13486d9cf80Sbostic * above for loop.
13586d9cf80Sbostic */
13686d9cf80Sbostic if (list1->isCirc) {
13786d9cf80Sbostic list1->lastPtr->nextPtr = list1->firstPtr;
13886d9cf80Sbostic list1->firstPtr->prevPtr = list1->lastPtr;
13986d9cf80Sbostic } else {
14086d9cf80Sbostic last->nextPtr = NilListNode;
14186d9cf80Sbostic }
14286d9cf80Sbostic
14386d9cf80Sbostic if (list2->isCirc) {
14486d9cf80Sbostic list2->lastPtr->nextPtr = list2->firstPtr;
14586d9cf80Sbostic }
14686d9cf80Sbostic }
14786d9cf80Sbostic
14886d9cf80Sbostic return (SUCCESS);
14986d9cf80Sbostic }
15086d9cf80Sbostic
151