/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
 */

/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 *
 * MODULE: dapl_llist.c
 *
 * PURPOSE: Manage doubly linked lists within the DAPL Reference Implementation
 *
 *	A link list head points to the first member of a linked list, but
 *	is itself not a member of the list.
 *
 *          +---------------------------------------------+
 *          |      entry         entry         entry      |
 *  HEAD -> |    +-------+     +-------+     +-------+    |
 *          +--> | flink | --> | flink | --> | flink | >--+
 *	         | data  |     | data  |     | data  |
 *	    +--< | blink | <-- | blink | <-- | blink | <--|
 *          |    +-------+     +-------+     +-------+    |
 *          |                                             |
 *          +---------------------------------------------+
 *
 * Note:  Each of the remove functions takes an assertion failure if
 *        an element cannot be removed from the list.
 *
 * $Id: dapl_llist.c,v 1.9 2003/06/13 12:21:11 sjs2 Exp $
 */

#include "dapl.h"

/*
 * dapl_llist_init_head()
 *
 * Purpose: initialize a linked list head
 */
void
dapl_llist_init_head(DAPL_LLIST_HEAD *head)
{
	*head = NULL;
}

/*
 * dapl_llist_init_entry()
 *
 * Purpose: initialize a linked list entry
 */
void
dapl_llist_init_entry(DAPL_LLIST_ENTRY *entry)
{
	entry->blink = NULL;
	entry->flink = NULL;
	entry->data = 0;
	entry->list_head = NULL;
}

/*
 * dapl_llist_is_empty()
 *
 * Purpose: returns TRUE if the linked list is empty
 */
DAT_BOOLEAN
dapl_llist_is_empty(DAPL_LLIST_HEAD *head)
{
	return (*head == NULL);
}

/*
 * dapl_llist_add_head()
 *
 * Purpose: Add an entry to the head of a linked list
 */
void
dapl_llist_add_head(DAPL_LLIST_HEAD *head,
		DAPL_LLIST_ENTRY *entry,
		void *data)
{
	DAPL_LLIST_ENTRY *first;

	/* deal with empty list */
	if (dapl_llist_is_empty(head)) {
		entry->flink = entry;
		entry->blink = entry;
	} else {
		first = *head;
		entry->flink = first;
		entry->blink = first->blink;
		first->blink->flink = entry;
		first->blink = entry;
	}

	*head		= entry;
	entry->data	= data;
	entry->list_head = head;
}

/*
 * dapl_llist_add_tail()
 *
 * Purpose: Add an entry to the tail of a linked list
 */
void
dapl_llist_add_tail(DAPL_LLIST_HEAD *head,
	DAPL_LLIST_ENTRY *entry,
	void *data)
{
	DAPL_LLIST_ENTRY *last;

	/* deal with empty list */
	if (dapl_llist_is_empty(head)) {
		*head = entry;
		entry->flink = entry;
		entry->blink = entry;
	} else {
		last = (*head)->blink;
		entry->flink = last->flink;
		entry->blink = last;
		last->flink->blink = entry;
		last->flink = entry;
	}
	entry->data = data;
	entry->list_head = head;
}


/*
 * dapl_llist_add_entry()
 *
 * Purpose: Add an entry before an element in the list
 */
void
dapl_llist_add_entry(DAPL_LLIST_HEAD * head,
		DAPL_LLIST_ENTRY * entry,
		DAPL_LLIST_ENTRY * new_entry,
		void * data)
{
	DAPL_LLIST_ENTRY *last;

	/* deal with empty list */
	if (dapl_llist_is_empty(head)) {
		*head = entry;
		entry->flink = entry;
		entry->blink = entry;
	} else {
		last = entry->blink;
		entry->blink = new_entry;
		last->flink  = new_entry;

		new_entry->flink = entry;
		new_entry->blink = last;

	}
	new_entry->data = data;
	new_entry->list_head = head;
}

/*
 * dapl_llist_remove_head()
 *
 * Purpose: Remove the first entry of a linked list
 */
