1 /* $OpenBSD: lstConcat.c,v 1.3 1996/11/30 21:09:11 millert Exp $ */ 2 /* $NetBSD: lstConcat.c,v 1.6 1996/11/06 17:59:34 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1988, 1989, 1990, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Adam de Boor. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. All advertising materials mentioning features or use of this software 20 * must display the following acknowledgement: 21 * This product includes software developed by the University of 22 * California, Berkeley and its contributors. 23 * 4. Neither the name of the University nor the names of its contributors 24 * may be used to endorse or promote products derived from this software 25 * without specific prior written permission. 26 * 27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37 * SUCH DAMAGE. 38 */ 39 40 #ifndef lint 41 #if 0 42 static char sccsid[] = "@(#)lstConcat.c 8.1 (Berkeley) 6/6/93"; 43 #else 44 static char rcsid[] = "$OpenBSD: lstConcat.c,v 1.3 1996/11/30 21:09:11 millert Exp $"; 45 #endif 46 #endif /* not lint */ 47 48 /*- 49 * listConcat.c -- 50 * Function to concatentate two lists. 51 */ 52 53 #include "lstInt.h" 54 55 /*- 56 *----------------------------------------------------------------------- 57 * Lst_Concat -- 58 * Concatenate two lists. New elements are created to hold the data 59 * elements, if specified, but the elements themselves are not copied. 60 * If the elements should be duplicated to avoid confusion with another 61 * list, the Lst_Duplicate function should be called first. 62 * If LST_CONCLINK is specified, the second list is destroyed since 63 * its pointers have been corrupted and the list is no longer useable. 64 * 65 * Results: 66 * SUCCESS if all went well. FAILURE otherwise. 67 * 68 * Side Effects: 69 * New elements are created and appended the the first list. 70 *----------------------------------------------------------------------- 71 */ 72 ReturnStatus 73 Lst_Concat (l1, l2, flags) 74 Lst l1; /* The list to which l2 is to be appended */ 75 Lst l2; /* The list to append to l1 */ 76 int flags; /* LST_CONCNEW if LstNode's should be duplicated 77 * LST_CONCLINK if should just be relinked */ 78 { 79 register ListNode ln; /* original LstNode */ 80 register ListNode nln; /* new LstNode */ 81 register ListNode last; /* the last element in the list. Keeps 82 * bookkeeping until the end */ 83 register List list1 = (List)l1; 84 register List list2 = (List)l2; 85 86 if (!LstValid (l1) || !LstValid (l2)) { 87 return (FAILURE); 88 } 89 90 if (flags == LST_CONCLINK) { 91 if (list2->firstPtr != NilListNode) { 92 /* 93 * We set the nextPtr of the 94 * last element of list two to be NIL to make the loop easier and 95 * so we don't need an extra case should the first list turn 96 * out to be non-circular -- the final element will already point 97 * to NIL space and the first element will be untouched if it 98 * existed before and will also point to NIL space if it didn't. 99 */ 100 list2->lastPtr->nextPtr = NilListNode; 101 /* 102 * So long as the second list isn't empty, we just link the 103 * first element of the second list to the last element of the 104 * first list. If the first list isn't empty, we then link the 105 * last element of the list to the first element of the second list 106 * The last element of the second list, if it exists, then becomes 107 * the last element of the first list. 108 */ 109 list2->firstPtr->prevPtr = list1->lastPtr; 110 if (list1->lastPtr != NilListNode) { 111 list1->lastPtr->nextPtr = list2->firstPtr; 112 } else { 113 list1->firstPtr = list2->firstPtr; 114 } 115 list1->lastPtr = list2->lastPtr; 116 } 117 if (list1->isCirc && list1->firstPtr != NilListNode) { 118 /* 119 * If the first list is supposed to be circular and it is (now) 120 * non-empty, we must make sure it's circular by linking the 121 * first element to the last and vice versa 122 */ 123 list1->firstPtr->prevPtr = list1->lastPtr; 124 list1->lastPtr->nextPtr = list1->firstPtr; 125 } 126 free ((Address)l2); 127 } else if (list2->firstPtr != NilListNode) { 128 /* 129 * We set the nextPtr of the last element of list 2 to be nil to make 130 * the loop less difficult. The loop simply goes through the entire 131 * second list creating new LstNodes and filling in the nextPtr, and 132 * prevPtr to fit into l1 and its datum field from the 133 * datum field of the corresponding element in l2. The 'last' node 134 * follows the last of the new nodes along until the entire l2 has 135 * been appended. Only then does the bookkeeping catch up with the 136 * changes. During the first iteration of the loop, if 'last' is nil, 137 * the first list must have been empty so the newly-created node is 138 * made the first node of the list. 139 */ 140 list2->lastPtr->nextPtr = NilListNode; 141 for (last = list1->lastPtr, ln = list2->firstPtr; 142 ln != NilListNode; 143 ln = ln->nextPtr) 144 { 145 PAlloc (nln, ListNode); 146 nln->datum = ln->datum; 147 if (last != NilListNode) { 148 last->nextPtr = nln; 149 } else { 150 list1->firstPtr = nln; 151 } 152 nln->prevPtr = last; 153 nln->flags = nln->useCount = 0; 154 last = nln; 155 } 156 157 /* 158 * Finish bookkeeping. The last new element becomes the last element 159 * of list one. 160 */ 161 list1->lastPtr = last; 162 163 /* 164 * The circularity of both list one and list two must be corrected 165 * for -- list one because of the new nodes added to it; list two 166 * because of the alteration of list2->lastPtr's nextPtr to ease the 167 * above for loop. 168 */ 169 if (list1->isCirc) { 170 list1->lastPtr->nextPtr = list1->firstPtr; 171 list1->firstPtr->prevPtr = list1->lastPtr; 172 } else { 173 last->nextPtr = NilListNode; 174 } 175 176 if (list2->isCirc) { 177 list2->lastPtr->nextPtr = list2->firstPtr; 178 } 179 } 180 181 return (SUCCESS); 182 } 183 184