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