1 /* 2 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Adam de Boor. 7 * 8 * Redistribution and use in source and binary forms are permitted 9 * provided that the above copyright notice and this paragraph are 10 * duplicated in all such forms and that any documentation, 11 * advertising materials, and other materials related to such 12 * distribution and use acknowledge that the software was developed 13 * by the University of California, Berkeley. The name of the 14 * University may not be used to endorse or promote products derived 15 * from this software without specific prior written permission. 16 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 19 */ 20 21 #ifndef lint 22 static char sccsid[] = "@(#)lstConcat.c 5.2 (Berkeley) 03/11/90"; 23 #endif /* not lint */ 24 25 /*- 26 * listConcat.c -- 27 * Function to concatentate two lists. 28 */ 29 30 #include "lstInt.h" 31 32 /*- 33 *----------------------------------------------------------------------- 34 * Lst_Concat -- 35 * Concatenate two lists. New elements are created to hold the data 36 * elements, if specified, but the elements themselves are not copied. 37 * If the elements should be duplicated to avoid confusion with another 38 * list, the Lst_Duplicate function should be called first. 39 * If LST_CONCLINK is specified, the second list is destroyed since 40 * its pointers have been corrupted and the list is no longer useable. 41 * 42 * Results: 43 * SUCCESS if all went well. FAILURE otherwise. 44 * 45 * Side Effects: 46 * New elements are created and appended the the first list. 47 *----------------------------------------------------------------------- 48 */ 49 ReturnStatus 50 Lst_Concat (l1, l2, flags) 51 Lst l1; /* The list to which l2 is to be appended */ 52 Lst l2; /* The list to append to l1 */ 53 int flags; /* LST_CONCNEW if LstNode's should be duplicated 54 * LST_CONCLINK if should just be relinked */ 55 { 56 register ListNode ln; /* original LstNode */ 57 register ListNode nln; /* new LstNode */ 58 register ListNode last; /* the last element in the list. Keeps 59 * bookkeeping until the end */ 60 register List list1 = (List)l1; 61 register List list2 = (List)l2; 62 63 if (!LstValid (l1) || !LstValid (l2)) { 64 return (FAILURE); 65 } 66 67 if (flags == LST_CONCLINK) { 68 if (list2->firstPtr != NilListNode) { 69 /* 70 * We set the nextPtr of the 71 * last element of list two to be NIL to make the loop easier and 72 * so we don't need an extra case should the first list turn 73 * out to be non-circular -- the final element will already point 74 * to NIL space and the first element will be untouched if it 75 * existed before and will also point to NIL space if it didn't. 76 */ 77 list2->lastPtr->nextPtr = NilListNode; 78 /* 79 * So long as the second list isn't empty, we just link the 80 * first element of the second list to the last element of the 81 * first list. If the first list isn't empty, we then link the 82 * last element of the list to the first element of the second list 83 * The last element of the second list, if it exists, then becomes 84 * the last element of the first list. 85 */ 86 list2->firstPtr->prevPtr = list1->lastPtr; 87 if (list1->lastPtr != NilListNode) { 88 list1->lastPtr->nextPtr = list2->firstPtr; 89 } 90 list1->lastPtr = list2->lastPtr; 91 } 92 if (list1->isCirc && list1->firstPtr != NilListNode) { 93 /* 94 * If the first list is supposed to be circular and it is (now) 95 * non-empty, we must make sure it's circular by linking the 96 * first element to the last and vice versa 97 */ 98 list1->firstPtr->prevPtr = list1->lastPtr; 99 list1->lastPtr->nextPtr = list1->firstPtr; 100 } 101 free ((Address)l2); 102 } else if (list2->firstPtr != NilListNode) { 103 /* 104 * We set the nextPtr of the last element of list 2 to be nil to make 105 * the loop less difficult. The loop simply goes through the entire 106 * second list creating new LstNodes and filling in the nextPtr, and 107 * prevPtr to fit into l1 and its datum field from the 108 * datum field of the corresponding element in l2. The 'last' node 109 * follows the last of the new nodes along until the entire l2 has 110 * been appended. Only then does the bookkeeping catch up with the 111 * changes. During the first iteration of the loop, if 'last' is nil, 112 * the first list must have been empty so the newly-created node is 113 * made the first node of the list. 114 */ 115 list2->lastPtr->nextPtr = NilListNode; 116 for (last = list1->lastPtr, ln = list2->firstPtr; 117 ln != NilListNode; 118 ln = ln->nextPtr) 119 { 120 PAlloc (nln, ListNode); 121 nln->datum = ln->datum; 122 if (last != NilListNode) { 123 last->nextPtr = nln; 124 } else { 125 list1->firstPtr = nln; 126 } 127 nln->prevPtr = last; 128 nln->flags = nln->useCount = 0; 129 last = nln; 130 } 131 132 /* 133 * Finish bookkeeping. The last new element becomes the last element 134 * of list one. 135 */ 136 list1->lastPtr = last; 137 138 /* 139 * The circularity of both list one and list two must be corrected 140 * for -- list one because of the new nodes added to it; list two 141 * because of the alteration of list2->lastPtr's nextPtr to ease the 142 * above for loop. 143 */ 144 if (list1->isCirc) { 145 list1->lastPtr->nextPtr = list1->firstPtr; 146 list1->firstPtr->prevPtr = list1->lastPtr; 147 } else { 148 last->nextPtr = NilListNode; 149 } 150 151 if (list2->isCirc) { 152 list2->lastPtr->nextPtr = list2->firstPtr; 153 } 154 } 155 156 return (SUCCESS); 157 } 158 159