1*31a9abe6Sbostic /* 2*31a9abe6Sbostic * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 3*31a9abe6Sbostic * All rights reserved. 4*31a9abe6Sbostic * 5*31a9abe6Sbostic * This code is derived from software contributed to Berkeley by 6*31a9abe6Sbostic * Adam de Boor. 7*31a9abe6Sbostic * 8*31a9abe6Sbostic * Redistribution and use in source and binary forms are permitted 9*31a9abe6Sbostic * provided that the above copyright notice and this paragraph are 10*31a9abe6Sbostic * duplicated in all such forms and that any documentation, 11*31a9abe6Sbostic * advertising materials, and other materials related to such 12*31a9abe6Sbostic * distribution and use acknowledge that the software was developed 13*31a9abe6Sbostic * by the University of California, Berkeley. The name of the 14*31a9abe6Sbostic * University may not be used to endorse or promote products derived 15*31a9abe6Sbostic * from this software without specific prior written permission. 16*31a9abe6Sbostic * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 17*31a9abe6Sbostic * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 18*31a9abe6Sbostic * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 19*31a9abe6Sbostic */ 20*31a9abe6Sbostic 21*31a9abe6Sbostic #ifndef lint 22*31a9abe6Sbostic static char sccsid[] = "@(#)lstConcat.c 5.2 (Berkeley) 03/11/90"; 23*31a9abe6Sbostic #endif /* not lint */ 24*31a9abe6Sbostic 2586d9cf80Sbostic /*- 2686d9cf80Sbostic * listConcat.c -- 2786d9cf80Sbostic * Function to concatentate two lists. 2886d9cf80Sbostic */ 2986d9cf80Sbostic 3086d9cf80Sbostic #include "lstInt.h" 3186d9cf80Sbostic 3286d9cf80Sbostic /*- 3386d9cf80Sbostic *----------------------------------------------------------------------- 3486d9cf80Sbostic * Lst_Concat -- 3586d9cf80Sbostic * Concatenate two lists. New elements are created to hold the data 3686d9cf80Sbostic * elements, if specified, but the elements themselves are not copied. 3786d9cf80Sbostic * If the elements should be duplicated to avoid confusion with another 3886d9cf80Sbostic * list, the Lst_Duplicate function should be called first. 3986d9cf80Sbostic * If LST_CONCLINK is specified, the second list is destroyed since 4086d9cf80Sbostic * its pointers have been corrupted and the list is no longer useable. 4186d9cf80Sbostic * 4286d9cf80Sbostic * Results: 4386d9cf80Sbostic * SUCCESS if all went well. FAILURE otherwise. 4486d9cf80Sbostic * 4586d9cf80Sbostic * Side Effects: 4686d9cf80Sbostic * New elements are created and appended the the first list. 4786d9cf80Sbostic *----------------------------------------------------------------------- 4886d9cf80Sbostic */ 4986d9cf80Sbostic ReturnStatus 5086d9cf80Sbostic Lst_Concat (l1, l2, flags) 5186d9cf80Sbostic Lst l1; /* The list to which l2 is to be appended */ 5286d9cf80Sbostic Lst l2; /* The list to append to l1 */ 5386d9cf80Sbostic int flags; /* LST_CONCNEW if LstNode's should be duplicated 5486d9cf80Sbostic * LST_CONCLINK if should just be relinked */ 5586d9cf80Sbostic { 5686d9cf80Sbostic register ListNode ln; /* original LstNode */ 5786d9cf80Sbostic register ListNode nln; /* new LstNode */ 5886d9cf80Sbostic register ListNode last; /* the last element in the list. Keeps 5986d9cf80Sbostic * bookkeeping until the end */ 6086d9cf80Sbostic register List list1 = (List)l1; 6186d9cf80Sbostic register List list2 = (List)l2; 6286d9cf80Sbostic 6386d9cf80Sbostic if (!LstValid (l1) || !LstValid (l2)) { 6486d9cf80Sbostic return (FAILURE); 6586d9cf80Sbostic } 6686d9cf80Sbostic 6786d9cf80Sbostic if (flags == LST_CONCLINK) { 6886d9cf80Sbostic if (list2->firstPtr != NilListNode) { 6986d9cf80Sbostic /* 7086d9cf80Sbostic * We set the nextPtr of the 7186d9cf80Sbostic * last element of list two to be NIL to make the loop easier and 7286d9cf80Sbostic * so we don't need an extra case should the first list turn 7386d9cf80Sbostic * out to be non-circular -- the final element will already point 7486d9cf80Sbostic * to NIL space and the first element will be untouched if it 7586d9cf80Sbostic * existed before and will also point to NIL space if it didn't. 7686d9cf80Sbostic */ 7786d9cf80Sbostic list2->lastPtr->nextPtr = NilListNode; 7886d9cf80Sbostic /* 7986d9cf80Sbostic * So long as the second list isn't empty, we just link the 8086d9cf80Sbostic * first element of the second list to the last element of the 8186d9cf80Sbostic * first list. If the first list isn't empty, we then link the 8286d9cf80Sbostic * last element of the list to the first element of the second list 8386d9cf80Sbostic * The last element of the second list, if it exists, then becomes 8486d9cf80Sbostic * the last element of the first list. 8586d9cf80Sbostic */ 8686d9cf80Sbostic list2->firstPtr->prevPtr = list1->lastPtr; 8786d9cf80Sbostic if (list1->lastPtr != NilListNode) { 8886d9cf80Sbostic list1->lastPtr->nextPtr = list2->firstPtr; 8986d9cf80Sbostic } 9086d9cf80Sbostic list1->lastPtr = list2->lastPtr; 9186d9cf80Sbostic } 9286d9cf80Sbostic if (list1->isCirc && list1->firstPtr != NilListNode) { 9386d9cf80Sbostic /* 9486d9cf80Sbostic * If the first list is supposed to be circular and it is (now) 9586d9cf80Sbostic * non-empty, we must make sure it's circular by linking the 9686d9cf80Sbostic * first element to the last and vice versa 9786d9cf80Sbostic */ 9886d9cf80Sbostic list1->firstPtr->prevPtr = list1->lastPtr; 9986d9cf80Sbostic list1->lastPtr->nextPtr = list1->firstPtr; 10086d9cf80Sbostic } 10186d9cf80Sbostic free ((Address)l2); 10286d9cf80Sbostic } else if (list2->firstPtr != NilListNode) { 10386d9cf80Sbostic /* 10486d9cf80Sbostic * We set the nextPtr of the last element of list 2 to be nil to make 10586d9cf80Sbostic * the loop less difficult. The loop simply goes through the entire 10686d9cf80Sbostic * second list creating new LstNodes and filling in the nextPtr, and 10786d9cf80Sbostic * prevPtr to fit into l1 and its datum field from the 10886d9cf80Sbostic * datum field of the corresponding element in l2. The 'last' node 10986d9cf80Sbostic * follows the last of the new nodes along until the entire l2 has 11086d9cf80Sbostic * been appended. Only then does the bookkeeping catch up with the 11186d9cf80Sbostic * changes. During the first iteration of the loop, if 'last' is nil, 11286d9cf80Sbostic * the first list must have been empty so the newly-created node is 11386d9cf80Sbostic * made the first node of the list. 11486d9cf80Sbostic */ 11586d9cf80Sbostic list2->lastPtr->nextPtr = NilListNode; 11686d9cf80Sbostic for (last = list1->lastPtr, ln = list2->firstPtr; 11786d9cf80Sbostic ln != NilListNode; 11886d9cf80Sbostic ln = ln->nextPtr) 11986d9cf80Sbostic { 12086d9cf80Sbostic PAlloc (nln, ListNode); 12186d9cf80Sbostic nln->datum = ln->datum; 12286d9cf80Sbostic if (last != NilListNode) { 12386d9cf80Sbostic last->nextPtr = nln; 12486d9cf80Sbostic } else { 12586d9cf80Sbostic list1->firstPtr = nln; 12686d9cf80Sbostic } 12786d9cf80Sbostic nln->prevPtr = last; 12886d9cf80Sbostic nln->flags = nln->useCount = 0; 12986d9cf80Sbostic last = nln; 13086d9cf80Sbostic } 13186d9cf80Sbostic 13286d9cf80Sbostic /* 13386d9cf80Sbostic * Finish bookkeeping. The last new element becomes the last element 13486d9cf80Sbostic * of list one. 13586d9cf80Sbostic */ 13686d9cf80Sbostic list1->lastPtr = last; 13786d9cf80Sbostic 13886d9cf80Sbostic /* 13986d9cf80Sbostic * The circularity of both list one and list two must be corrected 14086d9cf80Sbostic * for -- list one because of the new nodes added to it; list two 14186d9cf80Sbostic * because of the alteration of list2->lastPtr's nextPtr to ease the 14286d9cf80Sbostic * above for loop. 14386d9cf80Sbostic */ 14486d9cf80Sbostic if (list1->isCirc) { 14586d9cf80Sbostic list1->lastPtr->nextPtr = list1->firstPtr; 14686d9cf80Sbostic list1->firstPtr->prevPtr = list1->lastPtr; 14786d9cf80Sbostic } else { 14886d9cf80Sbostic last->nextPtr = NilListNode; 14986d9cf80Sbostic } 15086d9cf80Sbostic 15186d9cf80Sbostic if (list2->isCirc) { 15286d9cf80Sbostic list2->lastPtr->nextPtr = list2->firstPtr; 15386d9cf80Sbostic } 15486d9cf80Sbostic } 15586d9cf80Sbostic 15686d9cf80Sbostic return (SUCCESS); 15786d9cf80Sbostic } 15886d9cf80Sbostic 159