OpenSolaris_b135/lib/udapl/udapl_tavor/common/dapl_llist.c
/*
* 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;
}
}