Commit | Line | Data |
---|---|---|
bb2109e7 KB |
1 | /* |
2 | * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
c65fedcf | 4 | * |
bb2109e7 KB |
5 | * This code is derived from software contributed to Berkeley by |
6 | * Adam de Boor. | |
c65fedcf | 7 | * |
f15db449 | 8 | * %sccs.include.redist.c% |
c65fedcf | 9 | */ |
bb2109e7 | 10 | |
c65fedcf | 11 | #ifndef lint |
f15db449 | 12 | static char sccsid[] = "@(#)lstConcat.c 5.3 (Berkeley) %G%"; |
bb2109e7 KB |
13 | #endif /* not lint */ |
14 | ||
15 | /*- | |
16 | * listConcat.c -- | |
17 | * Function to concatentate two lists. | |
18 | */ | |
c65fedcf KB |
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 | |
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 | } | |
80 | list1->lastPtr = list2->lastPtr; | |
81 | } | |
82 | if (list1->isCirc && list1->firstPtr != NilListNode) { | |
83 | /* | |
84 | * If the first list is supposed to be circular and it is (now) | |
85 | * non-empty, we must make sure it's circular by linking the | |
86 | * first element to the last and vice versa | |
87 | */ | |
88 | list1->firstPtr->prevPtr = list1->lastPtr; | |
89 | list1->lastPtr->nextPtr = list1->firstPtr; | |
90 | } | |
91 | free ((Address)l2); | |
92 | } else if (list2->firstPtr != NilListNode) { | |
93 | /* | |
94 | * We set the nextPtr of the last element of list 2 to be nil to make | |
95 | * the loop less difficult. The loop simply goes through the entire | |
96 | * second list creating new LstNodes and filling in the nextPtr, and | |
97 | * prevPtr to fit into l1 and its datum field from the | |
98 | * datum field of the corresponding element in l2. The 'last' node | |
99 | * follows the last of the new nodes along until the entire l2 has | |
100 | * been appended. Only then does the bookkeeping catch up with the | |
101 | * changes. During the first iteration of the loop, if 'last' is nil, | |
102 | * the first list must have been empty so the newly-created node is | |
103 | * made the first node of the list. | |
104 | */ | |
105 | list2->lastPtr->nextPtr = NilListNode; | |
106 | for (last = list1->lastPtr, ln = list2->firstPtr; | |
107 | ln != NilListNode; | |
108 | ln = ln->nextPtr) | |
109 | { | |
110 | PAlloc (nln, ListNode); | |
111 | nln->datum = ln->datum; | |
112 | if (last != NilListNode) { | |
113 | last->nextPtr = nln; | |
114 | } else { | |
115 | list1->firstPtr = nln; | |
116 | } | |
117 | nln->prevPtr = last; | |
118 | nln->flags = nln->useCount = 0; | |
119 | last = nln; | |
120 | } | |
121 | ||
122 | /* | |
123 | * Finish bookkeeping. The last new element becomes the last element | |
124 | * of list one. | |
125 | */ | |
126 | list1->lastPtr = last; | |
127 | ||
128 | /* | |
129 | * The circularity of both list one and list two must be corrected | |
130 | * for -- list one because of the new nodes added to it; list two | |
131 | * because of the alteration of list2->lastPtr's nextPtr to ease the | |
132 | * above for loop. | |
133 | */ | |
134 | if (list1->isCirc) { | |
135 | list1->lastPtr->nextPtr = list1->firstPtr; | |
136 | list1->firstPtr->prevPtr = list1->lastPtr; | |
137 | } else { | |
138 | last->nextPtr = NilListNode; | |
139 | } | |
140 | ||
141 | if (list2->isCirc) { | |
142 | list2->lastPtr->nextPtr = list2->firstPtr; | |
143 | } | |
144 | } | |
145 | ||
146 | return (SUCCESS); | |
147 | } | |
148 |