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