/*-
 * 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.
 *
 * $FreeBSD$
 */

/*-
 * lst.c --
 *	Routines to maintain a linked list of objects.
 */

#include <stdio.h>
#include <stdlib.h>

#include "lst.h"
#include "util.h"

/**
 * Lst_Append
 *	Create a new node and add it to the given list after the given node.
 *
 * Arguments:
 *	l	affected list
 *	ln	node after which to append the datum
 *	d	said datum
 *
 * Side Effects:
 *	A new LstNode is created and linked in to the List. The lastPtr
 *	field of the List will be altered if ln is the last node in the
 *	list. lastPtr and firstPtr will alter if the list was empty and
 *	ln was NULL.
 */
void
Lst_Append(Lst *list, LstNode *ln, void *d)
{
	LstNode *nLNode;

	nLNode = emalloc(sizeof(*nLNode));
	nLNode->datum = d;

	if (ln == NULL) {
		nLNode->nextPtr = nLNode->prevPtr = NULL;
		list->firstPtr = list->lastPtr = nLNode;
	} else {
		nLNode->prevPtr = ln;
		nLNode->nextPtr = ln->nextPtr;

		ln->nextPtr = nLNode;
		if (nLNode->nextPtr != NULL) {
			nLNode->nextPtr->prevPtr = nLNode;
		}

		if (ln == list->lastPtr) {
			list->lastPtr = nLNode;
		}
	}
}

/**
 * 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.
 *
 * Arguments:
 *	list1	The list to which list2 is to be appended
 *	list2	The list to append to list1
 *	flags	LST_CONCNEW if LstNode's should be duplicated
 *		LST_CONCLINK if should just be relinked
 *
 * Side Effects:
 *	New elements are created and appended the first list.
 */
void
Lst_Concat(Lst *list1, Lst *list2, int flags)
{
	LstNode	*ln;	/* original LstNode */
	LstNode	*nln;	/* new LstNode */
	LstNode	*last;	/* the last element in the list. Keeps
			 * bookkeeping until the end */

	if (list2->firstPtr == NULL)
		return;

	if (flags == LST_CONCLINK) {
		/*
		 * 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;

		Lst_Init(list2);
	} else {
		/*
		 * The loop simply goes through the entire second list creating
		 * new LstNodes and filling in the nextPtr, and prevPtr to fit
		 * into list1 and its datum field from the datum field of the
		 * corresponding element in list2. The 'last' node follows the
		 * last of the new nodes along until the entire list2 has been
		 * appended. Only then does the bookkeeping catch up with the
		 * changes. During the first iteration of the loop, if 'last'
		 * is NULL, the first list must have been empty so the
		 * newly-created node is made the first node of the list.
		 */
		for (last = list1->lastPtr, ln = list2->firstPtr;
		    ln != NULL;
		    ln = ln->nextPtr) {
			nln = emalloc(sizeof(*nln));
			nln->datum = ln->datum;
			if (last != NULL) {
				last->nextPtr = nln;
			} else {
				list1->firstPtr = nln;
			}
			nln->prevPtr = last;
			last = nln;
		}

		/*
		 * Finish bookkeeping. The last new element becomes the last
		 * element of list one.
		 */
		list1->lastPtr = last;
		last->nextPtr = NULL;
	}
}

/**
 * Lst_DeQueue
 *	Remove and return the datum at the head of the given list.
 *
 * Results:
 *	The datum in the node at the head or (ick) NULL if the list
 *	is empty.
 *
 * Side Effects:
 *	The head node is removed from the list.
 */
void *
Lst_DeQueue(Lst *l)
{
	void *rd;
	LstNode *tln;

	tln = Lst_First(l);
	if (tln == NULL) {
		return (NULL);
	}

	rd = tln->datum;
	Lst_Remove(l, tln);
	return (rd);
}

/**
 * Lst_Destroy
 *	Destroy a list and free all its resources. If the freeProc is
 *	given, it is called with the datum from each node in turn before
 *	the node is freed.
 *
 * Side Effects:
 *	The given list is freed in its entirety.
 */
void
Lst_Destroy(Lst *list, FreeProc *freeProc)
{
	LstNode *ln;

	if (list->firstPtr == NULL)
		return;

	if (freeProc != NOFREE) {
		while ((ln = list->firstPtr) != NULL) {
			list->firstPtr = ln->nextPtr;
			(*freeProc)(ln->datum);
			free(ln);
		}
	} else {
		while ((ln = list->firstPtr) != NULL) {
			list->firstPtr = ln->nextPtr;
			free(ln);
		}
	}
	list->lastPtr = NULL;
}

/**
 * Lst_Duplicate
 *	Duplicate an entire list. If a function to copy a void * is
 *	given, the individual client elements will be duplicated as well.
 *
 * Arguments:
 *	dst	the destination list (initialized)
 *	src	the list to duplicate
 *	copyProc A function to duplicate each void
 */
void
Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc)
{
	LstNode *ln;

	ln = src->firstPtr;
	while (ln != NULL) {
		if (copyProc != NOCOPY)
			Lst_AtEnd(dst, (*copyProc)(ln->datum));
		else
			Lst_AtEnd(dst, ln->datum);
		ln = ln->nextPtr;
	}
}

/**
 * Lst_Insert
 *	Insert a new node with the given piece of data before the given
 *	node in the given list.
 *
 * Parameters:
 *	l	list to manipulate
 *	ln	node before which to insert d
 *	d	datum to be inserted
 *
 * Side Effects:
 *	the firstPtr field will be changed if ln is the first node in the
 *	list.
 */
void
Lst_Insert(Lst *list, LstNode *ln, void *d)
{
	LstNode *nLNode;	/* new lnode for d */

	nLNode = emalloc(sizeof(*nLNode));
	nLNode->datum = d;

	if (ln == NULL) {
		nLNode->prevPtr = nLNode->nextPtr = NULL;
		list->firstPtr = list->lastPtr = nLNode;
	} else {
		nLNode->prevPtr = ln->prevPtr;
		nLNode->nextPtr = ln;

		if (nLNode->prevPtr != NULL) {
			nLNode->prevPtr->nextPtr = nLNode;
		}
		ln->prevPtr = nLNode;

		if (ln == list->firstPtr) {
			list->firstPtr = nLNode;
		}
	}
}

LstNode *
Lst_Member(Lst *list, void *d)
{
	LstNode *lNode;

	lNode = list->firstPtr;
	if (lNode == NULL) {
		return (NULL);
	}

	do {
		if (lNode->datum == d) {
			return (lNode);
		}
		lNode = lNode->nextPtr;
	} while (lNode != NULL && lNode != list->firstPtr);

	return (NULL);
}

/**
 * Lst_Remove
 *	Remove the given node from the given list.
 *
 * Side Effects:
 *	The list's firstPtr will be set to NULL if ln is the last
 *	node on the list. firsPtr and lastPtr will be altered if ln is
 *	either the first or last node, respectively, on the list.
 */
void
Lst_Remove(Lst *list, LstNode *ln)
{
	/*
	 * unlink it from the list
	 */
	if (ln->nextPtr != NULL)
		/* unlink from the backward chain */
		ln->nextPtr->prevPtr = ln->prevPtr;
	else
		/* this was the last element */
		list->lastPtr = ln->prevPtr;

	if (ln->prevPtr != NULL)
		/* unlink from the forward chain */
		ln->prevPtr->nextPtr = ln->nextPtr;
	else
		/* this was the first element */
		list->firstPtr = ln->nextPtr;

	/*
	 * note that the datum is unmolested. The caller must free it as
	 * necessary and as expected.
	 */
	free(ln);
}