diff options
Diffstat (limited to 'lst.lib/lstConcat.c')
| -rw-r--r-- | lst.lib/lstConcat.c | 185 |
1 files changed, 185 insertions, 0 deletions
diff --git a/lst.lib/lstConcat.c b/lst.lib/lstConcat.c new file mode 100644 index 0000000..534d34e --- /dev/null +++ b/lst.lib/lstConcat.c @@ -0,0 +1,185 @@ +/* $NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $ */ + +/* + * Copyright (c) 1988, 1989, 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Adam de Boor. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef MAKE_NATIVE +static char rcsid[] = "$NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $"; +#else +#include <sys/cdefs.h> +#ifndef lint +#if 0 +static char sccsid[] = "@(#)lstConcat.c 8.1 (Berkeley) 6/6/93"; +#else +__RCSID("$NetBSD: lstConcat.c,v 1.16 2008/12/13 15:19:29 dsl Exp $"); +#endif +#endif /* not lint */ +#endif + +/*- + * listConcat.c -- + * Function to concatentate two lists. + */ + +#include "lstInt.h" + +/*- + *----------------------------------------------------------------------- + * Lst_Concat -- + * Concatenate two lists. New elements are created to hold the data + * elements, if specified, but the elements themselves are not copied. + * If the elements should be duplicated to avoid confusion with another + * list, the Lst_Duplicate function should be called first. + * If LST_CONCLINK is specified, the second list is destroyed since + * its pointers have been corrupted and the list is no longer useable. + * + * Input: + * l1 The list to which l2 is to be appended + * l2 The list to append to l1 + * flags LST_CONCNEW if LstNode's should be duplicated + * LST_CONCLINK if should just be relinked + * + * Results: + * SUCCESS if all went well. FAILURE otherwise. + * + * Side Effects: + * New elements are created and appended the first list. + *----------------------------------------------------------------------- + */ +ReturnStatus +Lst_Concat(Lst l1, Lst l2, int flags) +{ + ListNode ln; /* original LstNode */ + ListNode nln; /* new LstNode */ + ListNode last; /* the last element in the list. Keeps + * bookkeeping until the end */ + List list1 = l1; + List list2 = l2; + + if (!LstValid (l1) || !LstValid (l2)) { + return (FAILURE); + } + + if (flags == LST_CONCLINK) { + if (list2->firstPtr != NULL) { + /* + * We set the nextPtr of the + * last element of list two to be NIL to make the loop easier and + * so we don't need an extra case should the first list turn + * out to be non-circular -- the final element will already point + * to NIL space and the first element will be untouched if it + * existed before and will also point to NIL space if it didn't. + */ + list2->lastPtr->nextPtr = NULL; + /* + * So long as the second list isn't empty, we just link the + * first element of the second list to the last element of the + * first list. If the first list isn't empty, we then link the + * last element of the list to the first element of the second list + * The last element of the second list, if it exists, then becomes + * the last element of the first list. + */ + list2->firstPtr->prevPtr = list1->lastPtr; + if (list1->lastPtr != NULL) { + list1->lastPtr->nextPtr = list2->firstPtr; + } else { + list1->firstPtr = list2->firstPtr; + } + list1->lastPtr = list2->lastPtr; + } + if (list1->isCirc && list1->firstPtr != NULL) { + /* + * If the first list is supposed to be circular and it is (now) + * non-empty, we must make sure it's circular by linking the + * first element to the last and vice versa + */ + list1->firstPtr->prevPtr = list1->lastPtr; + list1->lastPtr->nextPtr = list1->firstPtr; + } + free(l2); + } else if (list2->firstPtr != NULL) { + /* + * We set the nextPtr of the last element of list 2 to be nil to make + * the loop less difficult. The loop simply goes through the entire + * second list creating new LstNodes and filling in the nextPtr, and + * prevPtr to fit into l1 and its datum field from the + * datum field of the corresponding element in l2. The 'last' node + * follows the last of the new nodes along until the entire l2 has + * been appended. Only then does the bookkeeping catch up with the + * changes. During the first iteration of the loop, if 'last' is nil, + * the first list must have been empty so the newly-created node is + * made the first node of the list. + */ + list2->lastPtr->nextPtr = NULL; + for (last = list1->lastPtr, ln = list2->firstPtr; + ln != NULL; + ln = ln->nextPtr) + { + PAlloc (nln, ListNode); + nln->datum = ln->datum; + if (last != NULL) { + last->nextPtr = nln; + } else { + list1->firstPtr = nln; + } + nln->prevPtr = last; + nln->flags = nln->useCount = 0; + last = nln; + } + + /* + * Finish bookkeeping. The last new element becomes the last element + * of list one. + */ + list1->lastPtr = last; + + /* + * The circularity of both list one and list two must be corrected + * for -- list one because of the new nodes added to it; list two + * because of the alteration of list2->lastPtr's nextPtr to ease the + * above for loop. + */ + if (list1->isCirc) { + list1->lastPtr->nextPtr = list1->firstPtr; + list1->firstPtr->prevPtr = list1->lastPtr; + } else { + last->nextPtr = NULL; + } + + if (list2->isCirc) { + list2->lastPtr->nextPtr = list2->firstPtr; + } + } + + return (SUCCESS); +} + |