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