1 /*-
2  * listConcat.c --
3  *	Function to concatentate two lists.
4  *
5  * Copyright (c) 1988 by the Regents of the University of California
6  *
7  * Permission to use, copy, modify, and distribute this
8  * software and its documentation for any purpose and without
9  * fee is hereby granted, provided that the above copyright
10  * notice appears in all copies.  Neither the University of California nor
11  * Adam de Boor makes any representations about the suitability of this
12  * software for any purpose.  It is provided "as is" without
13  * express or implied warranty.
14  *
15  */
16 #ifndef lint
17 static char *rcsid =
18 "$Id: lstConcat.c,v 1.6 89/07/06 12:50:04 adam Exp $ SPRITE (Berkeley)";
19 #endif lint
20 
21 #include    "lstInt.h"
22 
23 /*-
24  *-----------------------------------------------------------------------
25  * Lst_Concat --
26  *	Concatenate two lists. New elements are created to hold the data
27  *	elements, if specified, but the elements themselves are not copied.
28  *	If the elements should be duplicated to avoid confusion with another
29  *	list, the Lst_Duplicate function should be called first.
30  *	If LST_CONCLINK is specified, the second list is destroyed since
31  *	its pointers have been corrupted and the list is no longer useable.
32  *
33  * Results:
34  *	SUCCESS if all went well. FAILURE otherwise.
35  *
36  * Side Effects:
37  *	New elements are created and appended the the first list.
38  *-----------------------------------------------------------------------
39  */
40 ReturnStatus
41 Lst_Concat (l1, l2, flags)
42     Lst    	  	l1; 	/* The list to which l2 is to be appended */
43     Lst    	  	l2; 	/* The list to append to l1 */
44     int	   	  	flags;  /* LST_CONCNEW if LstNode's should be duplicated
45 				 * LST_CONCLINK if should just be relinked */
46 {
47     register ListNode  	ln;     /* original LstNode */
48     register ListNode  	nln;    /* new LstNode */
49     register ListNode  	last;   /* the last element in the list. Keeps
50 				 * bookkeeping until the end */
51     register List 	list1 = (List)l1;
52     register List 	list2 = (List)l2;
53 
54     if (!LstValid (l1) || !LstValid (l2)) {
55 	return (FAILURE);
56     }
57 
58     if (flags == LST_CONCLINK) {
59 	if (list2->firstPtr != NilListNode) {
60 	    /*
61 	     * We set the nextPtr of the
62 	     * last element of list two to be NIL to make the loop easier and
63 	     * so we don't need an extra case should the first list turn
64 	     * out to be non-circular -- the final element will already point
65 	     * to NIL space and the first element will be untouched if it
66 	     * existed before and will also point to NIL space if it didn't.
67 	     */
68 	    list2->lastPtr->nextPtr = NilListNode;
69 	    /*
70 	     * So long as the second list isn't empty, we just link the
71 	     * first element of the second list to the last element of the
72 	     * first list. If the first list isn't empty, we then link the
73 	     * last element of the list to the first element of the second list
74 	     * The last element of the second list, if it exists, then becomes
75 	     * the last element of the first list.
76 	     */
77 	    list2->firstPtr->prevPtr = list1->lastPtr;
78 	    if (list1->lastPtr != NilListNode) {
79  		list1->lastPtr->nextPtr = list2->firstPtr;
80 	    }
81 	    list1->lastPtr = list2->lastPtr;
82 	}
83 	if (list1->isCirc && list1->firstPtr != NilListNode) {
84 	    /*
85 	     * If the first list is supposed to be circular and it is (now)
86 	     * non-empty, we must make sure it's circular by linking the
87 	     * first element to the last and vice versa
88 	     */
89 	    list1->firstPtr->prevPtr = list1->lastPtr;
90 	    list1->lastPtr->nextPtr = list1->firstPtr;
91 	}
92 	free ((Address)l2);
93     } else if (list2->firstPtr != NilListNode) {
94 	/*
95 	 * We set the nextPtr of the last element of list 2 to be nil to make
96 	 * the loop less difficult. The loop simply goes through the entire
97 	 * second list creating new LstNodes and filling in the nextPtr, and
98 	 * prevPtr to fit into l1 and its datum field from the
99 	 * datum field of the corresponding element in l2. The 'last' node
100 	 * follows the last of the new nodes along until the entire l2 has
101 	 * been appended. Only then does the bookkeeping catch up with the
102 	 * changes. During the first iteration of the loop, if 'last' is nil,
103 	 * the first list must have been empty so the newly-created node is
104 	 * made the first node of the list.
105 	 */
106 	list2->lastPtr->nextPtr = NilListNode;
107 	for (last = list1->lastPtr, ln = list2->firstPtr;
108 	     ln != NilListNode;
109 	     ln = ln->nextPtr)
110 	{
111 	    PAlloc (nln, ListNode);
112 	    nln->datum = ln->datum;
113 	    if (last != NilListNode) {
114 		last->nextPtr = nln;
115 	    } else {
116 		list1->firstPtr = nln;
117 	    }
118 	    nln->prevPtr = last;
119 	    nln->flags = nln->useCount = 0;
120 	    last = nln;
121 	}
122 
123 	/*
124 	 * Finish bookkeeping. The last new element becomes the last element
125 	 * of list one.
126 	 */
127 	list1->lastPtr = last;
128 
129 	/*
130 	 * The circularity of both list one and list two must be corrected
131 	 * for -- list one because of the new nodes added to it; list two
132 	 * because of the alteration of list2->lastPtr's nextPtr to ease the
133 	 * above for loop.
134 	 */
135 	if (list1->isCirc) {
136 	    list1->lastPtr->nextPtr = list1->firstPtr;
137 	    list1->firstPtr->prevPtr = list1->lastPtr;
138 	} else {
139 	    last->nextPtr = NilListNode;
140 	}
141 
142 	if (list2->isCirc) {
143 	    list2->lastPtr->nextPtr = list2->firstPtr;
144 	}
145     }
146 
147     return (SUCCESS);
148 }
149 
150