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