void *
dapl_llist_remove_head(DAPL_LLIST_HEAD *head)
{
	DAPL_LLIST_ENTRY *first;

	dapl_os_assert(!dapl_llist_is_empty(head));
	first = *head;
	*head = first->flink;

	first->flink->blink = first->blink;
	first->blink->flink = first->flink;

	if (first->flink == first) {
		*head = NULL;
	}
	/* clean up the links for good measure */
	first->flink = NULL;
	first->blink = NULL;
	first->list_head = NULL;
	return (first->data);
}

/*
 * dapl_llist_remove_tail()
 *
 * Purpose: Remove the last entry of a linked list
 */
void *
dapl_llist_remove_tail(DAPL_LLIST_HEAD *head)
{
	DAPL_LLIST_ENTRY *last;

	dapl_os_assert(!dapl_llist_is_empty(head));
	last = (*head)->blink;

	last->blink->flink = last->flink;
	last->flink->blink = last->blink;

	if (last->flink == last) {
		*head = NULL;
	}
	/* clean up the links for good measure */
	last->flink = NULL;
	last->blink = NULL;
	last->list_head = NULL;

	return (last->data);
}

/*
 * dapl_llist_remove_entry()
 *
 * Purpose: Remove the specified entry from a linked list
 */
void *
dapl_llist_remove_entry(DAPL_LLIST_HEAD *head, DAPL_LLIST_ENTRY *entry)
{
	DAPL_LLIST_ENTRY *first;

	dapl_os_assert(!dapl_llist_is_empty(head));
	first = *head;

	/* if it's the first entry, pull it off */
	if (first == entry) {
		(*head) = first->flink;
		/* if it was the only entry, kill the list */
		if (first->flink == first) {
			(*head) = NULL;
		}
	}
#ifdef VERIFY_LINKED_LIST
	else {
		DAPL_LLIST_ENTRY *try_entry;

		try_entry = first->flink;
		for (;;) {
			if (try_entry == first) {
				/*
				 * not finding the element on the list
				 * is a BAD thing
				 */
				dapl_os_assert(0);
				break;
			}
			if (try_entry == entry) {
				break;
			}
			try_entry = try_entry->flink;
		}
	}
#endif /* VERIFY_LINKED_LIST */

	dapl_os_assert(entry->list_head == head);
	entry->list_head = NULL;

	entry->flink->blink = entry->blink;
	entry->blink->flink = entry->flink;
	entry->flink = NULL;
	entry->blink = NULL;

	return (entry->data);
}

/*
 * dapl_llist_peek_head
 */

void *
dapl_llist_peek_head(DAPL_LLIST_HEAD *head)
{
	DAPL_LLIST_ENTRY *first;

	dapl_os_assert(!dapl_llist_is_empty(head));
	first = *head;
	return (first->data);
}


/*
 * dapl_llist_next_entry
 *
 * Obtain the next entry in the list, return NULL when we get to the
 * head
 */

void *
dapl_llist_next_entry(IN    DAPL_LLIST_HEAD 	*head,
    IN    DAPL_LLIST_ENTRY 	*cur_ent)
{
	DAPL_LLIST_ENTRY *next;

	dapl_os_assert(!dapl_llist_is_empty(head));
	if (cur_ent == NULL) {
		next = *head;
	} else {
		next = cur_ent->flink;
		if (next == *head) {
			return (NULL);
		}
	}
	return (next->data);
}

/*
 * dapl_llist_debug_print_list()
 *
 * Purpose: Prints the linked list for debugging
 */
void
dapl_llist_debug_print_list(DAPL_LLIST_HEAD *head)
{
	DAPL_LLIST_ENTRY * entry;
	DAPL_LLIST_ENTRY * first;
	first = *head;
	if (!first) {
		dapl_dbg_log(DAPL_DBG_TYPE_RTN, "EMPTY_LIST\n");
		return;
	}
	dapl_dbg_log(DAPL_DBG_TYPE_RTN, "HEAD %p\n", *head);
	dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
	    first,
	    first->flink,
	    first->blink,
	    first->data);
	entry = first->flink;
	while (entry != first) {
		dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
		    entry,
		    entry->flink,
		    entry->blink,
		    entry->data);
		entry = entry->flink;
	}
}