1236769Sobrien/* $NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $ */ 2236769Sobrien 3236769Sobrien/* 4236769Sobrien * Copyright (c) 1988, 1989, 1990, 1993 5236769Sobrien * The Regents of the University of California. All rights reserved. 6236769Sobrien * 7236769Sobrien * This code is derived from software contributed to Berkeley by 8236769Sobrien * Adam de Boor. 9236769Sobrien * 10236769Sobrien * Redistribution and use in source and binary forms, with or without 11236769Sobrien * modification, are permitted provided that the following conditions 12236769Sobrien * are met: 13236769Sobrien * 1. Redistributions of source code must retain the above copyright 14236769Sobrien * notice, this list of conditions and the following disclaimer. 15236769Sobrien * 2. Redistributions in binary form must reproduce the above copyright 16236769Sobrien * notice, this list of conditions and the following disclaimer in the 17236769Sobrien * documentation and/or other materials provided with the distribution. 18236769Sobrien * 3. Neither the name of the University nor the names of its contributors 19236769Sobrien * may be used to endorse or promote products derived from this software 20236769Sobrien * without specific prior written permission. 21236769Sobrien * 22236769Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23236769Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24236769Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25236769Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26236769Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27236769Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28236769Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29236769Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30236769Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31236769Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32236769Sobrien * SUCH DAMAGE. 33236769Sobrien */ 34236769Sobrien 35236769Sobrien#ifndef MAKE_NATIVE 36236769Sobrienstatic char rcsid[] = "$NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $"; 37236769Sobrien#else 38236769Sobrien#include <sys/cdefs.h> 39236769Sobrien#ifndef lint 40236769Sobrien#if 0 41236769Sobrienstatic char sccsid[] = "@(#)lstConcat.c 8.1 (Berkeley) 6/6/93"; 42236769Sobrien#else 43236769Sobrien__RCSID("$NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $"); 44236769Sobrien#endif 45236769Sobrien#endif /* not lint */ 46236769Sobrien#endif 47236769Sobrien 48236769Sobrien/*- 49236769Sobrien * listConcat.c -- 50236769Sobrien * Function to concatentate two lists. 51236769Sobrien */ 52236769Sobrien 53236769Sobrien#include "lstInt.h" 54236769Sobrien 55236769Sobrien/*- 56236769Sobrien *----------------------------------------------------------------------- 57236769Sobrien * Lst_Concat -- 58236769Sobrien * Concatenate two lists. New elements are created to hold the data 59236769Sobrien * elements, if specified, but the elements themselves are not copied. 60236769Sobrien * If the elements should be duplicated to avoid confusion with another 61236769Sobrien * list, the Lst_Duplicate function should be called first. 62236769Sobrien * If LST_CONCLINK is specified, the second list is destroyed since 63236769Sobrien * its pointers have been corrupted and the list is no longer useable. 64236769Sobrien * 65236769Sobrien * Input: 66236769Sobrien * l1 The list to which l2 is to be appended 67236769Sobrien * l2 The list to append to l1 68236769Sobrien * flags LST_CONCNEW if LstNode's should be duplicated 69236769Sobrien * LST_CONCLINK if should just be relinked 70236769Sobrien * 71236769Sobrien * Results: 72236769Sobrien * SUCCESS if all went well. FAILURE otherwise. 73236769Sobrien * 74236769Sobrien * Side Effects: 75236769Sobrien * New elements are created and appended the first list. 76236769Sobrien *----------------------------------------------------------------------- 77236769Sobrien */ 78236769SobrienReturnStatus 79236769SobrienLst_Concat(Lst l1, Lst l2, int flags) 80236769Sobrien{ 81236769Sobrien ListNode ln; /* original LstNode */ 82236769Sobrien ListNode nln; /* new LstNode */ 83236769Sobrien ListNode last; /* the last element in the list. Keeps 84236769Sobrien * bookkeeping until the end */ 85236769Sobrien List list1 = l1; 86236769Sobrien List list2 = l2; 87236769Sobrien 88236769Sobrien if (!LstValid (l1) || !LstValid (l2)) { 89236769Sobrien return (FAILURE); 90236769Sobrien } 91236769Sobrien 92236769Sobrien if (flags == LST_CONCLINK) { 93236769Sobrien if (list2->firstPtr != NULL) { 94236769Sobrien /* 95236769Sobrien * We set the nextPtr of the 96236769Sobrien * last element of list two to be NIL to make the loop easier and 97236769Sobrien * so we don't need an extra case should the first list turn 98236769Sobrien * out to be non-circular -- the final element will already point 99236769Sobrien * to NIL space and the first element will be untouched if it 100236769Sobrien * existed before and will also point to NIL space if it didn't. 101236769Sobrien */ 102236769Sobrien list2->lastPtr->nextPtr = NULL; 103236769Sobrien /* 104236769Sobrien * So long as the second list isn't empty, we just link the 105236769Sobrien * first element of the second list to the last element of the 106236769Sobrien * first list. If the first list isn't empty, we then link the 107236769Sobrien * last element of the list to the first element of the second list 108236769Sobrien * The last element of the second list, if it exists, then becomes 109236769Sobrien * the last element of the first list. 110236769Sobrien */ 111236769Sobrien list2->firstPtr->prevPtr = list1->lastPtr; 112236769Sobrien if (list1->lastPtr != NULL) { 113236769Sobrien list1->lastPtr->nextPtr = list2->firstPtr; 114236769Sobrien } else { 115236769Sobrien list1->firstPtr = list2->firstPtr; 116236769Sobrien } 117236769Sobrien list1->lastPtr = list2->lastPtr; 118236769Sobrien } 119236769Sobrien if (list1->isCirc && list1->firstPtr != NULL) { 120236769Sobrien /* 121236769Sobrien * If the first list is supposed to be circular and it is (now) 122236769Sobrien * non-empty, we must make sure it's circular by linking the 123236769Sobrien * first element to the last and vice versa 124236769Sobrien */ 125236769Sobrien list1->firstPtr->prevPtr = list1->lastPtr; 126236769Sobrien list1->lastPtr->nextPtr = list1->firstPtr; 127236769Sobrien } 128236769Sobrien free(l2); 129236769Sobrien } else if (list2->firstPtr != NULL) { 130236769Sobrien /* 131236769Sobrien * We set the nextPtr of the last element of list 2 to be nil to make 132236769Sobrien * the loop less difficult. The loop simply goes through the entire 133236769Sobrien * second list creating new LstNodes and filling in the nextPtr, and 134236769Sobrien * prevPtr to fit into l1 and its datum field from the 135236769Sobrien * datum field of the corresponding element in l2. The 'last' node 136236769Sobrien * follows the last of the new nodes along until the entire l2 has 137236769Sobrien * been appended. Only then does the bookkeeping catch up with the 138236769Sobrien * changes. During the first iteration of the loop, if 'last' is nil, 139236769Sobrien * the first list must have been empty so the newly-created node is 140236769Sobrien * made the first node of the list. 141236769Sobrien */ 142236769Sobrien list2->lastPtr->nextPtr = NULL; 143236769Sobrien for (last = list1->lastPtr, ln = list2->firstPtr; 144236769Sobrien ln != NULL; 145236769Sobrien ln = ln->nextPtr) 146236769Sobrien { 147236769Sobrien PAlloc (nln, ListNode); 148236769Sobrien nln->datum = ln->datum; 149236769Sobrien if (last != NULL) { 150236769Sobrien last->nextPtr = nln; 151236769Sobrien } else { 152236769Sobrien list1->firstPtr = nln; 153236769Sobrien } 154236769Sobrien nln->prevPtr = last; 155236769Sobrien nln->flags = nln->useCount = 0; 156236769Sobrien last = nln; 157236769Sobrien } 158236769Sobrien 159236769Sobrien /* 160236769Sobrien * Finish bookkeeping. The last new element becomes the last element 161236769Sobrien * of list one. 162236769Sobrien */ 163236769Sobrien list1->lastPtr = last; 164236769Sobrien 165236769Sobrien /* 166236769Sobrien * The circularity of both list one and list two must be corrected 167236769Sobrien * for -- list one because of the new nodes added to it; list two 168236769Sobrien * because of the alteration of list2->lastPtr's nextPtr to ease the 169236769Sobrien * above for loop. 170236769Sobrien */ 171236769Sobrien if (list1->isCirc) { 172236769Sobrien list1->lastPtr->nextPtr = list1->firstPtr; 173236769Sobrien list1->firstPtr->prevPtr = list1->lastPtr; 174236769Sobrien } else { 175236769Sobrien last->nextPtr = NULL; 176236769Sobrien } 177236769Sobrien 178236769Sobrien if (list2->isCirc) { 179236769Sobrien list2->lastPtr->nextPtr = list2->firstPtr; 180236769Sobrien } 181236769Sobrien } 182236769Sobrien 183236769Sobrien return (SUCCESS); 184236769Sobrien} 185236769Sobrien 186